نمونه گیری تصادفی

ایده ی monte carlo: یک مجموعه تصادفی از فضا را انتخاب می کند و یک الگوریتم قطعی روی آن انجام می دهد. این کار را تکرار می کند.

این کار معادل این است که یک random walk روی فضای مساله بزنیم تا به جواب برسیم.

در تحلیل این روش احتمال انتخاب جواب نسبت تعداد جوابها به کل فضا است.

(almost uniform sampler: نمونه گیری که در آن احتمال یکنواخت بودن از یک اپسیلون کمتر باشد.)

برای بهبود آن نمونه گیری را در دو مرحله انجام می دهیم:

-فضای نمونه را به زیر مجموعه هایی افراز می کنیم که احتمال انتخاب هر کدام یکسان باشد و یکی را با احتمال متناسب با تعداد اعضایش انتخاب می کنیم.

-احتمال انتخاب یک عضو از زیر مجموعه هم یکسان باشد و یکی از آنها را یکنواخت انتخاب می کنیم.

با این کار احتمال انتخاب شدن هر عضو یکنواخت است. (مثل قبل)

می توانیم این کار را با تعداد بیشتری مرحله انجام بدهیم، یعنی در هر مرحله ی الگوریتم از جواب قبلی استفاده کنیم و از روی آن جواب جدید را بسازیم.

مثلا در روشهای افزایشی، هر بار از جواب قبلی استفاده کنیم و دو حالت داریم: یا این عضو جدید در جواب تاثیر دارد یا نه. با حساب کردن احتمال تغییر جواب می توانیم احتمال رسیدن به جواب نهایی را به دست بیاوریم.

این کار معادل markov chain روی فضای مساله است، چون دیگر احتمال رسیدن به هر وضعیت یکسان نیست. (متناسب با اعضای آن مجموعه است.)

برای اینکه این روش جواب بدهد باید دو شرط همگرایی markov chain برقرار باشند: همبند بودن و ب.م.م طول دورهای گراف=1 باشد.

برای برقرار شدن شرط اول که کاری نمیشه کرد؛ ولی برای برقرار شدن ب.م.م طول دورها = 1 می توانیم طوقه (دور با طول 1 یال: از هر راس به خودش) اضافه کنیم که اگر به اندازه ی n-d(u) باشه احتمال یکنواخت هم میشه و تبدیل به random walk میشه.