Écart entre les têtes et les queues

Considérons une séquence de $n$ flips d'une pièce non biaisée. Soit $H_i$ la valeur absolue de l'excédent du nombre de têtes sur les queues vu dans les premiers $i$ flips. Définissez $H=\text{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 des «algorithmes randomisés» de Raghavan et Motwani, il existe donc peut-être une preuve élémentaire de la déclaration ci-dessus. Je ne peux pas le résoudre, j'apprécierais donc toute aide.

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 donc $H_i^2 = X_i^2$ . Il est facile de calculer $E[X_i^2] = i$ (c'est juste la variance), et donc$E[H_i] \leq \sqrt{E[H_i^2]} = \sqrt{i}$ de la convexité. Nous savons également que$X_i$est distribué à peu près normal avec une moyenne et une variancenulles$i$, et vous pouvez donc calculer$E[H_i] \approx \sqrt{(2/\pi)i}$ .

$E[\max_{i \leq n} H_i]$$\sqrt{n}$$\tilde{O}(\sqrt{n})$$X_i$$X_i$

Edit: En l' , raison du principe de réflexion, voir cette question . Donc puisque . Maintenant et donc$\Pr[\max_{i \leq n} X_i = k] = \Pr[X_n = k] + \Pr[X_n = k+1]$

$$\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}{2} + \frac{1}{2}\Pr[X_n = 0] \\ &= E[H_n] + \Theta(1), \end{align*}$$ $\Pr[H_n = k] = \Pr[X_n = k] + \Pr[X_n = -k] = 2\Pr[X_n = k]$ $$\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),$$ $E[\max_{i \leq n} H_i] \leq 2E[H_n] + \Theta(1) = O(\sqrt{n})$. L'autre direction est similaire.

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

La distribution semi-normale indique que si est une distribution normale avec une moyenne de 0 et une variance , alorssuit une demi-distribution avec la moyenne , et la variance . Cela donne la réponse requise, puisque la variance de la marche normale est , et vous pouvez approximer la distribution de à une distribution normale en utilisant le théorème de la limite centrale.$X$$\sigma^2$$|X|$$\sigma \sqrt{\frac{2}{\pi}}$$\sigma^2 (1-2/\pi)$$\sigma^2$$n$$X$

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

Dans les premiers flips, supposons que nous obtenions queues, puis. Par conséquent, Utilisez l'approximation de Stirling , nous connaissons .$2i$$k$$H_{2i}=2|i-k|$

$$\begin{align} E(H_{2i}) & =2\sum_{k=0}^{i}\binom{2i}{k}(\frac{1}{2})^{2i}\cdot 2(i-k)\\ & = (\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}$$ $E(H_{2i})=\Theta(\sqrt{2i})$