فیلتر ذره‌ای
برآورد برپایه نمونه‌برداری Monte-Carlo

فرض کنید یک آزمایش تصادفی را به صورت مستقل از هم  N بار انجام دهیم و پیشامد   S را در طول این آزمایش مدنظر قرار دهیم. پس در این آزمایش تعداد دفعاتی که پیشامد  S  رخ می‌دهد را شمرده و با N_{s}  نشان می‌دهیم. در نتیجه احتمال رخداد پیشامد  S به صورت زیر بدست خواهد آمد.
Pr(S)=\lim _{N\rightarrow \infty }{\frac {N_{s}}{N}}
این رابطه بیان می‌کند که چنانچه آزمایش را با تعداد دفعات نامحدود و به صورت کاملاً مستقل از هم انجام دهیم، آنگاه می‌توان احتمال رخداد پیشامدی مانند  S را با شمردن تعداد رویداد آن پیشامد و تقسیم کردن بر تعداد دفعات کل بدست آورد. اما در جهان واقع به دلیل اینکه تعداد دفعات آزمایش محدود است و وابستگی‌هایی بین آزمایش‌ها وجود دارد می‌توان احتمال رخداد پیشامد S را به‌صورت زیر تقریب زد.
{\hat {Pr}}(S)={\frac {N_{s}}{N}}
به این تقریب، تقریب مونت کارلو (Monte-Carlo) گفته می‌شود. اینک با توجه به اینکه تعداد رویدادهای پیشامد مورد نظر برای  N‌های محدود یک متغیر تصادفی است، تقریب احتمال رخداد پیشامد  S (رابطه بالا) نیز یک متغیر تصادفی خواهد بود. اما برای آنکه برآورد به روش مونت‌کارلو کیفیت مناسبی داشته باشد باید دارای ویژگی‌های زیر باشد:
ویژگی اول: برآورد برپایه مونت‌کارلو باید نااریب باشد، یعنی اگر با انجام آزمایش‌های متعدد مقدارهای برآورد متفاوتی بدست‌آوردیم باید میانگین این مقادیر دقیقاً برابر با مقدار مورد برآورد باشد؛ یعنی اگر به دفعات با به‌کارگیری از روش مونت کارلو، احتمال رخداد پیشامد  S را برآورد کردیم و مجموعه‌ای از برآوردها (تخمین‌ها) بدست آوردیم، میانگین این برآوردها باید برابر با مقدار واقعی احتمال رخداد باشد.
ویژگی دوم: برآورد برپایه مونت‌کارلو باید سازگار (Consistent) باشد، یعنی واریانس مقادیر مختلف از مجموعه برآوردها بر پایه روش مونت‌کارلو با افزایش تعداد دفعات آزمایش به سمت صفر بگراید.
در نتیجه خطای برآورد نااریب و سازگار دارای میانگین آماری صفر بوده و واریانس آن با افزایش تعداد تکرر آزمایش به سمت صفر می‌گراید.
به عنوان یک مثال کاربردی از روش برآورد مونت‌کارلو می‌توان به برآورد مساحت اشاره‌کرد. فرض کنید برآورد مساحت یک ناحیه برای ما مطلوب است و این ناحیه مورد برآورد در یک ناحیه مشخص دیگری پَروسته (محصور) شده باشد که مساحت آن دانسته‌است؛ بنابراین بر طبق روش مونت‌کارلو یک آزمایش تصادفی که جزئیات آن بیان می‌شود را انجام می‌دهیم؛ ریختن ذره‌هایی به صورت کاملاً مستقل و تصادفی همگی در درون ناحیه‌ای که مساحت آن را می‌دانیم؛ بنابراین آزمایش انجام شد. اینک پیشامد برآورد شده  S  را به‌صورت تعداد ذره‌های که در درون ناحیه‌ای که می‌خواستیم تخمین بزنیم می‌افتند تعریف می‌کنیم. اکنون تعداد ذره‌هایی را که در درون ناحیه با مساحت نامعلوم می‌افتد با  N_{s}  و تعداد ذره‌هایی را که در درون ناحیه با مساحت معلوم می‌افتد با  N  نشان می‌دهیم. شکل زیر یک مثال از ناحیه‌ای که مساحتش را می‌خواهیم برآورد کنیم و ناحیه با مساحت معلوم را نشان می‌دهد.
اگر مساحت ناحیه معلوم را با  A و مساحت ناحیه برآورد شده را با  A_{s}  نشان دهیم، آنگاه نسبت مساحت ناحیه نامعلوم به کل مساحت ناحیه معلوم بر طبق این آزمایش تقریباً برابر است با:
{\frac {A_{s}}{A}}\approx {\frac {N_{s}}{N}}
اینک با توجه به اینکه مقدار  A معلوم است، مساحت ناحیه برآورد شده به صورت تقریبی از رابطه زیر بدست می‌آید.
A_{s}\approx A{\frac {N_{s}}{N}}
برای اینکه برآورد به صورت نااریب باشد لازم است ذره‌هایی که در درون ناحیه با مساحت معلوم قرار می‌گیرند دارای توزیع یکنواخت روی آن ناحیه باشند.
اما روش مونت‌کارلو به اینجا محدود نمی‌شود، فرض کنید ذره‌های   \{x^{(i)}\}_{i=1}^{N} به یک طریقی و به‌طور مستقل از هم و تصادفی از توزیع احتمال   P(x) بیرون کشیده شده باشند. اینک برپایه روش مونت‌کارلو تابع توزیع   P(x) به کمک ذره‌های بیرون کشیده شده به صورت زیر تقریب زده می‌شود.
P(x)\approx {\frac {1}{N}}\sum _{i=1}^{N}{\delta (x-x^{(i)})}
که در آن  \delta (.) تابع دلتای دیراک و  N تعداد ذره‌ها است. در نتیجه مقدار متوسط هر تابع دلخواه  f(x) را می‌توان به صورت زیر تقریب زد.
رابطه اخیر بیان می‌دارد که برای محاسبه امید ریاضی هر تابع دلخواه   f(x) کافیست   N ذره از تابع توزیع   P(x) نمونه داشت و مقدار آنها تحت تابعیت   f(x) را محاسبه کرد. در صورتی‌که  \mathbb {E} (f(x)) وجود داشته باشد بر طبق قانون ضعیف اعداد بزرگ برای هر کمیت کوچک اپسیلون رابطه زیر را می‌توان نوشت.
\lim _{N\rightarrow \infty }(|{\hat {f}}_{n}-\mathbb {E} (f(x))|\geq \epsilon )=0
بر طبق این رابطه هرچه   N بزرگتر شود احتمال اینکه برآورد متوسط تابع   f(x) از مقدر واقعی آن یعنی  \mathbb {E} (f(x)) دور شود کمتر است. از طرف دیگر این برآورد یک برآورد نااریب است چراکه داریم:
\mathbb {E} ({\hat {f}}_{N})=\mathbb {E} ({\frac {1}{N}}\sum _{i=1}^{N}f(x^{(i)}))={\frac {1}{N}}\sum _{i=1}^{N}{\mathbb {E} (f(x^{(i)}))}=\mathbb {E} (f(x))
همچنین این برآورد یک برآورد سازگار است، برای فهم آن نیز داریم:
{\begin{aligned}{\mbox{Var}}({\hat {f}}_{N})&=\mathbb {E} ({\hat {f}}_{N}^{2})-\mathbb {E} (f(x))^{2}=\mathbb {E} ({\frac {1}{N^{2}}}\sum _{i=1}^{N}{\sum _{j=1}^{N}{f(x^{(i)})f(x^{(j)}))}}-\mathbb {E} (f(x))^{2}\\&={\frac {1}{N^{2}}}((N^{2}-N)\mathbb {E} (f(x))^{2}+N\mathbb {E} (f(x)^{2}))-\mathbb {E} (f(x))^{2}\\&={\frac {1}{N}}(\mathbb {E} (f(x)^{2})-\mathbb {E} (f(x))^{2})={\frac {1}{N}}{\mbox{Var}}(f(x))\end{aligned}}
که در بدست آوردن رابطه اخیر، معادله زیر و با توجه به i.i.d. بودن ذره‌های بیرون کشیده شده بکار برده شد.
\mathbb {E} (f(x^{(i)})f(x^{(j)}))={\begin{cases}\mathbb {E} (f(x)^{2})&i=j,\\\mathbb {E} (f(x))^{2}&i\neq j\end{cases}}
اینک با توجه به اینکه بسیاری از کمیت‌ها و پارامترهایی را که می‌خواهیم برآورد کنیم می‌توان به صورت امید ریاضی نوشت و امید ریاضی را نیز می‌توان به کمک روش بیان شده مونت‌کارلو برآورد کرد، گستره کاربرد روش مونت‌کارلو روشن می‌شود. برای مثال فرض کنید بخواهیم کمیت  x را برپایه تخمین MMSE و با در نظر گرفتن کمیت مشاهده شده y تخمین بزنیم. بر طبق مرجع می‌دانیم که این برآورد به رابطه زیر می‌انجامد.
{\hat {x}}_{\mbox{MMSE}}=\mathbb {E} (x|y)
بنابراین باید تابع   f(x)=x را بر روی توزیع   P(x|y) متوسط بگیریم. بدین منظور کافیست ذره‌های مستقل و تصادفی  \{x^{(i)}\}_{i=1}^{N} را از توزیع   P(x|y) بیرون کشیده و طبق برآورد مونت‌کارلو در رابطه زیر قرار دهیم.
{\hat {x}}_{\mbox{MMSE}}\approx {\frac {1}{N}}\sum _{i=1}^{N}x^{(i)}
در ادامه پیرامون نمونه‌برداری بااهمیت به عنوان شاخه‌ای از برآورد مونت‌کارلو بحث می‌کنیم.