Yaos Minimax-Prinzip für Monte-Carlo-Algorithmen

Das berühmte Minimax-Prinzip von Yao beschreibt die Beziehung zwischen Verteilungskomplexität und randomisierter Komplexität. Sei ein Problem mit einer endlichen Menge von Eingaben und einer endlichen Menge von deterministischen Algorithmen, um zu lösen . Außerdem bezeichnen die Eingabeverteilung und die Wahrscheinlichkeitsverteilung für . Dann lautet das Prinzip $P$$\mathcal{X}$$\mathcal{A}$$P$$\mathcal{D}$$\mathcal{R}$$\mathcal{A}$

$$\min_{A\in\mathcal{A}}\quad\mathbb{E} cost(A,\mathcal{D}) \leq \max_{x\in\mathcal{X}}\quad\mathbb{E} cost(\mathcal{R},x) \quad\quad\text{for all $\mathcal{D}$ and $\mathcal{R}$}.$$ Dieser Beweis folgt direkt aus von Neumanns Minimaxsatz für Nullsummenspiele.

Meistens befasst sich Yaos Prinzip nur mit Las Vegas-Algorithmen , aber es kann wie folgt auf Monte-Carlo-Algorithmen verallgemeinert werden. wobei cost_ \ epsilon (\ cdot, \ cdot) die Kosten von Monte-Carlo-Algorithmen bezeichnet, bei denen die Wahrscheinlichkeit höchstens \ epsilon falsch ist .

$$\frac12 \min_{A\in\mathcal{A}}\quad\mathbb{E} cost_{2\epsilon}(A,\mathcal{D}) \leq \max_{x\in\mathcal{X}}\quad\mathbb{E} cost_{\epsilon}(\mathcal{R},x)\quad\quad\text{for all $\mathcal{D}$, $\mathcal{R}$ and $\epsilon\in [0,1/2]$}$$ $cost_\epsilon(\cdot,\cdot)$$\epsilon$

In Yaos Originalarbeit ist die Beziehung für Monte-Carlo-Algorithmen in Satz 3 ohne Beweis angegeben. Irgendein Hinweis, um es zu beweisen?

Dies ist nur ein ausführlicher Kommentar zu Marcos 'Antwort in seiner Notation. Ich bin nicht in der Lage, den Einzelheiten seines Arguments zu folgen, und das folgende ist ziemlich kurz und einfach.

Durch wird

$$\sum_A{q(A)\sum_x{d(x)\epsilon(A, x)}} = \sum_x{d(x)\sum_A{q(A)\epsilon(A, x)}} \leq \lambda.$$

Die obige Tatsache und Markovs Ungleichung implizieren .$\sum_{A \in \beta(2\lambda)}{q(A)} \geq 1/2$

So bekommen wir:

$$\begin{align*} \max_x \sum_A{q(A)r(A,x)} &\geq \sum_x{d(x)\sum_A{q(A)r(A, x)}}\\ &= \sum_A{q(A)\sum_x{d(x)r(A, x)}}\\ &\geq \sum_{A \in \beta(2\lambda)}{q(A)\sum_x{d(x)r(A, x)}}\\ &\geq \left(\sum_{A \in \beta(2\lambda)}{q(A)}\right) \min_{A \in \beta(2\lambda)}{\sum_x{d(x)r(A, x)}}\\ &\geq \frac{1}{2}\min_{A \in \beta(2\lambda)}{\sum_x{d(x)r(A, x)}} \end{align*}$$

Ich werde es versuchen. Ich werde die Originalnotation von Yao verwenden. Auf diese Weise wird es einfacher, einen Kontrast zu seinem Papier und seinen Definitionen herzustellen.

Sei eine endliche Menge von Eingaben, und sei eine endliche Menge von deterministischen Algorithmen, die auf einige Eingaben möglicherweise keine korrekte Antwort geben. Lassen Sie auch wenn die richtige Antwort für liefert , und wenn nicht. Bezeichnen Sie mit die Anzahl der Abfragen, die bei Eingabe von , oder äquivalent die Tiefe des Entscheidungsbaums vonI A 0 ≤ ( A , x ) = 0 A x ≤ ( A , x ) = 1 r ( A , x ) A x $\mathcal{I}$$\mathcal{A}_0$$\epsilon(A,x)=0$$A$$x$$\epsilon(A,x)=1$$r(A,x)$$A$$x$$A$

Durchschnittskosten: Bei gegebener Wahrscheinlichkeitsverteilung$d$ auf I , die durchschnittlich Kosten einen Algorithmus ist .$\mathcal{I}$$A\in \mathcal{A}_0$$C(A,d)=\sum_{x\in\mathcal{I}} d(x)\cdot r(A,x)$

Verteilungskomplexität: Sei . Für jede Verteilung auf den Eingaben sei die Teilmenge von gegeben durch . Die Verteilungskomplexität mit Fehler für ein Rechenproblem ist definiert als .$\lambda\in[0,1]$$d$$\beta(\lambda)$$\mathcal{A}_0$$\beta(\lambda)=\{A : A\in \mathcal{A}_0, \sum_{x\in\mathcal{I}} d(x)\cdot \epsilon(A,x)\leq \lambda\}$$\lambda$$P$$F_{1,\lambda}(P)=\max_{d} \min_{A\in \beta(\lambda)} C(A,d)$

$\lambda$ -toleranz: Eine Verteilung auf die Familie ist -tolerant, wenn .$q$$\mathcal{A}_0$$\lambda$$\max_{x\in \mathcal{I}} \sum_{A\in\mathcal{A}_0} q(A)\cdot \epsilon(A,x)\leq \lambda$

Erwartete Kosten: Für einen randomisierten Algorithmus sei eine Wahrscheinlichkeitsverteilung, die tolerant für . Die erwarteten Kosten von für eine gegebene Eingabe sind .$R$$q$$\lambda$$\mathcal{A}_0$$R$$x$$E(R,x)=\sum_{A\in \mathcal{A}_0} q(A)\cdot r(A,x)$

Randomisierte Komplexität: Lassen Sie . Die randomisierte Komplexität mit dem Fehler ist .$\lambda\in[0,1]$$\lambda$$F_{2,\lambda}=\min_R \max_{x\in\mathcal{I}} E(R,x)$

Jetzt sind wir bereit, ins Geschäft einzusteigen. Was wir beweisen wollen, ist eine Verteilung auf die Eingaben und ein randomisierter Algorithmus (dh eine Verteilung auf ).$d$$R$$q$$\mathcal{A}_0$

Yaos Minimax-Prinzip für Montecarlo-Algorithmen für .

$$\begin{equation}\max_{x\in\mathcal{I}} E(R,x)\geq \frac{1}{2}\min_{A\in \beta(2\lambda)} C(A,d) \end{equation}$$ $\lambda\in[0,1/2]$

Ich werde einem Ansatz von Fich, Meyer auf der Heide, Ragde und Wigderson folgen (siehe Lemma 4). Ihr Ansatz liefert keine Charakterisierung für Las Vegas-Algorithmen (nur die untere Schranke), ist aber für unsere Zwecke ausreichend. Aus ihrem Beweis ist es leicht zu ersehen, dass und$\mathcal{A}_0$$\mathcal{I}$

1. .$\max_{x\in \mathcal{I}} E(R,x)\geq \min_{A\in \mathcal{A}_0} C(A,d)$

Um dort die richtigen Zahlen zu erhalten, werden wir etwas Ähnliches tun. Da die Wahrscheinlichkeitsverteilung durch die randomisierten Algorithmus gegeben ist -toleranten auf wir haben , dass Wenn wir die Familie durch ersetzen$q$$R$$\lambda$$\mathcal{A}_0$

$$\begin{align*} \lambda &\geq \max_{x\in \mathcal{I}}\left\{ \sum_{A\in\mathcal{A}_0} q(A)\cdot \epsilon(A,x) \right\}\\ &\geq \sum_{x\in\mathcal{I}} d(x) \sum_{A\in \mathcal{A}_0} q(a)\cdot \epsilon(A,x)\\ &= \sum_{A\in \mathcal{A}_0} q(a)\sum_{x\in\mathcal{I}} d(x) \cdot \epsilon(A,x)\\ &\geq \min_{A\in \mathcal{A}_0}\left\{ \sum_{x\in\mathcal{I}} d(x) \cdot \epsilon(A,x) \right\}. \end{align*}$$ $\mathcal{A}_0$$\beta(2\lambda)$ wir sehen das

$$\begin{align*} \lambda &\geq \max_{x\in \mathcal{I}}\left\{ \sum_{A\in\mathcal{A}_0} q(A)\cdot \epsilon(A,x) \right\}\\ &\geq \max_{x\in \mathcal{I}}\left\{ \sum_{A\in\beta(2\lambda)} q(A)\cdot \epsilon(A,x) \right\}\\ &\geq \sum_{x\in\mathcal{I}} d(x) \sum_{A\in \beta(2\lambda)} q(a)\cdot \epsilon(A,x)\\ &= \sum_{A\in \beta(2\lambda)} q(a)\sum_{x\in\mathcal{I}} d(x) \cdot \epsilon(A,x)\\ &\geq \min_{A\in \beta(2\lambda)}\left\{ \frac{1}{2}\sum_{x\in\mathcal{I}} d(x) \cdot \epsilon(A,x) \right\}, \end{align*}$$

wobei die zweite Ungleichung folgt, weil und die letzte Ungleichung durch die Definition von wobei die durch 2 geteilte Summe nicht größer sein kann als . Daher $\beta(2\lambda) \subseteq \mathcal{A}_0$$\beta(2\lambda)$$\lambda$

$$\begin{equation}\max_{x\in \mathcal{I}}\left\{ \sum_{A\in\mathcal{A}_0} q(A)\cdot \epsilon(A,x) \right\}\geq\frac{1}{2} \min_{A\in \beta(2\lambda)}\left\{ \sum_{x\in\mathcal{I}} d(x) \cdot \epsilon(A,x) \right\}. \end{equation}$$

Indem wir feststellen, dass auf und auf und Anspruch 1 oben abgebildet sind, können wir jetzt die Funktion in der obigen Ungleichung sicher durch ersetzen , um zu erhalten die gewünschte Ungleichung.$\epsilon$$\{0,1\}$$r$$\mathbb{N}$$\epsilon$$r(A,x)$