Überlegungen zur Zufallsgenerator bei der Gestaltung randomisierter Algorithmen

Question

Es ist bekannt, dass die Effizienz randomisierter Algorithmen (zumindest in BPP und RP) von der Qualität des verwendeten zufälligen Generators abhängt. Perfekte zufällige Quellen sind in der Praxis nicht verfügbar. Obwohl nachgewiesen wird, dass für alle $ 0 < delta leq frac {1} {2} $ die Identität bpp = $ delta $ -bpp und rp = $ delta $ -rp halten, ist es nicht wahr, dass das Original das Original ist Algorithmus, der für eine Präfekten zufällige Quelle verwendet wird, kann direkt auch für eine $ delta $ -Random-Quelle verwendet werden. Stattdessen muss eine Simulation durchgeführt werden. Diese Simulation ist Polynom, aber der resultierende Algorithmus ist nicht so effizient wie der ursprüngliche.

Nach meinem Wissen sind die in der Praxis verwendeten zufälligen Generatoren normalerweise nicht einmal $ Delta $ -Sources, sondern Pseudo-Random-Quellen, die sich im schlimmsten Fall äußerst schlecht verhalten können.

Entsprechend Wikipedia:

In der üblichen Praxis werden randomisierte Algorithmen unter Verwendung eines Pseudorandom -Zahlengenerators anstelle einer echten Quelle von zufälligen Bits angenähert. Eine solche Implementierung kann vom erwarteten theoretischen Verhalten abweichen.

Tatsächlich waren die Implementierungen randomisierter Algorithmen, die ich bisher bisher gesehen habe, bloße Implementierungen der Algorithmen für perfekte zufällige Quellen, die unter Verwendung von Pseudorandomquellen ausgeführt wurden.

Meine Frage ist, ob diese allgemeine Praxis rechtfertigt ist. Gibt es einen Grund zu erwarten, dass der Algorithmus in den meisten Fällen ein korrektes Ergebnis zurückgibt (mit den Wahrscheinlichkeiten wie bei BPP bzw. RP)? Wie kann die im Zitat aus Wikipedia erwähnte "Näherung" formalisiert werden? Kann die erwähnte Abweichung zumindest im erwarteten Fall irgendwie geschätzt werden? Ist es möglich zu argumentieren, dass ein randomisierter Monte-Carlo-Algorithmus, der auf einer perfekten zufälligen Quelle ausgeführt wird, in einen gut verzeichneten stochastischen Algorithmus wird, wenn er auf einer Pseudorandomquelle ausgeführt wird? Oder gibt es ähnliche Überlegungen?

Answer 1

Hier ist eine gute Rechtfertigung. Nehmen wir an, Sie verwenden einen pseudorandom-zahlengenerator kryptografisch, um die zufälligen Bits zu generieren, die von einem randomisierten Algorithmus benötigt werden. Dann funktioniert der resultierende Algorithmus weiter, solange der Krypto -Algorithmus sicher ist.

EIN kryptografische Pseudorandom-Zahlengenerator ist ein Standardwerkzeug aus der Kryptographie, das einen kurzen Saatgut akzeptiert (z. B. 128 Bit wahre Zufälligkeit) und eine unbegrenzte Anzahl von Pseudorandom -Bits erzeugt. Es kommt mit einer sehr starken Sicherheitsgarantie: Solange der zugrunde liegende kryptografische Primitive nicht gebrochen ist aus einer Sequenz wahrer zufälliger Bits). Zum Beispiel erhalten wir möglicherweise eine Garantie, die besagt: Wenn die Faktorierung schwierig ist (oder wenn RSA sicher ist; oder, wenn AES sicher ist), ist dies ein guter Pseudorandomgenerator.

Dies ist in der Tat eine sehr starke Garantie, da es allgemein angenommen wird, dass es sehr schwer ist, diese kryptografischen Primitiven zu brechen. Wenn Sie beispielsweise einen effizienten Weg finden können, um sehr große Zahlen zu berücksichtigen, wäre dies ein Durchbruchergebnis. Für alle praktischen Zwecke können Sie so handeln, als ob die kryptografischen Primitiven unzerbrechlich sind. Dies bedeutet, dass Sie für alle praktischen Zwecke so wirken können, als ob die Ausgabe eines pseudorandom-Zahlengenerators mit kryptografischer Stärke im Grunde genommen so lange ist wie eine Abfolge von wahren Randombits. Insbesondere ist dies eine gute Quelle der Zufälligkeit, die von einem randomisierten Algorithmus benötigt wird.

(Ich habe die Tatsache beschönigt, dass Sie, um ein kryptofestes PRNG zu verwenden, immer noch 128 Bit wahrer Zufälligkeit selbst finden müssen, um den Samen zu bilden. Aber dies ist normalerweise nicht schwer, und tatsächlich gibt es kryptografische Werkzeuge auch bei dieser Aufgabe zu helfen.)

In der Praxis ist es so einfach, extrem gute Pseudorandombits zu bekommen

$ cat /dev/urandom

Answer 2

Es ist bekannt, dass die Effizienz randomisierter Algorithmen (zumindest in BPP und RP) von der Qualität des verwendeten zufälligen Generators abhängt. Ich muss nicht zustimmen. Was für ein gutes Pseudurandom -Sequenz -Ensemble Ihnen eine Garantie für die Leistung des Algorithmus gibt. Wenn Sie keine solche Garantie haben, können Sie nicht schließen, dass der Algorithmus schlecht funktioniert - Sie wissen es einfach nicht.

Gibt es eine Rechtfertigung dieser allgemeinen Praxis? Es klappt.

Ist es möglich zu argumentieren, dass ein randomisierter Monte-Carlo-Algorithmus, der auf einer perfekten zufälligen Quelle ausgeführt wird, in einen gut verzeichneten stochastischen Algorithmus wird, wenn er auf einer Pseudorandomquelle ausgeführt wird? Die Komplexitätstheorie leidet an zwei Mängel. Das erste ist, dass es sehr schwierig ist, etwas zu beweisen (zum Beispiel ist P vs. NP offen). Der zweite ist, dass es sich hauptsächlich um die Worst-Case-Analyse befasst. Zusammengenommen schließen diese beiden Einschränkungen die Komplexitätstheorie als ein gutes Modell für das Verhalten von Algorithmen in der Praxis aus.