Longitud esperada de un paseo al azar en una línea

Question

Me dan el siguiente algoritmo aleatorio para SAT,

• Entrada: una CNF-fórmula SABILIDAD $ \ Varphi $ .
• Salida: una asignación $ \ rho $ , de modo que $ \ rho \ modelos \ varphi $ .

El algoritmo funciona de la siguiente manera:

1. Elija una asignación arbitraria $ \ rho $ .
2. Mientras $ \ rho \ no \ modelos \ varphi $
   3. Elija una cláusula en $ \ varphi $ no satisfecho por $ \ rho $ uniformemente al azar.
   4. Elija una variable $ x \ in_ {u.a.r} \ operatorname {var} (c) $ .
   5. Flip el valor de $ \ rho (x) $ (set $ \ rho (x)=overline { \ rho (x)} $ ).

   Tenemos que demostrar que para una fórmula de 2 CNF, el algoritmo tiene tiempo de funcionamiento esperado polinomial.

   ---

   He demostrado que para una asignación fija $ \ alfa $ , tal taht $ \ alfa \ modelos \ varphi $ , con probabilidad $ P \ GEQ 1/2 $ , después de cada iteración el número de variables que se les asignan diferentes valores en $ \ alfa $ y $ \ rho $ Disminución de uno. Con probabilidad $ 1-p $ , las asignaciones $ \ rho $ y $ \ alfa $ difieren en una variable extra.

   Ahora tengo que demostrar que el algoritmo terminó en el número polinomial esperado de pasos. Pude agregar un paso más de la abstracción. Deje que $ x_i $ sea la variable aleatoria que indique la cantidad de pasos necesarios para hacer $ \ rho=alfa $ , cuando $ \ rho $ y $ \ alfa $ difieren exactamente $ i $ variables. Luego sostiene que $$ E [X_I]= 1 + P E [x_ {I-1}] + (1-P) e [x_ {i + 1}], $$ y $ x_i \ leq x_ {i + 1} $ para todos $ i $ y $ E [x_0] $ es igual a 0. Necesitamos encontrar un límite polinomial para $ e [x_i] $ .

   desde $ P \ geq 1/2 $ y $ x_i \ leq x_ {i + 1} $ , lo siguiente debe mantener $$ e [x_i] \ leq 1 + \ frac {e [x_ {i-1}] + e [x_ {i-1}]} {2} $$

   Ahora, esta puede verse como caminar en la línea entera, en cada paso nos movemos un paso hacia la izquierda o un paso hacia la derecha y la probabilidad de movernos a la izquierda es al menos la mitad. Tenemos que demostrar que en el polinomio esperado muchos pasos (polinomio en la posición inicial), llegamos al número $ 0 $ en la línea.

   Cualquier ayuda en este problema es muy apreciada :)

Answer 1

El comportamiento cuando $ p= 1/2 $ y cuando $ p> 1/2 $ es bastante diferente Cuando $ P> 1/2 $ , en expectativa que se mueve $ 2P-1 $ a la izquierda , Así que golpearás el origen después de un número lineal de pasos. Cuando $ P= 1/2 $ , la situación es más complicada.

Considere un paseo al azar en la línea comenzó en el origen. El número de paseos de longitud $ 2n $ que nunca se mueve a la derecha del origen es $ \ frac {\ binom {2n} {n}} {n + 1} $ (estas son las Números catalán ) , y así, la probabilidad de que se mueva a la derecha del origen en la primera vez después de exactamente $ 2n + 1 $ Pasos es $$ q_ {2n + 1}=frac {1} {2 ^ {2n + 1}} \ frac {\ binom {2n} {n}} {n + 1}=theta \ izquierda (\ frac {1} { n ^ {3/2}} \ Derecha). $$ Por lo tanto, el número esperado de pasos hasta que usted se mueva por primera vez a la derecha del origen es $$ \ sum_ {n= 0} ^ \ INFTY (2N + 1) Q_ {2n + 1}=sum_ {n= 0} ^ \ INFTY \ THETA \ Izquierda (\ frac {1} {\ sqrt {n}}} \ derecha)=INFTY. $$ Por otro lado, el número de visitas al origen es $$ \ sum_ {n= 0} ^ \ infty \ frac {\ binom {2n} {n}} {2 ^ {2n} {2 ^ {2n}}=sum_ {n= 0} ^ \ INFTY \ THETA \ IZQUIERDA (\ FRAC {1} {\ sqrt {n}} \ derecha)=Infty, $$ Así que se moverá a la derecha del origen infinitamente muchas veces.

La conclusión es que una caminata aleatoria comenzó en $ i> 0 $ golpeará el origen casi seguramente, pero el tiempo esperado para alcanzar el origen es infinito. < / p>

Su caso es, sin embargo, diferente, ya que "rebota" en $ i= n $ : cuando está en la posición $ n $ , siempre se mueve a $ n-1 $ . Puedes pensar en la situación de la siguiente manera. Aunque el conjunto real de posiciones es $ 0, \ ldots, n $ , imaginamos reflejar este set en el punto $ n $ , agregando $ n-1 $ nuevas posiciones $ n + 1, \ ldots, 2n $ . Aquí la posición $ n + k $ realmente juega el papel de la posición $ n-k $ . Podemos ejecutar la caminata aleatoria como de costumbre, declarando la victoria al llegar a la posición $ 0 $ o la posición $ 2n $ .

Después de $ t $ pasos, el desplazamiento de la posición inicial tiene distribución binomial $ \ mathrm {bin} (t , 1/2) $ , que está cerca de una distribución normal $ n (t / 2, t / 4) $ . Por lo tanto, después de $ t $ pasos, esperamos estar a una distancia de $ \ theTa (\ sqrt {t}) $ desde donde comenzamos (esto se puede mostrar formalmente al considerar el desplazamiento cuadrado y usar la desigualdad de Chebyshev, que requiere una estimación del momento de la variable aleatoria binomial). En su caso, comenzamos en algún puesto $ i \ in \ {1, \ ldots, n \} $ . Después de $ \ theTa (n ^ 2) $ pasos, esperamos que sean sobre $ \ theTa (n) $ Lejos de donde comenzamos, y así, pulsamos cualquiera de los $ 0 $ o $ 2n $ . Por lo tanto, el proceso debe converger en $ o (n ^ 2) $ pasos.

---

También podemos resolver la recurrencia directamente cuando $ p= 1/2 $ . Recuerde que la recurrencia es $$ E [x_i]= 1 + \ frac {e [x_ {i-1}] + e [x_ {i + 1}]} {2}, $$ con condiciones iniciales $ e [x_0]= e [x_ {2n}]= 0 $ .

Let $ n_i= e [x_i] + i ^ 2 $ . Luego $$ N_i= 1 + \ frac {n_ {i-1} + n_ {i + 1} - (I-1) ^ 2 - (i + 1) ^ 2} {2} + i ^ 2=frac {n_ { I-1} + n_ {i + 1}} {2}, $$ con condiciones iniciales $ n_0= 0 $ y $ n_ {2n}= 4n ^ 2 $ .

Let $ M_I= N_I - 2ni $ . Luego, $ M_I $ satisface la misma recurrencia que $ n_i $ , con condiciones iniciales $ m_0= m_ {2n}= 0 $ . Es fácil verificar que el mínimo y el máximo de la secuencia $ m_0, \ ldots, m_ {2n} $ deben alcanzarse en los puntos finales (desde $ \ max (M_ {I-1}, M_ {I + 1}) \ GEQ M_I $ y $ \ min (M_ {i -1}, m_ {i + 1}) \ leq m_i $ ), y así

ner "> $ M_I \ Equiv 0 $ . Por lo tanto, $ n_i= 2ni $ , y así $$ E [x_i]= i (2n-i)= n ^ 2 - (n-i) ^ 2. $$