Quando un algoritmo del Monte Carlo risolve un problema?

Question

Quando possiamo dire che un algoritmo di Monte Carlo risolve un problema?

Per citare da Wikipedia su Monte Carlo Algoritmi

.

Ad esempio, il test di primalità SOLOVAY-STRASENS viene utilizzato per determinare se un dato numero è un numero primo.Risponde sempre vero per gli input numerici PRIME;Per gli ingressi compositi, risponde false con probabilità almeno ½ e true con probabilità inferiore a ½.

Cosa succederebbe se il test SOLOVAY-STRASSEN risponderebbe vero per solo l'1% degli ingressi compositi?

Vorremmo ancora dire che risolve il problema della primalità di prova?

O c'è qualche requisito come che un algoritmo di Monte Carlo deve rispondere è vero per più della metà dei casi?

Answer 1

In generale Monte Carlo viene utilizzato per risolvere un'ampia varietà di diversi tipi di problemi. In questo caso particolare si desidera imparare se una variabile casuale è la costante 1 o meno. L'idea è semplice, campionare le variabili casuali più volte, (ciascun campione indipendentemente dal campione precedente per evitare pregiopia) e controllare se tutti i risultati fossero 1. Se almeno un po 'del risultato era 0, sappiamo per certo la variabile casuale non lo è Constant 1 (nel contesto del test SOLOVAY-STRASSEN, il numero è composito).

È importante sottolineare, dal momento che Monte Carlo è un algoritmo randomizzato, che si dice che risolva il problema se la probabilità di restituire la risposta sbagliata è inferiore a una soglia (un numero piccolo chiameremo $ \ Epsilon $ ).

Cosa succede se tutto il risultato era 1? C'è una possibilità che sia la costante 1, ma anche c'è una possibilità che non siamo stati fortunati e tutti i risultati erano 1 quando possono anche essere 0. Se la probabilità di campionamento a 1 è $ P <1 $ , quindi dopo $ N $ campioni La probabilità di ottenere tutto 1 è $ p_n= p ^ n $ . Si noti che mentre $ N $ Aumenta $ P_n \ Ramersow 0 $ . Possiamo specificare una soglia, diciamo $ \ Epsilon= 10 ^ {- 10} $ , in modo tale da se $ p_n < \ Epsilon $ (cioè la probabilità di avere un falso positivo è inferiore a $ \ epsilon $ ) Stiamo bene con quel risultato.

---

.

Ora la risposta alla tua domanda. $ \ Forall P <1, \ Epsilon> 0 \ SPAZIO \ Esiste n \ Space P ^ N <\ EPSILON $ . Cosa ti dice esattamente?

Qualunque sia la probabilità di successo, per quanto sia inferiore a $ 1 $ (ad esempio $ p= 0,99 $ o $ p= 0,01 $ o $ p= 0,5 $ ) e soglia $ \ epsilon $ Esistono una classe $ N $ tale che se eseguiamo l'esperimento $ N $ Times (campione $ N $ volte la variabile casuale in modo indipendente) Non riusciremo con la probabilità al massimo $ \ Epsilon $ . Quindi Monte Carlo può essere applicato per valori non degenerati di $ p $ , solo il numero $ N $ Il campione deve essere regolato per soddisfare la $ \ Epsilon $ Requisiti di soglia.