¿Por qué suma mod k de distribuciones uniformes converge a uniforme?

Denotemos la transformada de Fourier de$X_1$por

$$\varphi(j) = \mathbb{E}[\exp\{2\pi i j X_1 / k\}],$$

y consideración$\varphi$como una función en$\mathbb{Z}/k\mathbb{Z}$. Dado que los puntos en$\partial\mathbb{D}$son puntos extremos del conjunto convexo$\overline{\mathbb{D}}$, lo sabemos$|\varphi(j)| = 1$si y solo si$\exp\{2\pi i j X_1 /k\}$es constante como Esto equivale a decir que

$$x \equiv x' \pmod{k/\gcd(k,j)}$$

cuando sea$x$y$x'$mentir en el apoyo de$X_1$. Ahora, bajo la suposición del OP, esto puede ocurrir solo para$j = 0$. Como consecuencia,$|\varphi(j)| < 1$para$j \neq 0$y por lo tanto

$$\mathbb{E}[\exp\{2\pi i j Y_n / k\}] = \varphi(j)^n \to \mathbb{1}_{\{j = 0\}}.$$

Desde$\mathbb{1}_{\{j = 0\}}$es la transformada de Fourier de la distribución uniforme sobre$\mathbb{Z}/k\mathbb{Z}$, resulta que$Y_n$converge en distribución a la distribución uniforme sobre$\mathbb{Z}/k\mathbb{Z}$.

Si$(X_n:n\in\mathbb{N})$es una secuencia iid de variables aleatorias admitidas en$\{0,\ldots,k-1\}$. Si$S_{k, n}=\sum^n_{j=1}X_j\mod k$, entonces$\frac{1}{k}S_{k, n}\mod 1$se apoya en$\{j/k: 0\leq j< k-1\}$. Por lo tanto, es suficiente considerar medidas discretas con apoyo fino sobre el círculo$\mathbb{S}^1=\mathbb{R}/{2\pi \mathbb{Z}}$.

La transformada de Fourier de la distribución uniforme$\mu(j/k)=\frac{1}{k}$para$0\leq j<k$es

$$\hat{\mu}(m)=\sum^{k-1}_{j=0}\frac{1}{k}e^{-2\pi imj/k}=\frac{1-e^{-2\pi m}}{1-e^{-2\pi im/k}}=\mathbb{1}_{k\mathbb{Z}}(m)$$

Dejar$\{X_n\}$ser una secuencia iid soportada en$\{0,1/k,\ldots,(k-1)/k\}$con distribución$\nu$tal que hay$j_1<j_2$con$g.c.d(j_2-j_1,k)=1$tal que$\nu(j_1/k)\nu(j_2/k)>0$. Dejar$S_n=\sum^n_{j=1}X_j$

$$\hat{\nu}_{S_n}(m)=\big(\hat{\nu}(m)\big)^n=\Big(\int e^{-2\pi imx}\,\nu(dx)\Big)^n=\Big(\sum^{k-1}_{j=1}\nu(j/k)e^{-2\pi ijm/k}\Big)^n$$ Note que si$m\in k\mathbb{Z}$,$\hat{\nu}(m)=1$. Por el contrario, supongamos$m$es tal que$|\hat{\nu}(m)|=\Big|\int^1_0 e^{-2\pi i xm}\,\nu(dx)\Big|=1$, y deja$\theta_m\in(0,1)$tal que tal que$e^{2\pi i\theta}\hat{\nu}(m)=1$. Entonces $$1=e^{2\pi i\theta}\int^1_0e^{-2\pi mx}\,\nu(dx)=\int^1_0\cos(2\pi(mx-\theta))\,\nu(dx)$$ esto significa que$2\pi(mx-\theta)\in 2\pi\mathbb{Z}$, es decir$\operatorname{supp}(\nu)\subset\frac{\theta}{m}+\frac{1}{m}\mathbb{Z}$. Desde$\operatorname{supp}(\nu)\subset\{j/k: 0\leq j<k\}$se sigue que para dos puntos cualesquiera$\frac{j_1}{k},\frac{j_2}{k}$en$\operatorname{supp}(\nu)$,$j_1<j_2$, hay un entero$p$tal que $$j_2-j_1=\frac{kp}{m}<k$$ Por supuesto, hay un par$j_1/k$y$j_2/k$en$\operatorname{supp}(\nu)$con$0\leq j_1<j_2<k$tal que $$1=\ell_1(j_2-j_1)+\ell_2 k$$ para algunos$\ell_1, \ell_2\in\mathbb{Z}$. Por eso $$m=\ell_1m(j_2-j_2)+\ell_2mk=k(\ell_1p+m\ell_2),$$ eso es,$m=p'k$para algunos$p'\in\mathbb{N}$. Esto muestra que$\hat{\nu}(m)<1$a menos que$m\in k\mathbb{Z}$. Como consecuencia $$\lim_n\hat{\nu}_{S_n}(m)=\lim_n\big(\hat{\nu}(m)\big)^n=\mathbb{1}_{k\mathbb{Z}}(m)$$ Esto significa que$\nu_{S_n}$converge débilmente a la distribución uniforme sobre$\{0,\ldots,k-1\}$.

Comencemos con el caso más fácil, donde$P(X_i = 0) = P(X_i = 1) = 1/2.$Definir$Z_j = \sum_{i=1}^k X_i$. En este caso$Z_j$se distribuye binomialmente con$j$Pruebas y probabilidad de éxito.$1/2$. Supongamos por simplicidad que$k$divide$j+1$. Por lo tanto, para todos$0\leq a<k$

$$P(Y_j=a) = \sum_{i=0}^{ j/k} P(Z_j = ki + a) = 2^{-j} \sum_{i=0}^{ j/k} \binom{j}{ki+a}.$$ Ahora, usando $$\sum_{i=0}^{j/k} \binom{j}{ki+a}= \frac{1}{k}\sum_{i=0}^{k-1}\omega^{-i\,a} \big(1+\omega^i\big)^{j},$$ dónde$\omega$es el$k$-ésima raíz (compleja) de la unidad (esto se demuestra por ejemplo en suma lacunaria de coeficientes binomiales ), obtenemos $$P(Y_j=a) = \sum_{i=0}^{ j/k} P(Z_j = ki + a) = \frac{1}{k}\sum_{i=0}^{k-1}\omega^{-i\,a} \frac{\big(1+\omega^i\big)^{j}}{2^j}.$$ En esta última suma, todos los términos con$i\neq0$convergen a cero (ya que la base en el numerador tiene un valor absoluto estrictamente menor que 2) y por lo tanto $$P(Y_j=a) \to\frac{1}{k},$$ para$j\to\infty$como se desee.

Sin embargo, no estoy seguro de que un argumento combinatorio de este tipo pueda extenderse fácilmente a subconjuntos arbitrarios. Creo que el CLT podría ser útil, pero no sé cómo aplicarlo exactamente.

Con respecto a su pregunta sobre el significado de la convergencia de variables aleatorias, hay varias definiciones que se presentan, por ejemplo, en https://en.wikipedia.org/wiki/Convergence_of_random_variables . En su caso, hablamos de convergencia en la distribución, es decir, las masas de probabilidad convergen a$P(Y_j=a) \to 1/k$para todos$0\leq a<k$, cuando$j \to \infty$. Hay formas más fuertes de convergencia, que deberían probarse por separado.

Dejar$X_n$ser independientes e idénticamente distribuidos con apoyo en un subconjunto de$\{0, \ldots, k-1\}$para algunos$k$, con$d_1, d_2$dado tal que$gcd(d_2 - d_1, k) = 1$y$P(X_i = d_1) P(X_i = d_2) > 0$.

Entonces existen números enteros$s, t$tal que

$$\begin{eqnarray} s(d_2 - d_1) + tk & = & 1 \\ & = & 1 + k(d_2 - d_1) - k(d_2 - d_1) \\ & = & (s+k)(d_2 - d_1) + (t - d_2 + d_1)k \end{eqnarray}$$ Elija un positivo tal$s$, por ejemplo, mínimo. Después$s$transiciones, si todas las transiciones son$d_1$entonces un módulo particular$m$es alcanzado; si todas las transiciones son$d_2$entonces$m + 1$es alcanzado. Así, después$sk$transiciones cada módulo es alcanzable: puede alcanzar$km + \sum_{i=1}^k (0\textrm{ or }1)$.

Dejar$Y_n = (\sum_{i=1}^n X_i)\ \textrm{mod}\ k$. Entonces el$Y_n$formar una cadena de Markov (gracias a iid). Dejar$\mathbf{P}$sea ​​su matriz de transición. Dado que se puede acceder a cada estado desde cualquier otro estado después de algunos$m = sk$transiciones, la cadena es regular (en la terminología de Snell y Grinstead, ver http://pi.math.cornell.edu/~web3040/amsbook.mac-probability.pdf ).

Como la cadena es regular,$\mathbf{P}^n$converge a una matriz$\mathbf{W}$como$n \rightarrow \infty$donde todas las filas equivalen a algún vector de probabilidad$\mathbf{w}$(un vector$\mathbf{v}$es un vector de probabilidad si cada entrada está en$[0, 1]$y la suma de las entradas es 1). Además, si$\mathbf{v} = \mathbf{vP}$entonces$\mathbf{v}$es múltiplo de$\mathbf{w}$(ver Snell y Grinstead).

Dejar$\mathbf{1}_n$sea ​​el vector fila con$n$todas las entradas son 1. Entonces

$$(\mathbf{1}_k \mathbf{P})_{1,c} = \sum_{d=1}^k p_{c-d, c} = \sum_{d=0}^{k-1} P(X_* = d) = 1$$ y por lo tanto$\mathbf{w} = [\frac{1}{k} \cdots \frac{1}{k}]$, es decir$P(Y_n = i) \rightarrow 1/k$como$n \rightarrow \infty$para$i \in \{0, \ldots, k-1\}$. QED.

Algunas generalizaciones: una cadena de Markov con matriz$\mathbf{Q}$es reversible si cada fila de$\mathbf{Q}^{T}$es un vector de probabilidad. Cada cadena de Markov reversible tiene una distribución uniforme sobre estados como su estado estacionario, es decir$(\mathbf{Q}^n)_{i,j} \rightarrow \frac{1}{k}$como$n \rightarrow \infty$dónde$k$es el número de estados.

Dejar$f_1, \ldots, f_n$ser permutaciones de un conjunto finito de estados$S$tal que

$$\forall (i, j, s): i \not= j \Rightarrow f_i(s) \not= f_j(s)$$

Si cada transición elige aleatoriamente un$f_i$según cualquier distribución y mapas de cada estado$s$a$f_i(s)$, entonces la cadena de Markov será reversible. Si el conjunto de estados es un grupo y cada uno$f_{g_i}(g_j) = g_i \ast g_j$entonces el$f_{g_i}$formar una familia así. módulo de adición$k$es un grupo

Para cualquier familia así$f_{g_1}, \ldots, f_{g_n}$sobre un grupo cíclico abeliano, si$g_i \ast (g_j^{-1})$es un generador del grupo para algunos$i$y$j$, la cadena de Markov será regular (y por lo tanto convergente). si tenemos$gcd(d_2 - d_1, k) = 1$entonces$d_2 - d_1$es un generador de este tipo.

Además, si existe$g_{i_1} \ast \cdots \ast g_{i_a} = e = g_{j_1} \ast \cdots \ast g_{j_b}$con$0 < a < b$y$gcd(a, b) = 1$, y$\{g_1, \ldots, g_n\}$es un generador del grupo, entonces la cadena de Markov es regular: tomar el$|G|$productos que generan cada elemento y los rellenan con$e$-productos valorados de longitud$a$o$b$hasta que todas las secuencias generadoras tengan la misma longitud. Ahora se puede llegar a todos los elementos desde$e$en un número fijo de pasos; pero luego se puede llegar a cada elemento desde cualquier otro elemento en un número fijo de pasos. Esto supone que todos los elementos involucrados se eligen con probabilidad positiva.