Discrepancia entre cabezas y colas.

Considere una secuencia de lanzamientos de una moneda imparcial. Let denotan el valor absoluto del exceso del número de cabezas sobre las colas visto en la primera lanzamientos. Defina . Muestre que y . $n$ $H_i$ $i$ $H=\text{max}_i H_i$ $E[H_i]=\Theta ( \sqrt{i} )$ $E[H]=\Theta( \sqrt{n} )$

Este problema aparece en el primer capítulo de 'Algoritmos aleatorios' de Raghavan y Motwani, por lo que quizás haya una prueba elemental de la afirmación anterior. No puedo resolverlo, por lo que agradecería cualquier ayuda.

probability-theory randomized-algorithms Plummer
fuente

Respuestas:

Sus lanzamientos de monedas forman una caminata aleatoria unidimensional comenzando en , con , cada una de las opciones con probabilidad . Ahoray entonces . Es fácil calcular (esto es solo la varianza), y así de convexidad. También sabemos que se distribuye más o menos normal con media cero y varianza , por lo que puede calcular . $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$ $E[X_i^2] = i$ $E[H_i] \leq \sqrt{E[H_i^2]} = \sqrt{i}$ $X_i$ $i$ $E[H_i] \approx \sqrt{(2/\pi)i}$

En cuanto a , tenemos la ley del logaritmo iterado , que (quizás) nos lleva a esperar algo un poco más grande que . Si eres bueno con un límite superior de , puedes usar un límite de desviación grande para cada y luego el límite de unión, aunque eso ignora el hecho de que los están relacionados. $E[\max_{i \leq n} H_i]$ $\sqrt{n}$ $\tilde{O}(\sqrt{n})$ $X_i$ $X_i$

Editar: Como sucede, debido al principio de reflexión, vea esta pregunta . Entonces desde . Ahora y por lo tanto $\Pr[\max_{i \leq n} X_i = k] = \Pr[X_n = k] + \Pr[X_n = k+1]$

\begin{aligned} 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} (2 k - 1) Pr [X_{n} = k] \\ = \sum_{k \geq 1} 2 k Pr [X_{n} = k] - \frac{1}{2} + \frac{1}{2} Pr [X_{n} = 0] \\ = E [H_{n}] + Θ (1), \end{aligned}

$\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]

$\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}),

$\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 2 E [H_{n}] + Θ (1) = O (\sqrt{n})

$E[\max_{i \leq n} H_i] \leq 2E[H_n] + \Theta(1) = O(\sqrt{n})$ . La otra dirección es similar.

Yuval Filmus
fuente

Después de probar , ¿no podríamos decir que para tenemos el segundo resultado, es decir, no es mayor que .

E [H_{i}] = Θ (\sqrt{i})

$E[H_{i}] = \Theta ( \sqrt{i} )$

i = n

$i=n$

E [H_{i}]

$E[H_{i}]$

Θ (\sqrt{n})

$\Theta ( \sqrt{n} )$

chazisop

Si el fuera independiente, entonces la conclusión no será cierta, ya que realmente espera que algunos de estos valores sean algo mayores de lo esperado. No es cierto en general que .

H_{i}

$H_i$

E [max (A, B)] = max (E [A], E [B])

$E[\max(A,B)] = \max(E[A],E[B])$

Yuval Filmus

La ley del logaritmo iterado no se aplica aquí, ya que es fijo y no estamos normalizando por . La respuesta para es .

n

$n$

i

$i$

E max_{i \leq n} H_{i}

$\mathrm{E} \max_{i\leq n} H_i$

θ (\sqrt{n})

$\theta(\sqrt{n})$

Peter Shor

+1 para la primera parte. pero honestamente no entiendo la segunda parte (¿puedes elaborar más por favor?). Sin embargo, esto no significa que no sea correcto.

AJed

Buena prueba ¿Pero estoy atrapado en cómo demostrar que es el límite inferior de ? Parece que la respuesta no menciona detalles sobre el límite inferior.

\sqrt{n}

$\sqrt{n}$

E (H_{i})

$E(H_i)$

konjac

Puede usar la distribución medio normal para probar la respuesta.

La distribución semi normal establece que si es una distribución normal con media 0 y varianza , entoncessigue una distribución media con media , y varianza . Esto da la respuesta requerida, ya que la varianza de la caminata normal es , y puede aproximar la distribución de a una distribución normal utilizando el teorema del límite central. $X$ $\sigma^2$ $|X|$ $\sigma \sqrt{\frac{2}{\pi}}$ $\sigma^2 (1-2/\pi)$ $\sigma^2$ $n$ $X$

$X$ es la suma de la caminata aleatoria como mencionó Yuval Filmus.

AJed
fuente

No prefiero esto que publiqué ... aunque da el límite inferior, no se puede decir nada sobre el límite superior. Intenté usar un argumento de distribución máxima para resolverlo, resultó ser una integración fea. Pero es bueno saber todas estas distribuciones.

AJed

En los primeros , supongamos que obtenemos colas, luego. Por lo tanto, Usa la aproximación de Stirling , sabemos que . $2i$ $k$ $H_{2i}=2|i-k|$

\begin{aligned} E (H_{2 i}) & = 2 \sum_{k = 0}^{i} (\binom{2 i}{k}) (\frac{1}{2})^{2 i} \cdot 2 (i - k) \\ = (\frac{1}{2})^{2 i - 2} [i \sum_{k = 0}^{i} (\binom{2 i}{k}) - \sum_{k = 0}^{i} k (\binom{2 i}{k})] \\ = (\frac{1}{2})^{2 i - 2} [i (2^{2 i} + (\binom{2 i}{i})) / 2 - 2 i \sum_{k = 0}^{i - 1} (\binom{2 i - 1}{k})] \\ = (\frac{1}{2})^{2 i - 2} \cdot i [2^{2 i - 1} + (\binom{2 i}{i}) / 2 - 2 \cdot 2^{2 i - 1} / 2] \\ = 2 i \cdot (\binom{2 i}{i}) / 2^{2 i} . \end{aligned}

$\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_{2 i}) = Θ (\sqrt{2 i})

$E(H_{2i})=\Theta(\sqrt{2i})$

Agua
fuente

¿No deberíamos tener en cuenta los casos en que ? parece que te pierdes un factor de multiplicación de 2, ¿verdad?

i < k \leq 2 i

$i<k\leq 2i$

omerbp