Duração esperada de um passeio aleatório em uma linha

Question

Recebi o seguinte algoritmo aleatório para SAT,

• Entrada:Uma fórmula CNF satisfatória $\varphi$.
• Saída:Uma tarefa $ ho$, de tal modo que $ ho \models \varphi$.

O algoritmo funciona da seguinte forma:

1. Escolha uma atribuição arbitrária $ ho$.
2. Desde que $ ho ot \models \varphi$
   3. Escolha uma cláusula em $\varphi$ não satisfeito por $ ho$ uniformemente ao acaso.
   4. Escolha uma variável $x\in_{uar}\operatorname{VAR}(C)$.
   5. Inverta o valor de $ ho(x)$ (definir $ ho(x) = \overline{ ho(x)}$).

Temos que provar que para uma fórmula 2-CNF, o algoritmo tem tempo de execução esperado polinomial.

---

Eu provei isso para uma tarefa fixa $\alfa$, tal $\alfa \modelos \varphi$, com probabilidade $p \geq 1/2$, após cada iteração o número de variáveis ​​às quais são atribuídos valores diferentes em $\alfa$ e $ ho$ diminuir em um.Com probabilidade $1-p$, as atribuições $ ho$ e $\alfa$ diferem em uma variável extra.

Agora tenho que provar que o algoritmo terminou no número polinomial esperado de etapas.Consegui adicionar mais uma etapa de abstração.Deixar $X_i$ seja a variável aleatória que indica o número de passos necessários para fazer $ ho = \alfa$, quando $ ho$ e $\alfa$ diferem exatamente $i$ variáveis.Então isso sustenta$$E[X_i] = 1 + p E[X_{i-1}] + (1-p) E[X_{i+1}],$$e $X_i \leq X_{i+1}$ para todos $i$ e $E[X_0]$ é igual a 0.Precisamos encontrar um limite polinomial para $E[X_i]$.

Desde $p\geq 1/2$ e $X_i \leq X_{i+1}$, o seguinte deve ser válido$$E[X_i] \leq 1 + \frac{E[X_{i-1}] + E[X_{i-1}]}{2}$$

Agora, isso pode ser visto como caminhar na reta inteira, em cada passo movemos um passo para a esquerda ou um passo para a direita e a probabilidade de nos movermos para a esquerda é de pelo menos metade.Temos que provar que em muitos passos polinomiais esperados (polinômio na posição inicial), alcançamos o número $0$ na linha.

Qualquer ajuda sobre este problema é muito apreciada :)

Answer 1

O comportamento quando $p = 1/2$ e quando $p > 1/2$ é bastante diferente.Quando $p > 1/2$, na expectativa de você se mover $2p-1$ passos para a esquerda, então você atingirá a origem após um número linear de passos.Quando $p = 1/2$, a situação é mais complicada.

Considere um passeio aleatório na reta iniciada na origem.O número de caminhadas de comprimento $2n$ que nunca se move para a direita da origem é $\frac{\binom{2n}{n}}{n+1}$ (estes são os Números catalães) e, portanto, a probabilidade de você se mover para a direita da origem na primeira vez após exatamente $2n+1$ passos é$$ q_{2n+1} = \frac{1}{2^{2n+1}} \frac{\binom{2n}{n}}{n+1} = heta\left(\frac{1}{n^{3/2}} ight).$$Portanto, o número esperado de passos até você se mover pela primeira vez para a direita da origem é$$ \sum_{n=0}^\infty (2n+1) q_{2n+1} = \sum_{n=0}^\infty heta\left(\frac{1}{\sqrt{n}} ight) = \infty.$$Por outro lado, o número de visitas à origem é$$ \sum_{n=0}^\infty \frac{\binom{2n}{n}}{2^{2n}} = \sum_{n=0}^\infty heta\left(\frac{1}{\sqrt{n}} ight) = \infty, $$então você se moverá para a direita da origem infinitas vezes.

A conclusão é que um passeio aleatório começou em $i > 0$ atingirá a origem quase com certeza, mas o tempo esperado para chegar à origem é infinito.

Seu caso é, entretanto, diferente, já que você "salta" em $eu = n$:quando na posição $n$, você sempre se move para $n-1$.Você pode pensar na situação da seguinte maneira.Embora o conjunto real de posições seja $0,\ldots,n$, imaginamos refletir esse conjunto ao longo do ponto $n$, adicionando $n-1$ novas posições $n+1,\ldots,2n$.Aqui posição $n+k$ realmente desempenha o papel de posição $nk$.Podemos realizar o passeio aleatório normalmente, declarando vitória ao alcançar qualquer posição $0$ ou posição $2n$.

Depois $t$ passos, o deslocamento da posição inicial tem distribuição binomial $\mathrm{Bin}(t,1/2)$, que está próximo de uma distribuição normal $N(t/2,t/4)$.Portanto depois $t$ passos, esperamos estar a uma distância de cerca de $ eta(\sqrt{t})$ de onde começamos (isso pode ser mostrado formalmente considerando o deslocamento quadrático e usando a desigualdade de Chebyshev, que requer uma estimativa do quarto momento de uma variável aleatória binomial).No seu caso, começamos em alguma posição $i \in \{1,\ldots,n\}$.Depois $ eta(n^2)$ passos, esperamos ser cerca de $ eta(n)$ longe de onde começamos, e então, acerte $0$ ou $2n$.Portanto, o processo deve convergir em $O(n^2)$ passos.

---

Também podemos resolver a recorrência diretamente quando $p = 1/2$.Lembre-se de que a recorrência é$$ E[X_i] = 1 + \frac{E[X_{i-1}] + E[X_{i+1}]}{2}, $$com condições iniciais $E[X_0] = E[X_{2n}] = 0$.

Deixar $N_i = E[X_i] + i^2$.Então$$ 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}, $$com condições iniciais $N_0 = 0$ e $N_{2n} = 4n^2$.

Deixar $M_i = N_i - 2ni$.Então $M_i$ satisfaz a mesma recorrência que $N_i$, com condições iniciais $M_0 = M_{2n} = 0$.É fácil verificar que o mínimo e o máximo da sequência $M_0,\ldots,M_{2n}$ deve ser alcançado nos pontos finais (uma vez que $\max(M_{i-1},M_{i+1}) \geq M_i$ e $\min(M_{i-1},M_{i+1}) \leq M_i$), e assim $M_i \equiv 0$.Portanto $N_i = 2ni$, e assim$$ e [x_i] = i (2n -i) = n^2 - (ni)^2.$$