المدة المتوقعة للمشي عشوائي على خط

Question

أنا أعطيت الخوارزمية العشوائية التالية ل SAT،

• المدخلات: راضي cnf-formula $ \ varphi $ .
• الإخراج: مهمة واحدة $ \ rho $ ، بحيث $ \ rho \ models \ varphi $ .

تعمل الخوارزمية على النحو التالي:

1. اختيار مهمة تعسفية $ \ rho $ .
2. طالما $ \ rho \ not \ models \ varphi $
   3. اختيار جملة في $ \ varphi $ غير راض عنها $ \ rho $ بشكل موحد عشوائيا.
   4. اختيار متغير $ x \ in_ {u.a.r} \ operatorname {var} (c) $ .
   5. الوجه قيمة $ \ rho (x) $ (تعيين $ \ rho (x)=overline { \ rho (x)} $ ).

   يتعين علينا إثبات ذلك في صيغة 2-CNF، تحتوي الخوارزمية على وقت التشغيل متعدد الحدود.

   ---

   لقد أثبتت أنه لمهمة ثابتة $ \ ألفا $ ، مثل Taht $ \ alpha \ models \ varphi $ ، مع احتمال $ p \ geq 1/2 $ ، بعد كل التكرار عدد المتغيرات التي تم تعيينها قيم مختلفة في $ \ ألفا $ و $ \ rho $ انخفاض من قبل واحد. مع الاحتمالات $ 1-P $ ، المهام $ \ rho $ و $ \ ألفا $ تختلف في متغير إضافي واحد.

   الآن يجب أن أثبت ذلك، أن الخوارزمية انتهت في عدد متعدد الحدود من الخطوات المتوقعة. كنت قادرا على إضافة خطوة أخرى من التجريد. دع $ x_i $ يكون المتغير العشوائي الذي يشير إلى عدد الخطوات اللازمة لجعل $ \ rho=alfa $ ، عندما $ \ rho $ و $ \ ألفا $ تختلف عن طريق $ i $ المتغيرات. ثم يحمل ذلك <تمتد الطبقة="الرياضيات حاوية"> $$ E [X_i]= 1 + ص E [X_ {ط 1}] + (1-ع) E [X_ {ط + 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}]} {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} $ (هذه هي أرقام الكاتالونية ) ، وبالتالي فإن الاحتمالية التي تحركها يمين الأصل في المرة الأولى بعد $ 2n + 1 $ الخطوات هي $$ q_ {2N + 1}=frac {1} {2 ^ {2n + 1}} \ frac {n} {n} {n + 1}=theta \ left (\ frac {1} { n ^ {3/2}} \ right). $ لذلك العدد المتوقع من الخطوات حتى تحرك لأول مرة من أصل المنشأ $$ \ sum_ {n= 0} ^ \ infty (2n + 1) q_ {2n + 1}=sum_ {n= 0} ^ \ infty \ theta \ left (\ frac {{} {n}}} \ يمين)=INFTY. $ من ناحية أخرى، عدد الزيارات إلى الأصل $$ \ sum_ {n= 0} ^ \ infty \ frac {\ binom {n} {n}} {2 ^ {2n}}=sum_ {n= 0} ^ \ infty \ Theta \ left (\ frac {1} {\ sqrt {n}} \ right)=infty، $ لذلك سوف تتحرك الحق من أصل بلا حدود عدة مرات.

الاستنتاج هو أن المشي العشوائي بدأ في $ i> 0 $ سيضرب الأصل بالتأكيد تقريبا، ولكن الوقت المتوقع للوصول إلى الأصل هو لانهائي. < / ص>

حالتك الخاصة، ومع ذلك، فاختلاف، لأنك "ترتد" في $ 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}) $ من حيث بدأنا (يمكن أن يظهر ذلك رسميا من خلال النظر في النزوح التربيعي واستخدام عدم المساواة في Chebyshev، مما يتطلب تقديرا ل الرابع لحظة متغير عشوائي ذو حدين). في حالتك، نبدأ في بعض الوظائف $ i \ {1، \ ldots، n \} $ . بعد $ \ theta (n ^ 2) $ steps، نتوقع أن نكون حول $ \ theta (n) $ بعيدا عن المكان الذي بدأنا فيه، وهكذا، اضغط إما $ 0 $ أو $ 2N $ . لذلك يجب أن تتقارب العملية في $ O (n ^ 2) $ الخطوات.

---

يمكننا أيضا حل التكرار مباشرة عند $ p= 1/2 $ . أذكر أن التكرار هو $$ ه [x_i]= 1 + \ frac {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 -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.