Ataque a Marte (probabilidad de destruir

Supongamos que la Tierra ha sido atacada por naves espaciales marcianas y supongamos que tenemos misiles para lanzar contra las naves espaciales. La probabilidad de golpear y destruir cada nave espacial por cada misil es (independiente del resto).$n$$m=k \cdot n$$n$$p$

¿Cuál es la probabilidad de destruir todas las naves espaciales si lanzamos todos los misiles al mismo tiempo pero cada misil elegirá una nave espacial al azar?

Un modelo equivalente para este proceso es el primero en poner los naves espaciales en una botella. Establece el recuento de naves destruidas en cero. Enumera los misiles . Para determinar qué nave es objetivo del misil , agite bien la botella y extraiga al azar una nave de la botella. Con probabilidad , márquelo como destruido; de lo contrario, no cambie ninguna de sus marcas. Si originalmente estaba intacto y ahora se ha marcado como destruido, incremente el recuento de naves destruidas. Devuelve este barco a la botella y repite.$n$$1, 2, \ldots, m$$i$$p$

Esto describe una cadena de Markov en los recuentos que se ejecutará a través de iteraciones. Después de buques han sido destruidos, la posibilidad de que otro serán destruidos (haciendo de esta manera una transición desde el estado para indicar ) será la probabilidad de selección de una nave no destruido (de los cuales hay ) veces la posibilidad de destruir que barco (que es ). Es decir,$0, 1, \ldots, n$$m$$i$$i$$i+1$$n-i$$p$

$$\Pr(i\to i+1) = \frac{n-i}{n} p.$$

De lo contrario, la cadena permanece en el estado . El estado inicial es . Centros de interés de la probabilidad de estar en el estado después de iteraciones.$i$$i=0$$n$$m$

La matriz de transición de estas probabilidades, donde es la probabilidad de hacer la transición de a , se diagonaliza fácilmente:$\mathbb{P}$$\mathbb{P}_{ij}$$i$$j$

$$\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-2p}{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} }$$

dónde

$$\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. Se descubre fácilmente que el inverso es

$$\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 matriz central (diagonal) se escriba , de modo que$\Lambda$

$$\Lambda_{jj} = \frac{n-jp}{n}.$$

La matriz para iteraciones es$m$

$$\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 posibilidad de estar en el estado después de comenzar en el estado . Es cero para y después de eso es veces un polinomio de grado (con términos distintos de cero de grados a ), lo que significa que no parece posible una mayor simplificación. Sin embargo, cuando es grande (alrededor de a o menos), las potencias en la suma se pueden aproximar por exponenciales,$n$$0$$m=0, 1, \ldots, n-1$$p^n$$m-n$$0$$m-n$$n/p$$10$$20$$**$

$$\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 se puede sumar mediante el teorema binomial, dando

$$\left(\mathbb{P}^m\right)_{0n} \approx \left(1 - e^{-m p / n}\right)^n .$$

(Cuando y son ambos grandes, esto puede además puede aproximar como ).$m p /n$$n$$\exp\left(e^{-mp}\right)$

Para ilustrar, este gráfico traza los valores correctos en azul y la aproximación en rojo para donde y . Las diferencias son solo un pequeño porcentaje como máximo.$m \le 100$$n=5$$p=1/3$

La aproximación se puede usar para estimar una que es probable que anule todas las naves. Si desea que haya al menos una probabilidad de de eso, elija para que$m$$1 - \varepsilon$$m$

1. $m p / n$ es grande y

2. $m \approx n (\log(n) - \log(\varepsilon))/ p$ .

Esto se obtiene de una expresión de la serie Taylor de primer orden para la aproximación. Por ejemplo, supongamos que nos gustaría tener una probabilidad del de eliminar todos los barcos en el ejemplo de la figura. Entonces y$95\%$$\varepsilon = 0.05$

$$m \approx 5(\log(5) - \log(0.05)) / (1/3) = 69.$$

Tenga en cuenta que no es terriblemente grande, pero está llegando allí: la aproximación podría estar bien. De hecho, la probabilidad aproximada es mientras que la probabilidad correcta es . $m p / n = 69(1/3)/5 = 4.6$$95.07\%$$95.77\%$

---

Se trata de una modificación de cupón problema de coleccionista en la que cada cupón que se encuentra sólo tiene un oportunidad de ser útil. El método utilizado aquí produce la distribución completa de naves destruidas para cualquier : solo inspeccione la primera fila de .$p$$m$$\mathbb{P}^m$