Ожидаемая длина случайной прогулки по линии

Question

Мне дают следующий рандомизированный алгоритм для SAT,

.
• Вход: Удовлетворный CNF-формул $ \ varphi $ .
• Выход: назначение $ \ Rho $ , так что $ \ Rho \ Models \ varphi $ ,

алгоритм работает как следующее:

1. Выберите произвольное назначение $ \ Rho $ .
2. дольше, как $ \ Rho \ Not \ Models \ varphi $
   3. Выберите предложение в $ \ varphi $ не удовлетворены $ \ Rho $ равномерно.
   4. Выберите переменную $ x \ in_ {u.a.r} \ inserationname {var} (c) $ .
   5. flip Значение $ \ Rho (x) $ (Установка $ \ Rho (x)=uverline { \ Rho (x)} $ ).

   Мы должны доказать, что для 2-CNF формулы алгоритм имеет многочлен ожидаемое время работы.

   ---

   Я доказал, что для фиксированного назначения $ \ alpha $ , такого taht $ \ alpha \ Models \ varphi $ , с вероятностью $ p \ geq 1/2 $ , после каждой итерации количества переменных, которые назначаются различные значения в $ \ alpha $ и $ \ Rho $ Снижение на один. С вероятностью $ 1 - P $ , назначения $ \ Rho $ и $ x_i $ - случайная переменная, которая указывает на количество шагов, необходимых для создания $ \ Rho=alpha $ , когда $ \ Rho $ и $ \ alpha $ отличается точно $ i $ Переменные. Тогда он держит, что $$ e [x_i]= 1 + p e [x_ {i-1}] + (1-p) e [x_ {i + 1}], $$ и $ x_i \ leq x_ {i + 1} $ для всех $ i $ и $ E [x_0] $ равен 0. Нам нужно найти полиномиальную границу для $ E [x_i] $ .

   С момента $ p \ geq 1/2 $ и $ x_i \ leq x_ {i + 1} $ , следует держать следующее $$ e [x_i] \ leq 1 + \ frac {e [x_ {i-1}] + e [x_ {i-1}]} {2} $$

   Теперь это может видеть пчела, как ходить на целочисленной линии, на каждом шаге мы перемещаем ни один шаг на левый или один шаг вправо, и вероятность движения влево - не менее половины. Мы должны доказать, что в ожидаемом полиноме много шагов (многочлена в исходном положении), мы достигаем числа $ 0 $ на линии.

   Любая помощь по этой проблеме очень ценится :)

Answer 1

Поведение, когда $ p= 1/2 $ а когда $ P> 1/2 $ довольно разное. Когда $ P> 1/2 $ , в ожидании вы перемещаете $ 2P-1 $ шаги слева Так что вы попадете на начало после линейного числа шагов. Когда $ p= 1/2 $ , ситуация сложнее.

Рассмотрим случайную прогулку по линии, запущенной в начале происхождения. Количество прогулок длиной $ 2N $ , который никогда не двигается справа от начала происхождения, является $ \ frac {\ binom {2n} {n}} {n + 1} $ (это Catalan Numbers ) Итак, вероятность того, что вы перемещаете справа от начала происхождения в первый раз после того, как именно $ 2n + 1 $ шаги $$ q_ {2n + 1}=frac {1} {2 ^ {2n + 1}} \ frac {\ binom {2n} {n}} {n + 1}=theta \ flea (\ frac {1} { n ^ {3/2}} \ справа). $$ Поэтому ожидаемое количество шагов до тех пор, пока вы сначала не двигаете право происхождения, не $$ \ sum_ {n= 0} ^ \ infty (2n + 1) q_ {2n + 1}=sum_ {n= 0} ^ \ infty \ theta \ левый (\ frac {1} {\ sqrt {n}} \ правильно)=infty. $$ С другой стороны, количество посещений происхождения является $$ \ sum_ {n= 0} ^ \ infty \ frac {\ binom {2n} {n}} {2 ^ {2n}}=sum_ {n= 0} ^ \ infty \ theta \ left (\ frac {1} {\ sqrt {n}} \ верно)=infty, $$ Таким образом, вы будете двигаться справа от происхождения бесконечно много раз.

Заключение состоит в том, что случайная прогулка началась в $ I> 0 $ Почести почти наверняка, но ожидаемое время достичь происхождения - это бесконечно. < / P >.

Ваш случай, однако, другой, по-разному, поскольку вы «подпрыгивают» на $ i= n $ : когда на позиции $ n $ , вы всегда переходите на $ N-1 $ . Вы можете подумать о ситуации следующим образом. Хотя фактический набор позиций является $ 0, \ LDOTS, N $ , мы представляем, что отражаем этот набор по точке $ n $ , добавление $ N-1 $ Новые позиции $ n + 1, \ ldots, 2n $ Здесь положение $ n + K $ действительно играет роль позиции $ n-k $ . Мы можем выполнить случайную прогулку, как обычно, объявляя победу при достижении либо положения $ 0 $ или позиция $ 2n $ ,

После $ t $ Шаги, смещение из исходного положения имеет биномиальное распределение $ \ mathrm {bin} (t , 1/2) $ , который близок к нормальному распределению $ n (T / 2, T / 4) $ . Поэтому после $ t $ шаги, мы ожидаем, что на расстоянии около $ \ Theta (\ SQRT {T}) $ От того места, где мы начали (это может быть показано формально, учитывая смещение в квадрате и с использованием неравенства Чебышева, что требует оценки MUSE четвертого момента биномиальной случайной переменной). В вашем случае мы начинаем в некоторой позиции $ i \ in \ {1, \ ldots, n \} $ . После $ \ theta (n ^ 2) $ шаги, мы ожидаем, что $ \ Theta (n) $ Дальше от того, где мы начали, и поэтому ударили либо $ 0 $ или $ 2n $ . Поэтому процесс должен сходиться в $ O (N ^ 2) $ Шаги.

---

Мы также можем решить рецидив напрямую, когда $ p= 1/2 $ . Напомним, что рецидив $$ E [x_i]= 1 + \ frac {e [x_ {i-1}] + e [x_ {i + 1}]} {2}, $$ При начальных условиях $ E [x_0]= e [x_ {2n}]= 0 $ .

Пусть $ n_i= e [x_i] + i ^ 2 $ . потом $$ 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}, $$ При первоначальных условиях $ n_0= 0 $ и $ n_ {2n}= 4n ^ 2 $ . .

Пусть $ m_i= n_i - 2ni $ . Тогда $ m_i $ удовлетворяет тому же рецидиву, что и $ n_i $ , с начальными условиями $ m_0= m_ {2n}= 0 $ . Легко проверить, что минимум и максимум последовательности $ m_0, \ ldots, m_ {2n} $ должен быть достигнут в конечных точках (поскольку $ \ max (m_ {i-1}, m_ {i + 1}) \ geq m_i $ и $ \ min (m_ {i i -1}, m_ {i + 1}) \ leq m_i $ ), а так

ner "> $ m_i \ equiv 0 $ . Следовательно, $ n_i= 2ni $ , и так $$ E [x_i]= i (2n-i)= n ^ 2 - (n-i) ^ 2. $$