Ataque a Marte (probabilidade de destruir

Suponha que a Terra tenha sido atacada por naves espaciais marcianas e suponha que temos mísseis para lançar contra as naves espaciais. A probabilidade de atingir e destruir cada nave espacial por cada míssil é (independente do resto).$n$$m=k \cdot n$$n$$p$

Qual é a probabilidade de destruir todas as naves espaciais se lançarmos todos os mísseis ao mesmo tempo, mas cada míssil escolherá uma espaçonave aleatoriamente?

Um modelo equivalente para esse processo é o primeiro a colocar as naves espaciais em uma garrafa. Defina a contagem de naves destruídas para zero. Enumere os mísseis . Para determinar qual navio é alvo de míssil , agite bem a garrafa e puxe aleatoriamente uma nave. Com probabilidade , marque-o como destruído; caso contrário, não altere nenhuma de suas marcações. Se originalmente estava intacto e agora foi marcado como destruído, aumente a contagem de navios destruídos. Devolva este navio para a garrafa e repita.$n$$1, 2, \ldots, m$$i$$p$

Esta descreve uma Cadeia Markov sobre as contagens de que vai ser executado por meio iterações. Depois que navios forem destruídos, a chance de que outro seja destruído (fazendo uma transição do estado para o estado ) terá a chance de selecionar um navio não destruído (do qual há ) vezes a chance de destruir esse navio. navio (que é ). Isso é,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.$$

Caso contrário, a cadeia permanece no estado . O estado inicial é . Centros de interesse sobre a possibilidade de estar no estado depois iterações.i = 0 n $i$$i=0$$n$$m$

A matriz de transição dessas probabilidades, em que é a probabilidade de fazer a transição de para , diagonaliza facilmente: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} }$$

Onde

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

é o triângulo de Pascal. O inverso é facilmente encontrado como

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

Que essa matriz central (diagonal) seja escrita , para que$\Lambda$

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

A matriz para iterações é$m$

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

e obviamente

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

Fazendo a multiplicação em 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{**}$$

Essa é a chance de estar no estado após iniciar no estado . É zero para e depois disso é vezes um polinômio de grau (com termos diferentes de zero dos graus a ), o que significa que nenhuma simplificação adicional parece possível. No entanto, quando é amplo (cerca de a ), as potências na soma podem ser aproximadas por exponenciais,$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 por sua vez pode ser somado através do Teorema Binomial, dando

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

(Quando e são grandes, isso pode ser aproximado como .)$m p /n$$n$$\exp\left(e^{-mp}\right)$

Para ilustrar, esta parcelas gráfico os valores correctos em azul e a vermelho em aproximação para , onde e . As diferenças são de apenas alguns por cento, no máximo.$m \le 100$$n=5$$p=1/3$

A aproximação pode ser usada para estimar um que provavelmente destruirá todos os navios. Se você deseja que haja pelo menos uma chance de disso, escolha para que$m$$1 - \varepsilon$$m$

1. $m p / n$ é amplo e

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

Isso é obtido a partir de uma expressão de primeira ordem da série Taylor para a aproximação. Por exemplo, suponha que gostaríamos de ter chance de destruir todos os navios no exemplo da figura. Então e$95\%$$\varepsilon = 0.05$

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

Observe que não é muito grande, mas está chegando lá: a aproximação pode estar correta. De fato, a chance aproximada é de enquanto a chance correta é de . 95,07 % 95,77 $m p / n = 69(1/3)/5 = 4.6$$95.07\%$$95.77\%$

---

Esta é uma versão modificada Coupon Problema de Colecionador em que cada cupom que é encontrado tem apenas uma chance de ser útil. O método usado aqui produz toda a distribuição de naves destruídas para qualquer : basta inspecionar a primeira linha de .m P$p$$m$$\mathbb{P}^m$