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 .dIA∈A0C(A,d)=∑x∈Id(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:A∈A0,∑x∈Id(x)⋅ϵ(A,x)≤λ}λPF1,λ(P)=maxdminA∈β(λ)C(A,d)
λ -tolerancia: una distribución en la familia es -tolerante si .qA0λmaxx∈I∑A∈A0q(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)=∑A∈A0q(A)⋅r(A,x)
Complejidad aleatoria: Let . La complejidad aleatoria con error es .λ∈[0,1]λF2,λ=minRmaxx∈IE(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 .
maxx∈IE(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. .maxx∈IE(R,x)≥minA∈A0C(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
λ≥maxx∈I{∑A∈A0q(A)⋅ϵ(A,x)}≥∑x∈Id(x)∑A∈A0q(a)⋅ϵ(A,x)=∑A∈A0q(a)∑x∈Id(x)⋅ϵ(A,x)≥minA∈A0{∑x∈Id(x)⋅ϵ(A,x)}.
A0β(2λ) vemos eso
λ≥maxx∈I{∑A∈A0q(A)⋅ϵ(A,x)}≥maxx∈I⎧⎩⎨∑A∈β(2λ)q(A)⋅ϵ(A,x)⎫⎭⎬≥∑x∈Id(x)∑A∈β(2λ)q(a)⋅ϵ(A,x)=∑A∈β(2λ)q(a)∑x∈Id(x)⋅ϵ(A,x)≥minA∈β(2λ){12∑x∈Id(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λ)λ
maxx∈I{∑A∈A0q(A)⋅ϵ(A,x)}≥12minA∈β(2λ){∑x∈Id(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)