Princípio Minimax de Yao sobre algoritmos de Monte Carlo

O célebre Princípio Minimax de Yao declara a relação entre complexidade distributiva e complexidade aleatória. Vamos haver um problema com um conjunto finito de entradas e um conjunto finito do algoritmo determinista para resolver . Também deixe denotar a distribuição de entrada e denote a distribuição de probabilidade em . O princípio declara $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}$}.$$ Essa prova segue diretamente do teorema do minimax de von Neumann para jogos de soma zero.

Principalmente o princípio de Yao trata apenas dos algoritmos de Las Vegas , mas pode ser generalizado para os algoritmos de Monte Carlo da seguinte forma.

$$\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]$}$$ onde $cost_\epsilon(\cdot,\cdot)$ denota o custo dos algoritmos de Monte Carlo que erram probabilidade no máximo $\epsilon$ .

No artigo original de Yao , a relação para os algoritmos de Monte Carlo é dada no Teorema 3 sem prova. Alguma dica para provar isso?

Este é apenas um comentário estendido sobre a resposta de Marcos, usando sua notação. Não sou capaz de acompanhar os detalhes de seu argumento, e o abaixo é bem curto e fácil.

média,

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

O fato acima e a desigualdade de Markov implicam .$\sum_{A \in \beta(2\lambda)}{q(A)} \geq 1/2$

Então temos:

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

Vou tentar isso. Vou usar a notação original de Yao. Dessa forma, será mais fácil contrastar com seu artigo e suas definições.

Seja um conjunto finito de entradas e seja um conjunto finito de algoritmos determinísticos que podem falhar em fornecer uma resposta correta para algumas entradas. Deixe também se fornecer a resposta correta para , e caso contrário. Denote também por o número de consultas feitas por na entrada , ou equivalente, a profundidade da árvore de decisão deA 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$

Custo médio: dada uma distribuição de probabilidade em , o custo médio de um algoritmo é .$d$$\mathcal{I}$$A\in \mathcal{A}_0$$C(A,d)=\sum_{x\in\mathcal{I}} d(x)\cdot r(A,x)$

Complexidade distributiva: Let . Para qualquer distribuição nas entradas, seja o subconjunto de fornecido por . A complexidade distributiva com erro para um problema computacional é definida como .$\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$ tolerância: Uma distribuição na família é tolerante se .$q$$\mathcal{A}_0$$\lambda$$\max_{x\in \mathcal{I}} \sum_{A\in\mathcal{A}_0} q(A)\cdot \epsilon(A,x)\leq \lambda$

Custo esperado: para um algoritmo aleatório , seja uma distribuição de probabilidade tolerante a em . O custo esperado de para uma determinada entrada é .$R$$q$$\lambda$$\mathcal{A}_0$$R$$x$$E(R,x)=\sum_{A\in \mathcal{A}_0} q(A)\cdot r(A,x)$

Complexidade aleatória: Let . A complexidade aleatória com o erro é .$\lambda\in[0,1]$$\lambda$$F_{2,\lambda}=\min_R \max_{x\in\mathcal{I}} E(R,x)$

Agora estamos prontos para entrar nos negócios. O que queremos provar é dada uma distribuição nas entradas e um algoritmo aleatório (ou seja, uma distribuição em )$d$$R$$q$$\mathcal{A}_0$

Princípio Minimax de Yao para algoritmos de Montecarlo para .

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

Vou seguir uma abordagem dada por Fich, Meyer auf der Heide, Ragde e Wigderson (ver Lema 4). Sua abordagem não produz uma caracterização para os algoritmos de Las Vegas (apenas o limite inferior), mas é suficiente para nossos propósitos. Pela prova deles, é fácil ver que, para qualquer e$\mathcal{A}_0$$\mathcal{I}$

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

Para obter os números corretos, faremos algo semelhante. Dado que a distribuição de probabilidade dada pelo algoritmo aleatório$q$$R$ é tolerante em A 0 , temos que $\lambda$$\mathcal{A}_0$ Se substituirmos a famíliaA0porβ(2λ), vemos que

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

onde a segunda desigualdade segue porque , e a última desigualdade é dada pela definição de β ( 2 λ ) onde a soma dividida por 2 não pode ser maior que λ . Assim, max x ∈ I { Σ Um ∈ A 0 q ( A ) ⋅ £ ( A , x ) } ≥ $\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}$$

De notar que a mapeia a { 0 , 1 } e r mapeia para N e acordo com a reivindicação 1 acima, podemos agora seguramente substituir a função ε na desigualdade acima por R ( A , x ) para se obter o desejado desigualdade.$\epsilon$$\{0,1\}$$r$$\mathbb{N}$$\epsilon$$r(A,x)$