Erwartete Länge eines zufälligen Spaziergangs auf einer Linie

Question

Ich habe den folgenden randomisierten Algorithmus für SAT,

.
• Input: Eine erfüllende CNF-Formel $ \ varphi $ .
• Ausgabe: Eine Zuordnung $ \ Rho $ , so dass $ \ Rho \ Models \ varphi $ .

Der Algorithmus funktioniert wie folgt:

.
1. Wählen Sie eine beliebige Zuordnung $ \ Rho $ .
2. solange $ \ Rho \ Not \ Models \ varphi $
   3. Wählen Sie eine Klausel in $ \ varphi $ Nicht zufrieden mit $ \ Rho $ gleichmäßig zufällig.
   4. Wählen Sie eine Variable $ X \ In_ {u.a.r} \ operatorName {var} (c) $ .
   5. drehen Sie den Wert von $ \ Rho (X) $ (Set $ \ Rho (x)=Overline { \ rho (x)} $ ).

   Wir müssen nachweisen, dass der Algorithmus für eine 2-CNF-Formel auf eine laufende Laufzeit von Polynom aufweist.

   ---

   Ich habe bewiesen, dass für eine feste Aufgabe $ \ alpha $ , solcher Taht $ \ alpha \ models \ varphi $ , mit Wahrscheinlichkeit $ P \ GEQ 1/2 $ , nach jeder Iteration die Anzahl der Variablen, die verschiedene Werte in $ \ alpha $ und $ \ Rho $ Abnahme von einem. Mit Wahrscheinlichkeit $ 1-P $ , die Zuweisungen $ \ Rho $ und $ \ alpha $ unterscheiden sich an einer zusätzlichen Variablen.

   Jetzt muss ich nachweisen, dass der Algorithmus in der erwarteten Polynomanzahl der Schritte fertig ist. Ich konnte einen weiteren Schritt der Abstraktion hinzufügen. Lassen Sie $ x_i $ die Zufallsvariable sein, die die Anzahl der Schritte angibt, die zum Erstellen von $ \ Rho=alpha $ , wenn $ \ rho $ und $ \ alpha $ von genau $ I $ Variablen. Dann hält es das $$ E [X_I]= 1 + P E [X_ {I-1}] + (1-P) E [x_ {i + 1}], $$ . und $ x_i \ leq x_ {i + 1} $ für alle $ i $ und $ E [x_0] $ ist gleich 0. Wir müssen eine Polynomgebühr für $ E [x_i] $ finden.

   seit $ p \ geq 1/2 $ und $ x_i \ leq x_ {i + 1} $ , der folgende muss halten $$ E [X_I] \ LEQ 1 + \ FRAC {E [X_ {I-1}] + E [X_ {I-1}]} {2} $$

   Jetzt kann er als Gehen auf der Ganzzeile angesehen werden, in jedem Schritt bewegen wir uns in jedem Schritt entweder einen Schritt nach links oder einen Schritt nach rechts und die Wahrscheinlichkeit, nach links zu ziehen, ist mindestens eine Hälfte. Wir müssen nachweisen, dass in erwarteten Polynom viele Schritte (Polynom in der Ausgangsposition) die Nummer $ 0 $ in der Zeile erreichen.

   Jede Hilfe zu diesem Problem ist sehr geschätzt :)

Answer 1

das Verhalten, wenn $ p= 1/2 $ und wann $ p> 1/2 $ ist ziemlich anders. Wenn $ p> 1/2 $ , in Erwartung, in Erwartung $ 2P-1 $ Schritte nach links , also treffen Sie den Ursprung nach einer linearen Anzahl von Schritten. Wenn $ p= 1/2 $ ist, ist die Situation komplizierter.

Betrachten Sie einen zufälligen Spaziergang auf der Linie, die am Ursprung begonnen hat. Die Anzahl der Spaziergänge der Länge $ 2N $ , die niemals rechts vom Ursprung bewegt, ist $ \ frac {\ Binom {2n} {n}} {n + 1} $ (diese sind die katalanische Nummern ) , und so die Wahrscheinlichkeit, dass Sie zum ersten Mal nach genau nach genau den 2N + 1 $ Schritte nach dem Ursprung des Ursprungs $$ q_ {2n + 1}=frac {1} {2 ^ {2n + 1}} \ frac {\ binom {2n} {n}} {n + 1}=theta \ linke (\ frac {1} { n ^ {3/2}}} \ rechts). $$ Daher ist die erwartete Anzahl von Schritten, bis Sie sich zum ersten Mal rechts vom Ursprung bewegen $$ \ sum_ {n= 0} ^ \ fashty (2n + 1) q_ {2n + 1}=sum_ {n= 0} ^ \ fmty \ theta \ linke (\ frac {1} {\ sqrt {n}} \ \ rechts)=fantastisch. $$ Andererseits ist die Anzahl der Besuche des Ursprungs $$ \ sum_ {n= 0} ^ \ fly \ frac {\ Binom {2n} {n}} {2 ^ {2n}}= ^ \ {n= 0} ^ \ flTy \ theta \ linke (\ frac {1} {\ sqrt {n}} \ right)=fanty, $$ Sie bewegen sich also rechts in den Ursprung unendlich viele Male.

Die Schlussfolgerung ist, dass ein zufälliger Spaziergang in $ I> 0 $ begonnen wird, der den Ursprung fast sicher trifft, aber die erwartete Zeit, um den Ursprung zu erreichen, ist unendlich. < / p>

Ihr Fall ist jedoch anders, da Sie bei $ i= n $ : wenn an Position $ n $ , Sie ziehen immer in $ n-1 $ . Sie können an die Situation auf folgende Weise denken. Obwohl der tatsächliche Satz von Positionen $ 0, \ ldots, n $ ist, stellen wir uns vor, dieses Set entlang des Punktes $ N $ zu reflektieren , Hinzufügen von $ N-1 $ Neue Positionen $ n + 1, \ ldots, 2n $ . Die Position $ n + k $ spielt wirklich die Rolle der Position $ n-k $ . Wir können den zufälligen Spaziergang wie üblich betreiben und den Sieg beim Erreichen der Position $ 0 $ oder Position $ 2N $ .

nach T $ Schritte, die Verschiebung von der Ausgangsposition verfügt über eine Binomialverteilung $ \ mathrm {bin} (t , 1/2) $ , die nahe an einer normalen Verteilung $ n (t / 2, t / 4) $ liegt. Daher nach T $ Schritte erwarten wir, in einem Abstand von etwa $ \ theta (\ sqrt {t}) zu sein $ Von wo aus wir begonnen haben (dies kann formal gezeigt werden, indem Sie die Squared-Verschiebung und die Verwendung von Chebyshevs Ungleichheit zeigen, was eine Schätzung des vierten -Moments einer binomialen zufälligen Variablen erfordert). In Ihrem Fall beginnen wir an einem bestimmten Ort $ i \ in \ {1, \ ldots, n \} $ . Nach $ \ theta (n ^ 2) $ Schritte erwarten wir, um $ \ theta (n) $ Weit entfernt von wo wir angefangen haben, und klagen Sie also entweder $ 0 $ oder $ 2N $ . Daher sollte der Prozess in $ O (n ^ 2) $ Schritte konvergieren.

---

Wir können das Wiederauftreten auch direkt lösen, wenn $ p= 1/2 $ . Erinnern an, dass das Wiederauftreten ist $$ E [x_i]= 1 + \ frac {e [x_ {i-1}] + e [x_ {i + 1}]} {2}, $$ mit Anfangsbedingungen $ e [x_0]= e [x_ {2n}]= 0 $ .

lass $ n_i= e [x_i] + i ^ 2 $ . Dann $$ 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}, $$ Mit Anfangsbedingungen $ n_0= 0 $ und $ n_ {2n}= 4n ^ 2 $ .

lass $ m_i= n_i - 2ni $ . Dann erfüllt $ m_i $ das gleiche Wiederholung wie $ n_i $ , mit Anfangsbedingungen $ M_0= M_ {2N}= 0 $ . Es ist einfach zu überprüfen, ob das Minimum und das Maximum der Sequenz $ M_0, \ ldots, m_ {2n} $ an den Endpunkten erreicht werden muss (seit $ \ MAX (M_ {I-1}, M_ {I + 1}) \ geq m_i $ und $ \ min (m_ {i -1}, m_ {i + 1}) \ leq m_i $ ), und so

ner "> $ m_i \ Equiv 0 $ . Daher $ n_i= 2ni $ , und so $$ E [x_i]= i (2n-i)= n ^ 2 - (n-i) ^ 2. $$