अस्वीकृति नमूनाकरण

संख्यात्मक विश्लेषण और कम्प्यूटेशनल आंकड़ों में, अस्वीकृति नमूनाकरण मूल तकनीक है जिसका उपयोग संभाव्यता वितरण से अवलोकन उत्पन्न करने के लिए किया जाता है। इसे सामान्यतः स्वीकृति-अस्वीकृति विधि या स्वीकार-अस्वीकार एल्गोरिथम भी कहा जाता है और यह एक प्रकार की स्पष्ट सिमुलेशन विधि है। यह विधि किसी भी वितरण $\mathbb {R} ^{m}$ संभाव्यता घनत्व फलन के साथ के लिए काम करती है।

अस्वीकृति नमूनाकरण अवलोकन पर आधारित है कि आयाम में यादृच्छिक चर का नमूना लेने के लिए, द्वि-आयामी कार्टेशियन ग्राफ का समान रूप से यादृच्छिक नमूनाकरण कर सकता है, और इसके घनत्व फलन के ग्राफ के अंतर्गत क्षेत्र में नमूने रख सकता है। ध्यान दें कि इस संपत्ति को n-आयाम कार्यों तक बढ़ाया जा सकता है।

विवरण

रिजेक्शन सैंपलिंग के पीछे की प्रेरणा की कल्पना करने के लिए, बड़े आयताकार बोर्ड पर यादृच्छिक चर के घनत्व फलन को ग्राफ़ करने और उस पर डार्ट्स फेंकने की कल्पना करें। मान लें कि डार्ट्स समान रूप से बोर्ड के चारों ओर वितरित किए जाते हैं। अब उन सभी डार्ट्स को हटा दें जो वक्र के नीचे के क्षेत्र से बाहर हैं। शेष डार्ट्स वक्र के अंतर्गत क्षेत्र के अन्दर समान रूप से वितरित किए जाएंगे, और इन डार्ट्स के x-पोजिशन को यादृच्छिक चर के घनत्व के अनुसार वितरित किया जाएगा। ऐसा इसलिए है क्योंकि डार्ट्स के लिए सबसे अधिक जगह है जहां वक्र उच्चतम है और इस प्रकार संभाव्यता घनत्व सबसे बड़ा है।

दृश्य जैसा कि अभी वर्णित किया गया है, अस्वीकृति नमूनाकरण के विशेष रूप के बराबर है जहाँ प्रस्ताव वितरण समान है (इसलिए इसका ग्राफ़ आयत है)। अस्वीकृति नमूनाकरण का सामान्य रूप मानता है कि बोर्ड आवश्यक रूप से आयताकार नहीं है, लेकिन कुछ प्रस्ताव वितरण के घनत्व के अनुसार आकार दिया गया है, जिसे हम जानते हैं कि कैसे नमूना लेना है (उदाहरण के लिए, उल्टा नमूनाकरण का उपयोग करके), और जो कम से कम हर बार उच्च है उस वितरण के रूप में इंगित करें जिससे हम नमूना लेना चाहते हैं, ताकि पूर्व पूरी तरह से उत्तरार्द्ध को घेर ले। (अन्यथा, घुमावदार क्षेत्र के कुछ भाग होंगे जिनसे हम नमूना लेना चाहते हैं, कभी नहीं पहुंचा जा सकता।)

अस्वीकृति नमूना निम्नानुसार काम करता है:

1. प्रस्ताव वितरण से x-अक्ष पर बिंदु का नमूना लें।
2. प्रस्ताव वितरण के प्रायिकता घनत्व फलन के अधिकतम y- मान तक, इस x- स्थिति पर लंबवत रेखा बनाएं।
3. इस रेखा के साथ समान रूप से 0 से अधिकतम संभाव्यता घनत्व फलन का नमूना लें। यदि नमूनाकृत मान इस लंबवत रेखा पर वांछित वितरण के मान से अधिक है, तो x-मान को अस्वीकार करें और चरण 1 पर वापस लौटें; अन्यथा x-मान वांछित वितरण से नमूना है।

इस एल्गोरिथ्म का उपयोग किसी भी वक्र के अंतर्गत क्षेत्र से नमूना लेने के लिए किया जा सकता है, भले ही फलन 1 को एकीकृत करता हो या नहीं। वास्तव में, किसी फलन को स्थिरांक द्वारा स्केल करने से नमूना x-स्थितियों पर कोई प्रभाव नहीं पड़ता है। इस प्रकार, एल्गोरिथ्म का उपयोग ऐसे वितरण से नमूना लेने के लिए किया जा सकता है जिसका सामान्यीकरण स्थिरांक अज्ञात है, जो कम्प्यूटेशनल आंकड़ों में सामान्य है।

सिद्धांत

रिजेक्शन सैंपलिंग पद्धति लक्ष्य वितरण से सैंपलिंग मान उत्पन्न करती है $X$ मनमाने ढंग से संभाव्यता घनत्व फलन के साथ $f(x)$ प्रस्ताव वितरण का उपयोग करके $Y$ संभाव्यता घनत्व के साथ $g(x)$. विचार यह है कि कोई नमूना मूल्य उत्पन्न कर सकता है $X$ इसके अतिरिक्त से नमूना लेना $Y$ और से नमूना स्वीकार करना $Y$ संभावना के साथ $f(x)/(Mg(x))$, ड्रॉ को दोहराते हुए $Y$ जब तक कोई मान स्वीकार नहीं किया जाता। $M$ यहाँ संभावना अनुपात पर स्थिर, परिमित सीमा है $f(x)/g(x)$, संतुष्टि देने वाला $1<M<\infty$ के समर्थन (गणित) पर $X$; दूसरे शब्दों में, एम को संतुष्ट करना चाहिए $f(x)\leq Mg(x)$ के सभी मूल्यों के लिए $x$. ध्यान दें कि इसके लिए समर्थन की आवश्यकता है $Y$ का समर्थन सम्मिलित करना चाहिए $X$-दूसरे शब्दों में, $g(x)>0$ जब कभी भी $f(x)>0$.है।

इस पद्धति का सत्यापन आवरण सिद्धांत है: जोड़ी का अनुकरण करते समय ${\textstyle (x,v=u\cdot Mg(x))}$, एक के सबग्राफ पर समान सिमुलेशन का उत्पादन करता है ${\textstyle Mg(x)}$. केवल ऐसी जोड़ियों को स्वीकार करना ${\textstyle u<f(x)/(Mg(x))}$ फिर जोड़े उत्पन करता है $(x,v)$ के सबग्राफ पर समान रूप से वितरित $f(x)$ और इस प्रकार, आंशिक रूप से, अनुकरण $f(x).$ इसका मतलब यह है कि, पर्याप्त प्रतिकृति के साथ, एल्गोरिथम वांछित वितरण से नमूना उत्पन्न करता है $f(x)$. इस एल्गोरिथम के लिए कई एक्सटेंशन हैं, जैसे मेट्रोपोलिटन एल्गोरिथम कहते है।

यह विधि मोंटे कार्लो पद्धति तकनीकों के सामान्य क्षेत्र से संबंधित है, जिसमें मार्कोव चेन मोंटे कार्लो एल्गोरिदम सम्मिलित हैं जो लक्ष्य वितरण से अनुकरण प्राप्त करने के लिए प्रॉक्सी वितरण का भी उपयोग करते हैं। $f(x)$. यह मेट्रोपोलिस एल्गोरिथम जैसे एल्गोरिदम के लिए आधार बनाता है।

बिना शर्त स्वीकृति संभावना प्रस्तावित नमूनों का अनुपात है जो स्वीकार किए जाते हैं, जो है।

$${\begin{aligned}\mathbb {P} \left(U\leq {\frac {f(Y)}{Mg(Y)}}\right)&=\operatorname {E} \mathbf {1} _{\left[U\leq {\frac {f(Y)}{Mg(Y)}}\right]}\\[6pt]&=E\left[\operatorname {E} [\mathbf {1} _{\left[U\leq {\frac {f(Y)}{Mg(Y)}}\right]}|Y]\right]&({\text{by tower property }})\\[6pt]&=\operatorname {E} \left[\mathbb {P} \left(U\leq {\frac {f(Y)}{Mg(Y)}}{\biggr |}Y\right)\right]\\[6pt]&=E\left[{\frac {f(Y)}{Mg(Y)}}\right]&({\text{because }}\Pr(U\leq u)=u,{\text{when }}U{\text{ is uniform on }}(0,1))\\[6pt]&=\int \limits _{y:g(y)>0}{\frac {f(y)}{Mg(y)}}g(y)\,dy\\[6pt]&={\frac {1}{M}}\int \limits _{y:g(y)>0}f(y)\,dy\\[6pt]&={\frac {1}{M}}&({\text{since support of }}Y{\text{ includes support of }}X)\end{aligned}}$$

कहाँ $U\sim \mathrm {Unif} (0,1)$, और का मूल्य $y$ हर बार घनत्व फलन के अंतर्गत उत्पन्न होता है $g(\cdot )$ प्रस्ताव वितरण के संबंध में $Y$है.

से आवश्यक नमूनों की संख्या $Y$ स्वीकृत मूल्य प्राप्त करने के लिए इस प्रकार संभाव्यता के साथ ज्यामितीय वितरण होता है $1/M$, जिसका मतलब है $M$. सहज रूप से, $M$ एल्गोरिथम की कम्प्यूटेशनल जटिलता के माप के रूप में आवश्यक पुनरावृत्तियों की अपेक्षित संख्या है।

उपरोक्त समीकरण को फिर से लिखें,

$$M={\frac {1}{\mathbb {P} \left(U\leq {\frac {f(Y)}{Mg(Y)}}\right)}}$$

ध्यान दें कि ${\textstyle 1\leq M<\infty }$, उपरोक्त सूत्र के कारण, जहाँ ${\textstyle \mathbb {P} \left(U\leq {\frac {f(Y)}{Mg(Y)}}\right)}$ प्रायिकता है जो अंतराल में केवल मान ले सकती है $[0,1]$. कब $M$ के समीप चुना जाता है, बिना शर्त स्वीकृति की संभावना उतनी ही अधिक होती है, जितना कम अनुपात भिन्न होता है, क्योंकि $M$ संभावना अनुपात के लिए ऊपरी सीमा है ${\textstyle f(x)/g(x)}$. व्यवहार में, का मूल्य के करीब को प्राथमिकता दी जाती है क्योंकि इसका तात्पर्य कम अस्वीकृत नमूनों से है, औसतन, और इस प्रकार एल्गोरिथम के कम पुनरावृत्तियों। इस अर्थ में, कोई लेना पसंद करता है $M$ जितना संभव हो उतना छोटा (अभी भी संतुष्ट करते हुए $f(x)\leq Mg(x)$, जिससे पता चलता है $g(x)$ सम्मिलित समान होना चाहिए $f(x)$ किसी तरह। चूंकि, ध्यान दें $M$ 1 के बराबर नहीं हो सकता: ऐसा इसका अर्थ होगा $f(x)=g(x)$, यानी कि लक्ष्य और प्रस्ताव वितरण वास्तव में समान वितरण हैं।

अस्वीकृति नमूनाकरण का उपयोग अधिकांशतः उन स्थितियों में किया जाता है जहां प्रपत्र $f(x)$ नमूनाकरण को कठिन बनाता है। अस्वीकृति एल्गोरिथम के एकल पुनरावृत्ति के लिए प्रस्ताव वितरण से नमूने लेने, समान वितरण से आरेखण करने और प्रस्ताव का मूल्यांकन करने की आवश्यकता होती है $f(x)/(Mg(x))$ अभिव्यक्ति। इस प्रकार अस्वीकृति नमूनाकरण किसी अन्य विधि की तुलना में अधिक कुशल होता है जब भी इन कार्यों की m गुना लागत - जो अस्वीकृति नमूनाकरण के साथ नमूना प्राप्त करने की अपेक्षित लागत होती है - अन्य विधि का उपयोग करके नमूना प्राप्त करने की लागत से कम होती है।

एल्गोरिथम

एल्गोरिथम, जिसका उपयोग जॉन वॉन न्यूमैन द्वारा किया गया था और जॉर्जेस-लुई लेक्लेर, कॉम्टे डे बफन और बफन की सुई के समय से है, वितरण से नमूना प्राप्त करता है $X$ घनत्व के साथ $f$ वितरण से नमूने का उपयोग करना $Y$ घनत्व के साथ $g$ निम्नलिखित :

• नमूना प्राप्त करें $y$ वितरण से $Y$ और नमूना $u$ से $\mathrm {Unif} (0,1)$ (इकाई अंतराल पर समान वितरण)।
• चेक करें या नहीं ${\textstyle u<f(y)/Mg(y)}$.
  • यदि यह मान्य है, तो स्वीकार करें $y$ से लिए गए नमूने के रूप में $f$;है।
  • यदि नहीं, के मूल्य को अस्वीकार करें $y$ और नमूनाकरण चरण पर लौटें।

एल्गोरिदम औसत लेगा $M$ पुनरावृत्तियाँ नमूना प्राप्त करने के लिए ।

सहज विधियों का उपयोग करके नमूनाकरण पर लाभ

कुछ स्थितियों में सरल तरीकों की तुलना में अस्वीकृति नमूनाकरण कहीं अधिक कुशल हो सकता है। उदाहरण के लिए, नमूनाकरण के रूप में समस्या दी गई है ${\textstyle X\sim F(\cdot )}$ सशर्त रूप से $X$ सेट दिया $A$, अर्थात।, ${\textstyle X|X\in A}$, कभी-कभी ${\textstyle X}$ भोली विधियों का उपयोग करके आसानी से अनुकरण किया जा सकता है (उदाहरण के लिए प्रतिलोम रूपांतरण नमूनाकरण द्वारा):

• नमूना ${\textstyle X\sim F(\cdot )}$ स्वतंत्र रूप से, और उन्हें संतुष्ट करने वालों को छोड़ दें $\{n\geq 1:X_{n}\in A\}$ * आउटपुट: $\{X_{1},X_{2},...,X_{N}:X_{i}\in A,i=1,...,N\}$

समस्या यह है कि यह नमूनाकरण कठिन और अक्षम हो सकता है, यदि ${\textstyle \mathbb {P} (X\in A)\approx 0}$. पुनरावृत्तियों की अपेक्षित संख्या होगी ${\frac {1}{\mathbb {P} (X\in A)}}$, जो अनंत के करीब हो सकता है। इसके अतिरिक्त, जब आप अस्वीकृति नमूनाकरण विधि प्रयुक्त करते हैं, तब भी बाउंड को अनुकूलित करना हमेशा कठिन होता है $M$ संभावना अनुपात के लिए अधिक से अधिक, $M$ बड़ा है और अस्वीकृति दर अधिक है, एल्गोरिथ्म बहुत अक्षम हो सकता है। प्राकृतिक घातीय परिवार (यदि यह उपस्थित है), जिसे घातीय झुकाव के रूप में भी जाना जाता है, प्रस्ताव वितरण का वर्ग प्रदान करता है जो गणना जटिलता को कम कर सकता है, का मान $M$ और संगणनाओं को गति दें (उदाहरण देखें: प्राकृतिक घातीय परिवारों के साथ काम करना)।

उदाहरण: प्राकृतिक घातीय परिवारों के साथ काम करना

यादृच्छिक चर दिया $X\sim F(\cdot )$, $F(x)=\mathbb {P} (X\leq x)$ लक्ष्य वितरण है। सादगी के लिए मान लें, घनत्व फलन स्पष्ट रूप से लिखा जा सकता है $f(x)$. प्रस्ताव को इस रूप में चुनें

$${\begin{aligned}F_{\theta }(x)&=\mathbb {E} \left[\exp(\theta X-\psi (\theta ))\mathbb {I} (X\leq x)\right]\\&=\int _{-\infty }^{x}e^{\theta y-\psi (\theta )}f(y)dy\\g_{\theta }(x)&=F'_{\theta }(x)=e^{\theta x-\psi (\theta )}f(x)\end{aligned}}$$

जहाँ $\psi (\theta )=\log \left(\mathbb {E} \exp(\theta X)\right)$ और $\Theta =\{\theta :\psi (\theta )<\infty \}$. स्पष्ट रूप से, $\{F_{\theta }(\cdot )\}_{\theta \in \Theta }$, प्राकृतिक घातीय परिवार से है। इसके अतिरिक्त, संभावना अनुपात है।

$$Z(x)={\frac {f(x)}{g_{\theta }(x)}}={\frac {f(x)}{e^{\theta x-\psi (\theta )}f(x)}}=e^{-\theta x+\psi (\theta )}$$

ध्यान दें कि $\psi (\theta )<\infty$ तात्पर्य यह है कि यह वास्तव में लॉग क्षण-उत्पन्न करने वाला कार्य है। मोमेंट-जेनरेशन फलन, यानी $\psi (\theta )=\log \mathbb {E} {\exp(tX)}|_{t=\theta }=\log M_{X}(t)|_{t=\theta }$. और प्रस्ताव के लॉग क्षण-सृजन फलन को प्राप्त करना आसान है और इसलिए प्रस्ताव के क्षण।

$${\begin{aligned}\psi _{\theta }(\eta )&=\log \left(\mathbb {E} _{\theta }\exp(\eta X)\right)=\psi (\theta +\eta )-\psi (\theta )<\infty \\\mathbb {E} _{\theta }(X)&=\left.{\frac {\partial \psi _{\theta }(\eta )}{\partial \eta }}\right|_{\eta =0}\\\mathrm {Var} _{\theta }(X)&=\left.{\frac {\partial ^{2}\psi _{\theta }(\eta )}{\partial ^{2}\eta }}\right|_{\eta =0}\end{aligned}}$$

साधारण उदाहरण के रूप में, मान लीजिए $F(\cdot )$, $X\sim \mathrm {N} (\mu ,\sigma ^{2})$, साथ ${\textstyle \psi (\theta )=\theta \mu +{\frac {\sigma ^{2}\theta ^{2}}{2}}}$. लक्ष्य नमूना लेना है $X|X\in \left[b,\infty \right]$, $b>\mu$. विश्लेषण इस प्रकार है।

• प्रस्ताव वितरण का रूप चुनें $F_{\theta }(\cdot )$, लॉग मोमेंट-जेनरेटिंग फलन के रूप में ${\textstyle \psi _{\theta }(\eta )=\psi (\theta +\eta )-\psi (\eta )=\eta (\mu +\theta \sigma ^{2})+{\frac {\sigma ^{2}\eta ^{2}}{2}}}$, जिसका अर्थ है कि यह सामान्य वितरण है $\mathrm {N} (\mu +\theta \sigma ^{2},\sigma ^{2})$.
• अच्छी तरह से चुने गए का फैसला करें $\theta ^{*}$ प्रस्ताव वितरण के लिए इस सेटअप में, चुनने का सहज विधि $\theta ^{*}$ लगाना है $\mathbb {E} _{\theta }(X)=\mu +\theta \sigma ^{2}=b$, वह है $\theta ^{*}={\frac {b-\mu }{\sigma ^{2}}}$
• स्पष्ट रूप से लक्ष्य, प्रस्ताव और संभावना अनुपात लिखें
  $${\begin{aligned}f_{X|X\geq b}(x)&={\frac {f(x)\mathbb {I} (x\geq b)}{\mathbb {P} (X\geq b)}}\\g_{\theta ^{*}}(x)&=f(x)\exp(\theta ^{*}x-\psi (\theta ^{*}))\\Z(x)&={\frac {f_{X|X\geq b}(x)}{g_{\theta ^{*}}(x)}}={\frac {\exp(-\theta ^{*}x+\psi (\theta ^{*}))\mathbb {I} (x\geq b)}{\mathbb {P} (X\geq b)}}\end{aligned}}$$
• सीमा प्राप्त करें $M$ संभावना अनुपात के लिए $z(x)$, जो कि घटता हुआ कार्य है $x\in [b,\infty ]$, इसलिए
  $$M=Z(b)={\frac {\exp(-\theta ^{*}b+\psi (\theta ^{*}))}{\mathbb {P} (X\geq b)}}={\frac {\exp \left(-{\frac {(b-\mu )^{2}}{2\sigma ^{2}}}\right)}{\mathbb {P} (X\geq b)}}={\frac {\exp \left(-{\frac {(b-\mu )^{2}}{2\sigma ^{2}}}\right)}{\mathbb {P} \left(\mathrm {N} (0,1)\geq {\frac {b-\mu }{\sigma }}\right)}}$$
• अस्वीकृति नमूनाकरण मानदंड: के लिए $U\sim \mathrm {Unif} (0,1)$, अगर
  $$U\leq {\frac {Z(x)}{M}}=e^{-\theta ^{*}(x-b)}\mathbb {I} (x\geq b)$$
  रखता है, का मान स्वीकार करता है $X$; यदि नहीं, तो नया नमूना लेना जारी रखें ${\textstyle X\sim _{i.i.d.}\mathrm {N} (\mu +\theta ^{*}\sigma ^{2},\sigma ^{2})}$ और नया ${\textstyle U\sim \mathrm {Unif} (0,1)}$ स्वीकृति तक।

उपरोक्त उदाहरण के लिए, दक्षता की माप के रूप में, पुनरावृत्तियों की अपेक्षित संख्या एनईएफ-आधारित अस्वीकृति नमूना पद्धति क्रम b की है, अर्थात $M(b)=O(b)$, जबकि भोली पद्धति के अंतर्गत, पुनरावृत्तियों की अपेक्षित संख्या है ${\textstyle {\frac {1}{\mathbb {P} (X\geq b)}}=O(b\cdot e^{\frac {(b-\mu )^{2}}{2\sigma ^{2}}})}$, जो कहीं अधिक अक्षम है।

सामान्यतः, घातीय झुकाव, प्रस्ताव वितरण का पैरामीट्रिक वर्ग, अपने उपयोगी गुणों के साथ अनुकूलन समस्याओं को आसानी से हल करता है जो सीधे प्रस्ताव के वितरण की विशेषता बताते हैं। इस प्रकार की समस्या के लिए अनुकरण करना $X$ सशर्त रूप से $X\in A$, सरल वितरण के वर्ग के बीच, एनईएफ का उपयोग करने की चाल है, जो जटिलता पर कुछ नियंत्रण प्राप्त करने में सहायता करती है और गणना को काफी तेज करती है। दरअसल, एनईएफ का उपयोग करने के गहरे गणितीय कारण हैं।

कमियां

यदि नमूना लिया जा रहा कार्य निश्चित क्षेत्र में अत्यधिक केंद्रित है, उदाहरण के लिए फलन जिसमें किसी स्थान पर स्पाइक है, तो अस्वीकृति नमूनाकरण से बहुत सारे अवांछित नमूने लिए जा सकते हैं। कई वितरणों के लिए, इस समस्या को अनुकूली विस्तार (देखें # अनुकूली अस्वीकृति नमूनाकरण) का उपयोग करके या यूनिफार्म के अनुपात की विधि के साथ चर के उचित परिवर्तन के साथ हल किया जा सकता है। इसके अतिरिक्त, जैसे-जैसे समस्या का आयाम बड़ा होता जाता है, एम्बेडिंग वॉल्यूम के कोनों में एम्बेडेड वॉल्यूम का अनुपात शून्य की ओर बढ़ता जाता है, इस प्रकार उपयोगी नमूना उत्पन्न होने से पहले बहुत सारे अस्वीकरण हो सकते हैं, इस प्रकार एल्गोरिथम को अक्षम बना दिया जाता है और अव्यावहारिक। आयामीता का अपवाद देखें। उच्च आयामों में, अलग दृष्टिकोण का उपयोग करना आवश्यक है, सामान्यतः मार्कोव श्रृंखला मोंटे कार्लो विधि जैसे मेट्रोपोलिस नमूनाकरण या गिब्स नमूनाकरण। (चूंकि, गिब्स नमूनाकरण, जो बहु-आयामी नमूनाकरण समस्या को निम्न-आयामी नमूनों की श्रृंखला में विभाजित करता है, इसके चरण के रूप में अस्वीकृति नमूनाकरण का उपयोग कर सकता है।)

अनुकूली अस्वीकृति नमूनाकरण

कई वितरणों के लिए, ऐसा प्रस्ताव वितरण खोजना मुश्किल है जिसमें बहुत अधिक बर्बाद जगह के बिना दिए गए वितरण को सम्मिलित किया गया हो। अस्वीकृति नमूनाकरण का विस्तार जिसका उपयोग इस कठिनाई को दूर करने के लिए किया जा सकता है और विभिन्न प्रकार के वितरणों से कुशलता से नमूना लिया जा सकता है (बशर्ते कि उनके पास लॉगरिदमिक रूप से अवतल कार्य हो। लॉग-अवतल घनत्व कार्य, जो वास्तव में अधिकांश सामान्य वितरणों के स्थितियों में है- यहां तक ​​​​कि जिनके घनत्व कार्य स्वयं अवतल नहीं हैं) को 'अनुकूली अस्वीकृति नमूनाकरण (एआरएस)' के रूप में जाना जाता है।

1992 में गिल्क्स द्वारा अंततः पेश की गई इस तकनीक के लिए तीन मूल विचार हैं:

1. यदि यह सहायता करता है, तो इसके अतिरिक्त लॉग स्पेस (जैसे लॉग-प्रायिकता या लॉग-घनत्व) में अपने लिफाफा वितरण को परिभाषित करें। यानी साथ काम करें $h\left(x\right)=\log g\left(x\right)$ के अतिरिक्त $g\left(x\right)$ सीधे।
   • अधिकांशतः, जिन वितरणों में बीजगणितीय रूप से गड़बड़ घनत्व कार्य होते हैं, उनके पास यथोचित सरल लॉग घनत्व कार्य होते हैं (अर्थात जब $f\left(x\right)$ गन्दा है, $\log f\left(x\right)$ के साथ काम करना सरल हो सकता है या कम से कम, टुकड़ों में रैखिक के करीब)।
2. समान लिफ़ाफ़ा घनत्व फलन के अतिरिक्त, अपने लिफाफे के रूप में टुकड़ा-वार रैखिक घनत्व फलन का उपयोग करें।
   • हर बार जब आपको किसी नमूने को अस्वीकार करना हो, तो आप के मान का उपयोग कर सकते हैं $f\left(x\right)$ जिसका आपने मूल्यांकन किया है, टुकड़ों के सन्निकटन में सुधार करने के लिए $h\left(x\right)$. इससे आपके अगले प्रयास के अस्वीकृत होने की संभावना कम हो जाती है। असम्बद्ध रूप से, आपके नमूने को अस्वीकार करने की आवश्यकता की संभावना शून्य हो जानी चाहिए, और व्यवहार में, अधिकांशतः बहुत तेज़ी से।
   • जैसा कि प्रस्तावित है, किसी भी समय हम ऐसा बिंदु चुनते हैं जिसे अस्वीकार कर दिया जाता है, हम लिफाफे को अन्य रेखा खंड के साथ कसते हैं जो उस बिंदु पर स्पर्शरेखा है जो चुने गए बिंदु के समान x-निर्देशांक के साथ है।
   • प्रस्ताव लॉग वितरण का टुकड़ावार रेखीय मॉडल टुकड़ेवार घातीय वितरण के सेट में परिणाम देता है (यानी एक या अधिक घातीय वितरण के खंड, अंत से अंत तक संलग्न)। घातीय वितरण अच्छी तरह से व्यवहार किया जाता है और अच्छी तरह से समझा जाता है। घातीय वितरण का लघुगणक सीधी रेखा है, और इसलिए इस पद्धति में अनिवार्य रूप से रेखा खंडों की श्रृंखला में घनत्व के लघुगणक को सम्मिलित करना सम्मिलित है। यह लॉग-अवतल प्रतिबंध का स्रोत है: यदि कोई वितरण लॉग-अवतल है, तो इसका लघुगणक अवतल (उल्टा-नीचे U जैसा आकार) है, जिसका अर्थ है कि वक्र के लिए स्पर्शरेखा रेखा खंड हमेशा वक्र के ऊपर से गुजरेगा।
   • यदि लॉग स्पेस में काम नहीं कर रहा है, तो टुकड़े के अनुसार रैखिक घनत्व फलन को त्रिकोण वितरण के माध्यम से भी नमूना लिया जा सकता है
3. मूल्यांकन की लागत से संभावित रूप से बचने के लिए हम (लॉग) समतलता आवश्यकता का और भी लाभ उठा सकते हैं $f\left(x\right)$ जब आपका नमूना स्वीकार किया जाता है।
   • जैसे हम के मानों का उपयोग करके टुकड़े की रैखिक ऊपरी सीमा (लिफ़ाफ़ा फलन) का निर्माण कर सकते हैं $h\left(x\right)$ कि हमें अस्वीकृति की वर्तमान श्रृंखला में मूल्यांकन करना था, हम इन मूल्यों का उपयोग करके टुकड़े की रैखिक निचली सीमा (निचोड़ने का कार्य) भी बना सकते हैं।
   • मूल्यांकन करने से पहले (संभावित महंगा) $f\left(x\right)$ यह देखने के लिए कि आपका नमूना स्वीकार किया जाएगा या नहीं, हम पहले से ही जान सकते हैं कि यह (आदर्श रूप से सस्ता) के खिलाफ तुलना करके स्वीकार किया जाएगा या नहीं $g_{l}\left(x\right)$ (या $h_{l}\left(x\right)$ इस स्थितियों में) निचोड़ने का कार्य जो उपलब्ध है।
   • गिलक्स द्वारा सुझाए जाने पर भी यह निचोड़ने वाला कदम वैकल्पिक है। सर्वोत्तम रूप से यह आपको आपके (गड़बड़ और/या महंगे) लक्ष्य घनत्व के केवल अतिरिक्त मूल्यांकन से बचाता है। चूंकि, संभवतः विशेष रूप से महंगे घनत्व कार्यों के लिए (और शून्य की ओर अस्वीकृति दर के तेजी से अभिसरण को मानते हुए) यह अंतिम रनटाइम में बड़ा अंतर बना सकता है।

इस पद्धति में अनिवार्य रूप से सीधी-रेखा खंडों के लिफाफे को क्रमिक रूप से निर्धारित करना सम्मिलित है जो लघुगणक को बेहतर और अच्छा बनाता है, जबकि अभी भी वक्र के ऊपर शेष है, निश्चित संख्या में खंडों (संभवतः केवल स्पर्शरेखा रेखा) से प्रारंभ होता है। छोटे घातीय यादृच्छिक चर से नमूनाकरण सीधा है। बस समान यादृच्छिक चर का लॉग लें (उचित अंतराल और संबंधित ट्रंकेशन के साथ)।

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

यह भी देखें

• उलटा नमूना बदलना
• वर्दी का अनुपात
• छद्म यादृच्छिक संख्या नमूनाकरण
• ज़िगगुरैट एल्गोरिथम

अग्रिम पठन

• Robert, C. P.; Casella, G. (2004). Monte Carlo Statistical Methods (Second ed.). New York: Springer-Verlag.