Marsangriff (Wahrscheinlichkeit,

Angenommen, die Erde wurde von Marsraumschiffen angegriffen und wir haben Raketen, die gegen die Raumschiffe abgefeuert werden können. Die Wahrscheinlichkeit, jedes Raumschiff von jeder Rakete zu treffen und zu zerstören, beträgt (unabhängig vom Rest).m = k ⋅ n n $n$$m=k \cdot n$$n$$p$

Wie groß ist die Wahrscheinlichkeit, alle Raumschiffe zu zerstören, wenn wir alle Raketen gleichzeitig loslassen, aber jede Rakete zufällig ein Raumschiff auswählt?

Ein äquivalentes Modell für diesen Prozess besteht darin, zuerst die Raumschiffe in eine Flasche zu füllen. Setzen Sie die Anzahl der zerstörten Schiffe auf Null. Zählen Sie die Raketen . Um festzustellen, auf welches Schiff die Rakete zielt , schütteln Sie die Flasche gut und ziehen Sie zufällig ein Schiff aus der Flasche. Markieren Sie es mit der Wahrscheinlichkeit als zerstört; Andernfalls ändern Sie keine der Markierungen. Wenn es ursprünglich intakt war und jetzt als zerstört markiert wurde, erhöhen Sie die Anzahl der zerstörten Schiffe. Geben Sie dieses Schiff wieder in die Flasche und wiederholen Sie den Vorgang.1 , 2 , … , m i $n$$1, 2, \ldots, m$$i$$p$

Diese beschreibt eine Markov - Kette auf den Zählungen das wird durchlaufen werden Iterationen. Nachdem Schiffe zerstört wurden, ist die Chance, dass ein anderes zerstört wird (wodurch ein Übergang von Zustand zu Zustand ) die Chance, ein unzerstörtes Schiff (von dem es ) auszuwählen, mal die Chance, dies zu zerstören Schiff (das ist ). Das ist,m i i i + 1 n - i $0, 1, \ldots, n$$m$$i$$i$$i+1$$n-i$$p$

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

Ansonsten bleibt die Kette im Zustand . Der Anfangszustand ist . Das Interesse konzentriert sich auf die Chance, in Zustand ist nach Iterationen.i = 0 n $i$$i=0$$n$$m$

Die Übergangsmatrix dieser Wahrscheinlichkeiten, wobei die Wahrscheinlichkeit für den Übergang von nach , lässt sich leicht diagonalisieren:P i j i $\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} }$$

wo

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

ist Pascals Dreieck. Das Inverse ist leicht zu finden

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

Lassen Sie diese zentrale (diagonale) Matrix schreiben , so dassΛ j j = n - j $\Lambda$

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

Die Matrix für Iterationen$m$

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

und natürlich

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

Wenn wir die Multiplikation in , finden wir$*$

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

Dies ist die Chance, nach dem Start in Zustand im Zustand . Es ist Null für und danach ist es mal ein Polynom vom Grad (mit Termen ungleich Null von Grad bis ), was bedeutet, dass keine weitere Vereinfachung möglich erscheint. Wenn jedoch größer ist (ungefähr bis oder so), können die Potenzen in der Summe durch Exponentiale angenähert werden.$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,$$

was wiederum über den Binomialsatz summiert werden kann und ergibt

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

(Wenn und beide groß sind, kann dies weiter als angenähert werden .)$m p /n$$n$$\exp\left(e^{-mp}\right)$

Zur Veranschaulichung zeigt diese Grafik die korrekten Werte in Blau und die Näherung in Rot für wobei und . Die Unterschiede betragen höchstens wenige Prozent.$m \le 100$$n=5$$p=1/3$

Die Annäherung kann verwendet werden, um ein zu schätzen , das wahrscheinlich alle Schiffe auslöscht. Wenn Sie möchten, dass dies mindestens eine Chance gibt, wählen Sie so$m$$1 - \varepsilon$$m$

1. $m p / n$ ist groß und

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

Dies wird aus einem Taylorreihenausdruck erster Ordnung für die Approximation erhalten. Angenommen, wir möchten eine Chance haben, alle Schiffe im Beispiel der Abbildung auszulöschen. Dann ist und$95\%$$\varepsilon = 0.05$

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

Beachten Sie, dass nicht besonders groß ist, aber es kommt dahin: Die Annäherung könnte in Ordnung sein. Tatsächlich beträgt die ungefähre Chance während die korrekte Chance beträgt . 95,07 % 95,77 $m p / n = 69(1/3)/5 = 4.6$$95.07\%$$95.77\%$

---

Dies ist eine modifizierte Coupon Sammler Problem , bei dem jeder Coupon, der nur eine gefunden wird , hat Chance, nützlich. Die hier verwendete Methode erzeugt die gesamte Verteilung der zerstörten Schiffe für jedes : Überprüfen Sie einfach die erste Zeile von .m P$p$$m$$\mathbb{P}^m$