# Mars attack (probability to destroy $n$ spaceships with $k \cdot n$ missiles)

Suppose Earth has been attacked by $n$ Martian spaceships and suppose that we have $m=k \cdot n$ missiles to release against the $n$ spaceships. The probability to hit and destroy each spaceship by each missile is $p$ (independent from the rest).

What is the probability to destroy all the spaceships if we release all the missiles at the same time but each missile will choose a spaceship at random?

An equivalent model for this process is first to put the $n$ spaceships into a bottle. Set the count of destroyed ships to zero. Enumerate the missiles $1, 2, \ldots, m$. To determine which ship is targeted by missile $i$, shake the bottle well and randomly draw a ship from the bottle. With probability $p$, mark it as destroyed; otherwise, do not change any of its markings. If it originally was intact and now has been marked as destroyed, increment the count of destroyed ships. Return this ship to the bottle and repeat.

This describes a Markov Chain on the counts $0, 1, \ldots, n$ that will be run through $m$ iterations. After $i$ ships have been destroyed, the chance that another will be destroyed (thereby making a transition from state $i$ to state $i+1$) will be the chance of selecting an undestroyed ship (of which there are $n-i$) times the chance of destroying that ship (which is $p$). That is,

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

Otherwise, the chain stays in the state $i$. The initial state is $i=0$. Interest centers on the chance of being in state $n$ after $m$ iterations.

The transition matrix $\mathbb{P}$ of these probabilities, where $\mathbb{P}_{ij}$ is the probability of making the transition from $i$ to $j$, easily 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-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} }

where

$$\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}$$

is Pascal’s Triangle. The inverse is readily found to be

$$\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} }$$

Let that central (diagonal) matrix be written $\Lambda$, so that $$\Lambda_{jj} = \frac{n-jp}{n}.$$

The matrix for $m$ iterations is

$$\mathbb{P}^m = \left(\mathbb{V \Lambda V^{-1}}\right)^m = \mathbb{V} \Lambda^m \mathbb{V}^{-1}\tag{*}$$

and, obviously,

$$(\Lambda^m)_{jj} = \Lambda_{jj}^m = \left(\frac{n-jp}{n}\right)^m.$$

Doing the multiplication in $*$ we find

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

This is the chance of being in state $n$ after starting in state $0$. It is zero for $m=0, 1, \ldots, n-1$ and after that it is $p^n$ times a polynomial of degree $m-n$ (with nonzero terms of degrees $0$ through $m-n$), which means no further simplification appears possible. However, when $n/p$ is largish (around $10$ to $20$ or so), the powers in the sum $**$ can be approximated by exponentials,

$$\left(\frac{n – jp}{n}\right)^m = \left(1 – \frac{j p}{n}\right)^m \approx \left(e^{-m p / n}\right)^j,$$

which in turn can be summed via the Binomial Theorem, giving

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

(When $m p /n$ and $n$ are both large, this can further be approximated as $\exp\left(e^{-mp}\right)$.)

To illustrate, this graphic plots the correct values in blue and the approximation in red for $m \le 100$ where $n=5$ and $p=1/3$. The differences are only a few percent at most. The approximation can be used to estimate an $m$ that is likely to wipe out all the ships. If you would like there to be at least a $1 – \varepsilon$ chance of that, then choose $m$ so that

1. $m p / n$ is largish and

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

This is obtained from a first-order Taylor series expression for the approximation. For instance, suppose we would like to have a $95\%$ chance of wiping out all the ships in the example of the figure. Then $\varepsilon = 0.05$ and

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

Note that $m p / n = 69(1/3)/5 = 4.6$ is not terribly large, but it’s getting there: the approximation might be OK. In fact, the approximate chance is $95.07\%$ while the correct chance is $95.77\%$.

This is a modified Coupon Collector’s Problem in which each coupon that is found has only a $p$ chance of being useful. The method used here produces the entire distribution of destroyed ships for any $m$: just inspect the first row of $\mathbb{P}^m$.