| Autor |
Beitrag |
    
Maria
| | Veröffentlicht am Dienstag, den 24. Oktober, 2000 - 22:05: | 
|
Die Lügnerkette; Ein 01-Signal gelangt über n Zwischenstationen vom Sender zum Empfänger. Jede Station gibt das signal, jeweils unabhängig von den anderen, mit Wahrscheinlichkeit p korrekt, und mit Wahrscheinlichkeit q=1-p verfälscht an die nächste Station weiter. Was ist die Wahrscheinlichkeit Pn, dass das ursprüngliche Signal korrekt beim Empfänger ankommt? Berechnen Sie lim(index:ngegen unendlich)Pn.
Hinweis: Betrachten Sie die Binomialentwicklung von (p-q)hoch n oder stellen Sie eine Rekursionsgleichung für Pn auf.
Vielen Dank |
Matroid (Matroid)
| | Veröffentlicht am Mittwoch, den 25. Oktober, 2000 - 21:17: |
|
Hi Maria, da hast Du mir was aufgeladen, bitte hab Geduld mit meinem vielen Geschriebenen.
Wann kommt das Signal also richtig an:
1. wenn alle Stationen korrekt übertragen
und dann (und das macht es erst interessant)
2. wenn trotz irgendwelcher Fehler bei irgendwelchen Stationen, das Signal durch weitere
Fehler folgender Stationen "zufällig" wieder richtig geworden ist.
Nun ist das Signal sehr einfach, es besteht nur aus 0 oder 1. Welchen Fehler kann eine
Station also machen? Aus einer 0 eine 1 machen oder umgekehrt. Wenn nun die Anzahl der
Fehler auf dem Weg gerade ist, dann gleicht sich alles wieder aus.
Achtung: Es ist hier nicht von einer Länge der Nachricht die Rede. p und q sind also die
Wahrscheinlichkeiten, daß eine 0 oder 1 richtig oder falsch übertragen wird.
Sei En das Ereignis, dass das Signal an Station n richtig ankommt. Und sei Fn das
gegenteilige Ereignis.
Die Wahrscheinlichkeit dafür ist w(En) = Pn
Und w(En) = p * w(En-1) + q * w(Fn-1)
Entweder war das Signal an der vorigen Station richtig und bleibt auch beim letzten Senden
richtig, oder es war an der vorigen Station falsch und wird durch einen weiteren Fehler beim
letzten Senden "zufällig" wieder richtig.
Das Signal kann ja nur richtig oder falsch an Station n ankommen. Deshalb gilt
w(En) + w(Fn) = 1
Und deshalb
w(En) = p * w(En-1) + q * (1-w(En-1))
Ab jetzt kann ich auch wieder Pn statt w(...) schreiben, das F ist ja weg:
Pn = p * Pn-1 + q * (1-Pn-1) = (p-q) * Pn-1 + q
P1 = p, die Wahrscheinlichkeit, dass das Signal bei einer Übertragung richtig ankommt.
P2 = (p-q) * P1 + q = (p-q) * p + q
P3 = (p-q) * P2 + q = (p-q)*[(p-q) * p + q] + q
P4 = (p-q) * P3 + q = (p-q)*[(p-q)*[(p-q) * p + q] + q] + q
Raten wir die Formel für n:
Pn = (p-q)n-1 * p + q Sn-2 i=0 (p-q)i
(Beweis durch vollständige Induktion möglich)
Und nun der Grenzwert!
In der letzten Darstellung für Pn geht der Term (p-q)n-1 * p für p ungleich 0 oder 1
gegen 0, denn p-q = p -(1 - p) = 2p-1 nimmt Werte > -1 und < 1 an.
Falls aber p=1 oder p=0 ist der erste Term 1 oder (-1)n-1*0 (je nachdem), nämlich für
p=1 immer 1 und für p=0 immer 0.
Der erste Term konvergiert also für alle 0 <= p <= 1.
Der zweite Term ist eine geometrische Reihe.
Für 0<p<1 ist deren Grenzwert q * 1 / ( 1 - ( p - q ) ) = 1/2 [ein Wunder!]
Für p=1 ist der zweite Term wegen q=1-p=0 : 0 * Sn-2 i=0 1i = 0
Für p=0 ist der zweite Term 1 * Sn-2 i=0 (-1)i entweder 1 oder 0, abhängig davon ob
n gerade oder ungerade ist, d.h. dieser Term ist dann nicht konvergent.
Und das Endergebnis:
lim Pn = 1/2 für 0<p<1
lim Pn = 1 für p=1, d.h. wenn keine Übertragungsfehler auftauchen, dann ist es
sicher, daß das Signal richtig ankommt.
lim Pn existiert nicht für p=0, d.h. wenn immer Übertragungsfehler auftauchen, dann
hängt das Ergebnis davon ab, ob n gerade oder ungerade ist. P{n} "schwankt ständig"
zwischen 0 und 1.
Eine interessante Aufgabe, aber mehr was für die Prüfung auf eine 1, oder?
Habe ich Dir helfen können.
Gruß Matroid |
|
