Aproximación de mínimos entre muchos binomios

Question

Elegimos $k$ números independientemente de la distribución binomial $B(n,1/2)$, donde podemos pensar en $n$ tan grande. ¿Cuál es la expectativa del mínimo de los números de $k$? ¿Hay una buena manera de aproximar?

(Podemos calcular la probabilidad exacta de que todos los números de $k$ están por debajo de un % constante $c$, pero que implica un montón de términos binomiales.)

Answer 1

El siguiente debe al menos en parte, la respuesta a su pregunta.

Deje $X_1,\ldots,X_k$ ser variables aleatorias i.yo.d de acuerdo a $B(n,\frac{1}{2})$. Vamos $$Y_k=min\{X_1,\ldots,X_k\}$$ El siguiente es válido:

\begin{align*} E(Y_k) &= \frac{1}{2^{nk}}\sum_{t=1}^{n}\left(\sum_{j=t}^{n}\binom{n}{j}\right)^k\tag{1}\\ \\ E(Y_k) &\sim \left(1-\frac{1}{2^n}\right)^k \qquad\qquad \text{for }k\text{ large}\tag{2}\\ \end{align*}

Que yo sepa no hay ninguna cerrado fórmula (1), pero podemos demostrar que el comportamiento asintótico de un gran $k$ está de acuerdo (2).

Paso 1:

Con el fin de mostrar (1) tomamos nota de que si $X \sim B(n,p)$ tenemos \begin{align*} P(X=j)=\binom{n}{j}\left(\frac{1}{2}\right)^j\left(\frac{1}{2}\right)^{n-j}=\binom{n}{j}\left(\frac{1}{2}\right)^{n}\tag{3} \end{align*}

A continuación podemos observar:

El mínimo de la variable aleatoria $Y_k$:

• $Y_k=0$ fib, al menos, una de las $k$ variables aleatorias $X_1,\ldots,X_k$$0$, o, equivalentemente, no todos los $X_l\geq 1 \quad (1\leq l \leq k)$.

• $Y_k=1$ fib todas las variables aleatorias $X_l \geq 1 $ y no todos los $X_l \geq 2$.

Procediendo de esta manera, obtenemos:

\begin{align*} P(Y_k=0)&=1-P(Y_k\geq 1) = 1-P(X_1\geq 1)^k\\ P(Y_k=1)&=P(X_1\geq 1)^k-P(X_1\geq 2)^k\\ P(Y_k=2)&=P(X_1\geq 2)^k-P(X_1\geq 3)^k\\ &\ldots\\ P(Y_k=n)&=P(X_1\geq n)^k \end{align*}

A partir de estas ecuaciones se puede deducir la expectativa $E(Y_k)$:

\begin{align*} E(Y_k)&=\sum_{t=0}^ntP(Y_k=t)\\ &=\sum_{t=1}^{n-1}t\left(P(X_1\geq t)^k-P(X_1\geq t+1)^k\right)+nP(X_1\geq n)^k\\ &=\sum_{t=1}^{n}tP(X_1\geq t)^k-\sum_{t=1}^{n-1}tP(X_1\geq t+1)^k\\ &=\sum_{t=1}^{n}tP(X_1\geq t)^k-\sum_{t=2}^{n}(t-1)P(X_1\geq t)^k\\ &=\sum_{t=1}^{n}P(X_1\geq t)^k\tag{4}\\ &=\sum_{t=1}^n\left(\sum_{j=t}^{n}\frac{1}{2^n}\binom{n}{j}\right)^k\\ &=\frac{1}{2^{nk}}\sum_{t=1}^n\left(\sum_{j=t}^{n}\binom{n}{j}\right)^k \end{align*}

lo que muestra (1).

Paso 2:

Con el fin de mostrar el comportamiento asintótico de $Y_k$ grandes $k$, en primer lugar tenga en cuenta que para $j\geq 2$:

$$0\leq P(X_1\geq j) \leq P(X_i\geq 2)$$

También vemos que de acuerdo a (3):

\begin{align*} P(X_1 \geq t)&=\frac{1}{2^n}\sum_{j=t}^{n}\binom{n}{j}\\ P(X_1\geq 1)&=\frac{1}{2^n}\left(2^n-1\right)=1-\frac{1}{2^n}\\ P(X_1\geq 2)&=\frac{1}{2^n}\left(2^n-1-n\right)=1-\frac{1}{2^n}-\frac{n}{2^n}\tag{5}\\ &=\left(1-\frac{1}{2^n}\right)\left(1-\frac{n}{2^n-1}\right)\\ \end{align*}

Por lo tanto, tenemos según (4) y (5)

\begin{align*} P(X_1\geq 1)^k\leq &\sum_{t=1}^{n}P(X_1\geq t)^k\leq P(X_1\geq 1)^k+(n-1)P(X_1 \geq 2)^k\\ \end{align*}

que puede ser escrito como

\begin{align*} \left(1-\frac{1}{2^n}\right)^k\leq E(Y_k)&\leq\left(1-\frac{1}{2^n}\right)^k+(n-1)\left(1-\frac{1}{2^n}\right)\left(1-\frac{n}{2^n-1}\right)^k\\ &\leq\left(1-\frac{1}{2^n}\right)^k\left(1+(n-1)\left(1-\frac{n}{2^n-1}\right)^k\right)\\ \end{align*}

Sigue

\begin{align*} 1\leq \frac{E(Y_k)}{\left(1-\frac{1}{2^n}\right)^k}\leq1+(n-1)\left(1-\frac{n}{2^n-1}\right)^k\\ \end{align*}

Llegamos a la conclusión de

\begin{align*} \lim_{k\rightarrow\infty}\frac{E(Y_k)}{\left(1-\frac{1}{2^n}\right)^k}=1 \end{align*} y (2) de la siguiente manera.

---

Nota:

• (1) es sólo una adaptación de la respuesta de @AndréNicolas a esta pregunta y

• La esencia de (2) viene de @Hicieron que respondieron a esta pregunta

Answer 2

Sólo una sugerencia:

Deje $X\sim B(n,1/2)$.

• Definir $Y=-X$.
• Escribir la cdf de $Y$. En este punto de la aproximación normal puede ser utilizado.
• Aplicar el método descrito aquí para el máximo de $k$ random ensayos de $Y$ para obtener el correspondiente cdf.
• Diferenciar el cdf para obtener pdf de máximo de $k$ ensayos de $Y$.
• Transformar este pdf a pdf de mínimo de $k$ ensayos de $X$.
• Calcular el expectated valor.