سلسلة ماركوف مونت كارلو

تذكر أنه في الحالة المنفصلة، ​​يُقال إن سلسلة ماركوف غير قابلة للاختزال إذا كان من الممكن الوصول إلى أي حالة من أي حالة أخرى في عدد محدود من الخطوات باحتمالية موجبة. مع ذلك، في الحالة المستمرة، تكون احتمالية الانتقالات من نقطة إلى أخرى صفرًا. في هذه الحالة، تعمم عدم قابلية الاختزال φ مفهوم عدم الاختزال باستخدام مقياس مرجعي φ على الفضاء القابل للقياس.${\displaystyle ({\mathcal {X}},{\mathcal {B}}({\mathcal {X}}))}$.

التعريف (φ-عدم الاختزال)

بالنظر إلى مقياس${\displaystyle \varphi }$محدد في${\displaystyle ({\mathcal {X}},{\mathcal {B}}({\mathcal {X}}))}$سلسلة ماركوف${\displaystyle (X_{n})}$مع نواة الانتقال${\displaystyle K(x,y)}$تكون غير قابلة للاختزال من النوع φ إذا، لكل${\displaystyle A\in {\mathcal {B}}({\mathcal {X}})}$مع${\displaystyle \varphi (A)>0}$، يوجد${\displaystyle n}$بحيث${\displaystyle K^{n}(x,A)>0}$للجميع${\displaystyle x\in {\mathcal {X}}}$(بمعنى آخر،${\displaystyle P_{x}(\tau _{A}<\infty )>0}$، هنا${\displaystyle \tau _{A}=\inf\{n\geq 1;X_{n}\in A\}}$هو الأول${\displaystyle n}$والتي تدخل السلسلة من أجلها في المجموعة${\displaystyle A}$).

هذا تعريف أعمّ لعدم قابلية اختزال سلسلة ماركوف في فضاء الحالة غير المنفصل. في الحالة المنفصلة، ​​يُقال إن سلسلة ماركوف غير القابلة للاختزال غير دورية إذا كان دورها يساوي 1. رسميًا، دورة الحالة${\displaystyle \omega \in {\mathcal {X}}}$يُعرَّف على النحو التالي:

${\displaystyle d(\omega ):=\mathrm {gcd} \{m\geq 1\,;\,K^{m}(\omega ,\omega )>0\}}$

بالنسبة للحالة العامة (غير المنفصلة)، نُعرّف اللا دورية من حيث المجموعات الصغيرة:

التعريف (طول الدورة والمجموعات الصغيرة)

سلسلة ماركوف غير قابلة للاختزال φ${\displaystyle (X_{n})}$يكون لها دورة طولها d إذا وُجدت مجموعة صغيرة${\displaystyle C}$، عدد صحيح مرتبط${\displaystyle M}$وتوزيع احتمالي${\displaystyle \nu _{M}}$بحيث يكون d هو القاسم المشترك الأكبر لـ:

${\displaystyle \{m\geq 1\,;\,\exists \,\delta _{m}>0{\text{ بحيث يكون }}C{\text{ صغيرًا لـ }}\nu _{m}\geq \delta _{m}\nu _{M}\}.}$

مجموعة${\displaystyle C}$يُطلق عليه اسم صغير إذا كان هناك${\displaystyle m\in \mathbb {N} ^{*}}$ومقياس غير صفري${\displaystyle \nu _{m}}$بحيث:

${\displaystyle K^{m}(x,A)\geq \nu _{m}(A),\quad \forall x\in C,\,\forall A\in {\mathcal {B}}({\mathcal {X}}).}$

تعريف (تكرار هاريس)

مجموعة${\displaystyle A}$هل متلازمة هاريس متكررة إذا${\displaystyle P_{x}(\eta _{A}=\infty )=1}$للجميع${\displaystyle x\in A}$، أين${\displaystyle \eta _{A}=\sum _{n=1}^{\infty }\mathbb {I} _{A}(X_{n})}$عدد زيارات السلسلة${\displaystyle (X_{n})}$إلى المجموعة${\displaystyle A}$.

السلسلة${\displaystyle (X_{n})}$يُقال إنها حالة متكررة وفقًا لهاريس إذا وُجد مقياس${\displaystyle \psi }$بحيث تكون السلسلة${\displaystyle \psi }$مجموعة غير قابلة للاختزال وكل مجموعة قابلة للقياس${\displaystyle A}$مع${\displaystyle \psi (A)>0}$هل مرض هاريس متكرر؟

يُعد المعيار التالي مفيدًا للتحقق من تكرار هاريس:

اقتراح

إذا لكل${\displaystyle A\in {\mathcal {B}}({\mathcal {X}})}$لدينا${\displaystyle P_{x}(\tau _{A}<\infty )=1}$لكل${\displaystyle x\in A}$، ثم${\displaystyle P_{x}(\eta _{A}=\infty )=1}$للجميع${\displaystyle x\in {\mathcal {X}}}$والسلسلة${\displaystyle (X_{n})}$هل مرض هاريس متكرر؟

لا يلزم هذا التعريف إلا عندما تكون مساحة الحالة${\displaystyle {\mathcal {X}}}$غير قابل للعد. في حالة القابل للعد، يتوافق التكرار مع${\displaystyle \mathbb {E} _{x}[\eta _{x}]=\infty }$وهو ما يعادل${\displaystyle P_{x}(\tau _{x}<\infty )=1}$للجميع${\displaystyle x\in {\mathcal {X}}}$.

التعريف (المقياس الثابت)

أ${\displaystyle \sigma }$-قياس محدود${\displaystyle \pi }$يقال إنها ثابتة بالنسبة لنواة الانتقال${\displaystyle K(\cdot ,\cdot )}$(والسلسلة المرتبطة بها) إذا:

${\displaystyle \pi (B)=\int _{\mathcal {X}}K(x,B)\,\pi (dx),\qquad \forall B\in {\mathcal {B}}({\mathcal {X}}).}$

عندما يوجد مقياس احتمالي ثابت لسلسلة غير قابلة للاختزال من النوع ψ (وبالتالي متكررة)، يُقال إن السلسلة متكررة موجبة . أما السلاسل المتكررة التي لا تسمح بوجود مقياس ثابت محدود فتُسمى متكررة صفرية .

في تطبيقات سلسلة ماركوف مونت كارلو (MCMC)، يتضمن معيار مفيد للغاية لتكرار هاريس استخدام الدوال التوافقية المحدودة.

التعريف (الدالة التوافقية)

دالة قابلة للقياس${\displaystyle h}$يقال إنها متناغمة بالنسبة للسلسلة${\displaystyle (X_{n})}$لو:

${\displaystyle \mathbb {E} [h(X_{n+1})\mid x_{n}]=h(x_{n})}$

هذه الدوال ثابتة تحت نواة الانتقال بالمعنى الوظيفي، وهي تساعد في تحديد خصائص تكرار هاريس.

اقتراح

بالنسبة لسلسلة ماركوف الموجبة، إذا كانت الدوال التوافقية المحدودة الوحيدة هي الدوال الثابتة، فإن السلسلة تكون متكررة من نوع هاريس.

نظرية (نظرية إرجوديك لسلسلة ماركوف مونت كارلو)

لو${\displaystyle (X_{n})}$لديه${\displaystyle \sigma }$مقياس ثابت محدود${\displaystyle \pi }$إذاً، فإن العبارتين التاليتين متكافئتان:

1. سلسلة ماركوف${\displaystyle (X_{n})}$هل مرض هاريس متكرر ؟
2. لو${\displaystyle f,g\in L^{1}(\pi )}$مع${\displaystyle \int g(x)\,d\pi (x)\neq 0}$، ثم${\displaystyle \lim _{n\to \infty }{\frac {S_{n}(f)}{S_{n}(g)}}={\frac {\int f(x)\,d\pi (x)}{\int g(x)\,d\pi (x)}}.}$

توفر هذه النظرية تبريراً أساسياً لاستخدام طرق سلسلة ماركوف مونت كارلو (MCMC)، وهي بمثابة نظير لقانون الأعداد الكبيرة (LLN) في مونت كارلو الكلاسيكي.

من الجوانب المهمة لهذه النتيجة أن${\displaystyle \pi }$لا يشترط أن يكون مقياسًا احتماليًا. لذا، قد يكون هناك نوع من الاستقرار القوي حتى لو كانت السلسلة متكررة صفريًا. علاوة على ذلك، يمكن بدء سلسلة ماركوف من أي حالة.

لو${\displaystyle \pi }$إذا كان مقياس احتمالي، فيمكننا أن نفرض${\displaystyle g\equiv 1}$واحصل على

${\displaystyle \lim _{n\to \infty }S_{n}(f)=\int f(x)\,d\pi (x).}$

هذه هي نظرية الإرجودية التي نعرفها أكثر.

توجد عدة شروط تتحقق بموجبها نظرية النهاية المركزية (CLT) لطرق مونت كارلو لسلاسل ماركوف (MCMC). أحد أكثر هذه الشروط شيوعاً هو شرط الانعكاسية .

التعريف (قابلية الانعكاس)

سلسلة ماركوف ثابتة${\displaystyle (X_{n})}$يُقال إن العملية قابلة للانعكاس إذا كان توزيع${\displaystyle X_{n+1}}$منح${\displaystyle X_{n+2}=x}$وهو نفس توزيع${\displaystyle X_{n+1}}$منح${\displaystyle X_{n}=x}$.

وهذا يعادل شرط التوازن التفصيلي ، والذي يتم تعريفه على النحو التالي:

التعريف ( الميزان التفصيلي )

سلسلة ماركوف ذات نواة انتقال${\displaystyle K}$يحقق شرط التوازن التفصيلي إذا وُجدت دالة${\displaystyle f}$بحيث:

${\displaystyle K(y,x)f(y)=K(x,y)f(x)}$

لكل زوج${\displaystyle (x,y)}$في فضاء الحالة.

نظرية (نظرية الانعكاسية المركزية)

لو${\displaystyle (X_{n})}$هي غير دورية، وغير قابلة للاختزال، وقابلة للعكس مع توزيع ثابت${\displaystyle \pi }$، ثم:

${\displaystyle {\frac {1}{\sqrt {N}}}\left(\sum _{n=1}^{N}\left(h(X_{n})-\mathbb {E} ^{\pi [h]\right)\right){\overset {\mathcal {L}}{\longrightarrow }}{\mathcal {N}}(0,\gamma _{h}^{2})}$

أين

${\displaystyle 0<\gamma _{h}^{2}=\mathbb {E} _{\pi }\left[{\bar {h}}^{2}(X_{0})\right]+2\sum _{k=1}^{\infty }\mathbb {E} _{\pi }\left[{\bar {h}}(X_{0}){\bar {h}}(X_{k})\right]<+\infty }$

و

${\displaystyle {\bar {h}}(\cdot )=h(\cdot )-E[h(\cdot )]}$.

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

يمكن تحديد تأثير الارتباط على التقدير كميًا من خلال نظرية النهاية المركزية لسلسلة ماركوف . بالنسبة لسلسلة تستهدف توزيعًا بتباين${\displaystyle \sigma ^{2}}$، تباين متوسط ​​العينة بعد${\displaystyle N}$عدد الخطوات تقريبًا${\displaystyle {\sigma ^{2}}{\big /}N_{\text{eff}}}$، أين${\displaystyle N_{\text{eff}}}$حجم العينة الفعال أصغر من${\displaystyle N}$وبصورة مكافئة، يمكن التعبير عن ذلك على النحو التالي:

${\displaystyle \mathrm {Var} ({\bar {X}}_{N})\approx {\frac {\sigma ^{2}}{N}}\left(1+2\sum _{k=1}^{\infty }\rho _{k}\right)}$

أين${\displaystyle {\bar {X}}_{N}}$هو متوسط ​​العينة و${\displaystyle \rho _{k}}$هو الارتباط الذاتي للسلسلة عند التأخير${\displaystyle k}$، كما هو مُعرَّف${\displaystyle \rho _{k}={\frac {\mathrm {Cov} (X_{0},X_{k})}{\sqrt {\mathrm {Var} (X_{0})\mathrm {Var} (X_{k})}}}}$المصطلح بين قوسين،${\displaystyle 1+2\sum _{k=1}^{\infty }\rho _{k}}$يُطلق عليه غالبًا اسم الارتباط الذاتي المتكامل. عندما لا يكون للسلسلة ارتباط ذاتي (${\displaystyle \rho _{k}=0}$للجميع${\displaystyle k\geq 1}$)، هذا العامل يساوي 1، ويستعيد المرء الوضع المعتاد${\displaystyle \sigma ^{2}/N}$التباين للعينات المستقلة. إذا كانت عينات السلسلة مترابطة بشكل كبير، فإن مجموع الارتباطات الذاتية يكون كبيرًا، مما يؤدي إلى تباين أكبر بكثير لـ${\displaystyle {\bar {X}}_{N}}$مقارنةً بالحالة المستقلة.

حجم العينة الفعال${\displaystyle N_{\text{eff}}}$يُعدّ هذا المقياس أداة تشخيصية مفيدة تُحوّل الارتباط الذاتي في سلسلة إلى عدد مكافئ من العينات المستقلة. ويُعرّف بالصيغة التالية:

${\displaystyle N_{\text{eff}}={\frac {N}{1+2\sum _{k=1}^{\infty }\rho _{k}}}}$

لهذا السبب.${\displaystyle N_{\text{eff}}}$يمثل عدد عمليات السحب المستقلة التي من شأنها أن تعطي نفس دقة التقدير التي يحققها${\displaystyle N}$يتم سحب البيانات التابعة من سلسلة ماركوف. على سبيل المثال، إذا${\displaystyle 1+2\sum _{k=1}^{\infty }\rho _{k}=5}$، ثم${\displaystyle N_{\text{eff}}=N/5}$، بمعنى سلسلة من الطول${\displaystyle N}$يحمل معلومات تعادل${\displaystyle N/5}$عينات مستقلة. في سيناريو مثالي بدون ارتباط،${\displaystyle \rho _{k}=0}$وبالتالي${\displaystyle N_{\text{eff}}\approx N}$لكن في سلسلة ذات مزج ضعيف وارتباط ذاتي قوي،${\displaystyle N_{\text{eff}}}$يمكن أن تكون أصغر بكثير من${\displaystyle N}$. من الناحية العملية، يعد رصد ESS لكل معلمة طريقة لقياس مدى وجود الارتباط: يشير انخفاض ESS إلى أنه قد يلزم إجراء المزيد من التكرارات لتحقيق عينة فعالة مرغوبة من عمليات السحب المستقلة.

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

نحدد عدة استراتيجيات عامة مثل إعادة تحديد المعلمات، وضبط الاقتراح التكيفي، وحجب المعلمات، والاسترخاء المفرط التي تساعد على تقليل الارتباط وتحسين كفاءة أخذ العينات ضمن إطار عمل MCMC القياسي.

• خوارزمية متروبوليس-هاستينغز : تُنشئ هذه الطريقة سلسلة ماركوف باستخدام كثافة اقتراح للخطوات الجديدة وطريقة لرفض بعض التحركات المقترحة. وهي في الواقع إطار عمل عام يتضمن، كحالات خاصة، خوارزمية MCMC (خوارزمية متروبوليس) الأولى والأبسط، بالإضافة إلى العديد من المتغيرات الأحدث المذكورة أدناه.
  • أخذ عينات جيبس : عندما يكون التوزيع المستهدف متعدد الأبعاد، تقوم خوارزمية أخذ عينات جيبس ^{​​[ 10 ]} بتحديث كل إحداثية من توزيعها الشرطي الكامل ، مع الأخذ في الاعتبار الإحداثيات الأخرى. يمكن اعتبار أخذ عينات جيبس ​​حالة خاصة من خوارزمية متروبوليس-هاستينغز، حيث يكون معدل القبول مساويًا لـ 1 بشكل موحد. عندما لا يكون السحب من التوزيعات الشرطية الكاملة أمرًا مباشرًا، تُستخدم خوارزميات أخذ عينات أخرى ضمن جيبس ​​(انظر على سبيل المثال ^{[ 11 ] و[ 12 ]} ). تحظى خوارزمية أخذ عينات جيبس ​​بشعبية كبيرة، ويرجع ذلك جزئيًا إلى أنها لا تتطلب أي "ضبط". يشبه هيكل خوارزمية أخذ عينات جيبس ​​إلى حد كبير هيكل الاستدلال التبايني لتصاعد الإحداثيات، حيث تستخدم كلتا الخوارزميتين التوزيعات الشرطية الكاملة في عملية التحديث. ^{[ 13 ]}
  • تعتمد خوارزمية لانجفين المعدلة وفقًا لنموذج متروبوليس وغيرها من الطرق التي تعتمد على تدرج (وربما المشتقة الثانية) لوغاريتم كثافة الهدف لاقتراح خطوات من المرجح أن تكون في اتجاه كثافة احتمالية أعلى. ^{[ 14 ]}
  • طريقة مونت كارلو الهاميلتونية (أو الهجينة ): تحاول هذه الطريقة تجنب سلوك المشي العشوائي من خلال إدخال متجه زخم مساعد وتطبيق ديناميكيات هاميلتونية ، بحيث تكون دالة طاقة الوضع هي الكثافة المستهدفة. يتم تجاهل عينات الزخم بعد أخذ العينات. نتيجةً لذلك، تتحرك المقترحات عبر فضاء العينات بخطوات أكبر؛ وبالتالي تكون أقل ارتباطًا وتتقارب مع التوزيع المستهدف بسرعة أكبر.
  • متروبوليس-هاستينغز الهامشي الزائف : تستبدل هذه الطريقة تقييم كثافة التوزيع المستهدف بتقدير غير متحيز وهي مفيدة عندما لا تكون الكثافة المستهدفة متاحة تحليليًا، على سبيل المثال نماذج المتغيرات الكامنة .
• أخذ العينات بالشرائح : تعتمد هذه الطريقة على مبدأ إمكانية أخذ عينات من توزيع ما عن طريق أخذ عينات منتظمة من المنطقة الواقعة أسفل منحنى دالة الكثافة. وتتناوب هذه الطريقة بين أخذ عينات منتظمة في الاتجاه الرأسي وأخذ عينات منتظمة من "الشريحة" الأفقية المحددة بالموقع الرأسي الحالي.
• متروبوليس متعددة المحاولات : هذه الطريقة هي شكل معدل من خوارزمية متروبوليس-هاستينغز، تسمح بإجراء عدة محاولات في كل نقطة. ومن خلال تمكين اتخاذ خطوات أكبر في كل تكرار، فإنها تساعد في التغلب على مشكلة الأبعاد الكبيرة.
• القفزة العكسية : تُعدّ هذه الطريقة صيغةً معدّلة من خوارزمية متروبوليس-هاستينغز، تسمح باقتراحات تُغيّر بُعد الفضاء. ^{[ 15 ]} لطالما استُخدمت طرق مونت كارلو لسلاسل ماركوف التي تُغيّر البُعد في تطبيقات الفيزياء الإحصائية ، حيث يُستخدم في بعض المسائل توزيعٌ يُمثّل مجموعةً إحصائيةً كبرى (على سبيل المثال، عندما يكون عدد الجزيئات في صندوقٍ ما مُتغيّرًا). لكنّ صيغة القفزة العكسية تُفيد عند إجراء مونت كارلو لسلاسل ماركوف أو أخذ عينات جيبس ​​على نماذج بايزية غير بارامترية ، مثل تلك التي تتضمّن عملية ديريشليه أو عملية المطعم الصيني ، حيث يُستنتج عدد مُكوّنات/مجموعات/إلخ الخلط تلقائيًا من البيانات.

تُعدّ منهجيات سلسلة ماركوف مونت كارلو التفاعلية فئةً من طرق الجسيمات ذات المجال المتوسط، تُستخدم للحصول على عينات عشوائية من سلسلة من التوزيعات الاحتمالية ذات مستوى متزايد من تعقيد أخذ العينات. ^{[ 16 ]} تشمل هذه النماذج الاحتمالية نماذج حالة فضاء المسار ذات الأفق الزمني المتزايد، والتوزيعات اللاحقة المتعلقة بسلسلة من الملاحظات الجزئية، ومجموعات مستويات القيود المتزايدة للتوزيعات الشرطية، وجداول درجات الحرارة المتناقصة المرتبطة ببعض توزيعات بولتزمان-جيبس، وغيرها الكثير. من حيث المبدأ، يمكن تحويل أي خوارزمية أخذ عينات من سلسلة ماركوف مونت كارلو إلى خوارزمية تفاعلية. ويمكن تفسير هذه الخوارزميات التفاعلية على أنها طريقة لتشغيل سلسلة من خوارزميات سلسلة ماركوف مونت كارلو بالتوازي. على سبيل المثال، تعتمد خوارزميات التلدين المحاكي التفاعلية على تحركات متروبوليس-هاستينغز المستقلة التي تتفاعل بالتتابع مع آلية من نوع الاختيار وإعادة أخذ العينات. على عكس طرق مونت كارلو التقليدية لسلاسل ماركوف، فإنّ معيار الدقة في هذه الفئة من خوارزميات مونت كارلو التفاعلية لسلاسل ماركوف يرتبط فقط بعدد هذه الخوارزميات التفاعلية. تنتمي هذه المنهجيات المتقدمة للجسيمات إلى فئة نماذج فاينمان-كاك للجسيمات، ^{[ 17 ] [ 18 ]} والتي تُعرف أيضًا باسم مونت كارلو التسلسلي أو طرق مرشح الجسيمات في مجتمعات الاستدلال البايزي ومعالجة الإشارات . ^{[ 19 ]} ويمكن أيضًا تفسير طرق مونت كارلو التفاعلية لسلاسل ماركوف على أنها خوارزمية جسيمات جينية تعتمد على الطفرات الانتقائية مع طفرات مونت كارلو لسلاسل ماركوف.

طريقة شبه مونت كارلو هي نظير لطريقة مونت كارلو العادية، لكنها تستخدم متواليات ذات تباين منخفض بدلاً من الأرقام العشوائية. ^{[ 20 ] [ 21 ]} ينتج عنها خطأ تكامل يتلاشى أسرع من خطأ أخذ العينات العشوائية الحقيقية، كما هو موضح في متباينة كوكسما-هلاوكا . عمليًا، تسمح هذه الطريقة بتقليل كل من خطأ التقدير ووقت التقارب بمقدار عشرة أضعاف. ^{[ 20 ]} تجمع طرق شبه مونت كارلو لسلسلة ماركوف ^{[ 22 ] [ 23 ]} ، مثل طريقة Array-RQMC، بين شبه مونت كارلو العشوائي ومحاكاة سلسلة ماركوف من خلال محاكاة${\displaystyle n}$تُحلل السلاسل في آنٍ واحد بطريقة تُقارب التوزيع الحقيقي للسلسلة بشكل أفضل من طريقة ماركوف مونت كارلو التقليدية. ^{[ 24 ]} في التجارب العملية، يتقارب تباين متوسط ​​دالة الحالة أحيانًا بمعدل${\displaystyle O(n^{-2})}$أو حتى أسرع من ذلك، بدلاً من${\displaystyle O(n^{-1})}$معدل مونت كارلو. ^{[ 25 ]}

في الإحصاء البايزي، تُستخدم عادةً طرق مونت كارلو لسلاسل ماركوف لحساب العزوم وفترات الثقة لتوزيعات الاحتمال اللاحق . يُمكّن استخدام طرق مونت كارلو لسلاسل ماركوف من حساب نماذج هرمية كبيرة تتطلب عمليات تكامل على مئات إلى آلاف من المعلمات المجهولة. ^{[ 30 ]}

يمكن معالجة العديد من المشكلات البحثية المعاصرة في الفيزياء الإحصائية بحلول تقريبية باستخدام محاكاة مونت كارلو، التي توفر رؤى قيّمة حول خصائص الأنظمة المعقدة. تُعدّ طرق مونت كارلو أساسية في الفيزياء الحاسوبية، والفيزياء الفلكية، والكيمياء الفيزيائية، والتخصصات ذات الصلة، ولها تطبيقات واسعة تشمل الفيزياء الطبية، حيث تُستخدم لنمذجة انتقال الإشعاع لحساب جرعات الإشعاع. ^{[ 31 ] [ 32 ]} بدلاً من التحليل الشامل لجميع حالات النظام الممكنة، تفحص طريقة مونت كارلو عشوائيًا مجموعة فرعية منها لتشكيل عينة تمثيلية، وتُنتج تقريبات دقيقة لخصائص النظام المميزة. ومع ازدياد عدد الحالات المأخوذة منها العينة، يمكن تقليل الخطأ إلى مستوى أدنى.

تُستخدم ديناميكيات لانجفين عادةً في أخذ عينات التوزيعات المعقدة والنمذجة التوليدية، ^{[ 33 ] [ 34 ]} عبر إجراء MCMC. على وجه التحديد، بالنظر إلى دالة كثافة الاحتمال ${\displaystyle p(x)}$، نستخدم تدرجها اللوغاريتمي${\displaystyle \nabla _{x}\log p(x)}$كدالة تسجيل النقاط والبدء من توزيع مسبق${\displaystyle x_{0}\sim p_{0}}$ثم يتم بناء سلسلة بواسطة

${\displaystyle x_{i+1}=x_{i}+\epsilon \nabla _{x}\log p(x)+{\sqrt {2\epsilon }}z_{i},z_{i}\sim {\mathcal {N}}(0,I)}$

ل${\displaystyle i=0,\dots ,K}$. متى${\displaystyle \epsilon \rightarrow 0}$و${\displaystyle K\rightarrow \infty }$،${\displaystyle x_{K}}$يتقارب إلى عينة من التوزيع المستهدف${\displaystyle p(x)}$.

بالنسبة لبعض التوزيعات المعقدة، إذا كنا نعرف دالة كثافة الاحتمال الخاصة بها ولكننا نجد صعوبة في أخذ عينات مباشرة منها، فيمكننا تطبيق ديناميكيات لانجفين كبديل. ومع ذلك، في معظم الحالات، وخاصة في النمذجة التوليدية، لا نعرف عادةً دالة كثافة الاحتمال الدقيقة للتوزيع المستهدف الذي نرغب في أخذ عينات منه، ولا دالة النتيجة.${\displaystyle \nabla _{x}\log p(x)}$في هذه الحالة، توفر طرق مطابقة الدرجات ^{[ 35 ] [ 36 ] [ 37 ]} حلولاً ممكنة، مما يقلل من مقياس معلومات فيشر بين نموذج قائم على الدرجات ومعلمات.${\displaystyle s_{\theta }(x)}$ويمكن تقدير دالة التقييم دون معرفة قيمة التقييم الحقيقية للبيانات. ويمكن تقدير دالة التقييم على مجموعة بيانات التدريب باستخدام خوارزمية التدرج العشوائي .

في الواقع العملي، لا تغطي بيانات التدريب سوى جزء صغير من التوزيع المستهدف، وتكون دوال التقييم المُقدَّرة غير دقيقة في المناطق الأخرى ذات الكثافة المنخفضة والتي تحتوي على عدد أقل من أمثلة البيانات المتاحة. وللتغلب على هذا التحدي، تعمل طرق مطابقة التقييم مع إزالة التشويش ^{[ 34 ] [ 36 ] [ 38 ]} على تشويش أمثلة البيانات المتاحة بضوضاء ذات مقاييس مختلفة، مما يُحسِّن تغطية المناطق ذات الكثافة المنخفضة، ثم تُستخدم هذه البيانات كمجموعة بيانات تدريب للنموذج القائم على التقييم. تجدر الإشارة إلى أن اختيار مقاييس الضوضاء أمرٌ دقيق، فالضوضاء الكبيرة جدًا تُشوِّه البيانات الأصلية، بينما الضوضاء الصغيرة جدًا لا تُغطي تلك المناطق ذات الكثافة المنخفضة. لذا، تُطبَّق جداول ضوضاء مُصمَّمة بعناية ^{[ 34 ] [ 37 ] [ 38 ] للحصول على بيانات ذات جودة أعلى.}

بصورة رسمية، دع${\displaystyle \pi }$يشير إلى التوزيع الثابت و${\displaystyle P^{t}(x,\cdot )}$توزيع سلسلة ماركوف بعد${\displaystyle t}$خطوات تبدأ من الولاية${\displaystyle x}$نظرياً، يمكن تحديد التقارب كمياً عن طريق قياس مسافة التباين الكلية :

${\displaystyle d_{\text{TV}}(P^{t}(x,\cdot ),\pi )=\sup _{A}|P^{t}(x,A)-\pi (A)|}$

يقال إن السلسلة تختلط بسرعة إذا${\displaystyle d_{\text{TV}}(P^{t}(x,\cdot ),\pi )\leq \epsilon }$للجميع${\displaystyle x\in {\mathcal {X}}}$في غضون عدد قليل من الخطوات${\displaystyle t}$ضمن هامش خطأ محدد مسبقًا${\displaystyle \epsilon >0}$بمعنى آخر، يتم الوصول إلى التوزيع الثابت بسرعة بدءًا من أي موضع، والحد الأدنى لهذا التوزيع هو قيمة معينة.${\displaystyle t}$يُعرف باسم زمن الخلط . ومع ذلك، من الناحية العملية، فإن حساب مسافة التباين الكلية أمر يصعب حسابه بشكل عام، خاصة في المشكلات ذات الأبعاد العالية أو عندما يكون التوزيع الثابت معروفًا فقط حتى ثابت التطبيع (كما هو الحال في معظم التطبيقات البايزية).

إحصائية جيلمان-روبين ، المعروفة أيضًا باسم عامل تقليل المقياس المحتمل (PSRF) ، تقيّم تقارب سلسلة ماركوف مونت كارلو (MCMC) عن طريق أخذ عينات من سلاسل ماركوف مستقلة متعددة ومقارنة التباينات داخل السلسلة وبين السلاسل. ^{[ 41 ]} إذا تقاربت جميع السلاسل إلى نفس التوزيع الثابت، فيجب أن تكون التباينات بين السلاسل وداخلها متشابهة، وبالتالي يجب أن يقترب PSRF من 1. عمليًا، قيمة .${\displaystyle <1.1}$غالباً ما يُعتبر ذلك دليلاً على التقارب. تشير القيم الأعلى إلى أن السلاسل لا تزال تستكشف أجزاءً مختلفة من التوزيع المستهدف.

يفحص تشخيص جيوك ما إذا كان توزيع العينات في الجزء المبكر من سلسلة ماركوف لا يمكن تمييزه إحصائيًا عن التوزيع في جزء لاحق. ^{[ 42 ]} بالنظر إلى سلسلة من عينات MCMC المترابطة${\displaystyle \{X_{1},X_{2},\dots ,X_{n}\}}$، يقسم التشخيص السلسلة إلى جزء مبكر يتكون من الأول${\displaystyle n_{A}}$العينات، التي يتم اختيارها عادة كـ${\displaystyle n_{A}=0.1n}$(أي أول 10% من السلسلة)، وجزء متأخر يتكون من الجزء الأخير${\displaystyle n_{B}}$العينات، التي يتم اختيارها عادة كـ${\displaystyle n_{B}=0.5n}$(أي، آخر 50% من السلسلة)

لنرمز إلى متوسطات العينة لهذه القطاعات على النحو التالي:

${\displaystyle {\bar {X}}_{A}={\dfrac {1}{n_{A}}}\sum _{i=1}^{n_{A}}X_{i},\;\;\;{\bar {X}}_{B}={\dfrac {1}{n_{B}}}\sum _{i=n-n_{B}+1}^{n}X_{i}}$

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

${\displaystyle Z={\dfrac {{\bar {X}}_{A}-{\bar {X}}_{B}}{\sqrt {{\hat {S}}(0)/n_{A}+{\hat {S}}(0)/n_{B}}}}}$

أين${\displaystyle {\hat {S}}(0)}$هو تقدير للتباين طويل المدى (أي الكثافة الطيفية عند التردد صفر)، ويُقدَّر عادةً باستخدام مُقدِّرات نيوي-ويست أو متوسطات الدُفعات. في ظل فرضية العدم للتقارب، فإن الإحصائية${\displaystyle Z}$يتبع التوزيع الطبيعي القياسي تقريبًا${\displaystyle Z\sim {\mathcal {N}}(0,1)}$.

لو${\displaystyle |Z|>1.96}$، يتم رفض الفرضية الصفرية عند مستوى دلالة 5٪، مما يشير إلى أن السلسلة لم تصل بعد إلى حالة الاستقرار.

يستند تشخيص هايدلبرغر-ويلش إلى التحليل الطيفي ونظرية الحركة البراونية ، وهو مفيد بشكل خاص في المراحل المبكرة من المحاكاة لتحديد وقت التثبيت ووقت التوقف المناسبين. ^{[ 43 ] [ 44 ]} يتكون التشخيص من عنصرين: اختبار الاستقرار الذي يقيم ما إذا كانت سلسلة ماركوف قد وصلت إلى حالة مستقرة، واختبار نصف العرض الذي يحدد ما إذا كان التوقع المقدر ضمن دقة يحددها المستخدم.

صُممت طريقة رافتري-لويس التشخيصية خصيصًا لتقييم عدد التكرارات اللازمة لتقدير الكميات أو احتمالات الذيل للتوزيع المستهدف بدقة وثقة مطلوبتين. ^{[ 45 ]} على عكس طريقتي جيلمان-روبين وجيوك التشخيصيتين، اللتين تعتمدان على تقييم التقارب مع التوزيع بأكمله، فإن طريقة رافتري-لويس التشخيصية موجهة نحو الهدف، إذ توفر تقديرات لعدد العينات المطلوبة لتقدير كمية محددة ذات أهمية ضمن هامش خطأ مطلوب.

يترك${\displaystyle q}$يرمز إلى الكمية المطلوبة (على سبيل المثال، 0.025) لدالة حقيقية القيمة${\displaystyle g(X)}$بمعنى آخر، الهدف هو إيجاد${\displaystyle u}$بحيث${\displaystyle P(g(X)\leq u)=q}$لنفترض أننا نرغب في تقدير هذه الكمية بحيث يقع التقدير ضمن الهامش${\displaystyle \varepsilon }$القيمة الحقيقية باحتمالية${\displaystyle 1-\alpha }$أي أننا نريد

${\displaystyle P(|{\hat {q}}-q|<\varepsilon )\geq 1-\alpha }$

تتم عملية التشخيص عن طريق تحويل مخرجات سلسلة MCMC إلى تسلسل ثنائي:

${\displaystyle W_{n}=\mathbb {I} (g(X_{n})\leq u),\;\;\;n=1,2,\dots }$

أين${\displaystyle I(\cdot )}$هي دالة المؤشر. التسلسل${\displaystyle \{W_{n}\}}$يُعامل هذا كتحقق من سلسلة ماركوف ثنائية الحالة. ورغم أن هذا قد لا يكون صحيحًا تمامًا، إلا أنه غالبًا ما يكون تقريبًا جيدًا في الممارسة العملية.

انطلاقاً من التحولات التجريبية في التسلسل الثنائي، تُقدّر طريقة رافتري-لويس ما يلي:

• الحد الأدنى لعدد التكرارات${\displaystyle n_{\text{min}}}$يتم الحصول على الدقة والثقة المطلوبتين لتقدير الكمية بناءً على النظرية التقاربية لعمليات برنولي:

${\displaystyle n_{\text{min}}={\bigg \{}\Phi ^{-1}{\bigg (}1-{\dfrac {\alpha }{2}}{\bigg )}{\bigg \}}^{2}{\dfrac {q(1-q)}{\varepsilon ^{2}}}}$

أين${\displaystyle \Phi ^{-1}(\cdot )}$هي دالة الكمية الطبيعية القياسية.

• فترة التشغيل الأولي${\displaystyle n_{\text{burn}}}$يتم حسابها باستخدام تحليل القيم الذاتية لمصفوفة الانتقال لتقدير عدد التكرارات الأولية اللازمة لسلسلة ماركوف لتنسى حالتها الأولية.