Borracho pie en el $n^{th}$ raíces de la unidad.

Question

Fijar un entero $n\geq 2$. Supongamos que comenzamos en el origen en el plano complejo, y en cada paso que elegir una $n^{th}$ de la raíz de la unidad al azar, y ir $1$ unidad de distancia en esa dirección. Deje de $X_N$ ser la distancia desde el origen después de la $N^{th}$ paso. Cómo estamos obligados a $E(X_N)$ de arriba?

En mi intento de calcular esto, he encontrado el límite de $\sqrt{N}$, pero tengo la sensación de que esto podría ser incorrecto, porque el problema que le estoy aplicando esto a su lugar ha $\sqrt{N\log N}$. (Este razonamiento se basa en la creencia de que es probable que el problema óptima) Lo que hice fue aplicar Cauchy Schwarz para obtener una suma con la norma al cuadrado, y luego tratar de hacer algún tipo de manipulación a partir de ahí, confiando en el hecho de que la suma de los vectores (no a distancia) es cero por la simetría.

Answer 1

Tengo la misma $\sqrt{N}$ enlazado.

Deje que el $k$-ésimo paso a ser de $z_k$ ( $$n-ésima raíz de la unidad), por lo que la posición en vez de $N$ es $z_1 + \cdots + z_N$. El cuadrado de la distancia desde el origen en el tiempo $N$ es$$ X_N^2 = \left( \sum_{k=1}^{N} \overline{z_k} \right) \cdot \left( \sum_{j=1}^{N} z_j \right) = \sum_{k=1}^{N} | z_{k} |^2 + \sum_{k \ne j} \overline{z_k} \cdot z_j = N + \sum_{k \ne j} \overline{z_k} \cdot z_j. $$Ya que cada sumando $\overline {z_k} \cdot z_j$ ($k \ne j$) se desvanece en la espera, tenemos $\mathbf E[X_N^2] = $ N. Finalmente$$ \mathbf EX_N \leqslant \sqrt{ \mathbf E[X_N^2] } = \sqrt{N} .$$

Esta se asienta que $\mathbf EX_N$ es asintóticamente $O(\sqrt{N})$, pero el resultado de la constante es más probable que no apretado desde la aproximación en el paso final es bastante crudo (para cualquier finito $n$).

Answer 2

Srivatsan ha dado una excelente respuesta, con un simple, elegante y análisis. Con un poco más de trabajo, podemos afinar el resultado.

Reclamo: Por $n \geq 3$, $\mathbb E X_N \sim \sqrt{\frac{\pi}{4} N}$ .

Podemos analizar esto por medio del teorema del límite central y la asignación continua teorema. A continuación es sólo un boceto. Hemos restringido a nosotros mismos para el caso $n \geq 3$ desde el caso $n = 2$ corresponde a la norma aleatorio simple paseo, que tiene comportamiento ligeramente diferente (cf. Henning del comentario). Intuitivamente, ya que por $n \geq 3$, el paseo aleatorio puede moverse en una dimensión extra, debemos anticipar que su norma esperada podría crecer un poco más rápido.

Prueba (boceto):

Deje de $Z_i = (R_i,I_i)$, $i=1,2,\ldots$, ser un iid (uniforme) de la muestra de las raíces de la unidad donde $R_i$ indica el "real" y el componente de $I_i$ el "imaginario" de los componentes de la $i$ésimo elemento de la muestra. Entonces, es un ejercicio sencillo comprobar que $\mathbb E R_i = \mathbb E I_i = 0$, y, también, de $\mathbb E R_i I_i = 0$. Además, $$\mathrm{Var}(R_i) = \mathrm{Var}(I_i) = 1/2 \>,$$ independientemente de $n$, usando simples propiedades de las raíces de la unidad.

Por lo tanto, por el multivariante teorema central del límite, tenemos que $$\sqrt{2N} (\bar{R}_N, \bar{I}_N) \xrightarrow{d} \,\mathcal \,N(0,\mathbf I_2 ) \> ,$$ donde $\bar{R}_N = N^{-1} \sum_{i=1}^N R_i$ e igualmente para $\bar{I}_N$. Aquí $\mathbf I_2$ indica $2 \times 2$ matriz de identidad.

Una aplicación de la asignación continua teorema usando $g(x,y) = x^2 + y^2$ rendimientos $$2 N (\bar{R}_N^2 + \bar{I}_N^2) = \frac{2}{N} X_N^2 = g( \sqrt{2N} \bar{R}_N, \sqrt{2N} \bar{I}_N ) \,\xrightarrow{d}\, \chi_2^2 \> .$$

Es decir, el reescalado el cuadrado de la norma tiene un límite de distribución que es el chi-cuadrado con dos grados de libertad.

La raíz cuadrada de un $\chi_2^2$ de distribución se conoce como una distribución de Rayleigh y tiene una media de $\sqrt{\pi/2}$.

Por lo tanto, una segunda aplicación de la asignación continua teorema, $\sqrt{\frac{2}{N}} X_N$ converge a una distribución de Rayleigh.

Esto sugiere (pero no demostrar) que $\mathbb E X_N \sim \sqrt{\frac{\pi}{4} N}$.

Para finalizar la prueba, tenga en cuenta que $\mathbb E \frac{2}{N} X_N^2 = 2$ para todo $N$. Por un estándar teorema de la teoría de la probabilidad, existe una secuencia de variables aleatorias $\{Y_N\}$ tal que $Y_N \stackrel{d}= \sqrt{\frac{2}{N}} X_N$ y $Y_N$ converge a $Y_\infty$, casi con toda seguridad, donde $Y_\infty$ es un estándar de Rayleigh. Por la uniformidad del segundo momento anterior, sabemos que el conjunto $\{Y_N\}$ es uniformemente integrable y por lo que $L_1$ convergente. Así, $$\mathbb |\mathbb E Y_N - \mathbb E Y_\infty| \leq \mathbb E |Y_N - Y_\infty| \0 \> .$$

Por lo tanto $\mathbb E Y_N = \mathbb E X_N \sim \sqrt{\frac{\pi}{4} N}$ como se desee.