Random Walk¶
تصور کنید که در یک هزارتو گیر افتاده اید. همه جا تاریک است و شما به هر تقاطعی که می رسید به صورت تصادفی یکی از مسیر ها را در پیش می گیرید. همچنین هیچگونه اطلاعاتی از مسیر ها و تقاطع ها به خاطر نمی سپارید. احتمال اینکه در نهایت بتوانید از هزار تو خارج شوید چقدر است؟ امیدریاضی زمانی که طول می کشد که از هزار تو خارج شوید چقدر است؟
مسئله کلی random walk به این شکل است که یک گراف جهت دار داده شده است. روی یال های مجاور هر راس یک توزیع احتمالاتی داریم. یعنی روی هر راس مثل \(v\) که باشیم به ازای هر کدام از مجاور های \(v\) مثل \(u\) احتمال \(p_{vu}\) را احتمال طی کردن این یال تعریف می کنیم. همچنین جمع احتمال تمام یال های مجاور \(v\) باید برابر با 1 باشد. حالا می توانیم تصور کنیم که فردی روی راس \(s\) ایستاده است و هر مرحله به صورت تصادفی و طبق توزیع احتمالاتی راسی که روی آن ایستاده است جا به جا می شود. فضای کلی مسئله به این شکل است. حالا می توان سوال های مختلفی در این فضا پرسید. دو تا از مهم ترین سوال ها که در این بخش آنها را بررسی می کنیم این است که احتمال و امیدریاضی تعداد حرکات رسیدن فرد به راس \(t\) چقدر است؟
تبدیل مسائل به Random Walk¶
اگر به مسائل احتمالات توجه کنید خیلی از آنها به Random Walk تبدیل می شوند. به این صورت که به ازای هر وضعیت ممکن (با بررسی مثال های پایین دقیق تر متوجه می شوید) یک راس در نظر می گیریم. عملیات هایی که انجام می دهیم هم در واقع یال هایی هستند که به صورت احتمالاتی وضعیت ما را عوض می کنند (ما را از یک راس به راس دیگر می برند).
چند مثال را بررسی می کنیم.
موش و پنیر¶
یک محور اعداد صحیح داریم. موشی نابینا روی نقطه \(s\) است و به دنبال یک پنیر می گردد که روی نقطه \(t\) است. موش در هر مرحله به احتمال \(p\) به جلو می رود و به احتمال \(1-p\) به عقب می رود. امیدریاضی مراحلی که طول می کشد تا موش به پنیر برسد چند است؟
تبدیل¶
برای تبدیل این مسئله به random walk کافی است گرافی با نامتناهی راس در نظر بگیریم. که راس \(x\) نشان دهنده نقطه \(x\) در محور اعداد است. هر راس \(x\) به \(x+1\) یال دارد که روی آن احتمال \(p\) نوشته شده است همچنین به \(x-1\) یال دارد که روی آن احتمال \(1-p\) نوشته شده است. حالا مسئله معادل با امیدریاضی یال های طی شده برای رسیدن از \(s\) به \(t\) است.
توجه کنید که صرفا توانستیم این مسئله را به random walk تبدیل کنیم ولی هنوز آن را حل نکرده ایم!
بمب¶
یک تروریست داریم که دکمه ای در دست دارد. بعد از گذشت هر ساعت تروریست دکمه را فشار می دهد. بعد از فشار دادن دکمه بمب به احتمال \(p\) منفجر می شود و به احتمال \(1-p\) هیچ اتفاقی نمی افتد. این روند انقدر ادامه پیدا می کند که بالاخره بمب منفجر بشود (یا این روند تا بی نهایت به طول می انجامد). امیدریاضی زمانی که طول می کشد تا بمب منفجر شود را بیابید.
تبدیل¶
تبدیل این مسئله به random walk در نگاه اول واضح نیست. اما همانطور که گفتیم، اکثر مسائل احتمالاتی را می توان به random walk تبدیل کرد (اما لزومی ندارد که گراف کوچک باشد و حل مسئله اصلی از طریق حل مسئله random walk ساده تر باشد).
در اینجا وضعیت های ما منفجر شدن و یا نشدن بمب است پس کافیست دو راس \(A\) و \(B\) در نظر بگیریم که \(A\) یعنی در وضعیتی هستیم که بمب منفجر نشده است. حالا بعد از گذشت هر ساعت (هر عملیات) به احتمال \(p\) بمب منفجر می شود. پس راس \(A\) یالی به \(B\) دارد که روی آن احتمال \(p\) نوشته شده است. همچنین به احتمال \(1-p\) بمب منفجر نمی شود که به وضعیت قبل خود بر می گردیم پس راس \(A\) یک یال به خودش دارد که روی آن احتمال \(1-p\) نوشته شده است.
در نهایت مسئله ما تبدیل به امیدریاضی تعداد یال های مورد نیاز برای رسیدن از \(A\) به \(B\) شد. گراف مورد بحث هم دارای دو راس و دو یال می باشد!
سه دزد بز دزد¶
در این مسئله سه دزد بز دزد داریم که آن ها را اولی، دومی و سومی می نامیم. سه دزد با هم مشغول بازی کردن هستند. هر مرحله از بازی به این صورت است :
- به صورت تصادفی آن ها از بین خودشان یکی را انتخاب می کنند. در هر گام به احتمال \(\frac 1 2\) اولی، به احتمال \(\frac 1 3\) دومی و به احتمال \(\frac 1 6\) سومی انتخاب می شود. فرض کنید دزدی که در اینجا انتخاب شده را آقای \(D\) بنامیم.
- آقای \(D\) به مزرعه می رود و یک بز می دزد. بز دزدیده شده به دارایی های آقای \(D\) اضافه می شود.
- در اینجا اگر بز های آقای \(D\) از یکی از دوستانش حداقل 2 تا بیشتر باشد، آقای آقای \(D\) سلطان دزد ها می شود و بازی تمام می شود. در غیر اینصورت دوباره یک نفر دیگر از بین خودشان انتخاب می کنند و این روند ادامه پیدا می کند.
پس به صورت کلی دزد ها آنقدر این روند را انجام می دهند که دزدی که بیشترین دارایی را دارد از دزدی که کمترین دارایی را دارد حداقل دو بز بیشتر داشته باشد...
حالا شما باید احتمال اینکه اولی سلطان دزد ها بشود را حساب کنید!
تبدیل¶
لیستی از وضعیت های مختلف بازی به این شکل است.
- همه تعداد بز های برابر داشته باشند. راس \(s\)
- تعداد بز های اولی یکی بیشتر از بقیه باشد. راس \(A_1\)
- تعداد بز های دومی یکی بیشتر از بقیه باشد. راس \(B_1\)
- تعداد بز های سومی یکی بیشتر از بقیه باشد. راس \(C_1\)
- تعداد بز های اولی یکی کمتر از بقیه باشد. راس \(A_{-1}\)
- تعداد بز های دومی یکی کمتر از بقیه باشد. راس \(B_{-1}\)
- تعداد بز های سومی یکی کمتر از بقیه باشد. راس \(C_{-1}\)
- اولی سلطان باشد. راس \(A_2\)
- دومی سلطان باشد. راس \(B_2\)
- سومی سلطان باشد. راس \(C_3\)
هر کدام از راس ها (به جز سه تای آخر)، دقیقا سه یال خروجی دارند که هر کدام بستگی به این دارد که کدام یک از دزد ها برای دزدیدن انتخاب شوند. به عنوان مثال مجاور های راس \(A_{-1}\) به این صورت هستند :
- اگر اولی انتخاب شود به راس \(s\) می رویم که احتمال \(\frac 1 2\) دارد.
- اگر دومی انتخاب شود به راس \(B_2\) می رویم که احتمال \(\frac 1 3\) دارد.
- اگر سومی انتخاب شود به راس \(C_2\) می رویم که احتمال \(\frac 1 6\) دارد.
در نهایت مسئله معادل با احتمال رسیدن از راس \(s\) به راس \(A_2\) می باشد.
حل مسئله Random Walk¶
در قسمت قبل دیدم که بسیاری از مسائل احتمال را می توان با Random Walk مدل سازی کرد. اما اگر این مدل سازی ما را به حل مسئله اصلی نزدیک تر نکند برای ما سودی نخواهد داشت! در این قسمت می بینیم که می توان مسئله احتمال و امیدریاضی رسیدن از \(s\) به \(t\) در Random Walk را به صورت الگوریتمی و با استفاده از دستگاه چند معادله و چند مجهول حل کرد!
فرض کنید احتمال رفتن از راس \(A\) به راس \(B\) برابر با \(P_{AB}\) باشد. در صورتیکه در گراف از \(A\) به \(B\) یالی نباشد، \(P_{AB}=0\) در نظر بگیرید. همچنین لزوما \(P_{AB}\) با \(P_{BA}\) مساوی نیست (چون گراف جهت دار است).
در این قسمت فرض می کنیم که راس \(t\) به ما داده شده است و ما می خواهیم به ازای تمام راس ها مثل \(u\) احتمال و امیدریاضی رسیدن از \(u\) به \(t\) را بیابیم.
احتمال رسیدن از \(u\) به \(t\) را \(ansP_u\) می نامیم و امیدریاضی تعداد یال های طی شده برای رسیدن از \(u\) به \(t\) را \(ansE_u\) می نامیم.
واضح است که \(ansP_t = 1\) و \(ansE_t = 0\).
معادلات زیر به ازای هر \(u \neq t\) برقرار هستند.
\(ansP_u = \sum P_{uv} \times ansP_v\)
\(ansE_u = 1 + \sum P_{uv} \times ansE_v\)
که اگر \(n\) راس داشته باشیم این معادلات به ما یک دستگاه \(n-1\) معادله و \(n-1\) مجهول می دهند. همچنین به طور خاص اگر گراف جهت دار ما DAG باشد دیگر نیازی به حل دستگاه معادلات نیست. بلکه گراف را به صورت ترتیب توپولوژیکی در نظر می گیریم و از آخر به اول جواب ها را به دست می آوریم (و این بسیار شبیه به کاری است که در توابع بازگشتی انجام می دهیم).
حل یک مثال¶
در اینجا می خواهیم مسئله بمب که در بالا گفته شد را حل کنیم. اگر دستگاه معادلات را شکل بدهیم نتیجه به این شکل است :
\(ansE_B = 0\)
\(ansE_A = 1 + (1-p) \times ansE_A + p \times ansE_B\)
که به راحتی نتیجه می شود \(ansE_A = \frac 1 p\)
نتیجه گیری¶
در اینجا وارد فضای Random Walk شدیم و در مورد بعضی از مسائلی که در این فضا تعریف می شوند کمی صحبت کردیم اما حقیقت این است که انواع پرسش هایی که در فضای Random Walk مطرح می شوند بسیار زیاد است و بحث در این مورد از حوصله کتاب خارج است.
روشی که برای تبدیل به Random Walk و سپس حل آن گفتیم بسیار کلی است. این کار برای شهود گرفتن ما نسبت به مسائل خوب است اما در خیلی از اوقات گرافی که ساخته می شود بسیار بزرگ تر از آن است که بتوان به صورت دستی معادلات مربوط به آن را حل کرد (مثل مسئله سه دزد بز دزد).
گاهی اوقات می توانیم از خاص بودن گراف استفاده کنیم. مثلا فرض کنید می خواهیم امیدریاضی رسیدن از راس \(s\) به \(t\) را بیابیم و ساختار گراف طوری است که هر مسیر از \(s\) به \(t\) حتما از راس \(w\) می گذرد. در اینجا طبق قوانین امیدریاضی می توانیم بفهمیم که امیدریاضی تعداد یال ها برای رسیدن از \(s\) به \(t\) برابر است با جمع امیدریاضی رسیدن از \(s\) به \(w\) و سپس رسیدن از \(w\) به \(t\). از این موضوع می توانید برای حل مسئله موش و پنیر استفاده کنید!
پس در کل می توان گفت تبدیل مسائل به Random Walk به ما کمک می کند ولی اغلب به تنهایی برای حل سوال کافی نیست و ما باید خلاقیت بیشتری برای ساده تر کردن مسئله استفاده کنیم.
این کتاب توسط مشارکت کنندگان شاززز به وجود آمده است.
این کتاب عمومی است و تحت پروانه cc-by-sa در دسترس است.
آخرین به روز رسانی در ژوئن 09, 2022.
