Princípio Minimax de Yao sobre algoritmos de Monte Carlo

22

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 PXAPDRA

minAAEcost(A,D)maxxXEcost(R,x)for all D and 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.

12minAAEcost2ϵ(A,D)maxxXEcostϵ(R,x)for all DR and ϵ[0,1/2]
onde costϵ(,) denota o custo dos algoritmos de Monte Carlo que erram probabilidade no máximo ϵ .

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?

Federico Magallanez
fonte

Respostas:

6

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,

UMAq(UMA)xd(x)ϵ(UMA,x)=xd(x)UMAq(UMA)ϵ(UMA,x)λ.

O fato acima e a desigualdade de Markov implicam .UMAβ(2λ)q(UMA)1/2

Então temos:

maxxAq(A)r(A,x)xd(x)Aq(A)r(A,x)=Aq(A)xd(x)r(A,x)Aβ(2λ)q(A)xd(x)r(A,x)(Aβ(2λ)q(A))minAβ(2λ)xd(x)r(A,x)12minAβ(2λ)xd(x)r(A,x)
Sasho Nikolov
fonte
8

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 AIA0ϵ(A,x)=0Axϵ(A,x)=1r(A,x)AxA

Custo médio: dada uma distribuição de probabilidade em , o custo médio de um algoritmo é .eudIAA0C(A,d)=xId(x)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 .λ[0,1]dβ(λ)A0β(λ)={A:AA0,xId(x)ϵ(A,x)λ}λPF1,λ(P)=maxdminAβ(λ)C(A,d)

λ tolerância: Uma distribuição na família é tolerante se .qA0λmaxxIAA0q(A)ϵ(A,x)λ

Custo esperado: para um algoritmo aleatório , seja uma distribuição de probabilidade tolerante a em . O custo esperado de para uma determinada entrada é .RqλA0RxE(R,x)=AA0q(A)r(A,x)

Complexidade aleatória: Let . A complexidade aleatória com o erro é .λ[0,1]λF2,λ=minRmaxxIE(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 )dRqA0

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

maxxIE(R,x)12minAβ(2λ)C(A,d)
λ[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 eA0I

Reivindicação 1. .maxxIE(R,x)minAA0C(A,d)

Para obter os números corretos, faremos algo semelhante. Dado que a distribuição de probabilidade dada pelo algoritmo aleatórioqR é tolerante em A 0 , temos que λλA0 Se substituirmos a famíliaA0porβ(2λ), vemos que

λmaxxI{AA0q(A)ϵ(A,x)}xId(x)AA0q(a)ϵ(A,x)=AA0q(a)xId(x)ϵ(A,x)minAA0{xId(x)ϵ(A,x)}.
A0β(2λ)

λmaxxI{AA0q(A)ϵ(A,x)}maxxI{Aβ(2λ)q(A)ϵ(A,x)}xId(x)Aβ(2λ)q(a)ϵ(A,x)=Aβ(2λ)q(a)xId(x)ϵ(A,x)minAβ(2λ){12xId(x)ϵ(A,x)},

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 ) }1β(2λ)A0β(2λ)λ

maxxI{AA0q(A)ϵ(A,x)}12minAβ(2λ){xId(x)ϵ(A,x)}.

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.ϵ{0,1}rNϵr(A,x)

Marcos Villagra
fonte
Existe uma breve explicação de onde vem o fator 2?
Robin Kothari 11/11
em resumo, vem da definição de . O somatório da definição dividida por 2 é no máximo λ . β(2λ)λ
Marcos Villagra
maxAβ(2λ)){12xId(x),ϵ(A,x)}λ
ϵr
em relação à sua primeira pergunta, adicionei mais detalhes.
Marcos Villagra