Maximum einer diskreten Funktion

12.02.2020, 01:37

Dopap

Maximum einer diskreten Funktion

Auf einem Pfälzer Weinfest wird der Inhalt eines 200 Liter Fasses den Abend über verlost.
Los #1 erhält 1%, Los#2 erhält 2 % des Restes, Los #3 wiederum 3% der im Fass verbliebenen Menge usw.

Welcher Losbesitzer darf mit der größten Menge zuhause weitertrinken ?

Das lässt sich mit einem guten Taschenrechner leicht feststellen.

kann das analytisch zumindest näherungsweise angegangen werden?
Insbesondere wenn der Zuwachs der Anteile in noch kleineren Schritten erfolgt.

12.02.2020, 07:57

Ulrich Ruhnau

Auf diesen Beitrag antworten »

RE: Maximum einer diskreten Funktion
Losbesitzer 10 schneidet am besten ab mit 12,56 Litern Wein, die er nach hause mitnimmt. Ich vermute, das ähnelt hier einer Poisson-Verteilung, aber ich muß das erst mal in Ruhe nachrechnen.

Losbesitzer, Menge
1 2.000000
2 3.960000
3 5.821200
4 7.528752
5 9.034502
6 10.299333
7 11.294935
8 12.004902
9 12.425074
10 12.563130
11 12.437499
12 12.075681
13 11.512149
14 10.785998
15 9.938527
16 9.010931
17 8.042256
18 7.067724
19 6.117507
20 5.215980
[attach]50617[/attach]

12.02.2020, 08:56

Huggy

Auf diesen Beitrag antworten »

RE: Maximum einer diskreten Funktion

Zitat:

Original von Dopap
Welcher Losbesitzer darf mit der größten Menge zuhause weitertrinken ?

kann das analytisch zumindest näherungsweise angegangen werden?
Insbesondere wenn der Zuwachs der Anteile in noch kleineren Schritten erfolgt.

Hat dir das HAL nicht schon mal vorgerechnet? Ich war zu faul zum suchen.

Es gebe $\begin{eqnarray*} n \end{eqnarray*}$ Lose. Der Anteil, der auf das Los $\begin{eqnarray*} k \end{eqnarray*}$ entfällt, sei $\begin{eqnarray*} a_k \end{eqnarray*}$ . Bevor $\begin{eqnarray*} a_k \end{eqnarray*}$ zugeteilt wird, sei noch ein Rest $\begin{eqnarray*} r \end{eqnarray*}$ vorhanden. Dann ist

$\begin{eqnarray*} a_k=r \frac k n \end{eqnarray*}$

$\begin{eqnarray*} a_{k+1}=r(1-\frac k n)\frac {k+1} n \end{eqnarray*}$

$\begin{eqnarray*} \Delta = a_{k+1}-a_k=r \frac {n-k(k+1} {n^2} \end{eqnarray*}$

Die positive Nullstelle des Zählers ist

$\begin{eqnarray*} k_g= -\frac 12 + \sqrt {\frac 1 4 +n} \end{eqnarray*}$

$\begin{eqnarray*} \Delta \end{eqnarray*}$ wird erstmal negativ für $\begin{eqnarray*} k = \lfloor k_g \rfloor +1 \end{eqnarray*}$ . Auf diese Losnummer entfällt also der größte Anteil.

12.02.2020, 09:04

klauss

Auf diesen Beitrag antworten »

RE: Maximum einer diskreten Funktion
Nach meiner Rechnung läßt sich der Anteil des k-ten Loses an der Gesamtmenge angeben durch

$\begin{eqnarray*} A_{k} =\frac{k}{100^{k} } \cdot \frac{99!}{(100-k)!} \end{eqnarray*}$

Kann man davon auch analytisch ein Maximum berechnen?

12.02.2020, 10:14

Huggy

Auf diesen Beitrag antworten »

RE: Maximum einer diskreten Funktion
Meinst du durch Ableiten? Dann müsste man die Fakultät im Nenner durch die Gammafunktion ausdrücken. Die Nullstelle der Ableitung dürfte sich nur numerisch bestimmen lassen.

12.02.2020, 10:15

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Huggy
Hat dir das HAL nicht schon mal vorgerechnet?

Irgendwie hatte ich beim Durchlesen auch ein Déjà-vu. Aber Dopap beherrscht die Kunst, Fragen in anderem Gewand nach so langer Zeit wieder zu stellen, dass inzwischen alle vergessen haben, wo wie und wann das Original aufgetaucht war. Zumal das Suchen womöglich länger dauert als die erneute Problemlösung. Augenzwinkern

12.02.2020, 12:19

Nils Hoppenstedt

Auf diesen Beitrag antworten »

RE: Maximum einer diskreten Funktion

Zitat:

Original von klauss
Nach meiner Rechnung läßt sich der Anteil des k-ten Loses an der Gesamtmenge angeben durch

$\begin{eqnarray*} A_{k} =\frac{k}{100^{k} } \cdot \frac{99!}{(100-k)!} \end{eqnarray*}$

Kann man davon auch analytisch ein Maximum berechnen?

Ja, indem man nicht das Maximum von A_k betrachet, sondern das Maximum von ln(Ak). Mit der Stiring-Näherung erhält man dann für die Ableitung:

[ln(Ak)]' = 1/k + ln(1 - k/n)

was mit Näherung ln(1 - k/n) = -k/n schließlich auf die Position des Maximums bei

k_max = sqrt(n)

führt.

Nils

12.02.2020, 15:03

Nils Hoppenstedt

Auf diesen Beitrag antworten »

Die analytische Näherung lautet übrigens:

A_k = k/n * exp(-k²/(2n))

12.02.2020, 15:15

klauss

Auf diesen Beitrag antworten »

@ Nils Hoppenstedt:
Danke, das ist schon interessant.
Welcher Wert ist bei Dir für n einzusetzen?

12.02.2020, 15:16

Nils Hoppenstedt

Auf diesen Beitrag antworten »

100

12.02.2020, 15:29

klauss

Auf diesen Beitrag antworten »

@ Nils Hoppenstedt:
Scheint zu funktionieren, damit erhält man auch Maximum 10.
Ich hoffe, Dopap kann die Lösung gebrauchen.

12.02.2020, 16:27

HAL 9000

Auf diesen Beitrag antworten »

Ich weiß gar nicht, warum so viel über Näherungen gesprochen wird, wo doch die exakte Position des Maximums schon lange im Thread steht:

Zitat:

Original von Huggy
Die positive Nullstelle des Zählers ist

$\begin{eqnarray*} k_g= -\frac 12 + \sqrt {\frac 1 4 +n} \end{eqnarray*}$

$\begin{eqnarray*} \Delta \end{eqnarray*}$ wird erstmal negativ für $\begin{eqnarray*} k = \lfloor k_g \rfloor +1 \end{eqnarray*}$ . Auf diese Losnummer entfällt also der größte Anteil.

Kurzum: Person $\begin{eqnarray*} \left\lfloor \frac{1+\sqrt{4n+1}}{2}\right\rfloor \end{eqnarray*}$ bekommt die Maximalmenge.

Bei den Näherungen besteht die Gefahr, dass man bei manchen $\begin{eqnarray*} n \end{eqnarray*}$ (bei n=100 wohl nicht) das Maximum nicht genau trifft, sondern man um eine Stelle daneben haut. Diese Gefahr besteht bei Huggys Formel nicht.

Bei manchen $\begin{eqnarray*} n \end{eqnarray*}$ gibt es allerdings zwei (dann benachbarte) globale Maximumstellen: Für $\begin{eqnarray*} n=m(m+1) \end{eqnarray*}$ sind sowohl $\begin{eqnarray*} k=m \end{eqnarray*}$ als auch $\begin{eqnarray*} k=m+1 \end{eqnarray*}$ Maximumstellen.

12.02.2020, 17:20

Nils Hoppenstedt

Auf diesen Beitrag antworten »

Klar, die exakte Lösung stand schon fest. Mich hat halt einfach die analytische Näherung für die Verteilung interessiert. Ist ganz praktisch, wenn man noch andere Eigenschaften der Verteilung ermitteln möchte (z.B. ab welcher Losnummer das Fass halb leer ist).

12.02.2020, 18:45

mYthos

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
...
Irgendwie hatte ich beim Durchlesen auch ein Déjà-vu. Aber Dopap beherrscht die Kunst, Fragen in anderem Gewand nach so langer Zeit wieder zu stellen, dass inzwischen alle vergessen haben, wo wie und wann das Original aufgetaucht war. Zumal das Suchen womöglich länger dauert als die erneute Problemlösung. Augenzwinkern

Na, wer sagt's denn!

Maximales Kuchenstück

mY+

12.02.2020, 19:59

Dopap

Auf diesen Beitrag antworten »

Zu Kommentaren wie
Lehrer

Zitat:

Original von Huggy
Hat dir das HAL nicht schon mal vorgerechnet? [...]

besteht keinerlei Anlass.
Ja, da hatte ich vor langer Zeit aus numerischer Sicht schon mal die richtige Idee gehabt.

Ansonsten sehr ergiebig. Das Histogramm von Ruhnau erinnert mich an die Rayleigh-Verteilung.
Rayleigh mit $\begin{eqnarray*} \sigma = 10 \quad \text{und Skalenfaktor}\quad Y= 200 \end{eqnarray*}$

$\begin{eqnarray*} f(x):= Y\cdot \left(\frac{x^2}{2\sigma^2}e^{-\frac {x^2}{2\sigma^2}}\right) \end{eqnarray*}$

stimmt mit Hoppenstedt wohl überein.

Ist ja etwas schief, die 100 Litermarke wird deshalb erst vom Los #12 mit 108.288 Liter überschritten.

12.02.2020, 21:19

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Dopap
Zu Kommentaren wie
Lehrer

Zitat:

Original von Huggy
Hat dir das HAL nicht schon mal vorgerechnet? [...]

besteht keinerlei Anlass.

Ja, nicht ganz, da nicht du es warst, der damals gefragt hatte (weit vor dem von mYthos verlinkten Thread):

Wahrscheinlichkeit, dass x nach y Versuchen eingetreten ist

Das Problem dort mag etwas anders verpackt sein, führt aber de facto auf ganz ähnliche Strukturen. Und das war es wohl, an das ich mich oben undeutlich erinnert hatte. Augenzwinkern

13.02.2020, 07:40

Huggy

Auf diesen Beitrag antworten »

Zitat:

Original von Dopap
Zu Kommentaren wie
Lehrer

Zitat:

Original von Huggy
Hat dir das HAL nicht schon mal vorgerechnet? [...]

besteht keinerlei Anlass.

Mir ist nicht klar, weshalb du dich dadurch angegriffen fühlst. Weshalb soll man nicht sagen dürfen, dass man glaubt sich zu erinnern, dass du das Problem schon mal eingestellt hast und HAL damals eine Lösung gegeben hat. Ob die Erinnerung nun falsch oder richtig ist, es gibt aus meiner Sicht keinen Grund, weshalb du so negativ darauf reagierst.

Neue Frage »

Antworten »

Maximum einer diskreten Funktion

Verwandte Themen