bräuchte kurz eure Hilfe für folgendes Beispiel:
Angenommen G ist ein sicherer PRG. Nun wird G so modifiziert, dass, sobald der Generator zehnmal das gleiche Symbol (also 10 0en oder 10 1en) hintereinander erzeugt, das letzte Symbol geändert wird (also 0 auf 1 oder 1 auf 0). Damit soll vermieden werden, dass besonders lange Folgen von gleichen Symbolen auftreten.
Ein Test T gibt als Ergebnis 0 zurück, wenn er entweder 10 Einsen oder 10 Nullen in Folge in einer Bitfolge entdeckt. Andernfalls antwortet er mit 1. Berechnen Sie Vort[T,G'], den Vorteil des Tests gegenüber dem modifizierten Generator, wenn dieser verwendet wird, um Bitfolgen der Länge 15 zu erzeugen.
Wie ich den Vorteil des Tests berechne ist mir klar, ebenfalls weiß ich, dass die Wahrscheinlichkeit, dass der Test beim PRG 1 ergibt gleich 100% ist, da es mit ihm ja unmöglich ist, 10 gleiche Bits zu erhalten -> kann nie 0 ergeben. Jetzt bräuchte ich aber noch die Wahrscheinlichkeit für einen zufälligen Bitstrom, bei dem eben 10 gleiche Symbole aufeinander folgen (und ich somit über die Gegenwahrscheinlichkeit auf P(T(r)=1) komme). Mein erster Ansatz wäre über die Binomialverteilung gegangen, was aber nichts hilft, da die ja nur aussagt, dass z.B. 10 von 15 Zeichen eine 1 sind. Dann dachte ich mir, dass die Wahrscheinlichkeit von 10 gleichen Zeichen hintereinander = 0.5^10 sein muss (insgesamt also 0.5^15, wobei ich da die übrigen Bits auch gleich hineingezogen habe, da sie ja dieselbe Wahrscheinlichkeit besitzen). Hierfür bräuchte ich jedoch die Anzahl der Möglichkeiten, auf die hin partout nicht kommen will.
Falls es wen hilft der Vorteil von dem Test gegenüber dem Generator soll 0.0068 laut Lösung sein.
Ich bedanke mich gleich im Voraus bei euch!
