Quando um algoritmo monte carlo resolve um problema?

Question

Quando podemos dizer que um algoritmo monte carlo resolve um problema?

para citar de Wikipedia em algoritmos de Monte Carlo

.

Por exemplo, o teste de primordial do Solovay-Strassen é usado para determinar se um determinado número é um número primo.Ele sempre responde a verdade para entradas de número primo;Para insumos compostos, responde false com probabilidade pelo menos ½ e verdadeiro com probabilidade menor que ½.

O que aconteceria se o teste de Solovay-Strassen responderia para apenas 1% das entradas compostas?

Nos ainda dizeríamos que resolve o problema de testar a primalidade?

ou existe algum requisito como se um algoritmo monte carlo tem que responder a verdade para mais da metade dos casos?

Answer 1

No general Monte Carlo é usado para resolver uma grande variedade de diferentes tipos de problemas. Neste caso particular, você deseja aprender se uma variável aleatória é a constante 1, ou não. A ideia é direta, amostra a variável aleatória várias vezes, (cada amostra independentemente da amostra anterior para evitar viés) e verifique se todos os resultados foram 1. Se pelo menos algum do resultado foi 0, sabemos que a variável aleatória não é Constante 1 (no contexto do teste do Solovay-Strassen, o número é compósito).

É importante enfatizar, já que Monte Carlo é um algoritmo randomizado, que é dito resolver o problema se a probabilidade de retornar a resposta errada estiver abaixo de algum limite (um pequeno número, chamaremos a matemática $ \ epsilon $ ).

O que acontece se todo o resultado fosse 1? Há uma chance de que é a constante 1, mas também há uma chance que não tivéssemos sorte e todos os resultados foram 1 quando eles também podem ser 0. Se a probabilidade de amostragem A 1 é $ p <1 $ , depois após $ n $ amostras A probabilidade de obter todas as 1 é $ p_n= p ^ n $ . Observe que, embora $ n $ aumente $ p_n \ rightarrow 0 $ . Podemos especificar um limiar, digamos $ \ epsilon= 10 ^ {- 10} $ , tal que, se $ p_n < \ epsilon $ (isto é, a probabilidade de ter um falso positivo é menor que $ \ epsilon $ ) Estamos bem com esse resultado.

---

.

Agora a resposta à sua pergunta. $ \ forall p <1, \ epsilon> 0 \ space \ existe n \ space p ^ n <\ epsilon $ . O que isso é informado exatamente?

Seja qual for a probabilidade de sucesso, tanto quanto é menor que $ 1 $ (por exemplo $ p= 0,99 $ ou $ p= 0,01 $ ou $ p= 0,5 $ ) e limiar $ \ epsilon $ Existe uma $ n $ tal que, se corrermos o experimento $ n $ vezes (amostra $ n $ vezes a variável aleatória independentemente) vamos falhar com probabilidade no máximo $ \ epsilon $ . Então Monte Carlo pode ser aplicado para valores não degenerados de $ P $ , apenas o número $ n $ de amostra deve ser ajustado para satisfazer a $ \ epsilon $ requisito de limite.