WS bei Eisstand

15.11.2006, 11:17	donkarabelas	Auf diesen Beitrag antworten »
WS bei Eisstand hi there! mir bereitet folgendes BSP probleme: Bei einem Eisstand warten $\begin{eqnarray} m+n \end{eqnarray}$ leute, davon haben $\begin{eqnarray} m \end{eqnarray}$ eine 1€ Münze und $\begin{eqnarray} n \end{eqnarray}$ eine 2€ Münze; es gilt $\begin{eqnarray} m>n \end{eqnarray}$ . Das Eis kostet 1€ und der Kassier hat am Anfang kein Wechselgeld. WIe hoch ist die W! dafür das niemand auf das Retourgeld warten muss? Ich habe keinen Dau wie ich hier agieren sollte. Könnte mir jemand hilfestellung geben? glg elias
15.11.2006, 13:19	AD	Auf diesen Beitrag antworten »
Insgesamt gibt es $\begin{eqnarray} \binom{m+n}{m} \end{eqnarray}$ Möglichkeiten der Warteschlange, indem man die $\begin{eqnarray} m \end{eqnarray}$ Positionen der 1-Euro-Leute innerhalb der Schlange betrachtet. Im Sinne der Laplace-Wahrscheinlichkeit ist das die Anzahl aller Möglichkeiten. Jetzt zu den günstigen Möglichkeiten, wo keiner auf das Wechselgeld warten muss: Offenbar muss an jeder Schlangenposition $\begin{eqnarray} k \end{eqnarray}$ , $\begin{eqnarray} k=1,\ldots,n \end{eqnarray}$ , die Anzahl der 1-Euro-Leute vor bis einschließlich dieser Position größer oder gleich als die Anzahl der 2-Euro-Leute sein. Sei $\begin{eqnarray} A(m,n) \end{eqnarray}$ die Anzahl der günstigen Warteschlangen für $\begin{eqnarray} m\geq n \end{eqnarray}$ . Man kann die Anzahl Warteschlangen zählen, wo es schiefgeht: Das kann nur an den ungeraden Positionen $\begin{eqnarray} k=2j+1 \end{eqnarray}$ für $\begin{eqnarray} j=0,1,\ldots,n-1 \end{eqnarray}$ der Fall sein, wenn nämlich vorher jeweils genau $\begin{eqnarray} j \end{eqnarray}$ Leute mit 1- und 2-Euromünzen in einer "günstigen" Anordnung stehen, an Position $\begin{eqnarray} k=2j+1 \end{eqnarray}$ eine 2-Euro-Münze und der Rest beliebig. Also gilt die Rekursion $\begin{eqnarray} A(m,n) = \binom{m+n}{n} - \sum\limits_{j=0}^{n-1} ~ A(j,j)\cdot \binom{m+n-2j-1}{n-j-1}\qquad () \end{eqnarray}$ Es sieht so aus, als würde $\begin{eqnarray} A(m,n) = \binom{m+n}{n} \cdot \frac{m-n+1}{m+1} \end{eqnarray}$ gelten, das kann man jetzt (versuchen), mit Induktion unter Benutzung von () zu beweisen. Was mich jetzt wurmt ist, dass das sicher viel einfacher geht. Irgendwo hab ich das auch schon mal gesehen, ich weiß verflixt bloß nicht mehr, wo...
15.11.2006, 15:29	donkarabelas	Auf diesen Beitrag antworten »
hi, danke mal für die ausführlichen überlegungen, vl kann man das irgendwie mit einer Zufallsvariablen lösen die sic nachher schön einer verteilung unterwirft. lg elias
15.11.2006, 16:15	AD	Auf diesen Beitrag antworten »
Ok, es gibt einen einfacheren Weg: Für $\begin{eqnarray} 0\leq n\leq m+1 \end{eqnarray}$ weisen wir die auch oben erhaltene Formel $\begin{eqnarray} p(m,n) = \frac{m+1-n}{m+1} \end{eqnarray}$ für die Wahrscheinlichkeit einer "passenden" Schlange durch Induktion über $\begin{eqnarray} n+m \end{eqnarray}$ nach. Der Induktionsanfang ist hier etwas komplizierter: $\begin{eqnarray} p(m,0) = 1 \end{eqnarray}$ (keine 2-Euro-Münzen) und $\begin{eqnarray} p(m,m+1) = 0 \end{eqnarray}$ (zuviel 2-Euro-Münzen) sollten aber inhaltlich klar sein. Jetzt zum Induktionsschluss $\begin{eqnarray} (m+n-1)\to (m+n) \end{eqnarray}$ : Den müssen wir nur betrachten für den Fall $\begin{eqnarray} 1\leq n\leq m \end{eqnarray}$ , alles andere deckt der Induktionsanfang ab. Wir schauen uns den letzten der (m+n) Wartenden an: Mit Wahrscheinlichkeit $\begin{eqnarray} \frac{m}{m+n} \end{eqnarray}$ ist das jemand mit einer 1-Euro-Münze, mit Wahrscheinlichkeit $\begin{eqnarray} \frac{n}{m+n} \end{eqnarray}$ dagegen jemand mit einer 2-Euro-Münze. Wie auch immer, falls vorher alles glattgeht, gibt es auch für diesen letzten selbst im zweiten Fall Wechselgeld, und zwar wegen $\begin{eqnarray} 1\leq n\leq m \end{eqnarray}$ . Es ergibt sich die Rekursion $\begin{eqnarray} p(m,n) = \frac{m}{m+n}\cdot p(m-1,n) + \frac{n}{m+n}\cdot p(m,n-1) \end{eqnarray}$ , in die man nun die Induktionsvoraussetzung in Form von $\begin{eqnarray} p(m-1,n) = \frac{m-n}{m} \end{eqnarray}$ und $\begin{eqnarray} p(m,n-1) = \frac{m+2-n}{m+1} \end{eqnarray}$ einsetzen kann. Dann ergibt sich $\begin{eqnarray} p(m,n) = \frac{m}{m+n}\cdot \frac{m-n}{m} + \frac{n}{m+n}\cdot \frac{m+2-n}{m+1} = \frac{(m-n)(m+1)+n(m+2-n)}{(m+n)(m+1)} = \frac{m+1-n}{m+1} \end{eqnarray}$ , Hurra.

1

Verwandte Themen