Attaque de Mars (probabilité de détruire vaisseaux spatiaux avec missiles)

Supposons que la Terre ait été attaquée par vaisseaux spatiaux martiens et supposons que nous ayons missiles à lancer contre les vaisseaux spatiaux. La probabilité de toucher et de détruire chaque vaisseau spatial par chaque missile est (indépendante du reste).$n$$m=k \cdot n$$n$$p$

Quelle est la probabilité de détruire tous les vaisseaux spatiaux si nous lâchons tous les missiles en même temps mais chaque missile choisira un vaisseau spatial au hasard?

Un modèle équivalent pour ce processus est tout d'abord de mettre les vaisseaux spatiaux dans une bouteille. Réglez le nombre de navires détruits à zéro. Énumérer les missiles . Pour déterminer quel navire est ciblé par le missile , secouez bien la bouteille et tirez au hasard un navire de la bouteille. Avec la probabilité , marquez-la comme détruite; sinon, ne modifiez aucun de ses marquages. S'il était à l'origine intact et a été marqué comme détruit, augmentez le nombre de navires détruits. Remettez ce navire dans la bouteille et répétez.$n$$1, 2, \ldots, m$$i$$p$

Ceci décrit une chaîne de Markov sur les nombres qui seront exécutés par itérations. Après que navires aient été détruits, la chance qu'un autre soit détruit (faisant ainsi une transition de l'état à l'état ) sera la chance de sélectionner un navire non détruit (dont il y a ) fois la chance de détruire ce navire (qui est ). C'est,$0, 1, \ldots, n$$m$$i$$i$$i+1$$n-i$$p$

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

Sinon, la chaîne reste dans l'état . L'état initial est . Centres d'intérêt sur la chance d'être dans un état après itérations.$i$$i=0$$n$$m$

La matrice de transition de ces probabilités, où est la probabilité de faire la transition de à , diagonise facilement:$\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} }$$

où

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

est le triangle de Pascal. L'inverse se révèle facilement être

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

Soit cette matrice centrale (diagonale) écrite , de sorte que$\Lambda$

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

La matrice des itérations est$m$

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

et, évidemment,

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

Faire la multiplication en on trouve$*$

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

C'est la chance d'être dans l'état après avoir commencé dans l'état . Il est nul pour et après cela, il est fois un polynôme de degré (avec des termes non nuls de degrés à ), ce qui signifie qu'aucune simplification supplémentaire ne semble possible. Cependant, lorsque est plus grand (environ à environ), les puissances de la somme peuvent être approximées par des exponentielles,$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,$$

qui à son tour peut être additionné via le théorème binomial, donnant

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

(Lorsque et sont tous deux grands, cela peut en outre être approximé par .)$m p /n$$n$$\exp\left(e^{-mp}\right)$

Pour illustrer, ce graphique trace les valeurs correctes en bleu et l'approximation en rouge pour où et . Les différences ne sont que de quelques pour cent au maximum.$m \le 100$$n=5$$p=1/3$

L’approximation peut être utilisée pour estimer un susceptible d’effacer tous les navires. Si vous souhaitez qu'il y ait au moins chance, choisissez pour que$m$$1 - \varepsilon$$m$

1. $m p / n$ est large et

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

Ceci est obtenu à partir d'une expression de série Taylor de premier ordre pour l'approximation. Par exemple, supposons que nous aimerions avoir chances d'effacer tous les navires dans l'exemple de la figure. Alors et$95\%$$\varepsilon = 0.05$

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

Notez que n'est pas terriblement grand, mais il y arrive: l'approximation pourrait être OK. En fait, la chance approximative est de tandis que la chance correcte est de . $m p / n = 69(1/3)/5 = 4.6$$95.07\%$$95.77\%$

---

Il s'agit d'un problème de collecteur de coupons modifié dans lequel chaque coupon trouvé n'a qu'une chance d'être utile. La méthode utilisée ici produit la distribution entière des navires détruits pour tout : il suffit d'inspecter la première ligne de .$p$$m$$\mathbb{P}^m$