روش مونت کارلو با زنجیره مارکوف (MCMC)

1402/06/14

دسترسی سریع

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

تاریخچه پیدایش روش مونت کارلو

این روش در سال 1949 با انتشار مقاله ای به نام روش مونت کارلو توسط دو ریاضیدان آمریکایی به نام های J.NEYMAN و S.ULAM شناخته شد. پایه های نظری این روش از مدت ها قبل شناخته شده بود و در قرن نوزدهم و اوایل قرن بیستم گاهی اوقات مسائل آماری را با کمک شبیه سازی کمیت های تصادفی که همان روش مونت کارو است ، حل می کردند. اما تا پیش از اختراع رایانه های الکترونیکی از این روش به دلیل خسته کننده بودن شبیه سازی کمیت های تصادفی زیاد استفاده نمی شد. بنابراین می توان شروع استفاده از روش مونت کارلو به عنوان یک تکنیک عددی عمومی، را همزمان با اختراع رایانه های الکترونیکی دانست. نام مونت کارلو از شهر مونت کارلو واقع در موناکو گرفته شده است.

روش مونت کارلو، شبیه سازی هر روندی که توسط عامل های تصادفی ایجاد شده اند را ممکن می سازد؛ اما این تنها مورد استفاده روش مونت کارلو نیست. برای بیش تر مسائل ریاضی که شانس در آن ها دخالت ندارد ما می توانیم به طور مصنوعی، مدل احتمال آن رار با تعداد زیادی نمونه تعیین کنیم. بنابراین روش مونت کارلو را می توان یک روش عمومی حل مسائل ریاضی دانست.

محاسبه انتگرال ها با روش مونت کارلو

فرض کنید g یک تابع حقیقی مقدار باشد که می خواهیم انتگرال آن را روی $\left[ {a,b} \right]$ محاسبه کنیم: $\theta = \int\limits_a^b {g(x)dx < \infty }$

برای محاسبه این انتگرال می توان به چند روش عمل کرد:

الف) روش تحلیلی: یافتن پادمشتق g و استفاده از قضییه اساسی حساب دیفرانسیل و انتگرال

$\theta = \int\limits_a^b {g(x)dx = G(b) - G(a)}$

ب) روش های عددی: اگر قادر به استفاده از روش تحلیلی نباشیم، از روش های عددی که برای تقریب $\theta$ وجود دارند، استفاده می کنیم. در این روش عمدتا تابع g با توابع ساده تری مانند توابع خطی تکه ای، چندجمله ای و ... تقریب زده می شده و مقدار انتگرال برای این توابع خوش رفتار محاسبه شده و به عنوان تقریب $\theta$ ارائه می شود.

ج) روش مونت کارلو، این روش نیز یک روش عددی است که در حالتی که روش های عددی بالا با پیچیدگی های زیادی همراه هستند و یا خطای این روش زیاد است و یا پیش فرض های روش های عددی برقرار نیستند، به ویژه وقتی که g یک بعدی نباشد، کاربرد دارد.

روش (برآورد) مونت کارلو

در این جا هدف محاسبه مقدار انتگرال زیر است :

$\theta = \int\limits_a^b {g(x)dx}$

برای این منظور توزیع دلخواهی بر $\left[ {a,b} \right]$ با چگالی $f(x)$ اختیار می کنیم. علاوه بر متغیر x که در فاصله $\left[ {a,b} \right]$ با چگالی $f(x)$ تعریف شده است، احتیاج به متغیر تصادفی $h(x) = \frac{{g(x)}}{{f(x)}}$ نیز داریم. در این صورت

$\theta = E(h(x)) = \int\limits_a^b {\frac{{g(x)}}{{f(x)}}f(x)dx}$

حال از چگالی f، نمونه تصادفی ${x_1},{x_2},...,{x_n}$ را استخراج می کنیم. آن گاه $h({x_1}),h({x_2}),...,h({x_n})$ نیز تصادفی بوده و داریم : $E(\frac{1}{n}\sum\limits_{i = 1}^n {h(} {x_i})) = \theta$

طبق قانون قوی اعداد بزرگ $\frac{1}{n}\sum\limits_{i = 1}^n {h(} {x_i}) \to \theta$

بنابراین $\frac{1}{n}\sum\limits_{i = 1}^n {h(} {x_i})$ برآورد معقولی برای $\theta$ می باشد و این برآورد معادل تقریب انتگرال موردنظر است. با این روش می توان بسیاری از انتگرال ها را که نمی توان به روش تحلیلی حل کرد، تقریب زد.

روشن است روش مونت کارلو را برای توابع چندمتغیره نیز می توان به کار برد. در واقع مزیت و برتری این روش نسبت به روش های عددی معمولی، در حل مسائل با بیش از یک بعد نمایان می شود. زیرا روش های عددی معمولی را می توان در حالت یک بعدی به کار برد.

فرض کنیم $g:R \to R$ و علاقمند به محاسبه انتگرال g بر ناحیه $A = \left[ {{a_1},{b_1}} \right] \times \left[ {{a_2},{b_2}} \right] \times ... \times \left[ {{a_d},{b_d}} \right]$ باشیم.

$\theta = \int\limits_{{a_1}}^{{b_1}} {\int\limits_{{a_2}}^{{b_2}} {...\int\limits_{{a_d}}^{{b_d}} {g({x_1},...,{x_d})d{x_1}...d{x_d}} } }$

برای این منظور چگالی دلخواه f بر A را درنظر می گیریم و تابع h(.) را به صورت $h({x_1},...,{x_d}) = \frac{{g({x_1},...,{x_d})}}{{f({x_1},...,{x_d})}}$ تعریف می کنیم. در این صورت

$\theta = E(h({x_1},...,{x_d})) =$

$\int\limits_{{a_1}}^{{b_1}} {\int\limits_{{a_2}}^{{b_2}} {...\int\limits_{{a_d}}^{{b_d}} {\frac{{g({x_1},...,{x_d})}}{{f({x_1},...,{x_d})}}f({x_1},...,{x_d})d{x_1}...d{x_d}} } }$

حال از چگالی f(.) نمونه تصادفی ${x_1},...,{x_d}$ که در آن ${X_i} = ({x_{1i}},...,{x_{di}})$ ، را استخراج می کنیم، آن گاه $h({X_1}),...,h({X_n})$ یک نمونه تصادفی بوده و داریم

$\frac{1}{n}\sum\limits_{i = 1}^n {h({X_i}} ) \to \theta$

بنابراین $\frac{1}{n}\sum\limits_{i = 1}^n {h({X_i}} )$ یک برآورد معقول برای $\theta$ یعنی انتگرال موردنظر می باشد.

چگونگی انتخاب چگالی:

در انتخاب f بدیهی است که باید fی را انتخاب کرد که به سادگی قابل نمونه گیری باشد. زیرا اساس روش مونت کارلو استخراج نمونه و تقریب $\theta$ با استفاده ار این نمونه می باشد. به هرحال برای هر f قابل نمونه گیری داریم $\theta = E(\frac{{g(x)}}{{f(x)}}) = E(h(x))$ که در آن $h(x) = \frac{{g(x)}}{{f(x)}}$ .

با این حال واریانس و درنتیجه خطای استاندارد برآوردگر $\theta$ بسته به انتخاب f می تواند کوچک و یا بزرگ باشد که مطلوب آن است که کمترین مقدار خطای استاندارد برآورد را داشته باشیم.

نظرات

هیچ نظری وجود ندارد.

روش مونت کارلو با زنجیره مارکوف (MCMC)

دسترسی سریع

نظرات

افزودن نظر

آخرین مقالات