أخذ العينات بالرفض

في التحليل العددي والإحصاء الحاسوبي ، يُعدّ أخذ العينات بالرفض أسلوبًا أساسيًا يُستخدم لتوليد مشاهدات من توزيع إحصائي . ويُعرف أيضًا باسم طريقة القبول والرفض أو "خوارزمية القبول والرفض"، وهو نوع من أساليب المحاكاة الدقيقة. تُطبّق هذه الطريقة على أي توزيع إحصائي.${\displaystyle \mathbb {R} ^{m}}$بكثافة .​

تعتمد معاينة الرفض على ملاحظة أنه لمعاينة متغير عشوائي في بُعد واحد، يمكن إجراء معاينة عشوائية منتظمة للرسم البياني الديكارتي ثنائي الأبعاد، مع الاحتفاظ بالعينات في المنطقة الواقعة أسفل منحنى دالة الكثافة الخاصة به. ^{[ 1 ] [ 2 ] [ 3 ]} تجدر الإشارة إلى أن هذه الخاصية قابلة للتعميم على الدوال ذات الأبعاد N.

تعتمد الخوارزمية، التي استخدمها جون فون نيومان ^{[ 4 ]} ويعود تاريخها إلى بوفون وإبرته ، على سحب عينة من دالة كثافة احتمالية (مستهدفة) .${\displaystyle f(x)}$وهو ما يتناسب مع${\displaystyle f_{\varpropto }(x)}$باستخدام سحوبات من دالة كثافة احتمالية أبسط (مقترحة)${\displaystyle g(x)}$على النحو التالي:

أخذ العينات بالرفض

مدخل

كثافة الهدف${\displaystyle f(x)={\frac {f_{\varpropto }(x)}{\int f_{\varpropto }(y)dy}}}$كثافة الاقتراح${\displaystyle g(x)}$، ثابت${\displaystyle M}$بحيث${\displaystyle f_{\varpropto }(x)\leq Mg(x)}$للجميع${\displaystyle x}$.

الخوارزمية

1. عينة${\displaystyle X\sim g(x)}$
2. عينة${\displaystyle U\sim \mathrm {Unif} (0,1)}$بشكل مستقل عن${\displaystyle X}$.
3. حساب نسبة الاحتمالية${\displaystyle W={\dfrac {f_{\varpropto }(X)}{g(X)}}}$.
4. لو${\displaystyle W<M\times U}$، يرفض${\displaystyle X}$وكرر الخطوات من 1. وإلا، فاقبل الملف وأخرجه.${\displaystyle X}$.

الناتج

نموذج${\displaystyle X}$مستمد من${\displaystyle f}$.

ستأخذ الخوارزمية متوسطًا لـ${\displaystyle {\frac {M}{\int f_{\varpropto }(y)dy}}}$رفض الحصول على عينة.

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

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

تعمل عملية أخذ العينات بالرفض على النحو التالي:

1. قم بأخذ عينة من نقطة على${\displaystyle x}$المحور السالب من توزيع الاقتراح.
2. ارسم خطًا رأسيًا عند هذه النقطة${\displaystyle x}$–الموقع، حتى قيمة y لدالة كثافة الاحتمال لتوزيع الاقتراح.
3. قم بأخذ عينة عشوائية بشكل منتظم على طول هذا الخط. إذا كانت القيمة المأخوذة من العينة أكبر من قيمة التوزيع المطلوب عند هذا الخط الرأسي، فارفض العينة.${\displaystyle x}$-القيمة والعودة إلى الخطوة 1؛ وإلا${\displaystyle x}$القيمة السالبة هي عينة من التوزيع المطلوب.

يمكن استخدام هذه الخوارزمية لأخذ عينات من المساحة تحت أي منحنى، بغض النظر عما إذا كانت الدالة تتكامل إلى 1 أم لا. في الواقع، لا يؤثر ضرب الدالة بثابت على العينة المأخوذة.${\displaystyle x}$–المواضع . وبالتالي، يمكن استخدام الخوارزمية لأخذ عينات من توزيع يكون ثابت التطبيع الخاص به غير معروف، وهو أمر شائع في الإحصاءات الحاسوبية .

في التحليل التالي، نفترض، تبسيطاً للأمر، أن ${\displaystyle f\equiv f_{\varpropto }}$تُنتج طريقة أخذ العينات بالرفض قيمًا للعينة من توزيع مستهدف ذي دالة كثافة احتمالية .${\displaystyle f(x)}$باستخدام توزيع اقتراح ذي كثافة احتمالية${\displaystyle g(x)}$الفكرة هي أنه يمكن للمرء توليد قيمة عينة من${\displaystyle f}$بدلاً من ذلك، يتم أخذ عينات من${\displaystyle g}$وقبول العينة من${\displaystyle f}$باحتمال${\displaystyle f(x)/(Mg(x))}$، مع تكرار عمليات السحب من${\displaystyle g}$إلى أن يتم قبول قيمة معينة. ${\displaystyle M}$يوجد حد ثابت ومحدود لنسبة الاحتمال${\displaystyle f(x)/g(x)}$مرضٍ${\displaystyle M<\infty }$على دعم​${\displaystyle f}$؛ بعبارة أخرى،${\displaystyle M}$يجب أن يفي${\displaystyle f(x)\leq Mg(x)}$لجميع قيم${\displaystyle x}$لاحظ أن هذا يتطلب دعم${\displaystyle g}$يجب أن يشمل ذلك دعم${\displaystyle f}$-بعبارة أخرى،${\displaystyle g(x)>0}$حينما${\displaystyle f(x)>0}$.

يُعد مبدأ الغلاف دليلاً على صحة هذه الطريقة: عند محاكاة الزوج${\textstyle (x,v=u\cdot Mg(x))}$، يقوم المرء بإنتاج محاكاة موحدة على الرسم البياني الفرعي لـ${\textstyle Mg(x)}$قبول الأزواج التي تحقق الشروط التالية فقط${\textstyle u<f(x)/(Mg(x))}$ثم ينتج أزواجًا${\displaystyle (x,v)}$موزعة بشكل منتظم على الرسم البياني الفرعي لـ${\displaystyle f(x)}$وبالتالي، بشكل هامشي، محاكاة من${\displaystyle f(x).}$

هذا يعني أنه مع وجود عدد كافٍ من التكرارات، تقوم الخوارزمية بتوليد عينة من التوزيع المطلوب${\displaystyle f(x)}$هناك عدد من التوسعات لهذه الخوارزمية، مثل خوارزمية متروبوليس .

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

احتمالية القبول غير المشروطة هي نسبة العينات المقترحة التي يتم قبولها، وهي$${\displaystyle {\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]&=\operatorname {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]&=\operatorname {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}}}$$أين${\displaystyle U\sim \mathrm {Unif} (0,1)}$وقيمة${\displaystyle Y}$يتم توليد كل مرة وفقًا لدالة الكثافة${\displaystyle g(\cdot )}$توزيع المقترح.

عدد العينات المطلوبة من${\displaystyle g}$وبالتالي فإن الحصول على قيمة مقبولة يتبع توزيعًا هندسيًا باحتمالية${\displaystyle 1/M}$، وهو ما يعني${\displaystyle M}$بشكل بديهي،${\displaystyle M}$يمثل العدد المتوقع للتكرارات المطلوبة، كمقياس للتعقيد الحسابي للخوارزمية.

أعد كتابة المعادلة أعلاه،$${\displaystyle 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)}$هي احتمالية لا يمكن أن تأخذ إلا قيمًا في الفترة${\displaystyle [0,1]}$. متى${\displaystyle M}$كلما قل تغير هذه النسبة، زادت احتمالية القبول غير المشروط، وذلك لأن${\displaystyle M}$يمثل الحد الأعلى لنسبة الاحتمال${\textstyle f(x)/g(x)}$عملياً، قيمة${\displaystyle M}$يفضل أن تكون القيمة أقرب إلى 1 لأنها تعني عددًا أقل من العينات المرفوضة، في المتوسط، وبالتالي عددًا أقل من تكرارات الخوارزمية. وبهذا المعنى، يفضل المرء أن تكون القيمة${\displaystyle M}$بأصغر حجم ممكن (مع الحفاظ على الرضا)${\displaystyle f(x)\leq Mg(x)}$مما يشير إلى أن${\displaystyle g(x)}$ينبغي أن يشبه بشكل عام${\displaystyle f(x)}$بطريقة ما. لاحظ مع ذلك أن${\displaystyle M}$لا يمكن أن يساوي 1: فهذا يعني أن${\displaystyle f(x)=g(x)}$أي أن توزيعات الهدف والاقتراح هي في الواقع نفس التوزيع.

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

قد يكون أخذ العينات بالرفض أكثر كفاءة بكثير مقارنة بالطرق البسيطة في بعض الحالات. على سبيل المثال، عند النظر في مشكلة مثل أخذ العينات${\textstyle X\sim F(\cdot )}$بشرط${\displaystyle X}$بالنظر إلى المجموعة${\displaystyle A}$، أي،${\textstyle X|X\in A}$، أحيانا${\textstyle X}$يمكن محاكاتها بسهولة باستخدام الطرق البسيطة (مثل أخذ عينات التحويل العكسي ):

• عينة${\textstyle X\sim F(\cdot )}$بشكل مستقل، وقبول ما يرضي${\displaystyle \{n\geq 1:X_{n}\in A\}}$
• الناتج:${\displaystyle \{X_{1},X_{2},...,X_{N}:X_{i}\in A,i=1,...,N\}}$(انظر أيضًا الاقتطاع (الإحصائيات) )

تكمن المشكلة في أن عملية أخذ العينات هذه قد تكون صعبة وغير فعالة، إذا${\textstyle \mathbb {P} (X\in A)\approx 0}$سيكون عدد التكرارات المتوقع هو${\displaystyle {\frac {1}{\mathbb {P} (X\in A)}}}$والتي قد تقترب من اللانهاية. علاوة على ذلك، حتى عند تطبيق طريقة أخذ العينات بالرفض، فإنه من الصعب دائمًا تحسين الحد.${\displaystyle M}$بالنسبة لنسبة الاحتمال. في أغلب الأحيان،${\displaystyle M}$إذا كان حجم البيانات كبيرًا ومعدل الرفض مرتفعًا، فقد تكون الخوارزمية غير فعالة للغاية. توفر عائلة التوزيعات الأسية الطبيعية (إن وجدت)، والمعروفة أيضًا باسم التوزيع الأسي المائل، فئة من توزيعات الاقتراحات التي يمكنها تقليل التعقيد الحسابي، وقيمة${\displaystyle M}$وتسريع العمليات الحسابية (انظر الأمثلة: العمل مع العائلات الأسية الطبيعية).

بافتراض وجود متغير عشوائي${\displaystyle X\sim F(\cdot )}$،${\displaystyle F(x)=\mathbb {P} (X\leq x)}$يمثل التوزيع المستهدف. ولتبسيط الأمر، نفترض أن دالة الكثافة يمكن كتابتها صراحةً على النحو التالي:${\displaystyle f(x)}$اختر الاقتراح كـ

$${\displaystyle {\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}}}$$

أين${\displaystyle \psi (\theta )=\log \left(\mathbb {E} \exp(\theta X)\right)}$و${\displaystyle \Theta =\{\theta$ :\psi (\theta )<\infty \}} . من الواضح،${\displaystyle \{F_{\theta }(\cdot )\}_{\theta \in \Theta }}$، ينتمي إلى عائلة الدوال الأسية الطبيعية . علاوة على ذلك، فإن نسبة الاحتمال هي

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

لاحظ أن${\displaystyle \psi (\theta )<\infty }$وهذا يعني أنها بالفعل دالة توليد تراكمية ، أي

${\displaystyle \psi (\theta )=\log \mathbb {E} {\exp(tX)}|_{t=\theta }=\log M_{X}(t)|_{t=\theta }}$.

من السهل استنتاج دالة توليد العزوم للاقتراح وبالتالي العزوم الخاصة بالاقتراح.

${\displaystyle {\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}}}$

كمثال بسيط، لنفترض تحت${\displaystyle F(\cdot )}$،${\displaystyle X\sim \mathrm {N} (\mu ,\sigma ^{2})}$، مع${\textstyle \psi (\theta )=\mu \theta +{\frac {\sigma ^{2}\theta ^{2}}{2}}}$الهدف هو أخذ عينات${\displaystyle X|X\in \left[b,\infty \right]}$، أين${\displaystyle b>\mu }$. ويتم التحليل على النحو التالي:

• اختر شكل توزيع المقترح${\displaystyle F_{\theta }(\cdot )}$، مع دالة توليد العزوم التراكمية كـ

${\textstyle \psi _{\theta }(\eta )=\psi (\theta +\eta )-\psi (\theta )=(\mu +\theta \sigma ^{2})\eta +{\frac {\sigma ^{2}\eta ^{2}}{2}}}$،

مما يعني كذلك أنه توزيع طبيعي${\displaystyle \mathrm {N} (\mu +\theta \sigma ^{2},\sigma ^{2})}$.

• اختر الخيار المناسب${\displaystyle \theta ^{*}}$لتوزيع المقترح. في هذا الإعداد، الطريقة البديهية للاختيار${\displaystyle \theta ^{*}}$هو أن يحدد

${\displaystyle \mathbb {E} _{\theta }(X)=\mu +\theta \sigma ^{2}=b}$،

إنه${\displaystyle \theta ^{*}={\frac {b-\mu }{\sigma ^{2}}}.}$وبالتالي فإن توزيع المقترح يكون${\displaystyle g_{\theta ^{*}}(x)=\mathrm {N} (b,\sigma ^{2})}$.

• اكتب بوضوح الهدف، والاقتراح، ونسبة الاحتمالية

$${\displaystyle {\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}}}$$

• استنتج الحد${\displaystyle M}$بالنسبة لنسبة الاحتمال${\displaystyle Z(x)}$وهي دالة متناقصة لـ${\displaystyle x\in [b,\infty ]}$، لذلك

$${\displaystyle 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)}}}$$

• معيار رفض العينة: لـ${\displaystyle U\sim \mathrm {Unif} (0,1)}$، لو

$${\displaystyle U\leq {\frac {Z(x)}{M}}=e^{-\theta ^{*}(x-b)}\mathbb {I} (x\geq b)}$$

يحمل، ويقبل قيمة${\displaystyle X}$وإلا، فاستمر في تجربة عينات جديدة${\textstyle X\sim _{i.i.d.}\mathrm {N} (\mu +\theta ^{*}\sigma ^{2},\sigma ^{2})}$وجديد${\textstyle U\sim \mathrm {Unif} (0,1)}$حتى القبول.

في المثال أعلاه، كمقياس للكفاءة، يكون العدد المتوقع للتكرارات في طريقة أخذ العينات بالرفض القائمة على عائلة التوزيع الأسي الطبيعي من الرتبة${\displaystyle b}$، إنه${\displaystyle M(b)=O(b)}$أما في ظل الطريقة البسيطة، فإن العدد المتوقع للتكرارات هو${\textstyle {\frac {1}{\mathbb {P} (X\geq b)}}=O(b\cdot e^{\frac {(b-\mu )^{2}}{2\sigma ^{2}}})}$وهو أمر أقل كفاءة بكثير.

بشكل عام، يُعدّ التوزيع الأسي المائل فئةً بارامتريةً من توزيعات الاقتراح، وهو يحلّ مسائل التحسين بسهولة، بفضل خصائصه المفيدة التي تُحدّد توزيع الاقتراح بشكل مباشر. ولمحاكاة هذا النوع من المسائل،${\displaystyle X}$بشرط${\displaystyle X\in A}$من بين فئة التوزيعات البسيطة، تكمن الحيلة في استخدام عائلة التوزيعات الأسية الطبيعية، مما يساعد على التحكم في التعقيد وتسريع الحساب بشكل ملحوظ. في الواقع، هناك أسباب رياضية عميقة لاستخدام عائلة التوزيعات الأسية الطبيعية.

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

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

عندما لا يوجد ثابت محدود${\displaystyle M}$استيفاء الشرط${\displaystyle M\geq \sup _{x}{\frac {f_{\varpropto }(x)}{g(x)}}}$ موجود، أو محدود مناسب${\displaystyle M<\infty }$نظرًا لصعوبة حسابها، يمكن استخدام نسخة معدلة من خوارزمية أخذ العينات بالرفض لمحاكاة الهدف (تقريبًا).${\displaystyle f}$على النحو التالي. ^{[ 5 ]}

أخذ عينات الرفض التجديدي

مدخل

كثافة الهدف${\displaystyle f(x)={\frac {f_{\varpropto }(x)}{\int f_{\varpropto }(y)dy}}}$كثافة الاقتراح${\displaystyle g(x)}$ثابت كبير ${\displaystyle M}$.

الخوارزمية

عداد الضبط${\displaystyle t\leftarrow 0}$.

1. عينة${\displaystyle X\sim g(x)}$وزيادة${\displaystyle t\leftarrow t+1}$.
2. حساب نسبة الاحتمالية${\displaystyle W_{t}={\dfrac {f_{\varpropto }(X)}{g(X)}}}$.
3. لو${\displaystyle W_{1}+\cdots +W_{t}<M}$، يرفض${\displaystyle X}$وكرر الخطوات من 1. وإلا، فاقبل الملف وأخرجه.${\displaystyle X}$.

الناتج

نموذج${\displaystyle X}$مستمد تقريبًا من${\displaystyle f}$.

الفرق الوحيد بين النسخة التجديدية المذكورة أعلاه وأسلوب أخذ العينات بالرفض الكلاسيكي هو أن قرار القبول يعتمد على ما إذا كان المجموع التراكمي لجميع نسب الاحتمالية${\displaystyle W_{1}+\cdots +W_{t}}$يتجاوز${\displaystyle M}$(إنه،${\displaystyle W_{1}+\cdots +W_{t}>M}$)، بدلاً من الاعتماد على ما إذا كانت نسبة الاحتمال الحالية${\displaystyle W_{t}}$يتجاوز${\displaystyle M\times U}$(إنه،${\displaystyle W_{t}>M\times U}$).

يمكن إثبات ذلك، كما${\displaystyle M\rightarrow \infty }$، وهو المتغير الناتج للخوارزمية ${\displaystyle X=X_{M}}$يتقارب التوزيع نحو الهدف المطلوب بكثافة${\displaystyle f}$[ ^{5 ]​}

هناك نهج آخر لا يتطلب معرفة ثابت التقييد الأمثل ${\displaystyle \sup _{x}{\frac {f_{\varpropto }(x)}{g(x)}}}$هي طريقة أخذ العينات التجريبية لرفض القيمة العليا . ^{[ 6 ]}

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

هناك ثلاث أفكار أساسية لهذه التقنية كما قدمها جيلكس في عام 1992: ^{[ 7 ]}

1. إذا كان ذلك مفيدًا، فحدد توزيع المغلف الخاص بك في فضاء لوغاريتمي (مثل الاحتمالية اللوغاريتمية أو الكثافة اللوغاريتمية) بدلاً من ذلك. أي، اعمل مع${\displaystyle h\left(x\right)=\log g\left(x\right)}$بدلاً من${\displaystyle g\left(x\right)}$مباشرة.
   • غالباً ما تكون التوزيعات التي تتميز بدوال كثافة معقدة جبرياً لها دوال كثافة لوغاريتمية أبسط نسبياً (أي عندما${\displaystyle f\left(x\right)}$فوضوي،${\displaystyle \log f\left(x\right)}$قد يكون من الأسهل التعامل معه أو على الأقل أقرب إلى الخطية القطعية).
2. بدلاً من استخدام دالة كثافة غلاف موحدة واحدة، استخدم دالة كثافة خطية مجزأة كغلاف لك.
   • في كل مرة تضطر فيها إلى رفض عينة، يمكنك استخدام قيمة${\displaystyle f\left(x\right)}$التي قمت بتقييمها، لتحسين التقريب القطعي${\displaystyle h\left(x\right)}$وبالتالي، يقلل هذا من احتمالية رفض محاولتك التالية. ومن الناحية النظرية، ينبغي أن يتقارب احتمال الحاجة إلى رفض العينة إلى الصفر، وفي الواقع العملي، غالبًا بسرعة كبيرة.
   • كما هو مقترح، في كل مرة نختار فيها نقطة مرفوضة، نقوم بتضييق الغلاف بقطعة مستقيمة أخرى مماسية للمنحنى عند النقطة التي لها نفس الإحداثي السيني للنقطة المختارة.
   • ينتج عن نموذج خطي مجزأ لتوزيع اللوغاريتم المقترح مجموعة من التوزيعات الأسية المجزأة (أي أجزاء من توزيع أسي واحد أو أكثر، متصلة طرفًا بطرف). تتميز التوزيعات الأسية بسلوكها المنتظم وفهمها الجيد. لوغاريتم التوزيع الأسي هو خط مستقيم، وبالتالي تتضمن هذه الطريقة أساسًا حصر لوغاريتم الكثافة في سلسلة من القطع المستقيمة. هذا هو مصدر قيد التقعر اللوغاريتمي: إذا كان التوزيع مقعرًا لوغاريتميًا، فإن لوغاريتمه يكون مقعرًا (على شكل حرف U مقلوب)، مما يعني أن أي قطعة مستقيمة مماسة للمنحنى ستمر دائمًا فوقه.
   • إذا لم يكن العمل في فضاء لوغاريتمي، فيمكن أيضًا أخذ عينات من دالة الكثافة الخطية القطعية عبر توزيعات المثلث ^{[ 8 ].}
3. يمكننا الاستفادة بشكل أكبر من شرط التقعر (اللوغاريتمي)، لتجنب تكلفة التقييم.${\displaystyle f\left(x\right)}$عندما يتم قبول عينتك .
   • تمامًا كما يمكننا إنشاء حد أعلى خطي مجزأ (دالة "الغلاف") باستخدام قيم${\displaystyle h\left(x\right)}$والتي كان علينا تقييمها في سلسلة الرفض الحالية، يمكننا أيضًا إنشاء حد أدنى خطي مجزأ (دالة "الضغط") باستخدام هذه القيم أيضًا.
   • قبل تقييم (الأمر الذي قد يكون مكلفاً)${\displaystyle f\left(x\right)}$لمعرفة ما إذا كانت عينتك ستُقبل، قد نعرف بالفعل ما إذا كانت ستُقبل من خلال مقارنتها بالعينة (الأرخص ثمناً من الناحية المثالية).${\displaystyle g_{l}\left(x\right)}$(أو${\displaystyle h_{l}\left(x\right)}$(في هذه الحالة) وظيفة الضغط المتاحة.
   • تُعدّ خطوة الضغط هذه اختيارية، حتى وإن اقترحها جيلكس. في أحسن الأحوال، تُجنّبك هذه الخطوة سوى تقييم إضافي واحد لدالة الكثافة المستهدفة (المعقدة و/أو المكلفة). مع ذلك، يُفترض أنه بالنسبة لدوال الكثافة المكلفة للغاية (وبافتراض التقارب السريع لمعدل الرفض نحو الصفر)، يُمكن أن تُحدث هذه الخطوة فرقًا كبيرًا في وقت التشغيل النهائي.

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

لسوء الحظ، لا يمكن تطبيق خوارزمية أخذ العينات التكيفية (ARS) إلا على عينات من توزيعات احتمالية لوغاريتمية مقعرة. لهذا السبب، اقتُرحت العديد من التوسعات لخوارزمية ARS في الأدبيات العلمية لمعالجة التوزيعات الاحتمالية غير اللوغاريتمية المقعرة. ^{[ 9 ] [ 10 ] [ 11 ]} علاوة على ذلك، صُممت تركيبات مختلفة من خوارزمية ARS وطريقة متروبوليس-هاستينغز للحصول على خوارزمية أخذ عينات شاملة تُنشئ توزيعات احتمالية ذاتية الضبط (أي توزيعات احتمالية تُنشأ وتُكيّف تلقائيًا مع التوزيع الاحتمالي المستهدف). تُعرف هذه الفئة من الطرق غالبًا باسم خوارزميات أخذ عينات متروبوليس التكيفية بالرفض (ARMS) . ^{[ 12 ] [ 13 ]} يمكن دائمًا تطبيق التقنيات التكيفية الناتجة، ولكن العينات المُولّدة تكون مترابطة في هذه الحالة (على الرغم من أن الارتباط يتلاشى بسرعة إلى الصفر مع ازدياد عدد التكرارات).

• أخذ العينات بالتحويل العكسي
• نسبة الزي الرسمي
• أخذ عينات الأرقام شبه العشوائية
• خوارزمية الزقورة

• روبرت، سي بي؛ كاسيلا، جي. (2004). الأساليب الإحصائية مونت كارلو (  الطبعة الثانية). نيويورك: سبرينغر-فيرلاغ.