Principio Minimax de Yao sobre algoritmos de Monte Carlo

22

PXAPDRA

minAAEcost(A,D)maxxXEcost(R,x)for all D and R.

El principio de Yao se ocupa principalmente de los algoritmos de Las Vegas únicamente, pero se puede generalizar a los algoritmos de Monte Carlo de la siguiente manera. donde denota el costo de los algoritmos de Monte Carlo que tienen un error de probabilidad como máximo .

12minAAEcost2ϵ(A,D)maxxXEcostϵ(R,x)for all DR and ϵ[0,1/2]
costϵ(,)ϵ

En el artículo original de Yao , la relación para los algoritmos de Monte Carlo se da en el Teorema 3 sin pruebas. ¿Alguna pista para probarlo?

Federico Magallanez
fuente

Respuestas:

6

Esto es solo un comentario extenso sobre la respuesta de Marcos, usando su notación. No puedo seguir los detalles de su argumento, y el siguiente es bastante corto y fácil.

Al promediar,

Aq(A)xd(x)ϵ(A,x)=xd(x)Aq(A)ϵ(A,x)λ.

El hecho anterior y la desigualdad de Markov implican .Aβ(2λ)q(A)1/2

Entonces obtenemos:

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
fuente
8

Lo intentaré con esto. Voy a usar la notación original de Yao. De esta manera será más fácil contrastar con su trabajo y sus definiciones.

Sea un conjunto finito de entradas, y sea un conjunto finito de algoritmos deterministas que pueden fallar al dar una respuesta correcta para algunas entradas. Supongamos también si da la respuesta correcta para , y caso contrario. Denote también por el número de consultas realizadas por en la entrada , o de manera equivalente, la profundidad del árbol de decisión deIA0ϵ(A,x)=0Axϵ(A,x)=1r(A,x)AxA

Costo promedio: Dada una distribución de probabilidad en , el costo promedio de un algoritmo es .dIAA0C(A,d)=xId(x)r(A,x)

Complejidad de distribución: Let . Para cualquier distribución en las entradas, dejemos que sea ​​el subconjunto de dado por . La complejidad distributiva con error para un problema computacional se define como .λ[0,1]dβ(λ)A0β(λ)={A:AA0,xId(x)ϵ(A,x)λ}λPF1,λ(P)=maxdminAβ(λ)C(A,d)

λ -tolerancia: una distribución en la familia es -tolerante si .qA0λmaxxIAA0q(A)ϵ(A,x)λ

Costo esperado: Para un algoritmo aleatorio , sea una distribución de probabilidad que sea -tolerante en . El costo esperado de para una entrada dada es .RqλA0RxE(R,x)=AA0q(A)r(A,x)

Complejidad aleatoria: Let . La complejidad aleatoria con error es .λ[0,1]λF2,λ=minRmaxxIE(R,x)

Ahora estamos listos para entrar en el negocio. Lo que queremos probar es una distribución en las entradas y un algoritmo aleatorio (es decir, una distribución en )dRqA0

Principio Minimax de Yao para Algoritmos de Montecarlo para .

maxxIE(R,x)12minAβ(2λ)C(A,d)
λ[0,1/2]

Seguiré un enfoque dado por Fich, Meyer auf der Heide, Ragde y Wigderson (ver Lema 4). Su enfoque no proporciona una caracterización para los algoritmos de Las Vegas (solo el límite inferior), pero es suficiente para nuestros propósitos. Según su prueba, es fácil ver que para cualquier yA0I

Reclamación 1. .maxxIE(R,x)minAA0C(A,d)

Para obtener los números correctos allí, haremos algo similar. Dado que la distribución de probabilidad dada por el algoritmo aleatorio es -tolerante en tenemos que Si reemplazamos la familia conqRλA0

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

λ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)},

donde sigue la segunda desigualdad porque , y la última desigualdad viene dada por la definición de donde la suma dividida por 2 no puede ser mayor que . Por lo tanto, β(2λ)A0β(2λ)λ

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

Al observar que asigna a y asigna a y la Reclamación 1 anterior, ahora podemos reemplazar con seguridad la función en la desigualdad anterior por para obtener La desigualdad deseada.ϵ{0,1}rNϵr(A,x)

Marcos Villagra
fuente
¿Hay una breve explicación de dónde viene el factor 2?
Robin Kothari
en resumen, proviene de la definición de . La suma en la definición dividida por 2 es como máximo . β(2λ)λ
Marcos Villagra
Algo me parece extraño. por definición, entonces, ¿por qué el min? maxAβ(2λ)){12xId(x),ϵ(A,x)}λ
Sasho Nikolov
Y no entiendo la última oración. ¿Cómo hizo un argumento completo sobre y luego lo reemplazó con ? ϵr
Sasho Nikolov
con respecto a su primera pregunta, agregué más detalles.
Marcos Villagra