Diskrepanz zwischen Kopf und Schwanz

Betrachten Sie eine Folge von $n$ Flips einer unbefangenen Münze. Sei $H_i$ der absolute Wert des Überschusses der Anzahl von Köpfen über Schwänzen, die in den ersten $i$ Flips gesehen wurden. Definiere $H=\text{max}_i H_i$ . Zeigen Sie, dass $E[H_i]=\Theta ( \sqrt{i} )$und$E[H]=\Theta( \sqrt{n} )$.

Dieses Problem taucht im ersten Kapitel von "Randomized Algorithms" von Raghavan und Motwani auf, weshalb es vielleicht einen elementaren Beweis für die obige Aussage gibt. Ich kann es nicht lösen, daher würde ich mich über jede Hilfe freuen.

Ihre Münzwürfe bilden ein eindimensionalen random walk $X_0,X_1,\ldots$ beginnend bei $X_0 = 0$ , wobei $X_{i+1} = X_i \pm 1$ , wobei jede der Optionen mit einer Wahrscheinlichkeit von $1/2$ . Jetzt ist $H_i = |X_i|$und so ist $H_i^2 = X_i^2$ . Es ist einfach, E [ X 2 i i zu berechnen$E[X_i^2] = i$(Dies ist nur die Varianz), und so ist aus Konvexität. Wir wissen auch, dassXimit dem Mittelwert Null und der Varianziungefähr normal verteilt ist, und daher können SieE[Hi]≈ √ berechnen$E[H_i] \leq \sqrt{E[H_i^2]} = \sqrt{i}$$X_i$$i$$E[H_i] \approx \sqrt{(2/\pi)i}$ .

Was betrifft , so haben wir das Gesetz des iterierten Logarithmus , was uns (vielleicht) dazu veranlasst, etwas etwas Größeres als √ zu erwarten$E[\max_{i \leq n} H_i]$ . Wenn Sie gut mit einer Obergrenze von ˜ O ($\sqrt{n}$können Sie eine große Abweichung für jedesXiund dann die Vereinigungsgrenze verwenden, obwohl dies die Tatsache ignoriert, dass dasX$\tilde{O}(\sqrt{n})$$X_i$$X_i$ verwandt sind.

Bearbeiten: Wie es passiert, ist aufgrund des Reflexionsprinzips , siehe diese Frage . Also ist E [ max i ≤ n x $\Pr[\max_{i \leq n} X_i = k] = \Pr[X_n = k] + \Pr[X_n = k+1]$ daPr[Hn=k]=Pr[Xn=k]+Pr[Xn=-k]=2Pr[Xn=k]. Jetzt 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]$ und daherE[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),$$ . Die andere Richtung ist ähnlich.$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})$.