Supongamos que la tierra ha sido atacada por naves espaciales marcianas de la $n$ y Supongamos que tenemos $m=k \cdot n$ misiles para lanzar contra el $n$ naves espaciales. La probabilidad de golpear y destruir cada nave espacial por cada misil es $p$ (independiente del resto).
¿Cuál es la probabilidad de destruir todas las naves espaciales Si liberamos todos los misiles al mismo tiempo pero cada misil escogerá al azar una nave espacial?
Un modelo equivalente de este proceso es el primero en poner el $n$ naves espaciales en una botella. Establecer el recuento de los barcos destruidos a cero. Enumerar los misiles $1, 2, \ldots, m$. Para determinar que la nave es atacada por misiles $i$, agite bien el frasco y saca al azar un barco en la botella. Con una probabilidad de $p$, lo marca como destruido; de lo contrario, no cambie ninguna de sus marcas. Si originalmente estaba intacta y ahora ha sido marcada como destruido, incrementar el recuento de los barcos destruidos. El retorno de este barco a la botella y repetir.
Esto describe una Cadena de Markov en la cuenta $0, 1, \ldots, n$ que se ejecutará a través de $m$ iteraciones. Después de $i$ barcos han sido destruidos, la posibilidad de que otro será destruido (haciendo una transición de estado $i$ estado $i+1$) será la probabilidad de selección de una indestructible de la nave (de los cuales hay $n-i$) veces la posibilidad de destruir ese barco (que es $p$). Es decir,
$$\Pr(i\to i+1) = \frac{n-i}{n} p.$$
De lo contrario, la cadena se queda en el estado $i$. El estado inicial es $i=0$. Centros de interés en la probabilidad de estar en estado de $n$ después $m$ iteraciones.
La matriz de transición $\mathbb{P}$ de estas probabilidades, donde $\mathbb{P}_{ij}$ es la probabilidad de hacer la transición de $i$$j$, fácilmente diagonalizes:
$$\eqalign{ \mathbb{P} & = \pmatrix{1-p & p & 0 & \cdots & 0 & 0 \\ 0 & 1-\frac{n-1}{n}p & \frac{n-1}{n}p & \cdots & 0 & 0 \\ 0 & 0 & 1 - \frac{n-2}{n}p & \frac{n-2}{n}p & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 0 & 1 - \frac{1}{n}p & \frac{1}{n}p \\ 0 & 0 & \cdots & 0 & 0 & 1} \\ &=\mathbb{V} \pmatrix{1 & 0 & 0 & \cdots & 0 & 0 \\ 0 & \frac{n-p}{n} & 0 & \cdots & 0 & 0 \\ 0 & 0 & \frac{n-2}{n} & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 0 & \frac{n - (n-1)p}{n} & 0 \\ 0 & 0 & \cdots & 0 & 0 & \frac{n - np}{n}} \mathbb{V}^{-1} }$$
donde
$$\mathbb{V} = \pmatrix{\binom{n}{0} & \binom{n}{1} & \binom{n}{2} & \cdots & \binom{n}{n-1} & \binom{n}{n} \\ \binom{n-1}{0} & \binom{n-1}{1} & \binom{n-1}{2} & \cdots & \binom{n-1}{n-1} & 0 \\ \vdots & \vdots & \ddots & \ddots & \vdots & \vdots \\ \binom{1}{0} & \binom{1}{1} & 0 & \cdots & 0 & 0 \\ \binom{0}{0} & 0 & 0 & \cdots & 0 & 0} $$
es el Triángulo de Pascal. La inversa es fácil de encontrar para ser
$$\mathbb{V}^{-1} = \pmatrix{0 & 0 & \cdots & 0 & 0 & \binom{0}{0} \\ 0 & 0 & \cdots & 0 & \binom{1}{1} & -\binom{1}{0} \\ 0 & 0 & \cdots & \binom{2}{2} & -\binom{2}{1} & \binom{2}{0} \\ \vdots & \vdots & \ddots & \ddots & \vdots & \vdots \\ 0 & \binom{n-1}{n-1} & \cdots & (-1)^{n-1+2}\binom{n-1}{2} & (-1)^{n-1+1}\binom{n-1}{2} & (-1)^{n-1+0}\binom{n-1}{0} \\ \binom{n}{0} & -\binom{n}{1} & \cdots & (-1)^{n+2}\binom{n}{2} & (-1)^{n+1}\binom{n}{2} & (-1)^{n+0}\binom{n}{0} }$$
Deje que la central (en diagonal) de la matriz escribirse $\Lambda$, por lo que el $$\Lambda_{jj} = \frac{n-jp}{n}.$$
La matriz de $m$ iteraciones es
$$\mathbb{P}^m = \left(\mathbb{V \Lambda V^{-1}}\right)^m = \mathbb{V} \Lambda^m \mathbb{V}^{-1}\tag{*}$$
y, obviamente,
$$(\Lambda^m)_{jj} = \Lambda_{jj}^m = \left(\frac{n-jp}{n}\right)^m.$$
Haciendo la multiplicación en $*$ encontramos
$$\left(\mathbb{P}^m\right)_{0n} = \sum_{j=0}^{\min(m,n)} (-1)^j \binom{n}{j} \left(\frac{n-jp}{n}\right)^m.\tag{**}$$
Esta es la oportunidad de estar en estado de $n$ después de la partida en el estado de $0$. Es cero para $m=0, 1, \ldots, n-1$ y después de es $p^n$ veces un polinomio de grado $m-n$ (con un valor distinto de cero términos de grados $0$ a través de $m-n$), lo que significa que no hay mayor simplificación posible. Sin embargo, cuando se $n/p$ es largish (alrededor de $10$ $20$o así), los poderes en la suma de $**$ puede ser aproximada por exponenciales,
$$\left(\frac{n - jp}{n}\right)^m = \left(1 - \frac{j p}{n}\right)^m \approx \left(e^{-m p / n}\right)^j,$$
que a su vez puede ser resumida mediante el Teorema del Binomio, dando
$$\left(\mathbb{P}^m\right)_{0n} \approx \left(1 - e^{-m p / n}\right)^n .$$
(Al $m p /n$ $n$ son grandes, esto puede ser aproximada como $\exp\left(e^{-mp}\right)$.)
Para ilustrar, este gráfico representa los valores correctos en azul y la aproximación en rojo para $m \le 100$ donde$n=5$$p=1/3$. Las diferencias son sólo de unos pocos por ciento en la mayoría de los.
La aproximación puede ser utilizado para la estimación de un $m$ que pueda acabar con todas las naves. Si desea que hay al menos un $1 - \varepsilon$ de probabilidad de que, a continuación, elija $m$, de modo que
$m p / n$ es largish y
$m \approx n (\log(n) - \log(\varepsilon))/ p$.
Este se obtiene a partir de un primer orden en series de Taylor de expresión para la aproximación. Por ejemplo, supongamos que nos gustaría tener un $95\%$ de posibilidades de acabar con todas las naves en el ejemplo de la figura. A continuación, $\varepsilon = 0.05$ y
$$m \approx 5(\log(5) - \log(0.05)) / (1/3) = 69.$$
Tenga en cuenta que $m p / n = 69(1/3)/5 = 4.6$ no es muy grande, pero es como llegar: la aproximación puede estar bien. De hecho, la probabilidad aproximada es $95.07\%$ mientras que la probabilidad correcta de es $95.77\%$.
Esta es una versión modificada de Cupón Colector del Problema en el que cada cupón que se encuentra tiene sólo un $p$ de probabilidad de ser útil. El método utilizado aquí se produce la distribución completa de los barcos destruidos por cualquier $m$: sólo inspeccionar la primera fila de $\mathbb{P}^m$.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
