मोंटे कार्लो एकीकरण

मोंटे कार्लो एकीकरण का एक उदाहरण। इस उदाहरण में, प्रांत डी आंतरिक चक्र है और प्रांत ई वर्ग है। क्योंकि वर्ग के क्षेत्रफल (4) की गणना आसानी से की जा सकती है, वृत्त का क्षेत्रफल (π*1.0²) का अनुमान सर्कल (40) के भीतर बिंदुओं के अनुपात (0.8) से अंकों की कुल संख्या (50) से लगाया जा सकता है, जिससे सर्कल के क्षेत्रफल के लिए 4*0.8 = 3.2 ≈ π का ​​अनुमान लगाया जा सकता है।

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

मोंटे कार्लो एकीकरण करने के लिए अलग-अलग विधि हैं, जैसे समान वितरण (निरंतर), स्तरीकृत प्रतिचयन , महत्व प्रतिचयन , कण निस्यंदक (कण निस्यंदक के रूप में भी जाना जाता है), और माध्य-क्षेत्र कण विधियाँ।

संक्षिप्त विवरण

संख्यात्मक एकीकरण में, समलंबी नियम जैसी विधि एक नियतात्मक एल्गोरिथ्म का उपयोग करते हैं। दूसरी ओर, मोंटे कार्लो एकीकरण, एक प्रसंभाव्य दृष्टिकोण को नियोजित करता है: प्रत्येक प्राप्ति एक अलग परिणाम प्रदान करती है। मोंटे कार्लो में, अंतिम परिणाम संबंधित त्रुटि पट्टियों के साथ उचित मान का अनुमान है, और उचित मान उन त्रुटि पट्टियों के भीतर होने की संभावना है।

समस्या मोंटे कार्लो एकीकरण पतों एक एकाधिक अभिन्न

$I=\int _{\Omega }f({\overline {\mathbf {x} }})\,d{\overline {\mathbf {x} }}$

की गणना है, जहाँ Ω, R^m का एक उपसमुच्चय है, आयतन

$V=\int _{\Omega }d{\overline {\mathbf {x} }}$ है

अनुभवहीन मोंटे कार्लो दृष्टिकोण Ω पर समान रूप से प्रतिदर्श बिंदुओं के लिए है: दिए गए N एकसमान प्रतिदर्श,

${\overline {\mathbf {x} }}_{1},\cdots ,{\overline {\mathbf {x} }}_{N}\in \Omega ,$

I को

$I\approx Q_{N}\equiv V{\frac {1}{N}}\sum _{i=1}^{N}f({\overline {\mathbf {x} }}_{i})=V\langle f\rangle$ द्वारा अनुमानित किया जा सकता है।

ऐसा इसलिए है क्योंकि बड़ी संख्या का नियम यह सुनिश्चित करता है कि

$\lim _{N\to \infty }Q_{N}=I$।

Q_N से I का अनुमान दिया गया है, Q_N की त्रुटि पट्टियों को भिन्नता

$\mathrm {Var} (f)\equiv \sigma _{N}^{2}={\frac {1}{N-1}}\sum _{i=1}^{N}\left(f({\overline {\mathbf {x} }}_{i})-\langle f\rangle \right)^{2}.$

के निष्पक्ष अनुमान का उपयोग करके प्रतिदर्श भिन्नता से अनुमान लगाया जा सकता है। जो

$\mathrm {Var} (Q_{N})={\frac {V^{2}}{N^{2}}}\sum _{i=1}^{N}\mathrm {Var} (f)=V^{2}{\frac {\mathrm {Var} (f)}{N}}=V^{2}{\frac {\sigma _{N}^{2}}{N}}$ की ओर जाता है।

जब तक क्रम

$\left\{\sigma _{1}^{2},\sigma _{2}^{2},\sigma _{3}^{2},\ldots \right\}$

हुआ है, तब तक यह भिन्नता 1/N के रूप में शून्य से कम हो जाती है। Q_N की त्रुटि का अनुमान इस प्रकार

$\delta Q_{N}\approx {\sqrt {\mathrm {Var} (Q_{N})}}=V{\frac {\sigma _{N}}{\sqrt {N}}}$

है, जो ${\tfrac {1}{\sqrt {N}}}$ के रूप में घटता है। यह $V$ से गुणा किए गए माध्य की मानक त्रुटि है। यह परिणाम अभिन्न के आयामों की संख्या पर निर्भर नहीं करता है, जो कि आयाम पर घातीय रूप से निर्भर करने वाले अधिकांश नियतात्मक विधियों के विरुद्ध मोंटे कार्लो एकीकरण का वचन दिया गया लाभ है। यह ध्यान रखना महत्वपूर्ण है कि, नियतात्मक विधियों के विपरीत, त्रुटि का अनुमान जटिल त्रुटि सीमा नहीं है; यादृच्छिक प्रतिचयन एकीकृत की सभी महत्वपूर्ण विशेषताओं को उजागर नहीं कर सकता है जिसके परिणामस्वरूप त्रुटि का अनुमान लगाया जा सकता है।

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

उदाहरण

thumb|right|स्केलिंग दिखाते हुए प्रतिदर्शों की संख्या के एक फलन के रूप में सापेक्ष त्रुटि ${\tfrac {1}{\sqrt {N}}}$|link=|alt={\displaystyle {\tfrac {1}{\sqrt {N}}}}मोंटे कार्लो एकीकरण का एक आदर्श उदाहरण π का ​​अनुमान है। फलन

$H\left(x,y\right)={\begin{cases}1&{\text{if }}x^{2}+y^{2}\leq 1\\0&{\text{else}}\end{cases}}$

और V = 4 के साथ समुच्चय Ω = [−1,1] × [−1,1] पर विचार करें। ध्यान दें कि

$I_{\pi }=\int _{\Omega }H(x,y)dxdy=\pi .$

इस प्रकार, मोंटे कार्लो एकीकरण के साथ π के मान की गणना करने का एक कच्चा तरीका Ω पर एन यादृच्छिक संख्या चुनना और गणना करना है

$Q_{N}=4{\frac {1}{N}}\sum _{i=1}^{N}H(x_{i},y_{i})$

दाईं ओर की आकृति में, सापेक्ष त्रुटि ${\tfrac {Q_{N}-\pi }{\pi }}$ एन के एक फलन के रूप में मापा जाता है, इसकी पुष्टि करता है ${\tfrac {1}{\sqrt {N}}}$।

सी उदाहरण

ध्यान रखें कि एक वास्तविक यादृच्छिक संख्या जेनरेटर का उपयोग किया जाना चाहिए।

int i, throws = 99999, insideCircle = 0;
double randX, randY, pi;

srand(time(NULL));

for (i = 0; i < throws; ++i) {
  randX = rand() / (double) RAND_MAX;
  randY = rand() / (double) RAND_MAX;
  if (randX * randX + randY * randY < 1) ++insideCircle;
}

pi = 4.0 * insideCircle / throws;

पायथन उदाहरण

पायथन (प्रोग्रामिंग भाषा) में निर्मित।

from numpy import random
import numpy as np

throws = 2000
inside_circle = 0
i = 0
radius = 1
while i < throws:
    # Choose random X and Y centered around 0,0
    x = random.uniform(-radius, radius)
    y = random.uniform(-radius, radius)
    # If the point is inside circle, increase variable
    if x**2 + y**2 <= radius**2:
        inside_circle += 1
    i += 1

# Calculate area and print; should be closer to Pi with increasing number of throws
area = (((2 * radius) ** 2) * inside_circle) / throws
print(area)

वोल्फ्राम गणित उदाहरण

नीचे दिया गया कोड फलन को एकीकृत करने की प्रक्रिया का वर्णन करता है

$f(x)={\frac {1}{1+\sinh(2x)\log(x)^{2}}}$

से $0.8<x<3$ गणित में मोंटे-कार्लो पद्धति का उपयोग करना:

func[x_] := 1/(1 + Sinh[2*x]*(Log[x])^2);

(*Sample from truncated normal distribution to speed up convergence*)
Distrib[x_, average_, var_] :=   PDF[NormalDistribution[average, var], 1.1*x - 0.1];
n = 10;
RV = RandomVariate[TruncatedDistribution[{0.8, 3}, NormalDistribution[1, 0.399]], n];
Int = 1/n Total[func[RV]/Distrib[RV, 1, 0.399]]*Integrate[Distrib[x, 1, 0.399], {x, 0.8, 3}]

NIntegrate[func[x], {x, 0.8, 3}] (*Compare with real answer*)

पुनरावर्ती स्तरीकृत प्रतिचयन

See also: Stratified sampling

thumb|right|पुनरावर्ती स्तरीकृत प्रतिचयन का एक उदाहरण। इस उदाहरण में, फलन: $f(x,y)={\begin{cases}1&x^{2}+y^{2}<1\\0&x^{2}+y^{2}\geq 1\end{cases}}$
उपरोक्त उदाहरण से सुझाए गए एल्गोरिथम का उपयोग करके एक इकाई वर्ग के भीतर एकीकृत किया गया था। सैंपल किए गए बिंदुओं को दर्ज किया गया और प्लॉट किया गया। स्पष्ट रूप से स्तरीकृत प्रतिचयन एल्गोरिदम उन क्षेत्रों में बिंदुओं को केंद्रित करता है जहां फलन की भिन्नता सबसे बड़ी है।|link=|alt={\displaystyle f(x,y)={\begin{cases}1&x^{2}+y^{2}<1\\0&x^{2}+y^{2}\geq 1\end{cases}}}पुनरावर्ती स्तरीकृत प्रतिदर्श बहु-आयामी पूर्णांक के लिए एक-आयामी अनुकूली चतुष्कोणों का सामान्यीकरण है। प्रत्येक पुनरावर्ती चरण पर एक सादे मोंटे कार्लो एल्गोरिथम का उपयोग करके अभिन्न और त्रुटि का अनुमान लगाया जाता है। यदि त्रुटि अनुमान आवश्यक सटीकता से बड़ा है तो एकीकरण वॉल्यूम को उप-खंडों में विभाजित किया जाता है और प्रक्रिया को पुनरावर्ती रूप से उप-खंडों पर लागू किया जाता है।

सामान्य 'दो से विभाजित' रणनीति बहु-आयामों के लिए काम नहीं करती है क्योंकि ट्रैक रखने के लिए उप-खंडों की संख्या बहुत तेज़ी से बढ़ती है। इसके बजाय एक अनुमान है कि किस आयाम के साथ एक उपखंड को सबसे अधिक लाभांश लाना चाहिए और मात्र इस आयाम के साथ मात्रा को उपविभाजित करता है।

स्तरीकृत सैंपलिंग एल्गोरिदम उन क्षेत्रों में सैंपलिंग पॉइंट्स को केंद्रित करता है जहां फलन का वेरिएंस सबसे बड़ा होता है, इस प्रकार ग्रैंड वेरिएंस को कम करता है और सैंपलिंग को अधिक प्रभावी बनाता है, जैसा कि चित्रण में दिखाया गया है।

लोकप्रिय MISER रूटीन एक समान एल्गोरिथम लागू करता है।

कंजूस मोंटे कार्लो

MISER एल्गोरिथ्म पुनरावर्ती स्तरीकृत प्रतिदर्श पर आधारित है। इस तकनीक का उद्देश्य उच्चतम विचरण के क्षेत्रों में एकीकरण बिंदुओं को केंद्रित करके समग्र एकीकरण त्रुटि को कम करना है। स्तरीकृत प्रतिचयन का विचार अवलोकन के साथ शुरू होता है कि दो अलग-अलग सेट क्षेत्रों के लिए ए और बी मोंटे कार्लो के अभिन्न अनुमानों के साथ $E_{a}(f)$ और $E_{b}(f)$ और प्रसरण $\sigma _{a}^{2}(f)$ और $\sigma _{b}^{2}(f)$, संयुक्त अनुमान का प्रसरण Var(f)।

$E(f)={\tfrac {1}{2}}\left(E_{a}(f)+E_{b}(f)\right)$

द्वारा दिया गया है,

$\mathrm {Var} (f)={\frac {\sigma _{a}^{2}(f)}{4N_{a}}}+{\frac {\sigma _{b}^{2}(f)}{4N_{b}}}$

यह दिखाया जा सकता है कि इस भिन्नता को बिंदुओं को वितरित करके कम किया जाता है,

${\frac {N_{a}}{N_{a}+N_{b}}}={\frac {\sigma _{a}}{\sigma _{a}+\sigma _{b}}}$

इसलिए प्रत्येक उप-क्षेत्र में फलन के मानक विचलन के अनुपात में प्रतिदर्श बिंदु आवंटित करके सबसे छोटी त्रुटि अनुमान प्राप्त किया जाता है।

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

महत्व प्रतिचयन

Main article: Importance sampling

विभिन्न प्रकार के महत्वपूर्ण सैंपलिंग एल्गोरिदम हैं, जैसे

महत्व प्रतिदर्श एल्गोरिथ्म

महत्व प्रतिचयन मोंटे-कार्लो एकीकरण करने के लिए एक बहुत ही महत्वपूर्ण उपकरण प्रदान करता है। इस पद्धति के महत्व के प्रतिदर्श का मुख्य परिणाम यह है कि एकसमान प्रतिचयन ${\overline {\mathbf {x} }}$ अधिक सामान्य पसंद का एक विशेष मामला है, जिस पर किसी भी वितरण से प्रतिदर्श लिए जाते हैं $p({\overline {\mathbf {x} }})$। विचार यह है $p({\overline {\mathbf {x} }})$ माप Q के विचरण को कम करने के लिए चुना जा सकता है_N।

निम्नलिखित उदाहरण पर विचार करें जहां कोई 0 पर केंद्रित एक गॉसियन फलन को संख्यात्मक रूप से एकीकृत करना चाहता है, σ = 1 के साथ -1000 से 1000 तक। स्वाभाविक रूप से, यदि प्रतिदर्श अंतराल [-1000, 1000] पर समान रूप से खींचे जाते हैं, तो मात्र एक उनमें से बहुत छोटा भाग अभिन्न के लिए महत्वपूर्ण होगा। जहां से प्रतिदर्श चुने गए हैं वहां से एक अलग वितरण चुनकर इसे बेहतर बनाया जा सकता है, उदाहरण के लिए σ = 1 के साथ 0 पर केंद्रित गाऊसी वितरण के अनुसार प्रतिचयन करके। निश्चित रूप से उचित विकल्प एकीकृत पर दृढ़ता से निर्भर करता है।

औपचारिक रूप से, वितरण से चुने गए प्रतिदर्शों का एक सेट दिया जाता है

$p({\overline {\mathbf {x} }}):\qquad {\overline {\mathbf {x} }}_{1},\cdots ,{\overline {\mathbf {x} }}_{N}\in V,$

I के लिए अनुमानक द्वारा दिया गया है

$Q_{N}\equiv {\frac {1}{N}}\sum _{i=1}^{N}{\frac {f({\overline {\mathbf {x} }}_{i})}{p({\overline {\mathbf {x} }}_{i})}}$

सहज रूप से, यह कहता है कि यदि हम किसी विशेष प्रतिदर्श को अन्य प्रतिदर्शों की तुलना में दोगुना चुनते हैं, तो हम इसे अन्य प्रतिदर्शों की तुलना में आधा वजन देते हैं। यह अनुमानक समान प्रतिचयन के लिए स्वाभाविक रूप से मान्य है, जहां मामला है $p({\overline {\mathbf {x} }})$ स्थिर है।

मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम उत्पन्न करने के लिए सबसे अधिक उपयोग किए जाने वाले एल्गोरिदम में से एक है ${\overline {\mathbf {x} }}$ से $p({\overline {\mathbf {x} }})$,इस प्रकार पूर्णांक कंप्यूटिंग का एक कुशल तरीका प्रदान करता है।

वेगास मोंटे कार्लो

Main article: VEGAS algorithm

VEGAS एल्गोरिथ्म एकीकरण क्षेत्र पर कई पास बनाकर सटीक वितरण का अनुमान लगाता है जो फलन f का हिस्टोग्राम बनाता है। प्रत्येक हिस्टोग्राम का उपयोग अगले पास के लिए प्रतिचयन वितरण को परिभाषित करने के लिए किया जाता है। असम्बद्ध रूप से यह प्रक्रिया वांछित वितरण में परिवर्तित हो जाती है। K की तरह बढ़ने वाले हिस्टोग्राम डिब्बे की संख्या से बचने के लिए^d, प्रायिकता बंटन एक वियोज्य फलन द्वारा अनुमानित है:

$g(x_{1},x_{2},\ldots )=g_{1}(x_{1})g_{2}(x_{2})\ldots$

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

यह भी देखें

• क्वासी-मोंटे कार्लो विधि
• सहायक क्षेत्र मोंटे कार्लो
• सांख्यिकीय भौतिकी में मोंटे कार्लो विधि
• मोंटे कार्लो विधि
• भिन्नता में कमी

संदर्भ

• Caflisch, R. E. (1998). "Monte Carlo and quasi-Monte Carlo methods". Acta Numerica. 7: 1–49. Bibcode:1998AcNum...7....1C. doi:10.1017/S0962492900002804. S2CID 5708790.
• Weinzierl, S. (2000). "Introduction to Monte Carlo methods". arXiv:hep-ph/0006269.
• Press, W. H.; Farrar, G. R. (1990). "Recursive Stratified Sampling for Multidimensional Monte Carlo Integration". Computers in Physics. 4 (2): 190. Bibcode:1990ComPh...4..190P. doi:10.1063/1.4822899.
• Lepage, G. P. (1978). "A New Algorithm for Adaptive Multidimensional Integration". Journal of Computational Physics. 27 (2): 192–203. Bibcode:1978JCoPh..27..192L. doi:10.1016/0021-9991(78)90004-9.
• Lepage, G. P. (1980). "VEGAS: An Adaptive Multi-dimensional Integration Program". Cornell Preprint CLNS 80-447.
• Hammersley, J. M.; Handscomb, D. C. (1964). Monte Carlo Methods. Methuen. ISBN 978-0-416-52340-9.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.
• Newman, MEJ; Barkema, GT (1999). Monte Carlo Methods in Statistical Physics. Clarendon Press.
• Robert, CP; Casella, G (2004). Monte Carlo Statistical Methods (2nd ed.). Springer. ISBN 978-1-4419-1939-7.

बाहरी संबंध

• Café math : Monte Carlo Integration : A blog article describing Monte Carlo integration (principle, hypothesis, confidence interval)
• Boost.Math : Naive Monte Carlo integration: Documentation for the C++ naive Monte-Carlo routines
• Monte Carlo applet applied in statistical physics problems