Discrepância entre cara e coroa

Considere uma sequência de $n$ lançamentos de uma moeda imparcial. Deixe $H_i$ denotar o valor absoluto do excesso do número de cabeças sobre caudas vistas nos primeiros $i$ flips. Defina $H=\text{max}_i H_i$ . Mostre que $E[H_i]=\Theta ( \sqrt{i} )$e$E[H]=\Theta( \sqrt{n} )$.

Esse problema aparece no primeiro capítulo de `Algoritmos aleatórios 'de Raghavan e Motwani, portanto, talvez haja uma prova elementar da afirmação acima. Não consigo resolvê-lo, por isso gostaria de receber qualquer ajuda.

Seu coin flips formar uma caminhada unidimensional aleatória a partir de X 0 = 0 , com X i + 1 = X i ± 1 , cada uma das opções com probabilidade 1 / 2 . Agora H i = | X i | e então H 2 i = X 2 i . É fácil calcular E [ X 2 i ] $X_0,X_1,\ldots$$X_0 = 0$$X_{i+1} = X_i \pm 1$$1/2$$H_i = |X_i|$$H_i^2 = X_i^2$ (esta é apenas a variação), e então E [ H i ] ≤ $E[X_i^2] = i$ de convexidade. Sabemos também queXié distribuído aproximadamente normal com média zero e variânciai, e assim você pode calcularE[Hi]≈$E[H_i] \leq \sqrt{E[H_i^2]} = \sqrt{i}$$X_i$$i$ .$E[H_i] \approx \sqrt{(2/\pi)i}$

Quanto a , temos a lei do logaritmo iterado , que (talvez) nos leva a esperar algo um pouco maior que $E[\max_{i \leq n} H_i]$ . Se você é bom com um limite superior de ˜ O ($\sqrt{n}$, você pode usar um grande desvio com destino a cadaXie depois a união obrigado, no entanto, que ignora o fato de que oXiestão relacionados.$\tilde{O}(\sqrt{n})$$X_i$$X_i$

Edit: Por acaso, devido ao princípio de reflexão, consulte esta pergunta . Então E [ max i ≤ n X i$\Pr[\max_{i \leq n} X_i = k] = \Pr[X_n = k] + \Pr[X_n = k+1]$ uma vez quePr[Hn=k]=Pr[Xn=k]+Pr[Xn=-k]=2Pr[Xn=k]. Agora max i ≤ n X i + max i ≤ n (

$$\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]$ e,portanto,E[maxi≤nHi]≤2E[Hn]+Θ(1)=O( $$\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),$$ . A outra direção é semelhante.$E[\max_{i \leq n} H_i] \leq 2E[H_n] + \Theta(1) = O(\sqrt{n})$

You can use the half-normal distribution to prove the answer.

The half-normal distribution states that if $X$ is a normal distribution with mean 0 and variance $\sigma^2$, then $|X|$ follows a half distribution with mean $\sigma \sqrt{\frac{2}{\pi}}$, and variance $\sigma^2 (1-2/\pi)$. This gives the required answer, since the variance $\sigma^2$ of the normal walk is $n$, and you can approximate the distribution of $X$ to a normal distribution using the central limit theorem.

$X$ is the sum of the random walk as Yuval Filmus mentioned.

In first $2i$ flips, suppose we get $k$ tails, then $H_{2i}=2|i-k|$. Therefore,

$$\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}$$ Use Stirling's approximation, we know $E(H_{2i})=\Theta(\sqrt{2i})$.