Referencia y prueba de identidad de cola binomial

Después de la multiplicación con$(1-p)^{k-n}$queremos mostrar para$p \in (0,1)$y$0 \leq k < n$

$$\begin{align*} \color{blue}{\sum_{i=0}^k\binom{n}{i}p^i(1-p)^{k-i}=\sum_{i=0}^k\binom{n-k-1+i}{i}p^i}\tag{1} \end{align*}$$

Ambos lados de (1) son polinomios en$p$de grado$k$. Mostramos la igualdad comparando coeficientes de potencias iguales de$p$. Usamos el coeficiente del operador$[p^t]$para denotar el coeficiente de$p^t$de una serie

Empezamos con el lado derecho de (1) y obtenemos para$0\leq t \leq k<n$:

$$\begin{align*} [p^t]\sum_{i=0}^k\binom{n-k-1+i}{i}p^i=\color{blue}{\binom{n-k-1+t}{t}}\tag{2} \end{align*}$$

Esta fue la parte fácil. Ahora el lado izquierdo de (1):

$$\begin{align*} [p^t]&\sum_{i=0}^k\binom{n}{i}p^i(1-p)^{k-i}\\ &=\sum_{i=0}^t\binom{n}{i}[p^{t-i}](1-p)^{k-i}\tag{2}\\ &=\sum_{i=0}^t\binom{n}{i}\binom{k-i}{t-i}(-1)^{t-i}\tag{3}\\ &=\sum_{i=0}^t\binom{n}{i}\binom{-k+t-1}{t-i}\tag{4}\\ &\,\,\color{blue}{=\binom{n-k+t-1}{t}}\tag{5} \end{align*}$$ de acuerdo con (2) y la reivindicación siguiente.

Comentario:

• En (2) aplicamos la regla$[p^{k-j}]A(p)=[p^k]p^jA(p)$. También fijamos el límite superior de la suma a$t$ya que otros índices no contribuyen a la suma.

• En (3) seleccionamos el coeficiente de$p^{t-i}$.

• En (4) usamos la identidad binomial$\binom{-n}{k}=\binom{n+k-1}{k}(-1)^k$.

• En (5) aplicamos la identidad de Chu-Vandermonde .

Encontré un argumento combinatorio también.

queremos mostrar$\Pr[\text{Binom}(n,p) \leq k] = (1-p)^{n-k} \sum_{i=0}^k {n-k-1+i \choose i} p^i$.

Imagine un proceso en el que lanzamos monedas con sesgo$p$hasta que hayamos visto$n-k$cruces, luego pare. La posibilidad de que nos detengamos en o antes del paso$n$es igual a$\Pr[\text{Binom}(n,p) \leq k]$, es decir, la probabilidad de que$n$los flips contienen al menos$n-k$cruz.

Ahora calculamos la probabilidad de una manera diferente.

La cantidad de formas en que podemos detenernos en un paso$t$, para$t \geq n-k$, es el número de formas de tener$n-k-1$cruz en la primera$t-1$voltea por supuesto el$t$El lanzamiento debe ser cruz, ya que paramos. Así que el número de formas es${t-1 \choose n-k-1} = {t-1 \choose t-n+k}$. La probabilidad de cada una de estas formas es$(1-p)^{n-k} p^{t-n+k}$. Entonces, la probabilidad total de detenerse en o antes del paso$n$es

$$\begin{align} &\sum_{t=n-k}^n {t-1 \choose t-n+k} (1-p)^{n-k} p^{t-n+k} \\ =& \sum_{i=0}^k {n-k-1+i \choose i} (1-p)^{n-k} p^i \end{align}$$ después de reparametrizar definiendo$i=t-n+k$, es decir, reemplazando cada$t$con$i+n-k$.