8
$\begingroup$

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?

$\endgroup$
14
$\begingroup$

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.

Figure

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$.

$\endgroup$
  • 2
    $\begingroup$ I did, too: apparently, $(**)$ generalizes the distribution function of a "Fisher $\xi$ distribution". See stats.stackexchange.com/questions/203410 . A copy of Fisher's original (1929) paper is available in PDF form at hekyll.services.adelaide.edu.au/dspace/bitstream/2440/15201/1/… . $\endgroup$ – whuber Mar 24 '16 at 17:11
  • 1
    $\begingroup$ Besides the coupon collector's problem this problem also relates to the occupancy problem and the approximation by exponentials relates to the Poissonization done here math.stackexchange.com/a/631534/466748 (ping to @Ben since he does a lot of these problems) $\endgroup$ – Sextus Empiricus Sep 1 '19 at 21:43
  • $\begingroup$ @Martijn Thank you for pointing that out: the same Markov chain appears in the occupancy problem. $\endgroup$ – whuber Sep 1 '19 at 21:47
  • 1
    $\begingroup$ I imagine you could also approach this as a multinomial distribution with $kn$ balls being distributed over $n+1$ cells with the first $n$ probability $p/n$ and the last cell probability $1-p$. Then expressing the problem more like a combinatorial problem and use Stirling numbers for equation ** (and possibly their properties can be used to arrive at a same approximation). (not that it's better, or possibly even worse, but it just gives a different angle to the solution) $\endgroup$ – Sextus Empiricus Sep 1 '19 at 22:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.