Welche randomisierten Algorithmen haben eine exponentiell geringe Fehlerwahrscheinlichkeit?

Angenommen, ein randomisierter Algorithmus verwendet Zufallsbits. Die niedrigste zu erwartende Fehlerwahrscheinlichkeit (die einem deterministischen Algorithmus mit Fehler 0 nicht entspricht) beträgt . Welche randomisierten Algorithmen erreichen eine so geringe Fehlerwahrscheinlichkeit? $r$ $2^{-\Omega(r)}$

Ein paar Beispiele, die mir einfallen, sind:

Abtastalgorithmen, z. B., bei denen die Größe eines Satzes geschätzt werden soll, für den die Zugehörigkeit überprüft werden kann. Wenn man die zu prüfenden Elemente gleichmäßig zufällig abtastet, garantiert die Chernoff-Grenze eine exponentiell kleine Fehlerwahrscheinlichkeit.
Der Karger-Klein-Tarjan-Algorithmus zur Berechnung des Minimum Spanning Tree. Der Algorithmus wählt jede Kante mit der Wahrscheinlichkeit 1/2 aus und findet rekursiv die MST im Sample. Man kann mit Chernoff argumentieren, dass es exponentiell unwahrscheinlich ist, dass es 2n + 0,1 m Kanten gibt, die besser sind als der Baum (dh man würde es vorziehen, sie über eine der Baumkanten zu ziehen).

Können Sie sich andere Beispiele vorstellen?

Die Antwort von Andras lautet wie folgt: In der Tat kann jeder Polynomzeitalgorithmus in einen langsameren Polynomzeitalgorithmus mit einer exponentiell kleinen Fehlerwahrscheinlichkeit umgewandelt werden. Mein Fokus liegt auf möglichst effizienten Algorithmen. Insbesondere für die zwei Beispiele, die ich gegeben habe, gibt es deterministische Polynomzeitalgorithmen, die die Probleme lösen. Das Interesse an den randomisierten Algorithmen beruht auf ihrer Effizienz.

randomized-algorithms Dana Moshkovitz
quelle

Keine vollständige Antwort, aber es hat einige Arbeiten in der randomisierten numerischen linearen Algebra gegeben. youtube.com/watch?v=VTroCeIqDVc

Baby Dragon

Vielleicht kann man es nicht erwarten , aber man kann mit Sicherheit hoffen (immer noch "einen deterministischen Algorithmus mit 0-Fehler verfehlen"), dass für alle reellen Zahlen

c

$c\hspace{-0.02 in}$ , wenn

c < 1

$\: c<1 \:$ Dann gibt es einen Algorithmus

$\hspace{.34 in}$ deren Fehlerwahrscheinlichkeit ist

2^{- c \cdot r}

$2^{-\hspace{.01 in}c\cdot r}\hspace{-0.03 in}$ .

$\:$ Ich glaube, Polynomial Identity Testing ist ein solches Problem.

$\hspace{.49 in}$

@ RickyDemer Ich verstehe deinen Kommentar nicht. Der übliche randomisierte Algorithmus für PIT weist einen Fehler auf, der in der Zufälligkeit nicht exponentiell ist. Also, was sagst du? Wollen Sie damit sagen, dass es für jedes BPP-Problem einen solchen Algorithmus geben könnte?

Sasho Nikolov

Mir ist jetzt klar, dass ich nicht wirklich nachweisen kann, dass PIT zu der von mir beschriebenen Klasse gehört.

$\:$ Andererseits würde es für das Schwartz-Zippel-Lemma ausreichen ,

superpolynomisch sein zu lassen (dh Länge (S) in Länge (d) superlinear sein zu lassen)

S

$S$

d

$d$

$\:$ (Fortsetzung ...)

$\;\;\;\;$

Viele probabilsitische Methodenkonstruktionen haben ein solches Verhalten, nicht wahr? Wenn Sie beispielsweise einen zufälligen Satz von Binärzeichenfolgen auswählen und auf das nächste Paar schauen, ist die Wahrscheinlichkeit, dass zwei Zeichenfolgen in einem Abstand kleiner als

sind, sehr gering. -------------------------------------------------- ----------------------- Im Sinne der folgenden BPP-Antwort gilt Folgendes: Bei einem konstanten Gradexpander mit n Eckpunkten und

markierten Eckpunkten wird die Wahrscheinlichkeit eines zufälligen Spaziergangs der Länge

n / 4

$n/4$

n / 2

$n/2$

O (t)

$O( t )$ einen markierten Scheitelpunkt verfehlt, beträgt

, wenn

2^{- Ω (t)}

$2^{-\Omega(t)}$

t = Ω (\log n)

$t = \Omega( \log n)$

Sariel Har-Peled

Antworten:

Impagliazzo und Zuckerman haben bewiesen (FOCS'89, siehe hier ), dass, wenn ein BPP-Algorithmus Zufallsbits verwendet, um eine Korrektheitswahrscheinlichkeit von mindestens 2/3 zu erreichen, dies durch Anwenden von Zufallsläufen auf Expandergraphen auf eine Korrektheitswahrscheinlichkeit verbessert werden kann von $r$ $1-2^{-k}$ unter Verwendung von Zufallsbits. ( Hinweis: Während die Autoren die spezifische Konstante 2/3 in der Zusammenfassung verwenden, kann sie durch jede andere Konstante ersetzt werden, die größer als 1/2 ist.) $O(r+k)$

Wenn wir , bedeutet dies , dass jeder BPP - Algorithmus, der eine konstante Fehlerwahrscheinlichkeit erreicht , wobei Zufallsbits können (nicht-trivialer) werden verbesserte Fehlerwahrscheinlichkeit haben . Also, (es sei denn, ich habe etwas falsch verstanden), die Fehlerwahrscheinlichkeit von $k=r$ $< 1/2$ $r$ $2^{-\Omega(r)}$ fürjedesBPP-Problemerreichbar. $\leq 2^{-\Omega(r)}$

Andras Farago
quelle

Das Problem bei solchen Verstärkungstechniken ist, dass sie den Algorithmus verlangsamen. Der neue Algorithmus verwendet möglicherweise nur O (r) Zufallsbits, seine Laufzeit beträgt jedoch r-mal (ursprüngliche Laufzeit). Wenn r beispielsweise in der Eingabegröße n mindestens linear ist (was normalerweise der Fall ist), haben Sie den Algorithmus nur um einen Faktor n verlangsamt.

Darüber

Ich bin mir nicht sicher, ob Sie das suchen, aber es hängt damit zusammen:

Angenommen, ich möchte eine zufällige Bit-Primzahl finden. Der übliche Algorithmus besteht darin, eine zufällige (ungerade) Bit-Ganzzahl auszuwählen und den Miller-Rabin-Primalitätstest für Runden darauf auszuführen und zu wiederholen, bis eine wahrscheinliche Primzahl gefunden wird. Wie groß ist die Wahrscheinlichkeit, dass diese Prozedur eine zusammengesetzte Zahl zurückgibt? Nenne diese Wahrscheinlichkeit . $k$ $k$ $t$ $p_{k,t}$

Die Standardanalyse des Miller-Rabin-Primalitätstests zeigt, dass Runden eine Ausfallwahrscheinlichkeit von höchstens . Dies impliziert zusammen mit dem Primzahlensatz $t$ $4^{-t}$

p_{k, t} \leq O (k \cdot 4^{- t}) .

$p_{k,t} \leq O(k\cdot 4^{-t}).$

$t=1$

p_{k, 1} \leq 2^{- (1 - o (1)) \frac{k \ln \ln k}{\ln k}} \leq 2^{- \tilde{Ω} (k)} .

$p_{k,1} \leq 2^{-(1-o(1))\frac{k \ln\ln k}{\ln k}} \leq 2^{-\tilde\Omega(k)}.$

Siehe Erdös und Pomerance (1986) , Kim und Pomerance (1989) und Dåmgard, Landrock und Pomerance (1993) für weitere Einzelheiten.

$O(k^2)$ $O(k)$

Thomas unterstützt Monica
quelle