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

मोंटे कार्लो एकीकरण का एक उदाहरण। इस उदाहरण में, प्रांत D आंतरिक वृत्त है और प्रांत E वर्ग है। क्योंकि वर्ग के क्षेत्रफल(4) की गणना सरलता से की जा सकती है, वृत्त का क्षेत्रफल(π*1.0²) का अनुमान वृत्त के भीतर बिंदुओं के अनुपात(0.8) (40) से अंकों की कुल संख्या(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$ से गुणा किए गए माध्य की मानक त्रुटि है। यह परिणाम अभिन्न के आयामों की संख्या पर निर्भर नहीं करता है, जो कि आयाम पर घातीय रूप से निर्भर करने वाले अधिकांश नियतात्मक विधियों के विरुद्ध मोंटे कार्लो एकीकरण का वचन दिया गया लाभ है। यह ध्यान रखना महत्वपूर्ण है कि, नियतात्मक विधियों के विपरीत, त्रुटि का अनुमान जटिल त्रुटि सीमा नहीं है; यादृच्छिक प्रतिचयन एकीकृत की सभी महत्वपूर्ण विशेषताओं को उजागर नहीं कर सकता है जिसके परिणामस्वरूप त्रुटि का अनुमान लगाया जा सकता है।

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

उदाहरण

File:Relative error of a Monte Carlo integration to calculate pi.svg

Relative error as a function of the number of samples, showing the scaling ${\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 .$

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

$Q_{N}=4{\frac {1}{N}}\sum _{i=1}^{N}H(x_{i},y_{i})$ की गणना करना है।

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

C उदाहरण

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

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

File:Strata.png

An illustration of Recursive Stratified Sampling. In this example, the function: $f(x,y)={\begin{cases}1&x^{2}+y^{2}<1\\0&x^{2}+y^{2}\geq 1\end{cases}}$
from the above illustration was integrated within a unit square using the suggested algorithm. The sampled points were recorded and plotted. Clearly stratified sampling algorithm concentrates the points in the regions where the variation of the function is largest.

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

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

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

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

मिसेर मोंटे कार्लो

मिसेर एल्गोरिदम पुनरावर्ती स्तरीकृत प्रतिदर्श पर आधारित है। इस तकनीक का उद्देश्य उच्चतम विचरण के क्षेत्रों में एकीकरण बिंदुओं को केंद्रित करके समग्र एकीकरण त्रुटि को कम करना है।

स्तरीकृत प्रतिचयन का विचार अवलोकन के साथ प्रारम्भ होता है कि दो असंयुक्त समुच्चय क्षेत्रों के लिए a और b मोंटे कार्लो के साथ $E_{a}(f)$ और $E_{b}(f)$ और प्रसरण $\sigma _{a}^{2}(f)$ और $\sigma _{b}^{2}(f)$ का अनुमान है, संयुक्त अनुमान

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

का भिन्नता Var(f),

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

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

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

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

Main article: महत्व प्रतिचयन

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

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

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

निम्नलिखित उदाहरण पर विचार करें जहां कोई गॉसियन फलन को संख्यात्मक रूप से एकीकृत करना चाहते है, जो 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: वेगास एल्गोरिदम

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

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

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

यह भी देखें

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

संदर्भ

• 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