Läufe bei binären Folgen

03.05.2010, 02:24

Bjoern1982

Läufe bei binären Folgen

Hallo zusammen.

Die Aufgabe lautet:

Binäre Folgen haben Läufe logarithmischer Länge (ld(n) entspricht hier der Anzahl der Bits, die man benötigt um n binär darzustellen)
Wir werfen eine Münze n mal und erhalten eine Folge von Ergebnissen X1, X2, . . . , Xn.
Als einen Lauf bezeichnen wir eine aufeinanderfolgende Teilfolge Xi, Xi+1, . . . , Xk mit Xi = Xi+1 =. . .= Xk.
(Wenn X3, X4, X5 alle das Ergebnis Kopf haben, dann ist das ein Lauf der Länge 3. Man beachte, dass ein Lauf der Länge 4 zwei Läufe der Länge 3 enthält.)

a) Zeige: prob[X besitzt einen Lauf der Länge ld( n) + k] beträgt höchstens 0,5^k.

b) Sei p die Wahrscheinlichkeit keinen Lauf der Länge ld(n) -2 ld (ld (n)) zu besitzen. Zeige, dass p für genügend großes n kleiner als 1/n ist.

Meine Ideen:

zu a)

Es gibt $\begin{eqnarray*} 2^{n-l} \end{eqnarray*}$ verbleibende Stellen, die nicht Teil des Laufs der Länge l sind, und jede dieser Stellen kann man mit 2 möglichen Ergebnissen belegen. Für den Lauf selbst gibt es n+1-l mögliche Positionen innerhalb des n-Tupels.

Da die Anzahl der günstigen Möglichkeiten für einen Lauf der Länge l sich somit durch $\begin{eqnarray*} 2^{n-l}\cdot(n+1-l)\cdot 2 \end{eqnarray*}$ ergibt folgt:

prob[A]= $\begin{eqnarray*} \frac{2^{n+1-l}(n+1-l)}{2^n}=2^{1-l}\cdot(n+1-l) \end{eqnarray*}$

Mit l=ld(n)+k folgt damit:

$\begin{eqnarray*} (\frac{1}{2})^k\cdot\frac{2}{n}\cdot(n+1-ld(n)-k) \end{eqnarray*}$

Um nun also die Gültigkeit der zu zeigenden oberen Schranke zu beweisen müsste ich beweisen, dass folgendes gilt:

$\begin{eqnarray*} \frac{2}{n}\cdot(n+1-ld(n)-k)\leq1 \end{eqnarray*}$ oder umgeformt $\begin{eqnarray*} \frac{1}{2}n+1-k\leq ld(n) \end{eqnarray*}$ mit $\begin{eqnarray*} k \leq n \end{eqnarray*}$

Für genügend große n und kleine k gilt diese Ungleichung offenbar nicht.
Also habe ich sicherlich irgendwo einen Fehler gemacht.

Sieht jemand wo ?

Gruß Björn

03.05.2010, 11:24

Auf diesen Beitrag antworten »

Zitat:

Original von Bjoern1982
Da die Anzahl der günstigen Möglichkeiten für einen Lauf der Länge l sich somit durch $\begin{eqnarray*} 2^{n-l}\cdot(n+1-l)\cdot 2 \end{eqnarray*}$ ergibt folgt:

prob[A]= $\begin{eqnarray*} \frac{2^{n+1-l}(n+1-l)}{2^n} \end{eqnarray*}$

Das stimmt so nicht: Du summierst hier einfach die Wahrscheinlichkeiten von nicht disjunkten Ereignissen, da kannst du allenfalls

prob[A] < $\begin{eqnarray*} \frac{2^{n+1-l}(n+1-l)}{2^n} \end{eqnarray*}$

folgern. Und diese Abschätzung scheint eben leider schon zu grob für das gewünschte Ziel zu sein.

Zudem ist nach der Definition

Zitat:

Original von Bjoern1982
ld(n) entspricht hier der Anzahl der Bits, die man benötigt um n binär darzustellen

hier $\begin{eqnarray*} \operatorname{ld}(n) = \lceil \log_2(n+1) \rceil \end{eqnarray*}$ und damit allenfalls $\begin{eqnarray*} 2^{\operatorname{ld}(n)} \geq n+1 \end{eqnarray*}$ , aber das ist nicht primär für das Scheitern, sondern die eben genannte Nichtdisjunktheit.

Neue Frage »

Antworten »

Läufe bei binären Folgen

Verwandte Themen