اقترانات من الماضي

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

لنفترض سلسلة ماركوف غير دورية غير قابلة للاختزال ذات حالات محدودة${\displaystyle M}$مع فضاء الحالة${\displaystyle S}$والتوزيع الثابت (الفريد)${\displaystyle \pi }$(${\displaystyle \pi }$(هو متجه احتمالي ). لنفترض أننا توصلنا إلى توزيع احتمالي${\displaystyle \mu }$على مجموعة الخرائط${\displaystyle f:S\to S}$مع الخاصية التي لكل ثابت${\displaystyle s\in S}$صورتها${\displaystyle f(s)}$يتم توزيعها وفقًا لاحتمالية الانتقال لـ${\displaystyle M}$من الولاية${\displaystyle s}$ومن أمثلة هذا التوزيع الاحتمالي التوزيع الذي${\displaystyle f(s)}$مستقل عن​${\displaystyle f(s')}$حينما${\displaystyle s\neq s'}$لكن من المفيد غالبًا النظر في توزيعات أخرى. لنفترض الآن${\displaystyle f_{j}}$ل${\displaystyle j\in \mathbb {Z} }$كن عينات مستقلة من${\displaystyle \mu }$.

لنفترض أن${\displaystyle x}$يتم اختيارها عشوائياً وفقاً لـ${\displaystyle \pi }$وهو مستقل عن التسلسل${\displaystyle f_{j}}$(لا داعي للقلق في الوقت الحالي بشأن مكان هذا${\displaystyle x}$(يأتي من.) ثم${\displaystyle f_{-1}(x)}$يتم توزيعها أيضًا وفقًا لـ${\displaystyle \pi }$، لأن${\displaystyle \pi }$يكون${\displaystyle M}$-ثابتة وافتراضنا بشأن قانون${\displaystyle f}$. يُعرِّف

${\displaystyle F_{j}:=f_{-1}\circ f_{-2}\circ \cdots \circ f_{-j}.}$

ثم يترتب على ذلك بالاستقراء أن${\displaystyle F_{j}(x)}$يتم توزيعها أيضًا وفقًا لـ${\displaystyle \pi }$لكل${\displaystyle j\in \mathbb {N} }$ومع ذلك، قد يحدث ذلك بالنسبة للبعض${\displaystyle n\in \mathbb {N} }$صورة الخريطة${\displaystyle F_{n}}$هو عنصر واحد من${\displaystyle S}$. بعبارة أخرى،${\displaystyle F_{n}(x)=F_{n}(y)}$لكل${\displaystyle y\in S}$لذلك، لسنا بحاجة إلى الوصول إلى${\displaystyle x}$من أجل الحساب${\displaystyle F_{n}(x)}$ثم تتضمن الخوارزمية إيجاد بعض${\displaystyle n\in \mathbb {N} }$بحيث${\displaystyle F_{n}(S)}$هو عنصر منفرد ، وإخراج عنصر هذا العنصر المنفرد. تصميم توزيع جيد${\displaystyle \mu }$والتي تتمثل مهمة إيجاد مثل هذا${\displaystyle n}$والحوسبة${\displaystyle F_{n}}$ليس من الواضح دائمًا أن التكلفة ليست باهظة، ولكن تم تحقيق ذلك بنجاح في العديد من الحالات المهمة. ^{[ 1 ]}

توجد فئة خاصة من سلاسل ماركوف تتميز بخيارات جيدة بشكل خاص لـ${\displaystyle \mu }$وأداة لتحديد ما إذا${\displaystyle |F_{n}(S)|=1}$. (هنا${\displaystyle |\cdot |}$(يشير إلى العدد الأصلي .) لنفترض أن${\displaystyle S}$هي مجموعة مرتبة جزئياً بترتيب${\displaystyle \leq }$، والذي يحتوي على عنصر بسيط فريد${\displaystyle s_{0}}$وعنصر أقصى فريد${\displaystyle s_{1}}$أي كل${\displaystyle s\in S}$يرضي${\displaystyle s_{0}\leq s\leq s_{1}}$. افترض أيضاً أن${\displaystyle \mu }$يمكن اختيارها لتكون مدعومة على مجموعة الخرائط الرتيبة${\displaystyle f:S\to S}$ومن ثم يسهل أن نرى ذلك${\displaystyle |F_{n}(S)|=1}$إذا وفقط إذا${\displaystyle F_{n}(s_{0})=F_{n}(s_{1})}$، منذ${\displaystyle F_{n}}$دالة رتيبة. لذا، يصبح التحقق من ذلك سهلاً للغاية. يمكن للخوارزمية أن تتابع باختيار${\displaystyle n:=n_{0}}$لبعض الثوابت${\displaystyle n_{0}}$أخذ عينات من الخرائط${\displaystyle f_{-1},\dots ,f_{-n}}$، وإخراج${\displaystyle F_{n}(s_{0})}$لو${\displaystyle F_{n}(s_{0})=F_{n}(s_{1})}$. لو${\displaystyle F_{n}(s_{0})\neq F_{n}(s_{1})}$تتم الخوارزمية عن طريق المضاعفة${\displaystyle n}$وتكرار ذلك حسب الحاجة حتى يتم الحصول على مخرجات. (لكن الخوارزمية لا تعيد أخذ عينات من الخرائط).${\displaystyle f_{-j}}$والتي تم أخذ عينات منها بالفعل؛ ويستخدم الخرائط التي تم أخذ عينات منها مسبقًا عند الحاجة.)

• بروب، جيمس غاري؛ ويلسون، ديفيد بروس (1996)، وقائع المؤتمر الدولي السابع حول الهياكل والخوارزميات العشوائية (أتلانتا، جورجيا، 1995) ، الصفحات 223-252 ، MR 1611693  
• بروب، جيمس؛ ويلسون، ديفيد (1998)، "الاقتران من الماضي: دليل المستخدم"، دراسات استقصائية مصغرة في الاحتمالات المنفصلة (برينستون، نيوجيرسي، 1997) ، سلسلة DIMACS في الرياضيات المنفصلة، ​​النظرية، وعلوم الحاسوب، المجلد  41، بروفيدنس، رود آيلاند: الجمعية الرياضية الأمريكية ، الصفحات 181-192 ، doi : 10.1090/dimacs/041/09 ، ISBN  9780821808276، MR 1630414 ، S2CID 2781385