Wann löst ein Monte-Carlo-Algorithmus ein Problem?

Question

Wenn wir sagen können, dass ein Monte-Carlo-Algorithmus ein Problem löst?

an Zitat von Wikipedia auf Monte Carlo Algorithmen

Beispielsweise wird der SOLOVAY-Strassen-Primality-Test verwendet, um zu bestimmen, ob eine bestimmte Zahl eine Primzahl ist.Es beantwortet immer true für Prime Number-Eingaben;Für Verbundeingänge antwortet er falsch mit der Wahrscheinlichkeit, mindestens ½ und true mit der Wahrscheinlichkeit weniger als ½.

Was würde passieren, wenn der Solovay-Strassen-Test nur für nur 1% der Verbundeingänge trifft?

Würden wir dann immer noch sagen, dass es das Problem der Prüfung der Hironalität löst?

oder gibt es solche Anforderungen, dass ein Monte-Carlo-Algorithmus für mehr als die Hälfte der Fälle trugen muss?

Answer 1

Im Allgemeinen wird Monte Carlo verwendet, um eine Vielzahl verschiedener Arten von Problemen zu lösen. In diesem speziellen Fall möchten Sie lernen, ob eine zufällige Variable die Konstante 1 ist, oder nicht. Die Idee ist unkompliziert, probieren Sie die Zufallsvariable mehrmals (jede Probe unabhängig von der vorherigen Probe zur Vermeidung von Bias) und prüfen Sie, ob alle Ergebnisse 1 waren. Wenn zumindest ein Teil des Ergebnisses 0 war, wissen wir sicher, dass die zufällige Variable nicht ist Konstante 1 (in Solloway-Strassen-Testkontext ist die Anzahl zusammengesetzt).

Es ist wichtig zu betonen, da Monte Carlo ein randomisierter Algorithmus ist, dass es gesagt wird, das Problem zu lösen, wenn die Wahrscheinlichkeit der Rücksendung der falschen Antwort unter einem bestimmten Schwellenwert liegt (eine kleine Zahl, die wir $ \ epsilon $ ).

Was passiert, wenn alle Ergebnisse 1 waren? Es besteht die Möglichkeit, dass es sich um die Konstante 1 handelt, aber auch gibt es eine Chance, dass wir nicht Glück haben, und alle Ergebnisse waren 1, wenn sie auch 0 sein können, wenn sie auch 0 sein können. Wenn die Wahrscheinlichkeit der Probenahme A 1 $ p <1 $ , dann nach $ n $ proben Die Wahrscheinlichkeit, alle 1 zu erhalten, ist $ P_N= p ^ n $ . Beachten Sie, dass während $ N $ Erhöhen $ P_N \ Rightarrow 0 $ . Wir können eine Schwelle angeben, sagen wir $ \ Epsilon= 10 ^ {- 10} $ , so dass, wenn $ p_n < \ Epsilon $ (dh die Wahrscheinlichkeit, ein falsches Positiv zu haben, ist weniger als $ \ Epsilon $ ) Wir sind mit diesem Ergebnis in Ordnung.

---

Jetzt die Antwort auf Ihre Frage. $ \ FORALL P <1, \ Epsilon> 0 \ space \ existiert n \ space p ^ n <\ epsilon $ . Was sagt Ihnen das genau?

Was auch immer die Erfolgswahrscheinlichkeit ist, soweit es weniger ist als $ 1 $ (z. B. $ p= 0,99 $) oder $ p= 0,01 $ oder $ p= 0,5 $ ) und Schwellenwert $ \ Epsilon $ Es gibt einen $ N $ so, dass, wenn wir den Experiment $ n $ Times (Sample $ N $ mal die Zufallsvariable unabhängig voneinander) Wir werden mit der Wahrscheinlichkeit höchstens $ \ Epsilon $ . So kann Monte Carlo für nicht degenerierte Werte von $ P $ angewendet werden, nur die Anzahl $ n $ der Probe muss angepasst werden, um den $ \ Epsilon $ Schwellenanforderung zu erfüllen.