Zasada Minimax Yao dotycząca algorytmów Monte Carlo

Słynny Yao Minimax Zasada stwierdza zależność między złożonością i dystrybucyjnej randomizowanym złożoności. Niech $P$ być problemu ze skończonego zbioru wejść i skończonego zbioru deterministycznego algorytmu rozwiązania . Niech także oznacza rozkład wejściowy, a niech oznacza rozkład prawdopodobieństwa na . Następnie zasada głosi: $\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}$}.$$ Dowód ten wynika bezpośrednio z twierdzenia von Neumanna o grach o sumie zerowej.

Głównie zasada Yao dotyczy tylko algorytmów Las Vegas , ale można ją uogólnić na algorytmy Monte Carlo w następujący sposób.

$$\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]$}$$ gdzie $cost_\epsilon(\cdot,\cdot)$ oznacza koszt algorytmów Monte Carlo, które mylą prawdopodobieństwo co najwyżej $\epsilon$ .

W oryginalnym artykule Yao związek między algorytmami Monte Carlo podano w Twierdzeniu 3 bez dowodu. Jakaś wskazówka na potwierdzenie tego?

To tylko rozszerzony komentarz do odpowiedzi Marcosa, z wykorzystaniem jego zapisu. Nie jestem w stanie śledzić szczegółów jego argumentu, a ten poniżej jest dość krótki i łatwy.

Uśredniając,

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

Powyższy fakt i nierówność Markowa implikują .$\sum_{A \in \beta(2\lambda)}{q(A)} \geq 1/2$

Otrzymujemy więc:

$$\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*}$$

Spróbuję tego. Użyję oryginalnej notacji Yao. W ten sposób łatwiej będzie kontrastować z jego opracowaniem i jego definicjami.

Niech skończonym zestawem danych wejściowych, a A 0 będzie skończonym zestawem deterministycznych algorytmów, które mogą nie dać poprawnej odpowiedzi dla niektórych danych wejściowych. Niech także ϵ ( A , x ) = 0, jeśli A daje poprawną odpowiedź dla x , a ϵ ( A , x ) = 1 w przeciwnym razie. Oznacz również przez r ( A , x ) liczbę zapytań wykonanych przez A na wejściu x lub równoważnie głębokość $\mathcal{I}$$\mathcal{A}_0$$\epsilon(A,x)=0$$A$$x$$\epsilon(A,x)=1$$r(A,x)$$A$$x$$A$drzewo decyzyjne.

Koszt średni: Biorąc pod uwagę rozkład prawdopodobieństwa na I , średni koszt algorytmu A ∈ A 0 wynosi C ( A , d ) = ∑ x ∈ I d ( x ) ⋅ r ( A , x ) .$d$$\mathcal{I}$$A\in \mathcal{A}_0$$C(A,d)=\sum_{x\in\mathcal{I}} d(x)\cdot r(A,x)$

Złożoność dystrybucyjna: Niech . Dla dowolnego rozkładu d na wejściach, niech β ( λ ) będzie podzbiorem A 0 podanym przez β ( λ ) = { A : A ∈ A 0 , ∑ x ∈ I d ( x ) ⋅ ϵ ( A , x ) ≤ λ $\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\}$. Złożoność dystrybucyjna z błędem dla problemu obliczeniowego P jest zdefiniowana jako F 1 , λ ( P ) = max d min A ∈ β ( λ ) C ( A , d ) .$\lambda$$P$$F_{1,\lambda}(P)=\max_{d} \min_{A\in \beta(\lambda)} C(A,d)$

tolerancja:$\lambda$rozkład w rodzinie A 0 jest λ - tolerancyjny, jeśli max x ∈ I ∑ A ∈ A 0 q ( A ) ⋅ ϵ ( A , x ) ≤ λ .$q$$\mathcal{A}_0$$\lambda$$\max_{x\in \mathcal{I}} \sum_{A\in\mathcal{A}_0} q(A)\cdot \epsilon(A,x)\leq \lambda$

Oczekiwany koszt: Dla algorytmu randomizowanego , niech q będzie rozkładem prawdopodobieństwa, który jest tolerancyjny dla λ na A 0 . Przewidywane koszty z R dla danego wejścia x jest E ( R , x ) = Σ ∈ 0 P ( ) ⋅ R ( , x ) .$R$$q$$\lambda$$\mathcal{A}_0$$R$$x$$E(R,x)=\sum_{A\in \mathcal{A}_0} q(A)\cdot r(A,x)$

Losowość złożoności: Niech . Losowa złożoność z błędem λ wynosi F 2 , λ = min R max x ∈ I E ( R , x ) .$\lambda\in[0,1]$$\lambda$$F_{2,\lambda}=\min_R \max_{x\in\mathcal{I}} E(R,x)$

Teraz jesteśmy gotowi do rozpoczęcia działalności. To, co chcemy udowodnić, to rozkład na wejściach i losowy algorytm R (tj. Rozkład q na A 0 )$d$$R$$q$$\mathcal{A}_0$

Zasada minimów Yao dla algorytmów Montecarlo dlaÎ∈[0,1/2].

$$\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]$

Podążę za podejściem Ficha, Meyera auf der Heide, Ragde i Wigderson (patrz Lemat 4). Ich podejście nie daje charakterystyki algorytmów Las Vegas (tylko dolna granica), ale jest wystarczające do naszych celów. Z ich dowodu łatwo zauważyć, że dla każdego i $\mathcal{A}_0$$\mathcal{I}$

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

Aby uzyskać tam prawidłowe liczby, zrobimy coś podobnego. Biorąc pod uwagę, że rozkład prawdopodobieństwa podany przez randomizowany algorytm R jest λ- tolerancyjny na A 0 , mamy to $q$$R$$\lambda$$\mathcal{A}_0$ Jeśli zastąpimy rodzinę0zβ(2λ)widzimy, że

$$\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)$

$$\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*}$$

$\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}$$

By noting that $\epsilon$ maps to $\{0,1\}$ and $r$ maps to $\mathbb{N}$ and Claim 1 above, now we can safely replace the function $\epsilon$ in the inequality above by $r(A,x)$ to obtain the desired inequality.