Ataque a Marte (probabilidade de destruir

8

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).nm=knnp

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?

will198
fonte

Respostas:

14

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.n1,2,,mip

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 p0,1,,nmiii+1nip

Pr(ii+1)=ninp.

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 mii=0nm

A matriz de transição dessas probabilidades, em que é a probabilidade de fazer a transição de para , diagonaliza facilmente:P i j i jPPijij

P=(1pp00001n1npn1np00001n2npn2np000011np1np00001)=V(100000npn00000n2pn00000n(n1)pn00000nnpn)V1

Onde

V=((n0)(n1)(n2)(nn1)(nn)(n10)(n11)(n12)(n1n1)0(10)(11)000(00)0000)

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

V1=(0000(00)000(11)(10)00(22)(21)(20)0(n1n1)(1)n1+2(n12)(1)n1+1(n12)(1)n1+0(n10)(n0)(n1)(1)n+2(n2)(1)n+1(n2)(1)n+0(n0))

Que essa matriz central (diagonal) seja escrita , para queΛ

Λjj=njpn.

A matriz para iterações ém

(*)Pm=(VΛV1)m=VΛmV1

e obviamente

(Λm)jj=Λjjm=(njpn)m.

Fazendo a multiplicação em encontramos

(**)(Pm)0n=j=0min(m,n)(1)j(nj)(njpn)m.

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,n0m=0,1,,n1pnmn0mnn/p1020

(njpn)m=(1jpn)m(emp/n)j,

que por sua vez pode ser somado através do Teorema Binomial, dando

(Pm)0n(1emp/n)n.

(Quando e são grandes, isso pode ser aproximado como .)mp/nnexp(emp)

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.m100n=5p=1/3

Figura

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 quem1εm

  1. mp/n é amplo e

  2. mn(log(n)log(ε))/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 e95%ε=0.05

m5(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 %mp/n=69(1/3)/5=4.695.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 mpmPm

whuber
fonte
2
Eu também: aparentemente, generaliza a função de distribuição de uma " distribuição Fisher ". Consulte stats.stackexchange.com/questions/203410 . Uma cópia do artigo original de Fisher (1929) está disponível em formato PDF em hekyll.services.adelaide.edu.au/dspace/bitstream/2440/15201/1/… . ξ()ξ
whuber
1
Além do problema do coletor de cupons, esse problema também se refere ao problema de ocupação e a aproximação por exponenciais refere-se à Poissonização feita aqui math.stackexchange.com/a/631534/466748 (execute ping no @Ben, pois ele resolve muitos desses problemas)
Sextus Empiricus
@ Martijn Obrigado por apontar isso: a mesma cadeia de Markov aparece no problema de ocupação.
whuber
1
Eu imagino que você também poderia abordar esta como uma distribuição multinomial com bolas sendo distribuídos mais de células com o primeiro probabilidade eo último probabilidade celular . Em seguida, expresse o problema mais como um problema combinatório e use os números de Stirling para a equação ** (e possivelmente suas propriedades podem ser usadas para chegar à mesma aproximação). (não que é melhor, ou possivelmente até mesmo pior, mas ele só dá um ângulo diferente para a solução)n + 1 n p / n 1 - pknn+1np/n1p
Sexto Empírico