Comment réduire la confiance d'un algorithme Monte Carlo dans sa réponse?

Question

Rappelez-vous qu'un algorithme Monte Carlo est $ p $-Correct s'il publie une réponse correcte avec une probabilité au moins $ p $. Dans le cas des problèmes de décision, où la réponse est binaire, la répétition de l'algorithme MC peut augmenter la confiance qu'une bonne réponse est obtenue.

Cependant, dans le cas où plus d'une réponse possible est correcte, cette confiance peut réellement diminuer. Je me demande combien de fois $ k $ Un tel algorithme doit-il être exécuté pour obtenir une confiance dans la réponse inférieure à 50%.

Voici ce que j'ai fait:

Supposer que $ k = 3 $ Et j'ai un algorithme MC à 75% correct qui produit 5 réponses possibles, dont 4 sont correctes, et 1 est erronée. Je pense que dans ce cas, la «correction» de 75% de l'algorithme est divisée entre toutes les bonnes réponses possibles, de sorte que chaque réponse correcte a une «probabilité» de 75% / 4.

Supposons que les bonnes réponses sont $ a, b, c, d $ Et une mauvaise réponse est $ e $.

Dans ce cas, si je répertorie toutes les combinaisons possibles de sorties d'un algorithme MC que j'exécute $ k = 3 $ fois, je reçois une liste de tuples $ (a, a, a) $, $ (a, a, b) $... et ainsi de suite, chacun étant associé à une probabilité de se produire. Donc, par exemple $ (a, a, a) $ a une probabilité $(0.75/4)^3$ de se produire et $ (a, a, e) $ a une probabilité $(0.75/4)^2 * 0.25$.

Donc, si je construis un tableau en associant chaque tuple possible à sa probabilité de se produire, et en résume les probabilités de tous les événements où l'algorithme publierait la bonne réponse par vote majoritaire (les liens sont divisés en choisissant au hasard), cela devrait me donner la finale " confiance "de l'algorithme. Dans ce cas, j'obtiens des nombres d'environ 0,65-0,75 (en raison de l'aléatoire dans les fentes à attacher).

Cependant, je n'ai pas pu trouver un $ k $ Cela permet à cette valeur de moins de 50%.

Des idées si je fais quelque chose de mal? L'aide est très appréciée.