Un algorithme aléatoire est-il une distribution de probabilité sur l'ensemble d'algorithmes déterministes?

Question

S'il y a un ensemble fini d'instances de taille n et l'ensemble d'algorithmes déterministes (raisonnables) est finit.

Un algorithme aléatoire peut-il être considéré comme une distribution de probabilité sur l'ensemble d'algorithmes déterministes?Et si oui, pourquoi?

Answer 1

Vous pouvez penser à un algorithme randomisé comme ayant accès à une variable aléatoire $ \ mathbf {r} $ , qui informe ses décisions aléatoires.Pour toute fixation de $ \ mathbf {r} $ , vous obtenez un algorithme déterministe et, de cette façon, vous pouvez afficher l'algorithme randomisé original comme une distribution sur des algorithmes déterministes.

Par exemple, considérez l'algorithme randomisé pour la résolution de max-3sat.L'algorithme choisit une affectation aléatoire.Vous pouvez penser à cette affectation comme spécifié par $ \ mathbf {r} $ .Toute affectation particulière correspond à un algorithme déterministe et l'algorithme randomisé d'origine n'est que la distribution uniforme sur ces algorithmes déterministes.