Convertir Las Vegas en Monte-Carlo, et retour

1. L'inégalité de Markov s'applique, car le temps $T$ est une variable aléatoire positive :

$$\mathrm{Pr}[T\ge \lambda t]\le \frac{1}{\lambda }.$$

En arrêtant l'algorithme après $10t$ et en rendant n'importe quoi, on obtient un Monte-Carlo de temps borné $10t$ et de probabilité d'erreur au plus $1/10$. La conversion est donc toujours possible, et elle ne demande rien de l'algorithme : ni structure, ni analyse fine.

2. Sur les huit reines, $t=438,26$ essais. Le nombre d'essais suit une loi géométrique de paramètre $p$, donc $\mathrm{Pr}[T>k]=(1-p{)}^k$ exactement. On compare :

Markov est correcte et très pessimiste : elle annonce $10\%$ d'échec là où la vérité est $4$ pour $100000$. C'est le prix de sa généralité — elle ne suppose rien d'autre que la positivité. Quand on connaît la loi, ici géométrique, on obtient une décroissance exponentielle et non en $1/\lambda$.

3. La conversion inverse demande un vérificateur. Si l'on sait tester en temps raisonnable si une réponse est correcte, on relance le Monte-Carlo jusqu'à obtenir une réponse qui passe le test : le résultat devient toujours correct, et le temps devient aléatoire. Avec une probabilité de succès $q$ par tentative, l'espérance du nombre de tentatives vaut $1/q$.

Trois exemples du livre : Rabin-Karp devient exact par la comparaison caractère par caractère ; le placement des reines par permutation est exactement ce schéma, le vérificateur étant valide ; et la fabrication d'un nombre premier (problème « Fabriquer un nombre premier ») relance un tirage jusqu'à ce qu'un test de primalité passe.

La dissymétrie mérite d'être notée. Passer de Las Vegas à Monte-Carlo est toujours possible et gratuit — on coupe. Passer de Monte-Carlo à Las Vegas exige un vérificateur, qui n'existe pas toujours. C'est pourquoi les problèmes dont une solution se vérifie facilement — ceux de la classe np du chapitre chap:decidabilite — sont précisément ceux où le hasard rend le plus de services.