Verstärkungslemma

Einfache Sprache

Das Verstärkungslemma ist eine Methode, die Fehlerwahrscheinlichkeit einer Probabilistische Turingmaschine exponentiell zu verkleinern. Einzige Voraussetzung ist, das die Fehlerwahrscheinlichkeit kleiner als $\frac{1}{2}$ ist.

Def. Verstärkungslemma

Sei $\varepsilon$ eine Konstante zwischen $0$ und $\frac{1}{2}$. Dann gilt für jedes Polynom $p(n)$, dass eine in Polynomialzeit laufende Probabilistische Turingmaschine $M_1$ die eine Fehlerwahrscheinlichkeit von $\varepsilon$ hat, eine äquivalente in Polynomialzeit laufende Probabilistische Turingmaschine $M_2$ mit einer Fehlerwahrscheinlichkeit von $2^{-p(n)}$ hat.

Idee: $M_2$ simuliert $M_1$ polynomial oft und gibt das Ergebnis aus, was am häufigsten vorkam. Folgendes Bespiel erklärt den Ansatz:

Verstärkungslemma Beispiel

Sei $\varepsilon =\frac{1}{3}$. Stell dir eine Behälter mit roten und blauen Kugeln vor. Wir wissen das eine Farbe $\frac{1}{3}$ Häufig vorkommt und die andere Farbe $\frac{2}{3}$ Häufig vorkommt. Wir wissen aber nicht welche Farbe häufig vorkommt. Wenn wir nun z.B. $100$ eine Kugel aus dieser Box ziehen, können wir ermitteln, welche Farbe häufiger vorkommt. Je größer die Stichprobe, desto sicherer können wir über das Ergebnis sein. Tatsächlich schrumpft die Wahrscheinlichkeit exponentiell mit der Größe der Stichprobe.

In diesem Beispiel sind die Kugeln eine Metapher für eine möglichen Berechnungen. Die Farben sind jeweils das akzeptieren oder verwerfen einer Berechnung.

Beweis: Gegeben ein Polynom $p(n)$ und eine Probabilistische Turingmaschine $M_1$, die eine Sprache $A$ entscheidet mit einer Fehlerwahrscheinlichkeit $\varepsilon\leq \frac{1}{2}$. Wir konstruieren eine Probabilistische Turingmaschine $M_2$, die $A$ mit einer Fehlerwahrscheinlichkeit von $2^{-p(n)}$ entscheidet. $M_2$ funktioniere wie folgt für die Eingabe $w$:

1. Berechne $k$ (siehe unten),
2. Simuliere $2k$ mal $M_1$ auf $w$ und speicher die Ergebnisse.
3. Falls die Mehrheit der Simulationen akzeptiert, akzeptiere. Sonst verwerfe.

Gegeben diese $2k$ Ergebnisse aus Schritt 2, schätzen wir die Wahrscheinlichkeit das mehr als die Hälfte der Ergebnisse Falsch sind: Sei $S$ die Folge der Ergebnisse aus Schritt 2. Jedes der $2k$ Ergebnisse aus $S$ ist entweder Richtig oder Falsch. Sei $c$ die Anzahl der richtigen Ergebnisse und $w$ die Anzahl der falschen Ergebnisse. Dann gilt $c+w=2k$. Falls $M_2$ die Ergebnisfolge $S$ produziert hat mit $c\leq w$, dann gibt $M_2$ das falsche Ergebnis aus. Wir nennen $S$ in diesem Fall eine schlechte Ergebnisfolge. Sei $\varepsilon_x$ die Wahrscheinlichkeit das $M_1$ für die Eingabe $w$ falsch liegt. Ist $S$ eine schlechte Ergebnisfolge. Bemerke dass

1. $\varepsilon_x\leq \varepsilon <\frac{1}{2}\implies \varepsilon_x(1-\varepsilon_x)\leq \varepsilon(1-\varepsilon)$,
2. $c\leq w$,
3. $k\leq w$ und
4. $\varepsilon < 1-\varepsilon$. Daraus folgt folgende Gleichung für $P_S$, die Wahrscheinlichkeit für dieses Ergebnis, als $$\begin{align}P_S&\leq (\varepsilon_x)^w(1-\varepsilon_x)^c &\Huge|\normalsize\text{Def. S}\\&\leq \varepsilon^w(1-\varepsilon)^c &\Huge|\normalsize\text{Siehe 1. und 2.}\\&\leq \varepsilon^k(1-\varepsilon)^k &\Huge|\normalsize\text{Siehe 3. und 4. }\\\end{align}$$

Wenn wir nun die Wahrscheinlichkeiten $P_S$ für alle schlechten Ergebnisfolgen $S$ aufsummieren, dann erhalten wir die Wahrscheinlichkeit dass $M_2$ das falsche Ergebnis ausgibt. Wir haben höchstens $2^{2k}$ schlechte Ergebnisfolgen, da $2^{2k}$ die Anzahl an möglichen Ergebnisfolgen ist. Also ergibt sich

Da $\varepsilon < \frac{1}{2}$ ist $4\varepsilon(1-\varepsilon)< 1$. Also schrumpft die obere Wahrscheinlichkeit exponentiell in $k$ und daher auch die Fehlerwahrscheinlichkeit von $M_2$. Um ein $k$ zu wählen, das die Fehlerwahrscheinlichkeit von $M_2$ von Oben mit $2^{-t}$ beschränkt für beliebiges $t\geq 1$, sei $\alpha = -\log_2(4\varepsilon(1-\varepsilon))$ und wähle $l\geq \frac{t}{a}$. Wir erhalten so eine Fehlerwahrscheinlichkeit für $M_1$ von $2^{-p(n)}$ in Polynomialzeit.