خوارزمية متروبوليس-هاستينغز

في الإحصاء والفيزياء الإحصائية ، تُعدّ خوارزمية متروبوليس-هاستينغز طريقةً من طرق مونت كارلو لسلاسل ماركوف (MCMC) للحصول على سلسلة من العينات العشوائية من توزيع احتمالي يصعب أخذ عينات مباشرة منه. تُضاف العينات الجديدة إلى السلسلة على مرحلتين: أولًا، تُقترح عينة جديدة بناءً على العينة السابقة، ثم تُضاف العينة المقترحة إلى السلسلة أو تُرفض بناءً على قيمة التوزيع الاحتمالي عند تلك المرحلة. يمكن استخدام السلسلة الناتجة لتقريب التوزيع (مثلًا لإنشاء مدرج تكراري ) أو لحساب تكامل (مثلًا القيمة المتوقعة ).

تُستخدم خوارزميات متروبوليس-هاستينغز وغيرها من خوارزميات سلسلة ماركوف مونت كارلو (MCMC) عادةً لأخذ عينات من التوزيعات متعددة الأبعاد، خاصةً عندما يكون عدد الأبعاد كبيرًا. أما بالنسبة للتوزيعات أحادية البعد، فتوجد عادةً طرق أخرى (مثل أخذ العينات بالرفض التكيفي ) التي يمكنها إرجاع عينات مستقلة مباشرةً من التوزيع، وهي خالية من مشكلة الارتباط الذاتي للعينات المتأصلة في طرق MCMC.

سُميت الخوارزمية جزئيًا نسبةً إلى نيكولاس متروبوليس ، المؤلف المشارك الأول في ورقة بحثية نُشرت عام 1953 بعنوان " حسابات معادلة الحالة بواسطة آلات الحوسبة السريعة" ، بالاشتراك مع أريانا دبليو. روزنبلث ، ومارشال روزنبلث ، وأوغستا إتش. تيلر، وإدوارد تيلر . لسنوات عديدة، عُرفت الخوارزمية ببساطة باسم خوارزمية متروبوليس . ^{[ 1 ] [ 2 ]} اقترحت الورقة البحثية الخوارزمية لحالة توزيعات الاقتراح المتناظرة، ولكن في عام 1970، قام دبليو كيه هاستينغز بتوسيعها لتشمل الحالة الأكثر عمومية. ^{[ 3 ]} عُرفت الطريقة المعممة في النهاية بكلا الاسمين، على الرغم من أن أول استخدام لمصطلح "خوارزمية متروبوليس-هاستينغز" غير واضح.

يُثار جدلٌ حول أحقية تطوير خوارزمية متروبوليس. كان متروبوليس، المُلمّ بالجوانب الحسابية للطريقة، قد صاغ مصطلح "مونت كارلو" في مقالٍ سابقٍ مع ستانيسواف أولام ، وقاد الفريق في القسم النظري الذي صمّم وبنى حاسوب MANIAC I المُستخدم في التجارب عام 1952. مع ذلك، لم يكن هناك سردٌ مُفصّلٌ لتطوير الخوارزمية قبل عام 2003. قبل وفاته بفترةٍ وجيزة، حضر مارشال روزنبلث مؤتمرًا في مختبر لوس ألاموس الوطني (LANL) عام 2003 بمناسبة الذكرى الخمسين لنشر الخوارزمية عام 1953. في هذا المؤتمر، وصف روزنبلث الخوارزمية وتطويرها في عرضٍ تقديميٍّ بعنوان "نشأة خوارزمية مونت كارلو للميكانيكا الإحصائية". ^{[ 4 ]} وقدّم غوبرناتيس مزيدًا من التوضيحات التاريخية في مقالٍ نُشر عام 2005 ^{[ 5 ]} يروي فيه أحداث مؤتمر الذكرى الخمسين. يوضح روزنبلث أنه وزوجته أريانا قاما بالعمل، وأن متروبوليس لم تلعب أي دور في التطوير سوى توفير وقت الكمبيوتر.

يتناقض هذا مع رواية إدوارد تيلر، الذي ذكر في مذكراته أن المؤلفين الخمسة لمقال عام 1953 عملوا معًا "لأيام (وليالٍ)". ^{[ 6 ]} في المقابل، تُنسب رواية روزنبلث المفصلة إلى تيلر اقتراحًا بالغ الأهمية ولكنه مبكر، وهو "الاستفادة من الميكانيكا الإحصائية وأخذ المتوسطات الجماعية بدلًا من اتباع علم الحركة التفصيلي ". ويقول روزنبلث إن هذا الأمر دفعه للتفكير في منهج مونت كارلو المعمم، وهو موضوع يقول إنه ناقشه كثيرًا مع جون فون نيومان . وروت أريانا روزنبلث (لغوبرناتيس عام 2003) أن أوغستا تيلر بدأت العمل على الحاسوب، لكن أريانا نفسها تولت الأمر وكتبت الشفرة من الصفر. وفي تاريخ شفوي سُجّل قبل وفاته بفترة وجيزة، ^{[ 7 ]} يُنسب روزنبلث مرة أخرى إلى تيلر طرح المشكلة الأصلية، وإلى نفسه حلها، وإلى أريانا برمجة الحاسوب.

تستطيع خوارزمية متروبوليس-هاستينغز سحب عينات من أي توزيع احتمالي ذي كثافة احتمالية${\displaystyle P(x)}$بشرط أن نعرف دالة${\displaystyle f(x)}$يتناسب مع الكثافة${\displaystyle P}$وقيم${\displaystyle f(x)}$يمكن حسابها. الشرط الذي${\displaystyle f(x)}$إن كون المعامل متناسبًا مع الكثافة فقط، وليس مساويًا لها تمامًا، يجعل خوارزمية متروبوليس-هاستينغز مفيدة بشكل خاص، لأنها تزيل الحاجة إلى حساب عامل تطبيع الكثافة، وهو أمر صعب للغاية في كثير من الأحيان من الناحية العملية.

تُولّد خوارزمية متروبوليس-هاستينغز سلسلة من قيم العينات بطريقة تجعل توزيع القيم، مع ازدياد عدد قيم العينات المُنتجة، أقرب إلى التوزيع المطلوب. تُنتج هذه القيم بشكل تكراري بحيث يعتمد توزيع العينة التالية فقط على قيمة العينة الحالية، مما يجعل سلسلة العينات سلسلة ماركوف . تحديدًا، في كل تكرار، تقترح الخوارزمية مرشحًا لقيمة العينة التالية بناءً على قيمة العينة الحالية. ثم، باحتمالية معينة، يُقبل المرشح، وفي هذه الحالة تُستخدم قيمته في التكرار التالي، أو يُرفض، وفي هذه الحالة تُهمل قيمته، وتُعاد استخدام القيمة الحالية في التكرار التالي. تُحدد احتمالية القبول بمقارنة قيم الدالة.${\displaystyle f(x)}$من قيم العينة الحالية والمرشحة فيما يتعلق بالتوزيع المطلوب.

تتميز الطريقة المستخدمة لاقتراح مرشحين جدد بتوزيع الاحتمالات.${\displaystyle g(x\mid y)}$(يكتب أحيانًا)${\displaystyle Q(x\mid y)}$) من عينة مقترحة جديدة${\displaystyle x}$بالنظر إلى العينة السابقة${\displaystyle y}$يُطلق على هذا اسم كثافة الاقتراح ، أو دالة الاقتراح ، أو التوزيع القافز . وهو خيار شائع لـ${\displaystyle g(x\mid y)}$هو توزيع غاوسي متمركز عند${\displaystyle y}$، بحيث تشير هذه النقاط إلى أقرب${\displaystyle y}$من المرجح أن تتم زيارتها لاحقًا، مما يجعل تسلسل العينات أشبه بمسار عشوائي غاوسي . في الورقة البحثية الأصلية التي نشرها متروبوليس وآخرون (1953)،${\displaystyle g(x\mid y)}$وقد تم اقتراح أن يكون توزيعًا منتظمًا يقتصر على مسافة قصوى معينة من${\displaystyle y}$. كما أن وظائف الاقتراح الأكثر تعقيدًا ممكنة أيضًا، مثل تلك الخاصة بـ Hamiltonian Monte Carlo أو Langevin Monte Carlo أو Crank–Nicolson المشروط مسبقًا .

ولغرض التوضيح، يتم وصف خوارزمية متروبوليس، وهي حالة خاصة من خوارزمية متروبوليس-هاستينغز حيث تكون دالة الاقتراح متناظرة، أدناه.

خوارزمية متروبوليس (توزيع الاقتراحات المتماثل)

يترك${\displaystyle f(x)}$لتكن دالة تتناسب مع دالة كثافة الاحتمال المطلوبة${\displaystyle P(x)}$(المعروف أيضًا باسم التوزيع المستهدف). ^{[ أ ]}

1. التهيئة: اختر نقطة عشوائية${\displaystyle x_{t}}$أن تكون أول ملاحظة في العينة واختيار دالة اقتراح${\displaystyle g(x\mid y)}$. في هذا القسم،${\displaystyle g}$يُفترض أن يكون متناظرًا؛ بمعنى آخر، يجب أن يحقق${\displaystyle g(x\mid y)=g(y\mid x)}$.
2. لكل تكرار t :
   • اقترح مرشحًا${\displaystyle x'}$بالنسبة للعينة التالية، يتم الاختيار من التوزيع.${\displaystyle g(x'\mid x_{t})}$.
   • احسب نسبة القبول${\displaystyle \alpha =f(x')/f(x_{t})}$، والتي ستُستخدم لتحديد ما إذا كان سيتم قبول المرشح أو رفضه. ^{[ ب ]} بما أن f تتناسب مع كثافة P ، فإن لدينا أن${\displaystyle \alpha =f(x')/f(x_{t})=P(x')/P(x_{t})}$.
   • قبول أو رفض :
     • قم بتوليد عدد عشوائي منتظم${\displaystyle u\in [0,1]}$.
     • لو${\displaystyle u\leq \alpha }$ثم اقبل المرشح عن طريق تحديد${\displaystyle x_{t+1}=x'}$،
     • لو${\displaystyle u>\alpha }$ثم ارفض المرشح وحدد${\displaystyle x_{t+1}=x_{t}}$بدلاً من.

تعتمد هذه الخوارزمية على محاولة التحرك بشكل عشوائي في فضاء العينة ، حيث تقبل التحركات أحيانًا وتبقى في مكانها أحيانًا أخرى.${\displaystyle P(x)}$عند نقطة محددة${\displaystyle x}$يتناسب مع عدد التكرارات التي يقضيها الخوارزمية على النقطة. لاحظ أن نسبة القبول${\displaystyle \alpha }$يشير إلى مدى احتمالية العينة المقترحة الجديدة بالنسبة للعينة الحالية، وفقًا للتوزيع الذي تكون كثافته${\displaystyle P(x)}$إذا حاولنا الانتقال إلى نقطة أكثر احتمالاً من النقطة الحالية (أي نقطة في منطقة ذات كثافة أعلى من${\displaystyle P(x)}$بما يتوافق مع${\displaystyle \alpha >1\geq u}$سنقبل هذه الخطوة دائمًا. مع ذلك، إذا حاولنا الانتقال إلى نقطة أقل احتمالًا، فسنرفض هذه الخطوة أحيانًا، وكلما زاد الانخفاض النسبي في الاحتمال، زاد احتمال رفضنا للنقطة الجديدة. لذا، سنميل إلى البقاء في المناطق ذات الكثافة العالية (وإعادة أعداد كبيرة من العينات منها).${\displaystyle P(x)}$، مع زيارة المناطق منخفضة الكثافة من حين لآخر فقط. وبشكل بديهي، هذا هو سبب نجاح هذه الخوارزمية وإرجاعها عينات تتبع التوزيع المطلوب بكثافة${\displaystyle P(x)}$.

بالمقارنة مع خوارزمية مثل أخذ العينات بالرفض التكيفي ^{[ 8 ]} التي تولد عينات مستقلة مباشرة من التوزيع، فإن خوارزمية متروبوليس-هاستينغز وغيرها من خوارزميات سلسلة ماركوف مونت كارلو لها عدد من العيوب:

• العينات مرتبطة ذاتيًا . على الرغم من أنها تتبع بشكل صحيح على المدى الطويل${\displaystyle P(x)}$ستكون مجموعة من العينات المتقاربة مرتبطة ببعضها البعض ولن تعكس التوزيع بدقة. هذا يعني أن أحجام العينات الفعالة قد تكون أقل بكثير من عدد العينات المأخوذة فعليًا، مما يؤدي إلى أخطاء كبيرة.
• على الرغم من أن سلسلة ماركوف تتقارب في النهاية إلى التوزيع المطلوب، إلا أن العينات الأولية قد تتبع توزيعًا مختلفًا تمامًا، خاصةً إذا كانت نقطة البداية في منطقة ذات كثافة منخفضة. ونتيجةً لذلك، عادةً ما تكون فترة تهيئة ضرورية ^{[ 9 ]} ، حيث يتم التخلص من عدد أولي من العينات.

من جهة أخرى، تعاني معظم طرق أخذ العينات بالرفض البسيطة من " لعنة الأبعاد "، حيث يزداد احتمال الرفض بشكل أُسّي مع ازدياد عدد الأبعاد. أما طريقة متروبوليس-هاستينغز، إلى جانب طرق سلسلة ماركوف مونت كارلو الأخرى، فلا تعاني من هذه المشكلة بهذا القدر، ولذا فهي غالباً الحلول الوحيدة المتاحة عندما يكون عدد أبعاد التوزيع المراد أخذ عينات منه كبيراً. ونتيجة لذلك، تُعدّ طرق سلسلة ماركوف مونت كارلو الخيار الأمثل لإنتاج عينات من النماذج البايزية الهرمية وغيرها من النماذج الإحصائية عالية الأبعاد المستخدمة حالياً في العديد من التخصصات.

في التوزيعات متعددة المتغيرات ، تتضمن خوارزمية متروبوليس-هاستينغز الكلاسيكية، كما وُصفت سابقًا، اختيار نقطة عينة جديدة متعددة الأبعاد. عندما يكون عدد الأبعاد كبيرًا، قد يكون من الصعب إيجاد توزيع القفز المناسب، نظرًا لاختلاف سلوك كل بُعد على حدة، وضرورة أن يكون عرض القفز (انظر أعلاه) مناسبًا تمامًا لجميع الأبعاد في آنٍ واحد لتجنب الخلط البطيء للغاية. ثمة نهج بديل، غالبًا ما يكون أكثر فعالية في مثل هذه الحالات، يُعرف باسم أخذ عينات جيبس ، ويتضمن اختيار عينة جديدة لكل بُعد على حدة، بدلًا من اختيار عينة لجميع الأبعاد دفعة واحدة. بهذه الطريقة، تُختزل مشكلة أخذ العينات من فضاء ذي أبعاد عالية محتملة إلى مجموعة من مشاكل أخذ العينات من فضاء ذي أبعاد صغيرة. ^{[ 10 ]} ينطبق هذا بشكل خاص عندما يتكون التوزيع متعدد المتغيرات من مجموعة من المتغيرات العشوائية الفردية ، حيث يكون كل متغير مشروطًا بعدد قليل فقط من المتغيرات الأخرى، كما هو الحال في معظم النماذج الهرمية النموذجية . ثم تُؤخذ عينات من المتغيرات الفردية واحدًا تلو الآخر، مع اشتراط كل متغير على أحدث قيم جميع المتغيرات الأخرى. يمكن استخدام خوارزميات متنوعة لاختيار هذه العينات الفردية، اعتمادًا على الشكل الدقيق للتوزيع متعدد المتغيرات: من بين الاحتمالات طرق أخذ العينات بالرفض التكيفي ، ^{[ 8 ]} وخوارزمية أخذ عينات متروبوليس بالرفض التكيفي، ^{[ 11 ]} وخطوة متروبوليس-هاستينغز أحادية البعد البسيطة، أو أخذ عينات الشرائح .

الغرض من خوارزمية متروبوليس-هاستينغز هو توليد مجموعة من الحالات وفقًا لتوزيع مرغوب فيه${\displaystyle P(x)}$ولتحقيق ذلك، تستخدم الخوارزمية عملية ماركوف ، التي تصل بشكل تقاربي إلى توزيع ثابت فريد${\displaystyle \pi (x)}$بحيث${\displaystyle \pi (x)=P(x)}$[ ^{12 ]​}

تُعرَّف عملية ماركوف بشكل فريد من خلال احتمالات انتقالها.${\displaystyle P(x'\mid x)}$، احتمال الانتقال من أي حالة معينة${\displaystyle x}$إلى أي ولاية أخرى معينة${\displaystyle x'}$. يتميز بتوزيع ثابت فريد${\displaystyle \pi (x)}$عند استيفاء الشرطين التاليين: ^{[ 12 ]}

1. وجود توزيع ثابت : يجب أن يكون هناك توزيع ثابت${\displaystyle \pi (x)}$يُعد التوازن التفصيلي شرطًا كافيًا ولكنه ليس شرطًا ضروريًا ، وهو ما يتطلب أن يكون كل انتقال${\displaystyle x\to x'}$قابل للعكس: لكل زوج من الحالات${\displaystyle x,x'}$، احتمال التواجد في الحالة${\displaystyle x}$والانتقال إلى الدولة${\displaystyle x'}$يجب أن يساوي احتمال التواجد في الحالة${\displaystyle x'}$والانتقال إلى الدولة${\displaystyle x}$،${\displaystyle \pi (x)P(x'\mid x)=\pi (x')P(x\mid x')}$.
2. تفرد التوزيع الثابت : التوزيع الثابت${\displaystyle \pi (x)}$يجب أن تكون فريدة. هذا مضمون من خلال خاصية الإرجودية لعملية ماركوف، والتي تتطلب أن تكون كل حالة (1) غير دورية - أي أن النظام لا يعود إلى نفس الحالة على فترات زمنية ثابتة؛ و(2) متكررة موجبة - أي أن العدد المتوقع للخطوات اللازمة للعودة إلى نفس الحالة محدود.

تتضمن خوارزمية متروبوليس-هاستينغز تصميم عملية ماركوف (عن طريق بناء احتمالات الانتقال) التي تحقق الشرطين المذكورين أعلاه، بحيث يكون توزيعها الثابت${\displaystyle \pi (x)}$يتم اختياره ليكون${\displaystyle P(x)}$يبدأ اشتقاق الخوارزمية بشرط التوازن التفصيلي :

${\displaystyle P(x'\mid x)P(x)=P(x\mid x')P(x'),}$

والتي أعيدت كتابتها على النحو التالي

${\displaystyle {\frac {P(x'\mid x)}{P(x\mid x')}}={\frac {P(x')}{P(x)}}.}$

يتمثل النهج في فصل عملية الانتقال إلى خطوتين فرعيتين: الاقتراح والقبول أو الرفض. توزيع الاقتراح${\displaystyle g(x'\mid x)}$هي الاحتمالية الشرطية لاقتراح حالة${\displaystyle x'}$منح${\displaystyle x}$وتوزيع القبول${\displaystyle A(x',x)}$احتمال قبول الحالة المقترحة${\displaystyle x'}$يمكن كتابة احتمالية الانتقال كحاصل ضربهما:

${\displaystyle P(x'\mid x)=g(x'\mid x)A(x',x).}$

بإدخال هذه العلاقة في المعادلة السابقة، نحصل على

${\displaystyle {\frac {A(x',x)}{A(x,x')}}={\frac {P(x')}{P(x)}}{\frac {g(x\mid x')}{g(x'\mid x)}}.}$

تتمثل الخطوة التالية في عملية الاشتقاق في اختيار نسبة قبول تحقق الشرط المذكور أعلاه. ومن الخيارات الشائعة خيار متروبوليس.

${\displaystyle A(x',x)=\min \left(1,{\frac {P(x')}{P(x)}}{\frac {g(x\mid x')}{g(x'\mid x)}}\right).}$

نسبة قبول هذه المدينة الكبرى${\displaystyle A}$، أيضاً${\displaystyle A(x',x)=1}$أو${\displaystyle A(x,x')=1}$وفي كلتا الحالتين، يتحقق الشرط.

وبالتالي، يمكن كتابة خوارزمية متروبوليس-هاستينغز على النحو التالي:

1. تهيئة
   1. اختر حالة أولية${\displaystyle x_{0}}$.
   2. تعيين${\displaystyle t=0}$.
2. أعاد
   1. قم بتوليد حالة مرشحة عشوائية${\displaystyle x'}$وفق${\displaystyle g(x'\mid x_{t})}$.
   2. احسب احتمالية القبول${\displaystyle A(x',x_{t})=\min \left(1,{\frac {P(x')}{P(x_{t})}}{\frac {g(x_{t}\mid x')}{g(x'\mid x_{t})}}\right)}$.
   3. قبول أو رفض :
      1. قم بتوليد عدد عشوائي منتظم${\displaystyle u\in [0,1]}$؛
      2. لو${\displaystyle u\leq A(x',x_{t})}$ثم اقبل الحالة الجديدة وقم بتعيينها${\displaystyle x_{t+1}=x'}$؛
      3. لو${\displaystyle u>A(x',x_{t})}$ثم ارفض الحالة الجديدة، وانسخ الحالة القديمة إلى الأمام${\displaystyle x_{t+1}=x_{t}}$.
   4. الزيادة : تعيين${\displaystyle t=t+1}$.

شريطة استيفاء الشروط المحددة، فإن التوزيع التجريبي للحالات المحفوظة${\displaystyle x_{0},\ldots ,x_{T}}$سوف يقترب${\displaystyle P(x)}$عدد التكرارات (${\displaystyle T}$) مطلوب لتقدير فعال${\displaystyle P(x)}$يعتمد ذلك على عدد من العوامل، بما في ذلك العلاقة بين${\displaystyle P(x)}$وتوزيع الاقتراح ودقة التقدير المطلوبة. ^{[ 13 ]} بالنسبة للتوزيع على فضاءات الحالة المنفصلة، ​​يجب أن يكون من رتبة زمن الارتباط الذاتي لعملية ماركوف. ^{[ 14 ]} يُقدَّم شرحٌ مُبسَّط لنظرية التقارب لخوارزمية متروبوليس-هاستينغز في ^{[ 15 ] .}

من المهم ملاحظة أنه ليس من الواضح، في مشكلة عامة، أي توزيع${\displaystyle g(x'\mid x)}$ينبغي على المرء استخدام عدد التكرارات اللازمة للتقدير الصحيح؛ كلاهما معلمات حرة للطريقة، والتي يجب تعديلها وفقًا للمشكلة المحددة قيد الدراسة.

يُستخدم خوارزمية متروبوليس-هاستينغز بشكل شائع لحساب التكامل. على وجه التحديد، لنفترض فضاءً${\displaystyle \Omega \subset \mathbb {R} }$وتوزيع احتمالي${\displaystyle P(x)}$زيادة${\displaystyle \Omega }$،${\displaystyle x\in \Omega }$يمكن لطريقة متروبوليس-هاستينغز تقدير تكامل على شكل

${\displaystyle P(E)=\int _{\Omega }A(x)P(x)\,dx,}$

أين${\displaystyle A(x)}$هي دالة (قابلة للقياس) ذات أهمية.

على سبيل المثال، لنفترض إحصائية${\displaystyle E(x)}$وتوزيع احتمالاته${\displaystyle P(E)}$وهو توزيع هامشي . لنفترض أن الهدف هو تقدير${\displaystyle P(E)}$ل${\displaystyle E}$في أعقاب${\displaystyle P(E)}$رسميًا،${\displaystyle P(E)}$يمكن كتابتها على النحو التالي

${\displaystyle P(E)=\int _{\Omega }P(E\mid x)P(x)\,dx=\int _{\Omega }\delta {\big (}E-E(x){\big )}P(x)\,dx=E{\big (}P(E\mid X){\big )}}$

وبالتالي، تقدير${\displaystyle P(E)}$ويمكن تحقيق ذلك من خلال تقدير القيمة المتوقعة لدالة المؤشر${\displaystyle A_{E}(x)\equiv \mathbf {1} _{E}(x)}$، وهو ما يساوي 1 عندما${\displaystyle E(x)\in [E,E+\Delta E]}$وصفر فيما عدا ذلك. لأن${\displaystyle E}$وهو في ذيل${\displaystyle P(E)}$، احتمال سحب بطاقة ولاية${\displaystyle x}$مع${\displaystyle E(x)}$في أعقاب${\displaystyle P(E)}$يتناسب مع${\displaystyle P(E)}$وهو صغير بحكم التعريف. يمكن استخدام خوارزمية متروبوليس-هاستينغز هنا لأخذ عينات من الحالات (النادرة) الأكثر احتمالاً، وبالتالي زيادة عدد العينات المستخدمة للتقدير.${\displaystyle P(E)}$على الذيول. يمكن القيام بذلك، على سبيل المثال، باستخدام توزيع المعاينة.${\displaystyle \pi (x)}$لتفضيل تلك الدول (مثلاً)${\displaystyle \pi (x)\propto e^{aE}}$مع${\displaystyle a>0}$).

لنفترض أن أحدث قيمة تم أخذ عينة منها هي${\displaystyle x_{t}}$ولمتابعة خوارزمية متروبوليس-هاستينغز، نقوم بعد ذلك برسم حالة اقتراح جديدة${\displaystyle x'}$مع كثافة الاحتمال${\displaystyle g(x'\mid x_{t})}$واحسب القيمة

${\displaystyle a=a_{1}a_{2},}$

أين

${\displaystyle a_{1}={\frac {P(x')}{P(x_{t})}}}$

هي نسبة الاحتمال (مثل الاحتمال الخلفي البايزي) بين العينة المقترحة${\displaystyle x'}$والعينة السابقة${\displaystyle x_{t}}$، و

${\displaystyle a_{2}={\frac {g(x_{t}\mid x')}{g(x'\mid x_{t})}}}$

هي نسبة كثافة الاقتراح في اتجاهين (من${\displaystyle x_{t}}$ل${\displaystyle x'}$والعكس صحيح). وهذا يساوي 1 إذا كانت كثافة الاقتراح متناظرة. عندئذٍ تكون الحالة الجديدة${\displaystyle x_{t+1}}$يتم الاختيار وفقًا للقواعد التالية.

لو${\displaystyle a\geq 1{:}}$

${\displaystyle x_{t+1}=x',}$

آخر:

${\displaystyle x_{t+1}={\begin{cases}x'&{\text{with probability }}a,\\x_{t}&{\text{with probability }}1-a.\end{cases}}}$

تبدأ سلسلة ماركوف من قيمة ابتدائية عشوائية${\displaystyle x_{0}}$ويتم تشغيل الخوارزمية لعدة دورات حتى يتم "نسيان" هذه الحالة الأولية. تُعرف هذه العينات، التي يتم تجاهلها، باسم عينات التثبيت . أما المجموعة المتبقية من القيم المقبولة فهي${\displaystyle x}$تمثل عينة من التوزيع${\displaystyle P(x)}$.

تعمل الخوارزمية بشكل أفضل إذا تطابقت كثافة الاقتراح مع شكل التوزيع المستهدف${\displaystyle P(x)}$والتي يصعب أخذ عينات مباشرة منها، أي${\displaystyle g(x'\mid x_{t})\approx P(x')}$إذا كانت كثافة اقتراح غاوسية${\displaystyle g}$يُستخدم معامل التباين${\displaystyle \sigma ^{2}}$يجب ضبطه خلال فترة التشغيل الأولي. ويتم ذلك عادةً عن طريق حساب معدل القبول ، وهو نسبة العينات المقترحة التي يتم قبولها في نافذة من آخر${\displaystyle N}$تعتمد نسبة القبول المطلوبة على التوزيع المستهدف، ولكن أظهرت الدراسات النظرية أن نسبة القبول المثالية لتوزيع غاوسي أحادي البعد تبلغ حوالي 50%، وتنخفض إلى حوالي 23% لتوزيع غاوسي أحادي البعد.${\displaystyle N}$توزيع غاوسي مستهدف ذو أبعاد n. ^{[ 16 ]} يمكن أن تكون هذه الإرشادات فعالة عند أخذ عينات من توزيعات بايزية خلفية منتظمة بدرجة كافية، حيث إنها غالبًا ما تتبع توزيعًا طبيعيًا متعدد المتغيرات، كما يمكن إثبات ذلك باستخدام نظرية برنشتاين-فون ميزس . ^{[ 17 ]}

لو${\displaystyle \sigma ^{2}}$إذا كانت صغيرة جدًا، فسوف يختلط التسلسل ببطء (أي أن معدل القبول سيكون مرتفعًا، لكن العينات المتتالية ستتحرك في الفضاء ببطء، ولن يتقارب التسلسل إلا ببطء).${\displaystyle P(x)}$من ناحية أخرى، إذا${\displaystyle \sigma ^{2}}$إذا كانت المساحة كبيرة جدًا، فسيكون معدل القبول منخفضًا للغاية لأن المقترحات من المرجح أن تقع في مناطق ذات كثافة احتمالية أقل بكثير، لذلك${\displaystyle a_{1}}$سيكون حجمها صغيرًا جدًا، وبالتالي ستتقارب السلسلة ببطء شديد. عادةً ما يتم ضبط توزيع الاقتراحات بحيث تقبل الخوارزميات ما يقارب 30% من جميع العينات، بما يتماشى مع التقديرات النظرية المذكورة في الفقرة السابقة.

يمكن استخدام طريقة ماركوف مونت كارلو المتسلسلة (MCMC) لسحب عينات من التوزيع الاحتمالي اللاحق لنموذج إحصائي . ويُعطى احتمال القبول بالصيغة التالية: ${\displaystyle P_{acc}(\theta _{i}\to \theta ^{*})=\min \left(1,{\frac {{\mathcal {L}}(y|\theta ^{*})P(\theta ^{*})}{{\mathcal {L}}(y|\theta _{i})P(\theta _{i})}}{\frac {Q(\theta _{i}|\theta ^{*})}{Q(\theta ^{*}|\theta _{i})}}\right),}$ أين${\displaystyle {\mathcal {L}}}$الاحتمالية ،​${\displaystyle P(\theta )}$كثافة الاحتمال المسبق و${\displaystyle Q}$احتمالية الاقتراح (الشرطي).

• الخوارزميات الجينية
• طرق الجسيمات ذات المجال المتوسط
• وسائل النقل الخفيف في المدينة
• متروبوليس متعدد المحاولات
• التصليد المتوازي
• مونت كارلو المتسلسل
• التلدين المحاكي

• بيرغ، بيرند أ. (أكتوبر 2004). محاكاة مونت كارلو لسلاسل ماركوف وتحليلها الإحصائي: باستخدام كود فورتران على الويب . وورلد ساينتيفيك . doi : 10.1142/5602 . ISBN 978-981-238-935-0.
• شيب، سيدهارتا؛ غرينبيرغ، إدوارد (نوفمبر 1995). "فهم خوارزمية متروبوليس-هاستينغز" . الإحصائي الأمريكي . 49 (4): 327. doi : 10.2307/2684568 .
• مينه، ديفيد دي إل؛ مينه، دو لي (بول) (2015-02-07). "فهم خوارزمية هاستينغز" . الاتصالات في الإحصاء - المحاكاة والحساب . 44 (2): 332-349 . arXiv : 1408.4438 . doi : 10.1080/03610918.2013.777455 . ISSN 0361-0918 . 
• بولستاد، ويليام م. (2010). فهم الإحصاءات البايزية الحاسوبية . سلسلة وايلي في الإحصاءات الحاسوبية. هوبوكين، نيوجيرسي: وايلي. ISBN 978-0-470-04609-8.