Algorithme de Monte-Carlo

Un algorithme de Monte-Carlo a deux caractéristiques : primo il est randomisé, c'est-à-dire qu'il utilise un aléa au cours de son calcul, secundo son temps d'exécution est déterministe. Sa nature aléatoire se manifeste dans son résultat qui peut être incorrect avec une certaine probabilité (généralement minime), mais qui peut-être quantifiée rigoureusement[1].

Le test de primalité de Solovay-Strassen est un test qui détermine si un nombre donné est premier. Il répond toujours vrai pour les nombres premiers, tandis que pour les nombres composés (c'est-à-dire non premiers), il répond faux avec une probabilité d'au moins ½ et vrai avec une probabilité d'au plus ½. Ainsi, les réponses faux de l'algorithme sont correctes, alors que les réponses vrai sont aléatoires ; autrement dit l'algorithme est biaisé vers le faux.

Alors que la réponse renvoyée par un algorithme déterministe est toujours exacte, ce n'est pas le cas pour les algorithmes de Monte-Carlo qui peuvent ne l'être que dans le cas d'un biais. Supposons qu'il s'agisse de résoudre un problème de décision, ces algorithmes sont dits alors soit non biaisés, soit biaisés vers le faux, soit biaisés vers le vrai. Un algorithme de Monte-Carlo biaisé vers le faux est toujours correct quand il retourne faux ; un algorithme biaisé vers le vrai est toujours correct quand il retourne vrai. Quant aux algorithmes de Monte-Carlo non biaisés, leur réponse (vrai ou faux) sera soit incorrecte, soit correcte avec une certaine probabilité bornée.

En anglais, on parle de one-sided error et two-sided error[1].

Étant donné un algorithme de Monte-Carlo biaisé, sa probabilité d'échec peut être réduite (et sa probabilité de succès augmentée) en l'exécutant k fois[1]. Considérons à nouveau l'algorithme de Solovay-Strassen qui est biaisé vers le faux. On peut l'exécuter plusieurs fois lui faisant retourner vrai s'il répond vrai lors des k étapes de l'itération et faux autrement. Ainsi, si le nombre est premier, alors la réponse est vraiment correcte, et si le nombre est composé, alors la réponse est correcte, avec une probabilité renforcée au moins 1−(1−½)^k = 1−2^−k.

Pour les algorithmes de décision de Monte-Carlo non biaisés, la probabilité d'erreur peut aussi être réduite en exécutant l'algorithme k fois et en retournant la réponse qui correspond à la majorité.

La classe de complexité BPP (pour bounded-error probabilistic polynomial time) décrit les problèmes de décision qui peuvent être résolus par un algorithme de Monte-Carlo non biaisé en temps polynomial, avec une probabilité bornée d'erreur[2].

La classe de complexité RP (pour randomized polynomial time) décrit les problèmes qui peuvent être résolus avec une probabilité bornée d'erreur par un algorithme de Monte-Carlo biaisé : si la bonne réponse est faux, l'algorithme le dit, mais il peut répondre faux dans des cas où la réponse correcte est vrai.

En revanche, la classe de complexité ZPP (pour zero-error probabilistic polynomial time) décrit les problèmes solubles en temps polynomial par un algorithme de Las Vegas. On a ZPP ⊆ RP ⊆ BPP, mais on ne sait pas si ces classes de complexité sont mutuellement distinctes. Autrement dit, les algorithmes de Monte-Carlo peuvent avoir de meilleures performances que les algorithmes de Las Vegas, mais cela n'a pas été démontré.

Une autre classe de complexité est PP (pour polynomial probabilistic) ; elle décrit les problèmes de décision résolus en temps polynomial par un algorithme de Monte-Carlo qui donne un résultat plus précis qu'un simple tirage à pile ou face, mais dont la probabilité d'erreur ne peut être ramenée significativement en dessous de ½.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Monte Carlo algorithm » (voir la liste des auteurs).

• (en) Rajeev Motwani et Prabhakar Raghavan, Randomized Algorithms, New York, Cambridge University Press, 1995, 476 p. (ISBN 978-0-521-47465-8)
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein (trad. de l'anglais), Algorithmique : Cours avec 957 exercices et 158 problèmes, Dunod, 2010, 3^e éd. (1^re éd. 1990), 1188 p. (ISBN 978-2-10-054526-1, BNF 42363501)
• (en) Kenneth A Berman et Jerome L. Paul, Algorithms : Sequential, Parallel, and Distributed, Boston, Course Technology, 2005, 962 p. (ISBN 978-0-534-42057-4), « Ch 24. Probabilistic and Randomized Algorithms »

• Hasard
• Méthode de Monte-Carlo
• Générateur de nombres pseudo-aléatoires
• Faux positif
• Faux négatif