Problema de límite con los coeficientes binomiales

Question

Pensé que el siguiente que haría un buen ejercicio, pero no estoy seguro de cómo evaluar su dificultad ya que me suelen faltar a la escuela primaria de soluciones. Cómo sobre usted responder? Sería genial tener varias pruebas.

Deje $m$ ser un entero positivo y $p \in (0,1)$. Demostrar que $\displaystyle \lim_{n\to\infty}\underset{m\mediados de k}{\sum_{0 \leq k \leq n}} \binom{n}{k}p^{k}(1-p)^{n-k} = \frac{1}{m}$.

Doy dos pruebas de este límite por debajo, pero todavía estoy interesado en la escuela primaria de las pruebas.

---

Edición 1. Como se nota por @rlgordonma, la suma es $\lim_{n \rightarrow \infty} \sum_{\ell = 0}^{\lfloor \frac{n}{m} \rfloor} \binom{n}{\ell m} p^{\ell m} (1-p)^{n - \ell m} = \frac{1}{m}$. Tal vez lo que hace las cosas más claras, como que.

---

Edit2. Gracias por su participación. Ahora voy a dar dos pruebas de este límite (uno de ellos siendo una reformulación de vonbrand de la solución). De hecho, voy a probar un poco más:

$$\forall r \in \{0,\dots,m-1\},\qquad\lim_{n\to\infty} \sum_{\substack{0 \leq k \leq n\\ k \equiv r\; [m]}} \binom{n}{k}p^k(1-p)^k = \frac{1}{m}$$

Paso 1 (probabilística de la interpretación).

Este paso no es necesario, pero creo que trae una mejor visión. Deje $X_1,X_2,\dots$ ser una secuencia de variables aleatorias de Bernoulli independientes con el parámetro $0 < p <1$$P(X_i=1)=1-P(X_i=0)=p$.

A continuación, $S_n = X_1 + \dots+ X_n$ es una variable aleatoria Binomial con parámetros de $(n,p)$, y la suma que nos interesa es simplemente: $$\sum_{\substack{0 \leq k \leq n\\ k \equiv r\; [m]}} \binom{n}{k}p^k(1-p)^k = P(S_n \equiv r\;[m]).$$ La secuencia de $(S_n)$ es una caminata aleatoria sobre$\mathbb{Z}$, pero dado que sólo estamos interesados en sus residuos modulo $m$ será mejor que lo vea como una caminata aleatoria sobre $\mathbb{Z}/m\mathbb{Z}$ (con un abuso de notación, vamos a escribir $S_n$ de este residuo).

Paso 2 (límite de comportamiento de la caminata al azar). Versión rápida, con Cadenas de Markov

El paseo aleatorio $(S_n)$ es una irreductible (y aperiódica) de la Cadena de Markov sobre el estado finito espacio de $\mathbb{Z}/m\mathbb{Z}$ con la matriz de transición dada por $Q(i,i)=1-p$$Q(i,i+1)=p$$i \in \mathbb{Z}/m\mathbb{Z}$. Se admite que la distribución uniforme como un stationnary de distribución, por lo tanto converge a esta distribución. QED

Paso 2 (bis). Sin Las Cadenas De Markov

El siguiente resultado (la inversión de la fórmula de la transformada de Fourier discreta) es una generalización de @vonbrand del truco:

Nota:$S = \{0,\dots,m-1\}$$\omega=\exp\left(i2\pi/m\right)$. Para cada función de $f \colon S\to \mathbb{C}$ y cada una de las $x \in S$, $$ f(x) = \sum_{k = 0}^{m-1} \widehat{f}(k)\,\omega^{kx},\qquad\text{donde}\quad \widehat{f}(k) = \frac{1}{m}\sum_{x=0}^{m-1}f(x)\omega^{-kx}. $$

En particular, hemos $$ E(f(S_n)) = \sum_{k=0}^{m-1}\widehat{f}(k)\,E\left[\omega^{k S_n}\right] $$ La secuencia de $X_1,X_2,\dots$ siendo yo.yo.d., $$ E\left[\omega^{k S_n}\right] = \left(E\left[\omega^{k X_1}\right] \right)^n = ((1-p)+p\omega^k)^n \xrightarrow[n\to\infty]{}\begin{cases}1 & \text{if } k=0\\0 & \text{else}\end{casos} $$ Por lo tanto, $\lim_{n\to\infty} E[f(S_n)] = \widehat{f}(0)$. Tomando $f(x) = 1_{\{x = r\}}$ se obtiene el resultado.

Answer 1

Hay un buen truco para seleccionar sólo los términos divisible por $m$ en una serie. Deje $A(z) = \sum_{k} a_n z^n$. A partir de ahora $\omega$ como un primitivo $m$-ésima raíz de 1, es decir, $\omega = \exp(2 \pi i / m)$. Es fácil comprobar que $1 + \omega + \omega^2 + \ldots + \omega^{m - 1} = 0$ también $\omega^m = 1$. A partir de ahora: $$ A(z) + A(\omega z) + \ldots + A(\omega^{m - 1} z) = \sum_{n \ge 0} a_n z^n (1 + \omega^n + \omega^{2 n} + \ldots + \omega^{(m - 1) n}) $$ Pero por lo anterior, si $m \mid n$, la suma en parentesis es $m$, de lo contrario es 0, y sólo aquellos términos sobrevivir.

Aplicando esto al caso concreto (no hay problemas de convergencia, la suma parece infinito, pero es muy finito): $$ S(z) = \sum_{k \ge 0} \binom{n}{k} p^k (1 - p)^{n - k} z^k = (1 - p (z - 1))^n $$ La suma original es simplemente: $$ S_{n,m} = \sum_{\substack{k \ge 0\\m \mediados n}} \binom{n}{k} p^k (1 -p)^{n - k} = \frac{1}{m} \sum_{0 \le k < m} \left(1 + p (\omega^k - 1) \right)^n $$ Parece plausible que la última suma es 1 solo, pero estoy perplejo aquí.

Edit: Gracias al comentario de @Ju, vi la luz: Al $k = 0$, el plazo se acaba de $1^n = 1$. De lo contrario, por la desigualdad de triángulo, tenemos: $$ \lvert 1 + p (\omega^k - 1) \rvert = \lvert (1 - p) + p \omega^k \rvert < (1 - p) + p = 1 $$ La desigualdad es estricta, debido a que $\omega^k$ no está en la dirección 1. Entonces: $$ \lim_{n \rightarrow \infty} \sum_{0 \le k < m} (1 + p (\omega^k - 1))^n = 1 + \lim_{n \rightarrow \infty} \sum_{1 < k < m}(1 + p \omega^k - 1))^n = 1 $$ Edit: Para seleccionar los términos $n \equiv r \mod{m}$ hacer como en el anterior, pero vaya: $$ A(z \omega^{m - r}) + A(z \omega^{m - r + 1}) + \ldots + (z^{i - 1}) $$ El resto de la prueba pasa a través justo como antes.

Answer 2

Os presento una heurística de justificación de ahora, voy a trabajar los detalles más tarde, siento que esto puede ser funcionado exactamente como en la prueba de DeMoivre-Laplace teorema que pasa a través de casi idénticos pasos.

El resultado requerido debe seguir a partir de la aproximación normal a la binomial función de masa de probabilidad.

Los siguientes locales "aproximación" es para una "suficientemente grandes" de la gama de $k$ $$\binom{n}{k}p^{k}q^{n-k} \approx \dfrac{1}{\sqrt{2\pi npq}} \exp\left(- \frac{1}{2}\left(\dfrac{k -np}{\sqrt{n pq}}\right)^2 \right),$$ donde por un grupo lo suficientemente grande grande de la gama, quiero decir, la suma de los términos fuera de este rango se desvanece en el límite, y la discrepancia debido a la aproximación también se desvanece.

Así que nuestra suma deseada se puede aproximar como, $$ \sum_{ k } \binom{n}{mk}p^{mk}q^{n-mk} \approx \sum_{k} \dfrac{1}{\sqrt{2\pi npq}} \exp\left( - \frac{1}{2}\left(\dfrac{mk -np}{\sqrt{n pq}}\right)^2 \right).$$

Deje $$ x_k = \dfrac{mk -np}{\sqrt{n pq} }, $$ a continuación, $$ \dfrac{ x_k - x_{k-1} } {m} = \dfrac{1}{\sqrt{ npq}}.$$

La aproximación se convierte en una suma de Riemann, $$ \frac{1}{m} \sum_{k} \frac{(x_k - x_{k-1})}{\sqrt{2\pi}} \exp \left( -\frac{x_k^2}{2} \right) \to \frac{1}{m}\int_{-\infty}^{\infty} \frac{1}{\sqrt{2\pi}}\exp \left(-\frac{x^2}{2}\right) dx = \frac{1}{m}.$$

Answer 3

Continuando vonbrand del multihilo enfoque, queremos mostrar que $T=\sum_{0 \le k < m} (1 + p (w^k - 1) )^n =1$, donde $w$ $n$- ésima raíz de la unidad.

Resumen de lo que sigue: Puedo obtener una suma de $T$ que no parece ser siempre 1. Sin embargo, estoy entrando en este caso es (1) he hecho un error que se puede arreglar o (2) mi resultado es correcto y el límite de mi resultado enfoques 1 para un gran $n$.

Deje $q = 1-p$ y $C(n, j) = n!/(j! (n-j)!)$. Entonces

$\begin{align} T &= \sum_{0 \le k < m} (1 + p (w^k - 1) )^n \\ & = \sum_{0 \le k < m} (1-p + p w^k )^n \\ & = \sum_{0 \le k < m} (q + p w^k )^n \\ & = \sum_{0 \le k < m} \sum_{0 \le j < n}C(n, j) q^{n-j} p^j w^{kj} \\ & = \sum_{0 \le j < n} \sum_{0 \le k < m}C(n, j) q^{n-j} p^j w^{kj} \\ & = \sum_{0 \le j < n} C(n, j) q^{n-j} p^j\sum_{0 \le k < m} w^{kj} \\ \end{align} $

La más interna suma de una serie geométrica: $\sum_{0 \le k < m} w^{kj} = \frac{w^{j m}-1}{w^j-1} $ when $w^j \ne 1$ and $m$ al $w^j = 1$.

$w^j = 1$ sólo al $j = 0$, así

$\begin{align} T &= m q^n + \sum_{0 < j < n} C(n, j) q^{n-j} p^j \frac{w^{j m}-1}{w^j-1}\\ \end{align} $.

(Me estoy agitando ahora, así que busque en casos especiales)

Si $m = 1$, $T = 1$ por el teorema del binomio.

Si $m = 2$,

$\begin{align} T &= 2 q^n + \sum_{0 < j < n} C(n, j) q^{n-j} p^j \frac{w^{2j}-1}{w^j-1}\\ &= 2 q^n + \sum_{0 < j < n} C(n, j) q^{n-j} p^j (w^j+1)\\ &= 2q^n + \sum_{0 < j < n} C(n, j) q^{n-j} p^j+ \sum_{0 < j < n} C(n, j) q^{n-j} p^j w^j\\ &= \sum_{0 \le j < n} C(n, j) q^{n-j} p^j+ \sum_{0 \le j < n} C(n, j) q^{n-j} p^j w^j\\ &= (p+q)^n + (q+p w)^n \\ &= 1 + (q+p w)^n \\ \end{align} $.

Para $n=2$ (donde $w = -1$ - me dijo originalmente que $w = i$, mi error),

$T = 1 + (q-p )^2 = 1 + (1-2p )^2 $,

y esto es $not\ 1$ a menos $p = 1/2$ (a menos que haya cometido un error, que creo que es muy probable).