Principe Minimax de Yao sur les algorithmes de Monte Carlo

Le célèbre principe Minimax de Yao établit la relation entre la complexité distributionnelle et la complexité aléatoire. Laissez $P$ un problème avec un ensemble fini des entrées et un ensemble fini de l' algorithme déterministe pour résoudre . Soit également la distribution d'entrée et let \ mathcal {R} la distribution de probabilité sur \ mathcal {A} . Le principe énonce alors \ min_ {A \ in \ mathcal {A}} \ quad \ mathbb {E} cost (A, \ mathcal {D}) \ leq \ max_ {x \ in \ mathcal {X}} \ quad \ mathbb {E} coût (\ mathcal {R}, x) \ quad \ quad \ text {pour tous $ \ mathcal {D} $ et $ \ mathcal {R} $}.$\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}$}.$$ Cette preuve découle directement du théorème de minimax de von Neumann pour les jeux à somme nulle.

La plupart du temps, le principe de Yao ne concerne que les algorithmes de Las Vegas , mais il peut être généralisé aux algorithmes de Monte Carlo comme suit.

$$\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]$}$$ où $cost_\epsilon(\cdot,\cdot)$ représente le coût des algorithmes de Monte Carlo qui errent la probabilité au plus $\epsilon$ .

Dans l'article original de Yao , la relation pour les algorithmes de Monte Carlo est donnée au Théorème 3 sans preuve. Une astuce pour le prouver?

Ceci est juste un commentaire étendu sur la réponse de Marcos, en utilisant sa notation. Je ne suis pas tout à fait en mesure de suivre les détails de son argument, et celui ci-dessous est assez court et facile.

En faisant la moyenne,

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

Le fait ci-dessus et l'inégalité de Markov impliquent .$\sum_{A \in \beta(2\lambda)}{q(A)} \geq 1/2$

Nous obtenons donc:

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

Je vais essayer ça. Je vais utiliser la notation originale de Yao. De cette façon, il sera plus facile de contraster avec son article et ses définitions.

Soit un ensemble fini d'entrées, et soit un ensemble fini d'algorithmes déterministes qui peuvent ne pas donner de réponse correcte pour certaines entrées. Soit également si donne la bonne réponse pour , et sinon. Notons également le nombre de requêtes effectuées par sur l'entrée , ou de manière équivalente, la profondeur de l' arbre de décision 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$

Coût moyen: étant donné une distribution de probabilité sur I , le coût moyen d'un algorithme A ∈ A 0 est 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)$

Complexité distributionnelle: Soit . Pour toute distribution d sur les entrées, soit β ( λ ) le sous-ensemble de A 0 donné par β ( λ ) = { 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\}$. La complexité distributionnelle avec l'erreur pour un problème de calcul P est définie comme 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)$

-tolérance:$\lambda$Une distribution sur la famille A 0 est λ -tolérante si 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$

Coût prévu: Pour un algorithme randomisé , soit q une distribution de probabilité qui est tolérante à λ sur A 0 . Le coût attendu de R pour une entrée donnée x est E ( R , x ) = ∑ A ∈ A 0 q ( A ) ⋅ r ( A , x ) .$R$$q$$\lambda$$\mathcal{A}_0$$R$$x$$E(R,x)=\sum_{A\in \mathcal{A}_0} q(A)\cdot r(A,x)$

Complexité aléatoire: Soit . La complexité aléatoire avec l'erreur λ est 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)$

Nous sommes maintenant prêts à nous lancer en affaires. Ce que nous voulons prouver est donné une distribution sur les entrées et un algorithme randomisé R (ie, une distribution q sur A 0 )$d$$R$$q$$\mathcal{A}_0$

Principe Minimax de Yao pour les algorithmes de Montecarlo pourλ∈[0,une/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]$

Je suivrai une approche donnée par Fich, Meyer auf der Heide, Ragde et Wigderson (voir Lemme 4). Leur approche ne donne pas de caractérisation pour les algorithmes de Las Vegas (seulement la borne inférieure), mais elle est suffisante pour nos besoins. D'après leur preuve, il est facile de voir que pour tout et $\mathcal{A}_0$$\mathcal{I}$

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

Pour obtenir les bons chiffres, nous ferons quelque chose de similaire. Étant donné que la distribution de probabilité donnée par l'algorithme randomisé R est λ -tolérante sur A 0, nous avons que $q$$R$$\lambda$$\mathcal{A}_0$ Si nous remplaçons la familleA0parβ(2λ),nous voyons 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*}$$

où la deuxième inégalité suit parce que , et la dernière inégalité est donnée par la définition de β ( 2 λ ) où la somme divisée par 2 ne peut pas être supérieure à λ . Par conséquent, max x ∈ I { ∑ A ∈ 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}$$

En notant que correspond à { 0 , 1 } et r correspond à N et à la revendication 1 ci-dessus, nous pouvons maintenant remplacer en toute sécurité la fonction ϵ dans l'inégalité ci-dessus par r ( A , x ) pour obtenir l'inégalité souhaitée.$\epsilon$$\{0,1\}$$r$$\mathbb{N}$$\epsilon$$r(A,x)$