Como se deve abordar o problema 213 do Projeto Euler (“Flea Circus”)?

Gostaria de resolver o Projeto Euler 213, mas não sei por onde começar, porque sou um leigo no campo da Estatística, observe que é necessária uma resposta precisa para que o método de Monte Carlo não funcione. Você poderia recomendar alguns tópicos estatísticos para eu ler? Por favor, não publique a solução aqui.

Flea Circus

Uma grade de quadrados 30 × 30 contém 900 pulgas, inicialmente uma pulga por quadrado. Quando um sino é tocado, cada pulga pula para um quadrado adjacente aleatoriamente (geralmente 4 possibilidades, exceto as pulgas na borda da grade ou nos cantos).

Qual é o número esperado de quadrados desocupados após 50 toques da campainha? Dê sua resposta arredondada para seis casas decimais.

Você está certo; Monte Carlo é impraticável. (Em uma simulação ingênua - isto é, que reproduz exatamente a situação do problema sem simplificações - cada iteração envolveria 900 movimentos de pulga. Uma estimativa bruta da proporção de células vazias é , implicando a variação do Monte - A estimativa de Carlo após dessas iterações é de aproximadamente Para fixar a resposta em seis casas decimais, é necessário estimar em 5.E -7 e, para obter uma confiança de 95 +% (digamos), seria necessário reduzir pela metade essa precisão para 2,5E-7. Resolver forneceN 1 / N 1 / e ( 1 - 1 / e ) = 0,2325 ... / N $1/e$$N$$1/N 1/e (1 - 1/e) = 0.2325\ldots /N$N>4E$\sqrt(0.2325/N) \lt 2.5E-7$$N > 4E12$, aproximadamente. Seriam cerca de 3,6E15 movimentos de pulgas, cada um tomando vários carrapatos de uma CPU. Com uma CPU moderna disponível, você precisará de um ano inteiro de computação (altamente eficiente). E eu assumi de maneira um tanto incorreta e super-otimista que a resposta é dada como uma proporção, em vez de uma contagem: como contagem, serão necessários mais três números significativos, implicando um aumento de um milhão de vezes no cálculo ... Você pode esperar muito tempo?)

No que diz respeito a uma solução analítica, algumas simplificações estão disponíveis. (Eles também podem ser usados ​​para reduzir o cálculo de Monte Carlo.) O número esperado de células vazias é a soma das probabilidades de vazio em todas as células. Para descobrir isso, você pode calcular a distribuição de probabilidade dos números de ocupação de cada célula. Essas distribuições são obtidas somando-se as contribuições (independentes!) De cada pulga. Isso reduz o problema de encontrar o número de caminhos de comprimento 50 ao longo de uma grade de 30 por 30 entre qualquer par de células nessa grade (uma é a origem da pulga e a outra é uma célula para a qual você deseja calcular a probabilidade da ocupação da pulga).

Você não poderia percorrer as probabilidades de ocupação das células para cada pulga. Ou seja, a pulga k está inicialmente na célula (i (k), j (k)) com probabilidade 1. Após 1 iteração, ele tem probabilidade de 1/4 em cada uma das 4 células adjacentes (supondo que ele não esteja no limite ou uma esquina). Em seguida, na próxima iteração, cada um desses quartos é "manchado" por sua vez. Após 50 iterações, você tem uma matriz de probabilidades de ocupação para os pulga. Repita sobre todas as 900 pulgas (se você tirar proveito das simetrias, isso reduz em quase um fator de 8) e adicione as probabilidades (você não precisa armazenar todas de uma só vez, apenas a matriz da pulga atual (hmm, a menos que você esteja muito inteligente, você pode querer uma matriz de trabalho adicional) e a soma atual de matrizes). Parece-me que existem muitas maneiras de acelerar isso aqui e ali.

Isso não envolve nenhuma simulação. No entanto, envolve muita computação; não deve ser muito difícil calcular o tamanho da simulação necessário para fornecer respostas com uma precisão um pouco melhor que 6 dp com alta probabilidade e descobrir qual abordagem será mais rápida. Espero que essa abordagem supere a simulação por alguma margem.

Embora não me oponha à impossibilidade prática (ou impraticabilidade) de uma resolução de Monte Carlo deste problema com uma precisão de 6 casas decimais apontada pelo whuber , eu pensaria que uma resolução com seis dígitos de precisão pode ser alcançada.

$t+1$$t$$K$

$K^2$

$\hat{p}_0$$50$$(\mathbf{X}^{(t)})$

pot=rep(c(rep(c(0,1),15),rep(c(1,0),15)),15)*c(2,
    rep(3,28),2,rep(c(3,rep(4,28),3),28),2,rep(3,28),2)
pot=pot/sum(pot)
sum((1-pot)^450)-450
[1] 166.1069

$166.11$

Como comentado por whuber , as estimativas precisam ser multiplicadas por 2 para responder corretamente à pergunta, portanto, um valor final de 332,2137,

Uma abordagem analítica pode ser entediante e eu não pensei nos meandros, mas aqui está uma abordagem que você pode querer considerar. Como você está interessado no número esperado de células que estão vazias após 50 toques, você precisa definir uma cadeia markov sobre o "Não das pulgas em uma célula" em vez da posição de uma pulga (consulte a resposta de Glen_b que modela a posição de uma pulga como uma cadeia de markov. Como apontado por Andy nos comentários a essa resposta, essa abordagem pode não conseguir o que você deseja.)

Especificamente, deixe:

$n_{ij}(t)$$i$$j$

Em seguida, a cadeia markov começa com o seguinte estado:

$n_{ij}(0) =1$$i$$j$

Como as pulgas se movem para uma das quatro células adjacentes, o estado de uma célula muda dependendo de quantas pulgas estão na célula-alvo e de quantas pulgas existem nas quatro células adjacentes e da probabilidade de elas se moverem para essa célula. Usando esta observação, você pode escrever as probabilidades de transição de estado para cada célula em função do estado dessa célula e do estado das células adjacentes.

Se desejar, posso expandir a resposta ainda mais, mas isso, juntamente com uma introdução básica às cadeias de markov, deve ajudá-lo a começar.

se você for seguir a rota numérica, uma observação simples: o problema parece estar sujeito à paridade vermelho-preto (uma pulga em um quadrado vermelho sempre se move para um quadrado preto e vice-versa). Isso pode ajudar a reduzir o tamanho do problema pela metade (considere apenas dois movimentos de cada vez e observe apenas as pulgas nos quadrados vermelhos).

Suspeito que algum conhecimento de cadeias de Markov em tempo discreto possa ser útil.