Longueur attendue d'une promenade aléatoire sur une ligne

Question

J'ai donné l'algorithme randomisé suivant pour SAT,

• Entrée: une formule CNF satisfiatable $ \ Varphi $ .
• sortie: une affectation $ \ rho $ , telle que $ \ rho \ modèles \ varphi $ .

L'algorithme fonctionne comme suit:

1. Choisissez une assignation arbitraire $ \ rho $ .
2. tant que $ \ RHO \ NOT \ MODÈLES \ VARPHI $
   3. Choisissez une clause dans $ \ VARPHI $ non satisfait par $ \ rho $ uniformément au hasard.
   4. Choisissez une variable $ x \ in_ {u.a.r} \ nom de commande {var} (c) $ .
   .
   5. Retournez la valeur de $ \ rho (x) $ (définir $ \ rho (x)=Overline { \ rho (x)} $ ).

   Nous devons prouver que pour une formule de 2 CNF, l'algorithme a du temps de fonctionnement attendu polnomial.

   ---

   J'ai prouvé que pour une assignation fixe $ \ alpha $ , telle taht $ \ alpha \ modèles \ varphi $ , avec probabilité $ p \ geq 1/2 $ , après chaque itération, le nombre de variables attribuées différentes valeurs dans $ \ alpha $ et $ \ rho $ diminue d'un. Avec probabilité $ 1-p $ , les assignations $ \ rho $ et $ \ alpha $ diffère à une variable supplémentaire.

   Maintenant, je dois prouver que l'algorithme a terminé dans un nombre polynomial attendu d'étapes. J'ai pu ajouter une autre étape d'abstraction. Laissez $ x_i $ Soyez la variable aléatoire indiquant le nombre d'étapes nécessaires à la fabrication $ \ rho=alpha $ , quand $ \ rho $ et $ \ alpha $ diffère exactement $ i $ variables. Alors il tient ça $$ e [x_i]= 1 + p e [x_ {i-1}] + (1-p) e [x_ {i + 1}], $$ et $ x_i \ leq x_ {i + 1} $ pour tous $ i $ et $ E [x_0] $ est égal à 0. Nous devons trouver une liaison polynomiale pour $ e [x_i] $ .

   depuis $ p \ geq 1/2 $ et $ x_i \ leq x_ {i + 1} $ , les suivants doivent contenir $$ e [x_i] \ Leq 1 + \ frac {e [x_ {i-1}] + e [x_ {i-1}]} {2} $$

   Maintenant, cela peut être vu comme marcher sur la ligne entière, à chaque étape, nous déplaçons une étape à gauche ou une étape à droite et la probabilité de passer à gauche est au moins une moitié. Nous devons prouver que dans le polynôme attendu de nombreuses étapes (polynôme dans la position de départ), nous atteignons le nombre 0 $ sur la ligne.

   Toute aide sur ce problème est très appréciée :)

Answer 1

Le comportement lorsque $ p= 1/2 $ et quand $ p> 1/2 $ est plutôt différent. Quand $ p> 1/2 $ , dans l'attente, vous déplacez $ 2P-1 $ marche vers la gauche , vous allez donc frapper l'origine après un nombre linéaire d'étapes. Quand $ p= 1/2 $ , la situation est plus compliquée.

Considérez une promenade aléatoire sur la ligne commencée à l'origine. Le nombre de promenades de longueur $ 2n $ qui ne déplacent jamais la droite de l'origine est $ \ frac {\ binom {2n} {n}} {n + 1} $ (ce sont les numéros catalans ) et donc la probabilité que vous déplacez à droite de l'origine à la première fois après exactement 2N + 1 $ étapes est $$ q_ {2n + 1}=frac {1} {2 ^ {2n + 1}} \ frac {\ binom {2n} {n}} {n + 1}=theta \ gauche (\ frac {1} { n ^ {3/2} \ \ droite). $$ Par conséquent, le nombre attendu d'étapes jusqu'à ce que vous puissiez passer à droite de l'origine, c'est $$ \ sum_ {n= 0} ^ \ \ ^ \ ± \ ^ \ ^ \ \ \ ^ \ \fty (2n + 1) q_ {2n + 1}=sum_ {n= 0} ^ \ \ \ theta \ gauche (\ frac {1} {\ sqrt {n}} \ à droite)=\fty. $$ D'autre part, le nombre de visites à l'origine est $$ \ sum_ {n= 0} ^ \ \ \ \ frac {\ binom {2n} {n}} {2 ^ {2n}}=sum_ {n= 0} ^ \ infty \ theta \ gone (\ frac {1} {\ sqrt {n}} \ droite)=\fty, $$ Donc, vous déplacerez à droite de l'origine à infiniment plusieurs fois.

La conclusion est qu'une promenade aléatoire a commencé à $ i> 0 $ frappera presque sûrement l'origine, mais le temps prévu pour atteindre l'origine est infinie. < / p>

Votre cas est toutefois différente, puisque vous "rebondissez" à $ i= n $ : quand en position $ N $ , vous déplacez toujours sur $ N-1 $ . Vous pouvez penser à la situation de la manière suivante. Bien que l'ensemble actuel de positions soit 0 $, \ ldots, n $ , nous imaginons réfléchir ce jeu le long du point $ N $ , ajout $ N-1 $ nouveaux positions $ n + 1, \ ldots, 2n $ . Ici, position $ n + k $ joue vraiment le rôle de position $ N-K $ . Nous pouvons exécuter la marche aléatoire comme d'habitude, déclarant la victoire après avoir atteint la position de la position $ 0 $ ou position $ 2n $ .

après $ T $ étapes, le déplacement de la position initiale a une distribution binomiale $ \ mathrm {bin} (T , 1/2) $ , qui est proche d'une distribution normale $ n (t / 2, t / 4) $ . Par conséquent, après $ T $ ÉTAPES, nous nous attendons à être à une distance de $ \ theta (\ sqrt {t}) $ d'où nous avons commencé (cela peut être affiché formellement en considérant le déplacement carré et en utilisant l'inégalité de Chebyshev, qui nécessite une estimation du moment quatrième d'une variable aléatoire binomiale). Dans votre cas, nous commençons à une position $ i \ \ \ \ \ \ {1, \ ldots, n \} $ . Après $ \ THETA (N ^ 2) $ Étapes, nous nous attendons à être sur $ \ THETA (N) $ Loin de l'endroit où nous avons commencé, frappez-le, soit 0 $ ou $ 2n $ . Par conséquent, le processus doit converger dans $ o (n ^ 2) $ étapes.

---

Nous pouvons également résoudre la récurrence directement lorsque $ p= 1/2 $ . Rappeler que la récurrence est $$ E [x_i]= 1 + \ frac {e [x_ {i-1}] + e [x_ {i + 1}]} {2}, $$ Avec des conditions initiales e $ e [x_0]= e [x_ {2n}]= 0 $ .

let $ n_i= e [x_i] + i ^ 2 $ . Puis $$ 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}, $$ avec des conditions initiales $ n_0= 0 $ et $ n_ {2n}= 4n ^ 2 $ .

let $ m_i= n_i - 2ni $ . Alors $ m_i $ satisfait la même récurrence que $ n_i $ , avec des conditions initiales $ m_0= m_ {2n}= 0 $ . Il est facile de vérifier que le minimum et le maximum de la séquence $ m_0, \ ldots, m_ {2n} $ doivent être atteints aux points de terminaison (puisque $ \ max (m_ {i-1}, m_ {i + 1}) \ geq m_i $ et $ \ min (m_ {i -1}, m_ {i + 1}) \ Leq m_i $ ), et donc

ner "> $ m_i \ équiv 0 $ . Par conséquent $ n_i= 2ni $ , et ainsi $$ E [x_i]= i (2n-i)= n ^ 2 - (N-I) ^ 2. $$