Bernoullivert.: Wie formal? < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 03:31 So 29.01.2012 | | Autor: | Pille456 |
| Aufgabe | Gegeben seien zwei Folgen von je n Bits. Die erste Folge liege auf einem PC auf der Festplatte und die andere Folge wird über das Netzwerk übertragen. Aufgrund einer fehlerhaften Leitung besteht eine [mm] p=\bruch{1}{n} [/mm] große Wahrscheinlichkeit, dass ein Bit flippt.
Wie groß ist die Wahrscheinlichkeit, dass beide Folge gleich sind, nachdem die eine Folge über das Netzwerk übertragen wurde?
Tipp: Nutzen Sie die Hamming-Distanz |
Hi!
Ich fand die Aufgabe eigentlich relativ einfach zu lösen:
Seien die Bitfolgen wie folgt:
[mm] X=X_1X_2X_3...X_n [/mm]
[mm] Y=Y_1Y_2Y_3...Y_n
[/mm]
mit der Hamming-Distanz = h(X,Y)
Dann müssen genau h(X,Y) Bits flippen und n-h(X,Y) Bits nicht flippen:
[mm] p=(\bruch{1}{n})^{h(X,Y)}*(1-\bruch{1}{n})^{n-h(X,Y)}
[/mm]
Erstmal vorab: Ist das so korrekt?
Mir wurde nun immer nahe gelegt im Bereich der Stochastik am Besten nicht nach "Bauchgefühl" zu handeln, sondern sich einfach an die Formeln zu halten, die gesichert und bewiesen sind.
Nun sieht mir das hier verdammt nach einem Bernoulli-Experiment aus, welches n mal ausgeführt wird: Entweder ein Bit muss geflippt werden oder nicht (und das wird halt für jedes Bit einzeln entschieden). Wenn ich das nun erkannt habe, gibt es dann auch eine Möglichkeit das ganze formaler zu lösen? Vielleicht irgendwie mit der Dichtefunktion oder so?
Normalerweise müsste es doch reichen, dass ich erkenne welcher bekannte Problemfall vorliegt, dann schaue was in meinem Beispiel die Variablen n,k,p etc konkret bedeuten und dann setze ich in die Formel ein und bin fertig, ohne über die Formel direkt nochmal nachzudenken.Aber irgendwie gelingt mir das hier gerade nicht.
Hat jemand eine Idee, wie man das "stupide nach Formel" macht?
Gruß
Pille
|
|
| |
|
> Gegeben seien zwei Folgen von je n Bits. Die erste Folge
> liege auf einem PC auf der Festplatte und die andere Folge
> wird über das Netzwerk übertragen. Aufgrund einer
> fehlerhaften Leitung besteht eine [mm]p=\bruch{1}{n}[/mm] große
Das n hier ist aber fest?
> Wahrscheinlichkeit, dass ein Bit flippt.
>
>
> Wie groß ist die Wahrscheinlichkeit, dass beide Folge
> gleich sind, nachdem die eine Folge über das Netzwerk
> übertragen wurde?
>
>
> Tipp: Nutzen Sie die Hamming-Distanz
> Hi!
>
> Ich fand die Aufgabe eigentlich relativ einfach zu lösen:
>
> Seien die Bitfolgen wie folgt:
> [mm]X=X_1X_2X_3...X_n[/mm]
> [mm]Y=Y_1Y_2Y_3...Y_n[/mm]
> mit der Hamming-Distanz = h(X,Y)
>
> Dann müssen genau h(X,Y) Bits flippen und n-h(X,Y) Bits
wieso müssen?
> nicht flippen:
> [mm]p=(\bruch{1}{n})^{h(X,Y)}*(1-\bruch{1}{n})^{n-h(X,Y)}[/mm]
>
> Erstmal vorab: Ist das so korrekt?
Ja das ist die Wkeit, dass h(X,Y) Bits nicht richtig übertragen wurden.
>
> Mir wurde nun immer nahe gelegt im Bereich der Stochastik
> am Besten nicht nach "Bauchgefühl" zu handeln, sondern
> sich einfach an die Formeln zu halten, die gesichert und
> bewiesen sind.
Wo studierst du? An einer Bourbaki-Uni?
> Nun sieht mir das hier verdammt nach einem
> Bernoulli-Experiment aus, welches n mal ausgeführt wird:
Mehr Zauberei steckt da auch m.E. nicht dahinter.
> Entweder ein Bit muss geflippt werden oder nicht (und das
> wird halt für jedes Bit einzeln entschieden).
und das auch noch unabhängig
> Wenn ich das nun erkannt habe, gibt es dann auch eine Möglichkeit das
> ganze formaler zu lösen? Vielleicht irgendwie mit der
> Dichtefunktion oder so?
Meinst du nicht, dass eine einfache Lösung genügt?
Du kannst folgendes Ereignis definieren:
[mm]A_i[/mm] = "i-tes Bit wurde richtig übertragen"
Dann suchst du doch das Ereignis ("Ein Fehler tritt auf"): [mm]\left(\bigcap_{n\in N}A_n \right)\cap A_j^C[/mm] mit [mm]N=\{1,\ldots,n\}\setminus \{j\}[/mm]. Also Bit j hat einen Fehler.
Auf Grund der Unabhängigkeit der Ereignisse [mm] $A_i$ [/mm] ist
[mm]P\left(A_j^C\cap\bigcap_{n\in N}A_n \right)=P(A_j^C)\produkt_{n\in N}{P(A_n)} =\frac{1}{n}\cdot \left( 1-\bruch{1}{n}\right)^{| N|}[/mm]
Und siehe da: Kein weiterer Erkenntnisgewinn.
> Normalerweise müsste es doch reichen, dass ich erkenne
> welcher bekannte Problemfall vorliegt, dann schaue was in
> meinem Beispiel die Variablen n,k,p etc konkret bedeuten
> und dann setze ich in die Formel ein und bin fertig, ohne
> über die Formel direkt nochmal nachzudenken.
Ich würde auch sagen, die Fehlerwkeit über Binomialverteilung ausgerechnet werden kann. Fertig.
> Aber irgendwie
> gelingt mir das hier gerade nicht.
Du hast doch genau das aufgeschrieben, was du benötigst. Bei dir musst du nur noch den Hammingabstand Eins setzen.
> Hat jemand eine Idee, wie man das "stupide nach Formel"
> macht?
>
> Gruß
> Pille
|
|
|
|
