Lunghezza prevista di una passeggiata casuale su una linea

Question

Sono dato il seguente algoritmo randomizzato per Sat,

.
• Input: un soddisfacente CNF-Formula $ \ Varfi $ .
• Output: un incarico $ \ rho $ , in modo tale che $ \ rho \ models \ varphi $ .

L'algoritmo funziona come segue:

.
1. Scegli un incarico arbitrario $ \ rho $ .
2. Finché $ \ rho \ not \ models \ varphi $
   3. Scegli una clausola in $ \ Varfi $ Non soddisfatto da $ \ rho $ uniformemente a caso.
   4. Scegli una variabile $ x \ in_ {u.a.r} \ OperatorName {var} (c) $ .
   5. capovolgere il valore di $ \ rho (x) $ (set $ \ rho (x)=overline { \ rho (x)} $ ).

   Dobbiamo dimostrare che per una formula a 2 cnf, l'algoritmo ha il tempo di esecuzione del polinomiale previsto.

   ---

   .

   Ho dimostrato che per un incarico fisso $ \ alfa $ , tale taht $ \ alfa \ models \ varphi $ , con probabilità $ p \ geq 1/2 $ , dopo ogni iterazione il numero di variabili assegnate a valori diversi in $ \ alfa $ e $ \ rho $ diminuzione di uno. Con probabilità $ 1-P $ , le assegnazioni $ \ rho $ e $ \ alfa $ differiscono in una variabile extra.

   Ora devo dimostrare che l'algoritmo ha rifinito il numero polinomiale previsto di passaggi. Sono stato in grado di aggiungere un altro passo dell'astrazione. Let $ x_i $ Essere la variabile casuale che indica il numero di passaggi necessari per creare $ \ rho=alpha $ , quando $ \ rho $ e $ \ alfa $ differiscono da esattamente $ i $ variabili. Quindi lo tiene $$ E [X_I]= 1 + P E [X_ {I-1}] + (1-P) E [X_ {I + 1}], $$ $ x_i \ leq x_ {i + 1} $ per tutti $ i $ e $ e [x_0] $ è uguale a 0. Dobbiamo trovare un bolizzato polinomiale per $ e [x_i] $ .

   poiché $ p \ geq 1/2 $ e $ x_i \ leq x_ {i + 1} $ , il seguente deve essere tenuto $$ e [x_i] \ leq 1 + \ frac {e [x_ {i-1}] + e [x_ {i-1}]} {2} $$

   Ora questa può essere vista come camminare sulla linea intera, in ogni fase muoviamo un passo a sinistra o un passo a destra e la probabilità di trasferirsi a sinistra è di almeno la metà. Dobbiamo dimostrare che nel polinomiale previsto molti passaggi (polinomio nella posizione di partenza), raggiungiamo il numero $ 0 $ sulla linea.

   Qualsiasi aiuto su questo problema è molto apprezzato :)

Answer 1

Il comportamento quando $ p= 1/2 $ e quando $ p> 1/2 $ è piuttosto diverso. Quando $ P> 1/2 $ , in attesa si sposta $ 2P-1 $ Passi a sinistra , quindi colpisci l'origine dopo un numero lineare di passaggi. Quando $ p= 1/2 $ , la situazione è più complicata.

Considera una passeggiata casuale sulla linea iniziata all'origine. Il numero di passeggiate di lunghezza $ 2N $ che non muoverà mai a destra dell'origine è $ \ frac {\ binom {2n} {n}} {n + 1} $ (Questi sono i numeri catalani ) e così la probabilità che tu muovi a destra dell'origine alla prima volta dopo esattamente $ 2n + 1 $ passaggi è $$ Q_ {2N + 1}=FRAC {1} {2 ^ {2N + 1}}} FRAC {\ BINOM {2N} {N}} {N + 1}=THETA \ SINISTRA (\ FRAC {1} { n ^ {3/2}} \ Destra). $$ Pertanto il numero previsto di passaggi finché non si muovi per la prima volta è a destra dell'origine $$ \ sum_ {n= 0} ^ \ INFTY (2N + 1) Q_ {2N + 1}=SUM_ {N= 0} ^ \ INFTY \ THETA \ SINISTRA (\ FRAC {1} {\ SQRT {N}} \ DESTRA)=INFTY. $$ D'altra parte, il numero di visite all'origine è $$ \ sum_ {n= 0} ^ \ infty \ frac {\ binom {2n} {n}} {2} {n}}} {2 ^ {2n}}}=sum_ {n= 0} ^ \ infty \ theta \ sinistra (\ frac {1} {\ sqrt {n}} \ destra)=Infty, $$ Quindi muoverai a destra dell'origine infinitamente molte volte.

La conclusione è che una passeggiata casuale avviata a $ I> 0 $ colpirà l'origine quasi sicuramente, ma il tempo previsto per raggiungere l'origine è infinito. < / P >.

Il tuo caso è, tuttavia, diverso, dal momento che "Bounce" a $ i= n $ : Quando è in posizione $ n $ , si sposta sempre in $ N-1 $ . Puoi pensare alla situazione nel modo seguente. Sebbene il set effettivo di posizioni sia $ 0, \ ldots, n $ , immaginiamo che riflettono questo set lungo il punto $ n $ , aggiungendo $ n-1 $ Nuove posizioni $ N + 1, \ Ldots, 2N $ . Qui posizione $ N + K $ Gioca davvero il ruolo della posizione $ n-k $ . Possiamo correre la camminata casuale come al solito, dichiarando la vittoria al raggiungimento della posizione $ 0 $ o posizione $ 2N $ .

dopo $ T $ passi, lo spostamento dalla posizione iniziale ha la distribuzione binomiale $ \ mathrm {bin} (t , 1/2) $ , che è vicino a una normale distribuzione $ N (T / 2, T / 4) $ . Pertanto dopo $ T $ passi, ci aspettiamo di essere ad una distanza di circa $ \ theta (\ sqrt {t}) $ Da dove abbiamo iniziato (questo può essere mostrato formalmente considerando lo spostamento quadrato e utilizzando la disuguaglianza di Chebyshev, che richiede una stima del momento quarto di una variabile casuale binomiale). Nel tuo caso, iniziamo ad alcune posizioni $ i \ in \ \ {1, \ Ldots, n \} $ . Dopo $ \ theta (n ^ 2) $ passi, ci aspettiamo di essere circa $ \ theta (n) $ lontano da dove abbiamo iniziato, e quindi, ha colpito la $ 0 $ o $ 2N $ . Pertanto il processo dovrebbe convergere in $ o (n ^ 2) $ passaggi.

---

.

Possiamo anche risolvere la ricorrenza direttamente quando $ P= 1/2 $ . Richiamare che la ricorrenza è $$ E [x_i]= 1 + \ frac {e [x_ {i-1}] + e [x_ {i + 1}]} {2}, $$ Con condizioni iniziali $ e [x_0]= e [x_ {2n}]= 0 $ .

Let $ n_i= e [x_i] + i ^ 2 $ . Poi $$ 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 condizioni iniziali $ n_0= 0 $ e $ n_ {2n}= 4n ^ 2 $ . .

Let $ M_i= n_i - 2Ni $ . Quindi $ M_i $ soddisfa la stessa recidiva come $ n_i $ , con condizioni iniziali $ M_0= M_ {2N}= 0 $ . È facile verificare che il minimo e il massimo della sequenza $ m_0, \ ldots, m_ {2n} $ deve essere raggiunto agli endpoint (poiché $ \ max (m_ {i-1}, m_ {i + 1}) \ geq m_i $ e $ \ min (m_ {i -1}, m_ {i + 1}) \ leq m_i $ ), e così

ner "> $ M_I \ Equiv 0 $ . Pertanto $ n_i= 2Ni $ , e così $$ E [x_i]= i (2n-i)= n ^ 2 - (n-i) ^ 2. $$