نمایش مبدأ برای الگوریتم متروپلیس-هیستینگز

در علم [[آمار]] و [[فیزیک آماری]]، الگوریتم متروپلیس-هیستینگز {{به انگلیسی|Metropolis–Hastings algorithm}} یک روش [[زنجیره مارکوف مونت کارلو]] {{به انگلیسی|Markov chain Monte Carlo}} برای به دست آوردن ترتیبی از نمونه‌های تصادفی از یک [[توزیع احتمال|توزیع احتمالی]] است که نمونه‌برداری مستقیم از آن دشوار می‌باشد. این ترتیب را می‌توان برای برآورد یک توزیع (به عنوان مثال تولید یک [[بافت‌نگار|هیستوگرام]]) یا برای محاسبهٔ برخی انتگرال‌ها (به‌طور مثال یک [[مقدار چشم‌داشتی|امید ریاضی]]) استفاده کرد. متروپلیس-هیستینگز و دیگر الگوریتم‌های MCMC عموماً برای نمونه‌برداری از توزیع‌های چند بعدی استفاده می‌شوند، به خصوص زمانی که تعداد ابعاد بالا باشد. برای توزیع‌های تک بعدی معمولاً روش‌های دیگری وجود دارند (به عنوان مثال نمونه‌گیری عدم پذیرش تطبیقی) که می‌توانند به‌طور مستقیم نمونه‌های مستقل را از توزیع بازگردانند؛ معمولاً این روش‌ها با مشکل [[خودهمبستگی]] که در روش‌های MCMC به صورت ذاتی وجود دارند، رو به رو نیستند.<ref name=":0">*{{یادکرد ویکی|عنوان =Metropolis–Hastings algorithm|پیوند = http://en.wikipedia.org/wiki/Metropolis–Hastings_algorithm |زبان =انگلیسی| بازیابی =۵ دسامبر ۲۰۱۲}}</ref>

== تاریخچه ==
این الگوریتم به افتخار [[نیکولاس متروپلیس|نیکلاس متروپلیس]] {{به انگلیسی|Nicholas Metropolis}} که در سال ۱۹۵۳ در مقاله‌ای با عنوان «معادلهٔ محاسبهٔ حالت به وسیلهٔ ماشین‌های [[رایانش]] سریع» به همراه همکارانش ([[آریانا روزنبلوث]] {{به انگلیسی| Arianna W. Rosenbluth}}، [[مارشال روزنبلوث]] {{به انگلیسی| Marshall N. Rosenbluth}}، [[اگوستا تلر]] {{به انگلیسی| Augusta H. Teller}} و [[ادوارد تلر]] {{به انگلیسی|Edward Teller}} منتشر کرده‌است، نام‌گذاری شده. این مقاله [[الگوریتم|الگوریتمی]] برای توزیع‌های پیشنهادی متقارن ارائه می‌دهد و سپس هیستینگز در سال ۱۹۷۰ الگوریتم را برای حالت‌های عمومی‌تر توسعه می‌دهد.<ref name=":0"/><ref>Hastings, W.K. (1970). "Monte Carlo Sampling Methods Using Markov Chains and Their Applications". ''Biometrika''. '''57''' (1): 97–109. Bibcode:1970Bimka..57...97H. doi:10.1093/biomet/57.1.97. JSTOR&nbsp;2334940. Zbl&nbsp;0219.65008</ref>

متروپولیس و اولام در سال ۱۹۴۹ برای تولید نمونه ای از یک [[تابع چگالی احتمال|تابع چگالی]] استفاده از الگوریتم متروپولیس را توسط یک تابع چگالی پیشنهادی ''q'' متقارن معرفی نمودند. متقارن بودن به این معنی است که به ازای هر ''x'' و ''y'' داشته باشیم: ''(q(x,y) = q(y,x''. در سال ۱۹۵۳ متروپولیس و همکارانش به مطالعه بیشتر این الگوریتم پرداختند. بعدها در سال ۱۹۷۰ هیستینگز شرط متقارن بودن را حذف نمود و الگوریتم متروپلیس-هیستینگز نامیده شد. انواع دیگر این الگوریتم بر اساس ویژگی‌های [[تابع تولید]] کنندهٔ نمونه در سال‌های بعد معرفی شدند.<ref>{{یادکرد وب|نویسنده=|کد زبان=|تاریخ=|وبگاه=|نشانی=https://www.civilica.com/Paper-CFMA03-CFMA03_090=روش-پیش-فرض-رائو-بلکولیزه-کردن-الگوریتم-های-متروپلیس--هستینگز.html|عنوان=روش پیش فرض رائو-بلکولیزه کردن الگوریتم‌های متروپلیس- هستینگز}}</ref>

در مورد این که توسعهٔ این الگوریتم دقیقاً به چه کسی نسبت داده شود بحث‌هایی وجود دارد. متروپلیس عبارت «مونت کارلو» در این زمینه را قبل‌تر در مقاله‌ای به همراه [[استانیسلاو اولام]] استفاده کرده‌بوده، همچنین با بحث‌های محاسباتی این روش آشنا بود و گروهی را در بحث‌های نظری مربوط به طراحی و ساخت کامپیوتر مانیاک۱ که برای آزمایش‌های این روش در سال ۱۹۵۲ استفاده می‌شد، رهبری می‌کرد. هرچند تا قبل از سال ۲۰۰۳ هیچ شرح دقیقی از فرایند توسعهٔ الگوریتم وجود نداشت. در آن زمان مارشال روزنبلات، کمی قبل‌تر از مرگش، در کنفرانسی در سال ۲۰۰۳ در [[آزمایشگاه ملی لس آلاموس|آزمایشگاه ملی لوس‌آلموس]] که برای پاس‌داشت پنجاهمین سالگرد انتشار مقاله برگزار شده‌بود، شرکت کرد و الگوریتم و فرایند توسعهٔ آن را در ارائه‌ای با عنوان «پیدایش [[الگوریتم مونت کارلو]] برای [[مکانیک آماری]]» شرح داد.<ref><cite class="citation journal">M.N. Rosenbluth (2003). "Genesis of the Monte Carlo Algorithm for Statistical Mechanics". ''[[:en:AIP_Conference_Proceedings|AIP Conference Proceedings]]''. '''690''': 22–30. [[:en:Digital_object_identifier|doi]]:[[doi:10.1063/1.1632112|10.1063/1.1632112]].</cite></ref> شفاف‌سازی‌های تاریخی بعدی به وسیلهٔ گوبرناتیس در مقاله‌ای در سال ۲۰۰۵ انجام شد.<ref><cite class="citation journal">J.E. Gubernatis (2005). [https://zenodo.org/record/1231899 "Marshall Rosenbluth and the Metropolis Algorithm"]. ''[[:en:Physics_of_Plasmas|Physics of Plasmas]]''. '''12''' (5): 057303. [[:en:Bibcode|Bibcode]]:[[bibcode:2005PhPl...12e7303G|2005PhPl...12e7303G]]. [[:en:Digital_object_identifier|doi]]:[[doi:10.1063/1.1887186|10.1063/1.1887186]].</cite></ref> روزنبلات به صورت شفافی بیان می‌کند که او و همسرش آریانا توسعهٔ الگوریتم را انجام داده‌اند و متروپلیس نقشی در توسعهٔ آن به جز فراهم کردن زمان کامپیوتر نداشته‌است.

این مطلب با حرف‌های ادوارد تلر که در خاطراتش اذعان می‌کند پنج نویسندهٔ مقالهٔ سال ۱۹۵۳ با هم برای روزها (و شب‌ها) کار می‌کرده‌اند تناقض دارد.<ref>Teller, Edward. ''Memoirs: A Twentieth-Century Journey in Science and Politics''. [[:en:Perseus_Publishing|Perseus Publishing]], 2001, p. 328</ref> در مقابل، شرح با جزئیات روزنبلات بیان می‌کند که تلر نقشی اساسی ولی اولیه در پیشنهاد ایدهٔ «بهره بردن از مکانیک آماری و گرفتن مجموعه‌ای از میانگین‌ها به جای استفادهٔ مفصل از [[سینماتیک]]» داشته‌است. روزنبلات می‌گوید این موضوع باعث شد او دربارهٔ عمومی کردن راهکار مونت کارلو بیندیشد؛ موضوعی که وی معمولاً با [[جان فون نویمان|فون نیومن]] دربارهٔ آن بحث می‌کرده‌است. آریانا بیان می‌کند (به گورنتیس در سال ۲۰۰۳) که آگوستا تلر کارهای کامپیوتری را آغاز کرد ولی آریانا آن را ادامه داد و کد مربوطه را از ابتدا نوشت. روزنبلات در یک تاریخ شفاهی که چندی قبل از مرگش ضبط شده<ref>Rosenbluth, Marshall. [https://www.aip.org/history-programs/niels-bohr-library/oral-histories/28636-1 "Oral History Transcript"]. American Institute of Physics</ref> یک بار دیگر نیز تلر را کسی معرفی می‌کند که مسئلهٔ اولیه را ارائه کرده و خودش را کسی می‌داند که مسئله را حل کرده و آریانا را برنامه‌نویس راه حل این مسئله معرفی می‌کند. از دید اعتبار سخن، دلایل چندانی برای این که اعتبار حرف‌های روزنبلات را زیر سؤال ببریم وجود ندارد. در یک شرح‌حال از زندگی روزنبلات [[فریمن دایسون]] دربارهٔ او می‌نویسد:<blockquote>بارهای زیادی پیش روزنبلات آمدم و از او سؤالی پرسیدم [...] و در طول دو دقیقه پاسخی از او دریافت کردم. سپس برای من معمولاً یک هفته کار می‌برد تا جزئیات این که چرا پاسخ روزنبلات درست بوده‌است را متوجه شوم. او توانایی خارق‌العاده‌ای در دیدن عمق وضعیت یک مسئلهٔ فیزیکی پیچیده و رسیدن به پاسخ درستی به کمک استدلال‌های فیزیکی داشت. [[انریکو فرمی]] تنها فیزیکدان دیگری بود که من می‌شناسم که در درک شهودی فیزیک توانایی مشابهی با روزنبلات داشت.<ref name=":0"/><ref>F. Dyson (2006). "Marshall N. Rosenbluth". ''Proceedings of the American Philosophical Society''. '''250''': 404.</ref></blockquote>

== معرفی ==
هنگام انجام استنتاج بیزی، هدف ما محاسبه و استفاده از توزیع مشترک پسین کامل مجموعه ای از [[متغیر تصادفی|متغیرهای تصادفی]] است. متأسفانه، این روش اغلب نیاز به محاسبهٔ انتگرالی غیرقابل حل دارد. در چنین مواردی ممکن است ما در برابر حل معادلات تحلیلی تسلیم شویم و روش نمونه‌گیری مبتنی بر روش [[زنجیره مارکوف مونت کارلو]] را ادامه دهیم. وقتی از زنجیره مارکوف مونت کارلو استفاده می‌کنیم با استفاده از نمونه‌ای شبیه‌سازی شده از توزیع پیشین، توزیع پسین و انتگرال‌های غیرقابل حل را تخمین می‌زنیم.<ref>{{یادکرد کتاب|عنوان=Bayesian Inference: Metropolis-Hastings Sampling|نام خانوادگی=Yildirim|نام=Ilker|ناشر=Department of Brain and Cognitive Sciences University of Rochester|سال=August 2012|شابک=|مکان=|صفحات=}}</ref>

=== معرفی روش‌های نمونه‌برداری برای تخمین توزیع احتمال ===
به صورت کلی روش‌های نمونه‌برداری (که روش‌های مونت کارلو نیز نامیده می‌شوند) به چهار دسته تقسیم می‌شوند:
* نمونه‌برداری پیش‌رو {{به انگلیسی|forward sampling}}
*[[روش نمونه‌برداری بازپس‌زننده|نمونه‌برداری بازپس‌زننده]] {{به انگلیسی|rejection sampling}}
* نمونه‌برداری بر پایهٔ اهمیت {{به انگلیسی|importance sampling}}
* زنجیرهٔ مارکف مونت کارلو {{به انگلیسی|Markov chain Monte Carlo}}

==== مشکلات روش نمونه‌برداری پیش‌رو ====
یکی از ساده‌ترین روشهای نمونه‌برداری در [[شبکه‌های بیزی]] روش نمونه‌برداری پیش‌رو است که با داشتن یک مرتب‌سازی موضعی از گراف، نمونه‌برداری از متغیرها را انجام می‌دهد. در این روش اگر تعداد متغیرهای شواهد زیاد باشد، بسیاری از نمونه‌ها حذف می‌شوند و در نتیجه برای تخمین دقیق‌تر باید از نمونه‌های بیشتری استفاده شود.

در بسیاری از موارد به دلیل پیچیده بودن توزیع اصلی نمی‌توان به‌صورت مستقیم از توزیع موردنظر <math>P(x)</math>نمونه‌برداری کرد، بلکه از توزیع پیشنهادی <math>Q(x)</math>نمونه‌برداری می‌کنیم. روشهای نمونه‌برداری بازپس‌زننده و نمونه‌برداری بر پایهٔ اهمیت از این ایده استفاده می‌کنند.<ref name=":1">{{Cite journal|date=2019-07-07|title=Metropolis–Hastings algorithm|url=https://en.wikipedia.org/w/index.php?title=Metropolis%E2%80%93Hastings_algorithm&oldid=905143780|journal=Wikipedia|language=en}}</ref>

==== مشکلات روش نمونه‌برداری بازپس‌زننده ====
در روش نمونه‌برداری بازپس‌زننده اگر توزیع پیشنهادی <math>Q(x)</math> تفاوت زیادی با <math>P(x)</math> داشته باشد؛ اکثر نمونه‌ها پذیرفته نمی‌شوند. همچنین در این روش‌ها مشکل [[نفرین ابعاد]] وجود دارد؛ یعنی با افزایش ابعاد توزیع موردنظر، احتمال پذیرفته نشدن نمونه‌ها به صورت نمایی افزایش می‌یابد.<ref name=":1" />

==== مشکلات نمونه‌برداری بر پایهٔ اهمیت ====
در روش نمونه‌برداری بر پایهٔ اهمیت اگر توزیع پیشنهادی <math>Q(x)</math>تفاوت زیادی با <math>P(x)</math>داشته باشد؛ اکثر نمونه‌ها وزن بسیار کمی خواهند داشت و با توجه به وزن آن‌ها رسیدن به نمونه‌های مناسبی از توزیع دشوار خواهد بود.<ref name=":2">{{یادکرد کتاب|عنوان=Probabilistic Graphical Models:Principles and Techniques|کوشش=D. Koller and N. Friedman|ref=D. Koller and N. Friedman, “Probabilistic Graphical Models:Principles and Techniques”, Chapter12}}</ref>

==== معرفی روش‌های نمونه‌برداری بر اساس زنجیرهٔ مارکف ====
یکی از روشهای دیگر نمونه‌برداری روش زنجیرهٔ مارکف مونت کارلو است. در این روش از توزیع پیشنهادی <math>Q(x')</math>استفاده نمی‌شود، بلکه از توزیع پیشنهادی <math>Q(x'|x)</math>استفاده می‌شود که در آن <math>x'</math>نمونه جدید به دست آمده و <math>x</math>آخرین نمونهٔ پذیرفته شده‌است. همزمان با تغییر <math>x</math>، <math>Q(x'|x)</math>نیز تغییر می‌کند.

روش‌های زنجیرهٔ مارکف مونت کارلو به دو روش [[نمونه‌برداری گیبز]] و نمونه‌برداری متروپلیس-هیستینگز تقسیم می‌شوند.

===== محدودیت‌های روش نمونه‌برداری گیبز =====
برای استفاده از روش گیبز باید <math>P(x_i|x_{-i})</math>را محاسبه کنیم. اگرچه این توزیع برای مدل‌های گرافی گسسته قابل بدست آوردن است؛ اما برای مدل‌های گرافی پیوسته به راحتی قابل محاسبه نیست. محدودیت مهمتری که در این روش وجود دارد این است که زنجیرهٔ گیبز تنها حرکات محدودی در فضای دامنهٔ متغییرهای تصادفی توزیع انجام می‌دهد. در این روش هر بار تنها یک متغیر تغییر می‌کند. در مدل‌هایی که متغییرهای آن به شدت به هم وابسته هستند، چنین تغییری منجر به این خواهد شد که از حالت‌هایی که احتمال بالایی برای وقوع دارند به حالت‌هایی منتقل شویم که احتمال بسیار پایینی برای وقوع دارند. در این صورت حالت‌های [[با احتمال بالا]] بیشتر نمونه‌های تولید شده را دربر خواهندگرفت و این موضوع باعث می‌شود زنجیره به سختی بتواند از آن نمونه‌ها فاصله بگیرد که به معنی سرعت پایین همگرایی آن به توزیع اصلی خواهد بود. در این صورت ما معمولاً روش‌هایی را ترجیح می‌دهیم که حرکات آن‌ها برد بیشتری داشته باشد و در نتیجه اجازهٔ حرکت بیشتری در فضای دامنهٔ توزیع احتمالی به ما بدهد. الگوریتم متروپلیس-هیستینگز یکی از این راه‌کارها می‌باشد.

به صورت کلی محدودیت‌های بسیاری برای روش‌های بیزی وجود دارد. حتی با داشتن توزیع مشترک پسین، ممکن است استفاده از آن برای به دست آوردن توزیع شرطی برای هر یک از متغییرهای تصادفی موجود در مدل امکان‌پذیر و عملی نباشد. با داشتن [[احتمال شرطی]] پسین همچنان ممکن است آن‌ها از یک فرم شناخته شده نباشند و راه ساده‌ای برای نمونه‌گیری از آن‌ها وجود نداشته باشد.

== نحوهٔ استفاده از زنجیرهٔ مارکف برای نمونه‌برداری از یک توزیع احتمالی ==
روش‌های زنجیرهٔ مارکف مونت کارلو (MCMC) با [[قدم زدن تصادفی]] در طول یک زنجیرهٔ مارکف نمونه‌برداری از یک توزیع را انجام می‌دهند. به‌عبارت دیگر توزیع اصلی موردنظر را برابر توزیع حالت پایدار یک زنجیرهٔ مارکف در نظر می‌گیرند و بنابراین اگر بتوان زنجیرهٔ مارکفی طراحی کرد که دارای توزیع حالت پایدار باشد، می‌توان با شروع از یک وضعیت اولیهٔ تصادفی در زنجیره مارکف و حرکت مطابق با ماتریس انتقال بین وضعیت‌ها، درنهایت پس از تعدادی حرکت در زنجیرهٔ مارکف به نمونه‌ای از توزیع حالت پایدار و در نتیجه نمونه‌هایی از توزیع اصلی رسید.

=== شرایط لازم برای استفاده از یک زنجیرهٔ مارکف برای نمونه‌برداری ===
باید توجه داشت که یک زنجیرهٔ مارکف برای این که مناسب نمونه‌برداری باشد، باید هم توزیع حالت پایدار داشته‌باشد و هم این توزیع برای آن صرف‌نظر از وضعیت شروع، یکتا باشد. این موضوع به عنوان یک قضیه در نظریهٔ مدل‌های گرافی احتمالی مطرح و اثبات می‌شود.

شرط این که یک زنجیرهٔ مارکف دارای توزیع حالت پایدار باشد، داشتن خاصیت برگشت‌پذیری {{به انگلیسی|Reversibility}} است.

==== خاصیت برگشت‌پذیری ====
اگر شرط «[[تعادل جزء به جزء]]» {{به انگلیسی|Detailed Balance}} برای یک زنجیرهٔ مارکف برقرار باشد، زنجیره مارکوف برگشت‌پذیر نامیده می‌شود. این شرط به صورت زیر تعریف می‌شود:

<math>\pi(x')T(x'\rightarrow x)= \pi(x)T(x\rightarrow x')</math>

اگر این شرط برقرار باشد، می‌توانیم بنویسیم:

<math>\sum_x\pi(x')T(x'\rightarrow x)= \sum_x\pi(x)T(x\rightarrow x')\quad\quad\Longrightarrow\pi(x')\sum_xT(x'\rightarrow x)= \sum_x\pi(x)T(x\rightarrow x')
\quad\quad\Longrightarrow\pi(x')= \sum_x\pi(x)T(x\rightarrow x')</math>
رابطهٔ اخیر رابطهٔ توزیع حالت پایدار است.

==== خاصیت منظم بودن ====
شرط کافی و نه لازم برای اینکه توزیع حالت پایدار زنجیرهٔ مارکف یکتا باشد؛ خاصیت منظم بودن {{به انگلیسی|Regularity}} آن است. زنجیرهٔ مارکف درصورت داشتن دو ویژگی زیر منظم خواهد بود<ref name=":2" />:

# کاهش‌ناپذیری {{به انگلیسی|Irreducibility}}: احتمال رفتن از هر وضعیت به وضعیت‌های دیگر بزرگتر از ۰ باشد.
# نامتناوب بودن {{به انگلیسی|Aperiodicity}}: در هر لحظه از زمان امکان بازگشت به هر وضعیت وجود داشته باشد.

به عبارت دیگر در صورتی یک زنجیرهٔ مارکف دارای خاصیت منظم بودن است که حداقل یک مقدار <math>k>0</math>وجود داشته باشد که به ازای هر دو وضعیت <math>x</math>و <math>x'</math>بتوان با دقیقاً <math>k</math>گام از وضعیت  <math>x</math>به <math>x'</math> رفت.

== نحوهٔ عملکرد الگوریتم متروپلیس-هیستینگز ==
در الگوریتم متروپلیس-هیستینگز به جای نمونه‌برداری از <math>P(x)</math>از توزیع شرطی <math>Q(x'|x)</math>نمونه‌برداری می‌کنیم و معمولاً <math>Q(x'|x)</math>به صورت توزیع نرمال <math>N(x';\sigma^2.x)</math>در نظر گرفته می‌شود.

در این الگوریتم هر نمونهٔ <math>x'</math>که بعد از نمونهٔ <math>x</math>تولید شده، احتمال مشخصی برای پذیرفته شدن دارد. این احتمال با <math>A(x\rightarrow x')</math>نمایش داده شده و به صورت زیر محاسبه می‌شود:

<math>A(x\rightarrow x')=\min(1,\frac{P(x')Q(x|x')}{P(x)Q(x'|x)})</math>

=== فرایند اجرا ===
در ابتدا به صورت تصادفی از یک وضعیت اولیه <math>x_0</math>شروع می‌کنیم و از توزیع <math>Q(x_1|x_0)</math>نمونه‌برداری می‌کنیم و نمونهٔ <math>x_1</math>را تولید می‌کنیم. این نمونه با احتمال <math>A(x_0\rightarrow x_1)</math>پذیرفته می‌شود.[[پرونده:Metropolis hastings algorithm.png|بندانگشتی|توزیع پیشنهادی Q نقطه‌ی بعدی که قدم‌زدن تصادفی احتمالاً به آن حرکت خواهد کرد را پیشنهاد می‌دهد.]]به‌همین ترتیب در یک حلقه شروع به نمونه‌گیری از توزیع <math>Q(x'|x)</math>و تولید نمونهٔ <math>x'</math>می‌کنیم. هر نمونهٔ <math>x'</math>با احتمال <math>A(x\rightarrow x')</math>شانس پذیرفته شدن دارد. دقت داریم که تابع A شامل یک کمینه‌گیری است و اگر مقدار پارامتر دیگر کمینه‌گیری بزرگ‌تر از یک شود، تابع مقدار یک را برخواهد گرداند و نمونه حتماً پذیرفته می‌شود. در صورتی که مقدار پارامتر دوم کمتر از یک شود، عددی تصادفی در بازهٔ [۰٬۱] تولید می‌کنیم و اگر کوچک‌تر یا برابر با مقدار پارامتر دوم شد، نمونه را می‌پذیریم و در غیر این صورت نمونهٔ جدید را برابر با نمونهٔ تولید شده در مرحلهٔ قبل قرار می‌دهیم.
ادامه دادن این روند منجر به همگرایی توزیع زنجیرهٔ استفاده شده به توزیع اصلی (که در حال تخمین آن هستیم) خواهد شد.

نمونه‌هایی که در این فرایند دور ریخته می‌شوند به عنوان نمونهٔ سوخته شناخته می‌شوند و در ادامهٔ فرایند الگوریتم به کار نمی‌آیند. مجموعهٔ باقی مانده از مقادیر مورد قبول <math>x</math>نمونه‌هایی از توزیع <math>P(x)</math>را نمایش می‌دهند.

در زیر شبه‌کدی از این الگوریتم به نمایش درآمده است.<ref name=":3">Eric Xing, Lecture 16, March 17, 2014</ref><syntaxhighlight lang="pascal" line="1">
initialize starting sate x(0)
set t=0
while samples have not converged:
    x=x(t)
    sample x* according to Q(x*|x)
    A(x to x*)=min(1,[P(x*)Q(x|x*)]/[P(x)Q(x*|x)])
    generate a uniform random number u from [0,1]
    if u < A(x to x*):
        x(t+1)=x*
    else:
        x(t+1)=x(t)
    t=t+1
</syntaxhighlight>

=== اثبات همگرایی الگوریتم متروپلیس-هیستینگز به توزیع اصلی ===
اگر با استفاده از توزیع <math>Q(x'|x)</math>نمونه‌ی<math>x'</math>را به دست آوریم، آن‌گاه احتمال رفتن از وضعیت <math>x</math>به <math>x'</math>برابر است با:

<math>T(x \rightarrow x')=Q(x'|x)A(x \rightarrow x')</math> (برای حالتی که <math>x</math>و <math>x'</math>برابر نباشند)

<math>T(x \rightarrow x)=Q(x|x)+\Sigma_{x\ne x'}(Q(x'|x)(1-A(x \rightarrow x')))</math> (برای حالتی که <math>x</math>و <math>x'</math>برابر باشند)<ref name=":2" />

اگر <math>A(x\rightarrow x')\leq 1</math>آن‌گاه <math>\frac{P(x)Q(x'|x)}{P(x')Q(x|x')} \geq 1</math>و در نتیجه <math>A(x'\rightarrow x)= 1</math>خواهد بود. در این صورت می‌توانیم بنویسیم:

<math>A(x\rightarrow x')= \frac{P(x')Q(x|x')}{P(x)Q(x'|x)}\quad\quad\Longrightarrow P(x)Q(x'|x)A(x\rightarrow x')=P(x')Q(x|x')A(x'\rightarrow x)
\quad\quad\Longrightarrow P(x)T(x\rightarrow x')=P(x')T(x'\rightarrow x)</math>

معادلهٔ آخر همان شرط تعادل دقیق است؛ یعنی الگوریتم متروپلیس-هیستینگز باعث می‌شود به یک توزیع حالت پایدار <math>P(x)</math>در زنجیرهٔ مارکف برسیم.

از طرف دیگر اگر <math>T(x\rightarrow x')>0</math>باشد؛ آن‌گاه شرط منظم بودن زنجیرهٔ مارکف نیز برقرار است.

بنابراین این الگوریتم در نهایت به توزیع اصلی همگرا می‌شود.<ref name=":3" />

=== مقدار مناسب برای واریانس توزیع گاوسی اولیه ===
الگوریتم متروپلیس-هیستینگز در حالتی به بهترین نحو عمل می‌کند که احتمال شرطی پیشنهاد شده، با احتمالی که در حال تخمین توزیع آن هستیم (و نمونه‌برداری مستقیم از آن دشوار است) مطابقت داشته‌باشد؛ به عبارتی باید داشته‌باشیم<math>Q(x'|x) \approx P(x') \,\!</math>. اگر از یک توزیع احتمالی گاوسی برای این کار استفاده شود، باید پارامتر [[واریانس]] آن <math>\displaystyle (\sigma^2)</math>در طول فرایند انتخاب نمونه‌های مناسب تنظیم شود. معمولاً این کار با محاسبهٔ یک نرخ پذیرش صورت می‌گیرد. این نرخ نیز براساس تعداد نمونه‌هایی که در طول تعداد دفعات مشخصی از نمونه‌گیری در گذشته مورد قبول واقع شده‌اند؛ حساب می‌شود. مقدار نرخ پذیرش مطلوب بستگی به توزیع هدف دارد، هر چند از دید نظری نشان داده شده که نرخ پذیرش ایده‌آل برای یک توزیع گاوسی تک بعدی حدود ۵۰٪ است. این مقدار هنگامی که از یک توزیع N بعدی گاوسی استفاده شود به ۲۳٪ کاهش پیدا می‌کند.<ref><cite class="citation journal">Roberts, G.O.; Gelman, A.; Gilks, W.R. (1997). [http://www.stat.columbia.edu/~gelman/research/published/theory7.ps "Weak convergence and optimal scaling of random walk Metropolis algorithms"]. ''[[:en:Ann._Appl._Probab.|Ann. Appl. Probab.]]'' '''7''' (1): 110–120. [[:en:CiteSeerX|CiteSeerX]]&nbsp;<span class="cs1-lock-free" title="Freely accessible">[https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.717.2582 10.1.1.717.2582]</span>. [[:en:Digital_object_identifier|doi]]:[[doi:10.1214/aoap/1034625254|10.1214/aoap/1034625254]].</cite></ref>[[پرونده:3dRosenbrock.png|جایگزین=|بندانگشتی|نتایج حاصل از سه زنجیره‌ی مارکف که با استفاده از الگوریتم متروپلیس-هیستینگز روی تابع روزنبروک سه بعدی اجرا شده‌اند. الگوریتم نمونه‌هایی از محل‌هایی که احتمال پسین در آن‌ها بالاست انتخاب می‌کند و زنجیره شروع به ترکیب این محل‌ها می‌کند. موقعیت حدودی بیشینه‌ی نمونه‌ها نمایش داده شده است. نقاط قرمز نقاطی هستند که پس از فرآیند رد کردن نمونه‌ها باقی مانده‌اند. نقاط اولیه در نظر گرفته نشده‌اند.]]

اگر مقدار<math>\displaystyle \sigma^2</math>خیلی کوچک انتخاب شود، زنجیره با سرعت پایینی به تعادل خواهد رسید (به عبارت دیگر نرخ پذیرش بالا خواهد بود ولی نمونه‌های پیاپی گرفته شده، با سرعت پایینی در فضای دامنهٔ متغیر توزیع پخش خواهند شد و بنابراین زنجیره با سرعت پایینی به <math>P(x)</math>همگرا می‌شود). از طرفی اگر<math>\displaystyle \sigma^2</math>خیلی بزرگ انتخاب شود، نرخ پذیرش بسیار پایین خواهد بود؛ چرا که نمونه‌های پیشنهادی احتمالاً در نقاطی از دامنهٔ چگالیِ احتمال خواهند افتاد که مقدار احتمال بسیار پایینی دارد و بنابراین <math>\frac{P(x')}{P(x)}</math>بسیار کوچک خواهد شد و دوباره سرعت همگرایی زنجیره بسیار پایین خواهد بود.<ref name=":3" /> با توجه به توضیحاتی که در مورد تخمین‌های نظری در این زمینه ارائه شد، این که توزیع پیشنهادی را طوری تنظیم کنیم که حدود ۳۰٪ از نمونه‌ها مورد پذیرش واقع شوند، روش مرسومی شناخته می‌شود.

== روش نمونه‌گیری گیبز به عنوان حالت خاصی از الگوریتم متروپلیس-هیستینگز ==
روش نمونه‌گیری گیبز حالت خاصی از الگوریتم متروپلیس-هیستینگز است که توزیع پیشنهادی که در هر گام برای نمونه‌برداری استفاده می‌کند تنها برای متغیر <math>i</math>م (که جزئی از متغییرهای تصادفی توزیع اصلی است) تعریف می‌شود و برابر است با:

<math>Q_i(x'|x)=P(x'_i|x_{-i})</math>

با استفاده از توزیع پیشنهادی معرفی شده در الگوریتم متروپلیس-هیستینگز می‌توان ثابت کرد که احتمال پذیرش هر نمونه در روش گیبز برابر ۱ است<ref name=":3" />:

<math>A(x\rightarrow x')=\min(1,\frac{P(x')Q(x|x')}{P(x)Q(x'|x)})=\min(1,\frac{P(x'_i,x'_{-i})P(x_i|x'_{-i})}{P(x_i,x_{-i})P(x'_i|x_{-i})})
\qquad\qquad x'_{-i}=x_{-i}\Longrightarrow\qquad\min (1,\frac{P(x'_i|x_{-i})P(x_{-i})P(x_i|x_{-i})}{P(x_i|x_{-i})P(x_{-i})P(x'_i|x_{-i})})=1
     </math>

== کاربرد الگوریتم متروپلیس-هیستینگز در انتگرال‌گیری عددی ==
یکی از کاربردهای مرسوم الگوریتم متروپلیس-هیستینگز در محاسبه‌ي یک [[انتگرال]] است. فضای <math>\Omega \subset \mathbb{R}</math> و یک توزیع احتمالی <math>P(x)</math>روی <math>\Omega</math> و  <math>x \in \Omega</math> را در نظر بگیرید. الگوریتم متروپلیس-هیستینگز می‌تواند انتگرالی در فرم زیر را تخمین بزند:

<math>
P(E) = \int_\Omega A(x) P(x) dx
</math>

که در آن <math>A(x)</math>تابعی دلخواه است. برای مثال [[آماره|آماره‌]]ي <math>E(x)</math> و توزیع احتمالی آن <math>P(E)</math> را که یک توزیع احتمالی حاشیه‌ای است، در نظر بگیرید. فرض کنیم هدف تخمین <math>P(E)</math> برای <math>E</math>براساس دنباله‌ای از <math>P(E)</math>باشد. <math>P(E)</math> را می‌توانیم به صورت زیر بازنویسی کنیم:

<math>
P(E) = \int_\Omega P(E|x) P(x) dx = \int_\Omega \delta(E - E(x)) P(x) dx=E_X(P(E|X))
</math>

و بنابراین تخمین <math>P(E)</math> می‌تواند با تخمین امید ریاضی مقدار [[تابع مشخصه|تابع مشخصه‌]]<nowiki/>ی<math>A_E(x) \equiv \mathbf{1}_E(x)</math>که مقدار آن تنها هنگامی یک خواهد بود که<math>E(x) \in [E, E + \Delta E]</math>(و درغیراینصورت صفر خواهدبود)، صورت پذیرد. به این دلیل که <math>E</math> روی دنباله‌ای از <math>P(E)</math> محاسبه می‌شود؛ احتمال این که حالت <math>x</math>با <math>E(x)</math>روی دنباله‌ای از <math>P(E)</math>به دست بیاید، متناسب با <math>P(E)</math> است، که طبق تعریف مقدار کوچکی خواهد بود. الگوریتم متروپلیس-هیستینگ می‌تواند در این‌جا برای نمونه‌گیری از حالت‌هایی که نادر هستند استفاده شود و آن‌ها را با احتمال بالاتری تولید کند که منجر به افزایش تعداد نمونه‌های مورد استفاده برای تخمین <math>P(E)</math>خواهدشد. این روش می‌تواند به عنوان مثال با استفاده از یک توزیع مولد نمونه مثل <math>\pi(x)</math>که بیشتر به آن حالت‌ها شانس تولید می‌دهد، پیاده‌سازی شود (برای مثال <math>\pi(x)</math> می‌تواند به شکل <math>\pi(x) \propto e^{a E}</math> با <math>a>0</math> تعریف شود).<ref name=":0" />

== منابع ==
{{پانویس}}
[[رده:الگوریتم‌های آماری]]
[[رده:روش‌های مونت‌کارلو]]
[[رده:زنجیره مارکوف مونت کارلو]]