अतीत से युग्मन

[[मार्कोव श्रृंखला मोंटे कार्लो]] (एमसीएमसी) एल्गोरिदम के बीच, अतीत से युग्मन मार्कोव श्रृंखला के स्थिर वितरण से नमूनाकरण (सांख्यिकी) के लिए एक विधि है। कई एमसीएमसी एल्गोरिदम के विपरीत, अतीत से युग्मन सिद्धांत रूप में स्थिर वितरण से एक आदर्श नमूना देता है। इसका आविष्कार 1996 में जेम्स प्रॉप और डेविड ब्रूस विल्सन ने किया था।

मूल विचार

एक परिमित अवस्था मार्कोव श्रृंखला मार्कोव श्रृंखला पर विचार करें $M$ राज्य स्थान के साथ $S$ और (अद्वितीय) स्थिर वितरण $\pi$ ($\pi$ एक संभाव्यता वेक्टर है)। मान लीजिए कि हम एक संभाव्यता वितरण लेकर आते हैं $\mu$ मानचित्रों के सेट पर $f:S\to S$ उस संपत्ति के साथ जो प्रत्येक के लिए निश्चित है $s\in S$, इसकी छवि $f(s)$ की संक्रमण संभावना के अनुसार वितरित किया जाता है $M$ राज्य से $s$. ऐसे संभाव्यता वितरण का एक उदाहरण वह है जहाँ $f(s)$ (संभावना) से स्वतंत्र है $f(s')$ जब कभी भी $s\neq s'$, लेकिन अक्सर अन्य वितरणों पर विचार करना सार्थक होता है। अब चलो $f_{j}$ के लिए $j\in \mathbb {Z}$ से स्वतंत्र नमूने बनें $\mu$.

लगता है कि $x$ के अनुसार यादृच्छिक रूप से चुना जाता है $\pi$ और अनुक्रम से स्वतंत्र है $f_{j}$. (अभी हमें इसकी चिंता नहीं है कि यह कहां है $x$ से आ रहा है.) फिर $f_{-1}(x)$ के अनुसार भी वितरित किया जाता है $\pi$, क्योंकि $\pi$ है $M$-स्थायी और के कानून पर हमारी धारणा $f$. परिभाषित करना

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

फिर यह प्रेरण द्वारा अनुसरण करता है $F_{j}(x)$ के अनुसार भी वितरित किया जाता है $\pi$ हरएक के लिए $j\in \mathbb {N}$. हालाँकि, कुछ लोगों के लिए ऐसा हो सकता है $n\in \mathbb {N}$ मानचित्र की छवि $F_{n}$ का एक तत्व है $S$. दूसरे शब्दों में, $F_{n}(x)=F_{n}(y)$ प्रत्येक के लिए $y\in S$. इसलिए, हमें पहुंच की आवश्यकता नहीं है $x$ गणना करने के लिए $F_{n}(x)$. फिर एल्गोरिदम में कुछ खोजना शामिल है $n\in \mathbb {N}$ ऐसा है कि $F_{n}(S)$ एक सिंगलटन (गणित) है, और उस सिंगलटन के तत्व को आउटपुट कर रहा है। एक अच्छे वितरण का डिज़ाइन $\mu$ जिसके लिए ऐसा खोजने का कार्य किया गया $n$ और कंप्यूटिंग $F_{n}$ यह बहुत महंगा नहीं है, यह हमेशा स्पष्ट नहीं होता है, लेकिन कई महत्वपूर्ण मामलों में इसे सफलतापूर्वक पूरा किया गया है।

मोनोटोन केस

मार्कोव श्रृंखलाओं का एक विशेष वर्ग है जिसमें विशेष रूप से अच्छे विकल्प हैं के लिए $\mu$ और यह निर्धारित करने के लिए एक उपकरण $|F_{n}(S)|=1$. (यहाँ $|\cdot |$ कार्डिनल संख्या को दर्शाता है.) मान लीजिए $S$ ऑर्डर के साथ आंशिक रूप से ऑर्डर किया गया सेट है $\leq$, जिसमें एक अद्वितीय न्यूनतम तत्व है $s_{0}$ और एक अद्वितीय अधिकतम तत्व $s_{1}$; यानी हर $s\in S$ संतुष्ट $s_{0}\leq s\leq s_{1}$. यह भी मान लीजिए $\mu$ मोनोटोन फ़ंक्शन मानचित्रों के सेट पर समर्थित होने के लिए चुना जा सकता है $f:S\to S$. फिर उसे देखना आसान है $|F_{n}(S)|=1$ अगर और केवल अगर $F_{n}(s_{0})=F_{n}(s_{1})$, तब से $F_{n}$ एकस्वर है. इस प्रकार, इसकी जाँच करना काफी आसान हो जाता है। एल्गोरिथम चुनकर आगे बढ़ सकता है $n:=n_{0}$ कुछ स्थिरांक के लिए $n_{0}$, नक्शों का नमूना लेना $f_{-1},\dots ,f_{-n}$, और आउटपुट $F_{n}(s_{0})$ अगर $F_{n}(s_{0})=F_{n}(s_{1})$. अगर $F_{n}(s_{0})\neq F_{n}(s_{1})$ एल्गोरिथ्म दोगुना होकर आगे बढ़ता है $n$ और आउटपुट प्राप्त होने तक आवश्यकतानुसार दोहराते रहें। (लेकिन एल्गोरिदम मानचित्रों का दोबारा नमूना नहीं बनाता है $f_{-j}$ जिनका नमूना पहले ही लिया जा चुका था; जरूरत पड़ने पर यह पहले से सैंपल किए गए मानचित्रों का उपयोग करता है।)

संदर्भ

• Propp, James Gary; Wilson, David Bruce (1996), Proceedings of the Seventh International Conference on Random Structures and Algorithms (Atlanta, GA, 1995), pp. 223–252, MR 1611693
• Propp, James; Wilson, David (1998), "Coupling from the past: a user's guide", Microsurveys in discrete probability (Princeton, NJ, 1997), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 41, Providence, R.I.: American Mathematical Society, pp. 181–192, doi:10.1090/dimacs/041/09, ISBN 9780821808276, MR 1630414, S2CID 2781385