Diskrepanz zwischen Köpfen und Schwänzen

Question

Betrachten Sie eine Sequenz von $ n $ Flips einer unvoreingenommenen Münze. Sei $ h_i $ den absoluten Wert des Überschusses der Anzahl der Köpfe über Schwänzen, die in den ersten $ i $ Flips zu sehen sind. Definieren Sie $ h = text {max} _i h_i $. Zeigen Sie, dass $ e [h_i] = theta ( sqrt {i}) $ und $ e [h] = theta ( sqrt {n}) $.

Dieses Problem erscheint im ersten Kapitel von "randomisierten Algorithmen" von Raghavan und Motwani, daher gibt es vielleicht einen elementaren Beweis der obigen Aussage. Ich kann es nicht lösen, also würde ich mich über jede Hilfe freuen.

Answer 1

Ihre Münzflipps bilden einen eindimensionalen Zufalls Walk $ x_0, x_1, ldots $ ab $ x_0 = 0 $, mit $ x_ {i+1} = x_i pm 1 $, jede der Optionen mit Wahrscheinlichkeit $ 1/2 $. Jetzt $ h_i = | x_i | $ und so $ h_i^2 = x_i^2 $. Es ist einfach, $ e [x_i^2] = i $ zu berechnen (dies ist nur die Varianz), und so $ e [h_i] leq sqrt {e [h_i^2]} = sqrt {i} $ von Konvexität. Wir wissen auch, dass $ x_i $ ungefähr normal mit nullem Mittelwert und Varianz $ i $ verteilt ist, und so können Sie $ E [H_I] appry sqrt {(2/ pi) i} $ berechnen.

Wie für $ e [ max_ {i leq n} h_i] $ haben wir das Gesetz des iterierten Logarithmus, was (vielleicht) dazu führt, dass wir etwas größeres als $ sqrt {n} $ erwarten. Wenn Sie mit einer Obergrenze von $ tilde {o} ( sqrt {n}) $ gut sind X_i $ sind verwandt.

Bearbeiten: $ pr [ max_ {i leq n} x_i = k] = pr [x_n = k] + pr [x_n = k + 1] $ aufgrund des Reflexionsprinzips siehe diese Frage. Also $$ begin {align*} e [ max_ {i leq n} x_i] & = sum_ {k geq 0} k ( pr [x_n = k] + pr [x_n = k + 1] ) & = sum_ {k geq 1} (2k -1) pr [x_n = k] & = sum_ {k geq 1} 2k pr [x_n = k] - frac {1 } Oder k] = pr [x_n = k] + pr [x_n = -k] = 2 pr [x_n = k] $. Now $$ frac{max_{i leq n} X_i + max_{i leq n} (-X_i)}{2} leq max_{i leq n} H_i leq max_{i Leq n} x_i + max_ {i leq n} (-x_i), $$ und daher $ e [ max_ {i leq n} h_i] leq 2e [h_n] + theta (1) = o (( sqrt {n}) $. Die andere Richtung ist ähnlich.

Answer 2

Du kannst den ... benutzen halbe normale Verteilung um die Antwort zu beweisen.

Die halb normale Verteilung besagt, dass $ x $ eine Normalverteilung mit Mittelwert 0 und Varianz $ sigma^2 $ ist, $ | x | $ folgt a Halbverteilung mit Mean $ sigma sqrt { frac {2} { pi}} $ und Varianz $ sigma^2 (1-2/ pi) $. Dies gibt die erforderliche Antwort, da die Varianz $ sigma^2 $ des normalen Spaziergangs $ n $ beträgt und Sie die Verteilung von $ x $ an eine Normalverteilung unter Verwendung des Central Limit -Theorems annähern.

$ X $ ist die Summe des Random Walk, wie Yuval Filmus erwähnt.

Answer 3

Angenommen, wir erhalten $ k $ Tails, dann $ h_ {2i} = 2 | ik | $. Daher begin {align} e (h_ {2i}) & = 2 sum_ {k = 0}^{i} binom {2i} {k} ( frac {1} {2})^{2i} cdot 2 (ik) & = ( frac {1} {2})^{2i-2} links [i sum_ {k = 0}^{i} binom {2i} {k}- sum_ {k = 0}^ik binom {2i} {k} right] & = ( frac {1} {2})^{2i-2} links [i links (2^{ 2i}+ binom {2i} {i} right)/2-2i sum_ {k = 0}^{i-1} binom {2i-1} {k} right] & = ( Frac {1} {2})^{2i-2} cdot i links [2^{2i-1}+ binom {2i} {i}/2-2 cdot 2^{2i-1}/ 2 right] & = 2i cdot binom {2i} {i}/2^{2i}. end {align} Verwendung Stirlings Annäherung, Wir wissen $ e (H_ {2i}) = theta ( sqrt {2i}) $.