Betrunkner will nach Hause... Helft ihm!

16.05.2008, 17:12

zwergnase

Betrunkner will nach Hause... Helft ihm!

Ein Betrunkner steht vor seiner Türe und hat N Schlüssel in seiner Tasche, er versucht die Türe folgendermaßen zu öffnen: Er wählt zufällig einen Schlüssel aus, wenn dieser nicht passt legt er ihn nicht wieder zurück zu den anderen Schlüsseln. Diese Experiment wiederholt er so lange bis der entsprechende Schlüssel passt. Mit welcher Wahrscheinlichkeit benötigt er höchstens M Versuche.

Mit der Biominalverteilung kann ich das nicht rechnen, weil p (= Anzahl der verbleibenden Möglichkeiten) ja ständig kleiner wird, also nicht konstant ist.

Für die Möglichkeiten habe ich mir das so gedacht: $\begin{eqnarray*} \sum_{k=0}^{N-1} ~ \frac{1}{N-k} = \frac{1}{N} +\frac{1}{N-1} + \frac{1}{N-2} + ... + \frac{1}{1} \end{eqnarray*}$

Nun fehlt mir noch die Wahrscheinlichkeit dass er höchstens M Versuche benötigt. Wie mache ich das?

16.05.2008, 17:22

tmo

Auf diesen Beitrag antworten »

Die Aufgabe ist einfacher als sie zunächst aussieht.

Sei X der Versuch, bei dem er den richtigen Schlüssel zieht. Dann gilt für $\begin{eqnarray*} 1 \leq k \leq N \end{eqnarray*}$ : $\begin{eqnarray*} P(X=k)=\frac{1}{N} \end{eqnarray*}$ .

Du musst nun mit $\begin{eqnarray*} I = \{1, \dotsc , M \} \end{eqnarray*}$ $\begin{eqnarray*} P\left( \bigcup_{i \in I} (X=i) \right) \end{eqnarray*}$ berechnen. Glücklicherweise sind diese Ereignisse alle disjunkt.

16.05.2008, 17:42

zwergnase

Auf diesen Beitrag antworten »

Warum? Sagen wir mal die ersten drei Schlüssel die er zieht passen nicht, dann ist es doch nicht mehr $\begin{eqnarray*} P(X=k)=\frac{1}{N} \end{eqnarray*}$ oder??? Dann müsste es doch $\begin{eqnarray*} P(X=k)=\frac{1}{N-3} \end{eqnarray*}$ restliche Möglichkeiten geben.

Zitat:

Original von tmo
Du musst nun mit $\begin{eqnarray*} I = \{1, \dotsc , M \} \end{eqnarray*}$ $\begin{eqnarray*} P\left( \bigcup_{i \in I} (X=i) \right) \end{eqnarray*}$ berechnen. Glücklicherweise sind diese Ereignisse alle disjunkt.

Könntest du mal bitte die ersten ein zwei Glieder hinschreiben, weil ich nicht so recht verstehe was da raus kommen soll. Was ist den z.B. konkret $\begin{eqnarray*} P(X=2) \end{eqnarray*}$ ?

16.05.2008, 17:43

Auf diesen Beitrag antworten »

@zwergnase

tmo hat Recht:

Die Wahrscheinlichkeit, der "richtige" zu sein, ist für jeden der $\begin{eqnarray*} N \end{eqnarray*}$ Schlüssel identisch gleich $\begin{eqnarray*} \frac{1}{N} \end{eqnarray*}$ .

Du dagegen begehst den häufig zu beobachtenden Fehler, eine bedingte Wahrscheinlichkeit mit einer (absoluten) Wahrscheinlichkeit zu verwechseln:

Die bedingte Wahrscheinlichkeit, dass der $\begin{eqnarray*} k \end{eqnarray*}$ -te Schlüssel der richtige ist unter der Bedingung, dass die vorherigen $\begin{eqnarray*} k-1 \end{eqnarray*}$ Schlüssel nicht passten, ist tatsächlich $\begin{eqnarray*} \frac{1}{N-k+1} \end{eqnarray*}$ . Aber darum ging es hier nicht!

16.05.2008, 17:52

zwergnase

Auf diesen Beitrag antworten »

@ Arthur Dent

Jetzt verstehe ich was tmo meint. Aber ich verstehe immer noch nicht so recht wie ich die Vereinigung der X = i berechnen soll.

16.05.2008, 19:39

zwergnase

Auf diesen Beitrag antworten »

Ist $\begin{eqnarray*} I = \{1, \dotsc , M \} \end{eqnarray*}$ $\begin{eqnarray*} P\left( \bigcup_{i \in I} (X=i) \right) = N \end{eqnarray*}$ ???

17.05.2008, 09:56

tmo

Auf diesen Beitrag antworten »

Hast du die Schreibweise richtig verstanden?
Es ist $\begin{eqnarray*} I = \{1, \dotsc , M \} \end{eqnarray*}$ und du musst dann $\begin{eqnarray*} P \left( \bigcup_{i \in I} (X=i) \right) \end{eqnarray*}$ berechnen.

Oder auch einfach nur:

$\begin{eqnarray*} P((X=1) \cup (X=2) \cup \dotsb \cup (X=M) ) \end{eqnarray*}$

Neue Frage »

Antworten »

Betrunkner will nach Hause... Helft ihm!

Verwandte Themen