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

मोंटे कार्लो एकीकरण का एक उदाहरण। इस उदाहरण में, डोमेन डी आंतरिक चक्र है और डोमेन ई वर्ग है। क्योंकि वर्ग के क्षेत्रफल (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} }}$

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

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

मुझे अंदाज़ा लगाया जा सकता है

$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 से I का अनुमान दिया गया है_N, 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इस प्रकार है

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

स्केलिंग दिखाते हुए नमूनों की संख्या के एक समारोह के रूप में सापेक्ष त्रुटि ${\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}}$

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

$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

File:Strata.png

पुनरावर्ती स्तरीकृत नमूनाकरण का एक उदाहरण। इस उदाहरण में, समारोह: $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