Quand un algorithme de Monte Carlo résout-il un problème?

Question

Quand pouvons-nous dire qu'un algorithme de Monte Carlo résout un problème?

Pour citer de Wikipedia sur Monte Carlo Algorithmes

Par exemple, le test de primalité Solovay-strassen est utilisé pour déterminer si un numéro donné est un nombre premier.Il répond toujours à VRAI pour les entrées de numéro de choix;Pour les entrées composites, il répond à False avec une probabilité d'au moins ½ et vraie avec une probabilité inférieure à ½.

Que se passerait-il si le test Solovay-strassen répondrait vrai pour seulement 1% des intrants composites?

Dirions-nous toujours qu'il résout le problème de la primalité des tests?

ou y a-t-il des exigences comme celui-là un algorithme de Monte Carlo doit répondre au vrai pour plus de la moitié des cas?

Answer 1

dans le général Monte Carlo est utilisé pour résoudre une grande variété de types de problèmes différents. Dans ce cas particulier, vous souhaitez apprendre si une variable aléatoire est la constante 1, ou non. L'idée est simple, échantillon de la variable aléatoire plusieurs fois (chaque échantillon de l'échantillon de manière indépendante de l'échantillon précédent pour éviter les biais) et vérifiez si tous les résultats étaient 1. Si au moins une partie du résultat était de 0, nous savons certainement que la variable aléatoire n'est pas Constante 1 (dans le contexte de test Solovay-strassen, le nombre est composite).

Il est important de souligner, car Monte Carlo est un algorithme randomisé, il est dit de résoudre le problème si la probabilité de retourner la mauvaise réponse est inférieure à un seuil (un petit nombre que nous appellerons $ \ epsilon $ ).

Que se passe-t-il si tout résultat était 1? Il y a une chance que ce soit la constante 1, mais aussi il y a une chance que nous n'étions pas chanceux et que tout résultat était 1 quand ils peuvent également être 0. Si la probabilité d'échantillonnage d'un échantillonnage a 1 est $ p <1 $ , puis après $ n $ échantillons La probabilité de faire tout 1 est $ p_n= p ^ n $ . Notez que, tandis que $ N $ augmente $ p_n \ rightarrow 0 $ . Nous pouvons spécifier un seuil, disons $ \ epsilon= 10 ^ {- 10} $ , tel que si $ p_n < \ epsilon $ (c'est-à-dire que la probabilité d'avoir un faux positif est inférieure à $ \ epsilon $ ) Nous sommes ok avec ce résultat.

---

Maintenant la réponse à votre question. $ \ Forall P <1, \ epsilon> 0 \ espace \ Existe n \ espace p ^ n <\ epsilon $ . Qu'est-ce que cela vous dit exactement?

Quelle que soit la probabilité de succès, aussi loin que 1 $ (par exemple $ p= 0,99 $ ou $ p= 0,01 $ ou $ p= 0,5 $ ) et le seuil $ \ epsilon $ il existe une $ n $ tel que si nous exécutons l'expérience $ N $ fois (échantillon $ N $ fois la variable aléatoire de manière indépendante) nous allons échouer avec probabilité au plus $ \ epsilon $ . Donc, Monte Carlo peut être appliqué pour des valeurs non dégénérées de $ p $ , juste le nombre $ n $ de l'échantillon doit être ajusté pour satisfaire la $ \ EPSILON $ Exigence de seuil.