Das Lügner-Problem

23.11.2012, 18:12

martha.1981

Das Lügner-Problem

Hallo,

die Aufgabe lautet:

Zitat:

Man betrachtet n Lügner $\begin{eqnarray*} I_1,...,I_n \end{eqnarray*}$ . $\begin{eqnarray*} I_1 \end{eqnarray*}$ erhält eine Information in der Form ja oder nein, gibt dies weiter an $\begin{eqnarray*} I_2 \end{eqnarray*}$ und so weiter, bis $\begin{eqnarray*} I_n \end{eqnarray*}$ die Information bekanntgibt. $\begin{eqnarray*} I_j \end{eqnarray*}$ gibt mit Wahrscheinlichkeit p , 0 < p < 1, das weiter, was er gehört hat. Mit Wahrscheinlichkeit 1-p gibt er das Gegenteil weiter.
Man berechne die Wahrscheinlichkeit $\begin{eqnarray*} p_n \end{eqnarray*}$ dafür, dass die Information richtig durchgegeben wurde.

Ich habe mir gedacht, das ist eine n-fache Bernoulli-Kette wobei ich davon ausgehe, das Lügner $\begin{eqnarray*} I_n \end{eqnarray*}$ ebenfalls mit einer W'keit von p das bekannt gibt, was er gehört hat und mit einer W'keit 1-p das Gegenteil.

D.h. $\begin{eqnarray*} \{0,1\}^n=\mathbb{F}_2^n \end{eqnarray*}$ ist die Menge aller Möglichen Ausgänge des Experiments.

Betrachte ich nun (o.E.!) von allen möglichen Ausgängen nur die mit einer 1 in der letzten Komponente, und ignoriere ich dabei die letzte Komponente für jedes Element dieser Teilmenge, so erhalte ich gerade $\begin{eqnarray*} \{0,1\}^{n-1} \end{eqnarray*}$ .

Jetzt definiere ich $\begin{eqnarray*} f(x):=\sum_{i=1}^{n-1}x_i \end{eqnarray*}$ und $\begin{eqnarray*} g(x):=(n-1)-f(x) \end{eqnarray*}$

Die Wahrscheinlichkeit, dass am Ende wieder die 1 herauskommt, also allg. wieder die Information vom Anfang, ist dann

$\begin{eqnarray*} P(A)=\sum_{x\in\{0,1\}^{n-1}} p^{f(x)}\cdot (1-p)^{g(x)} \end{eqnarray*}$

Passt das so?

M

EDIT: nein es passt nicht... unglücklich

23.11.2012, 21:05

Dopap

Auf diesen Beitrag antworten »

eigentlich wäre das Problem besser mit der Verbreitung eines Gerüchtes umschrieben, das sich in einer Stadt voll Lügner mit Wkt p verbreitet.
Ausnahme: $\begin{eqnarray*} I_0 \end{eqnarray*}$ ist der Bürgermeister, $\begin{eqnarray*} I_{n+1} \end{eqnarray*}$ der Stadtreporter, beide lügen niemals, der Bürgermeister beginnt.

mein Ansatz: sei n gerade. Dann ist mit q=1-p

$\begin{eqnarray*} p_n= \sum_{k=0}^n \binom n k q^{n-k} \end{eqnarray*}$

Andererseits gilt:

$\begin{eqnarray*} 1= (q+p)^n =\sum_{k=0}^n = \binom n k q^k p^{n-k}<br /> <br /> (q-p)^n= \sum_{k=0}^n= \binom n k q^kp^{n-k}(-1)^k \end{eqnarray*}$

summe:

$\begin{eqnarray*} 1+(q-p)^n=2p_n \end{eqnarray*}$

für $\begin{eqnarray*} p\neq 1 \end{eqnarray*}$ müsste das rasch gegen 0.5 streben.

24.11.2012, 15:22

Fragen über Fragen

Auf diesen Beitrag antworten »

Hi Dopap,
müsste nicht in der ersten Summe statt k ein 2k auftauchen (die Summe dafür bis n/2, wenn die Laufvariable weiter k heißen soll), und noch multipliziert mit p^(2k) ?

Neue Frage »

Antworten »

Das Lügner-Problem

Verwandte Themen