Divergence entre les têtes et les queues

Question

Soit une séquence de $ n flips $ d'une pièce non biaisée. Soit $ h_i $ représentent la valeur absolue de l'excédent du nombre de têtes sur les queues vu dans la première $ i $ flips. Définir $ H = \ texte {max} _i h_i $. Montrer que $ E [h_i] = \ Theta (\ sqrt {i}) $ et $ E [H] = \ Theta (\ sqrt {n}) $.

Ce problème apparaît dans le premier chapitre de `algorithmes probabilistes par Raghavan et Motwani, alors peut-être il y a une preuve élémentaire de la déclaration ci-dessus. Je suis incapable de le résoudre, je vous serais reconnaissant de toute aide.

Answer 1

Votre pièce flips forment une unidimensionnelle marche aléatoire X_0 $, x 1, \ ldots $ à partir de X_0 $ = 0 $, avec $ X_ {i + 1} = X_i \ pm 1 $, chacune des options avec une probabilité $ 1/2 $. Maintenant $ h_i = | X_i | $ et ainsi h_i $ ^ 2 = X_i ^ 2 $. Il est facile de calculer $ E [X_i ^ 2] = i $ (ce qui est tout simplement la variance), et ainsi $ E [h_i] \ leq \ sqrt {E [h_i ^ 2]} = \ sqrt {i} $ de convexité. Nous savons aussi que $ X_i $ est distribué à peu près normale avec zéro $ moyenne et la variance i $, et ainsi vous pouvez calculer $ E [h_i] \ environ \ sqrt {(2 / \ pi) i} $.

Quant à $ E [\ max_ {i \ leq n} h_i] $, nous avons le des itérée logarithme , qui (peut-être) nous conduit à attendre quelque chose de légèrement plus grand que $ \ sqrt {n} $. Si vous êtes bien avec une limite supérieure de $ \ tilde {O} (\ sqrt {n}) $, vous pouvez utiliser un grand écart lié pour chaque X_i $ et $, alors le syndicat lié, bien que ne tient pas compte du fait que le $ x_i $ sont liés.

Edit: Comme il arrive, $ \ Pr [\ max_ {i \ leq n} X_i = k] = \ Pr [X_n = k] + \ Pr [X_n = k + 1] $ en raison du principe de réflexion, voir cette question . Alors $$ \ Begin {align *} E [\ max_ {i \ leq n} X_i] & = \ sum_ {k \ geq 0} k (\ Pr [X_n = k] + \ Pr [X_n = k + 1]) \\ & = \ {K sum_ \ geq 1} (2k-1) \ Pr [X_n = k] \\ & = \ Sum_ {k \ geq 1} 2k \ Pr [X_n = k] - \ frac {1} {2} + \ frac {1} {2} \ Pr [X_n = 0] \\ & E ??= [H_n] + \ Theta (1), \ End {align *} $$ depuis $ \ Pr [H_n = k] = \ Pr [X_n = k] + \ Pr [X_n = k] = 2 \ Pr [X_n = k] $. Maintenant $$ \ 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), $$ et donc $ E [\ max_ {i \ leq n} h_i] \ leq 2E [H_n] + \ Theta (1) = O (\ sqrt {n}) $. L'autre direction est similaire.

Answer 2

Vous pouvez utiliser la la distribution semi-normale pour prouver la réponse.

Les demi-états normaux de distribution que si $ X $ est une distribution normale avec une moyenne 0 et de variance $ \ sigma ^ 2 $, puis $ | X | $ fait suite à une moitié la distribution avec une moyenne $ \ sigma \ sqrt {\ frac {2} {\ pi}} $, et la variance $ \ sigma ^ 2 (1-2 / \ pi) $. Cela donne la réponse nécessaire, étant donné que la variance $ \ sigma ^ 2 $ de la marche normale est $ n $, et vous pouvez approcher la distribution de X $ $ à une distribution normale en utilisant le théorème central limite.

$ X $ est la somme de la marche aléatoire comme Yuval Filmus mentionné.

Answer 3

Dans la première $ 2i $ flips, supposons que nous obtenons $ k queues $, alors H- $ {} = 2i de 2 | i-k | $. Par conséquent, \ 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} \ left [i \ sum_ {k = 0} ^ {i} \ binom {2i} {k} - \ sum_ {k = 0} ^ ik \ {binom 2i} {k} \ right] \\ & = (\ Frac {1} {2}) ^ {2i-2} \ left [i \ left (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 \ left [2 ^ {2i-1} + \ {binom 2i} {i} / 2-2 \ cdot 2 ^ {2i -1} / 2 \ right] \\ & = 2i \ cdot \ {binom 2i} {i} / 2 ^ {2i}. \ End {align} Utilisez d'approximation de Stirling, nous savons $ E (H- {2i}) = \ Theta ( \ sqrt {2i}) $.