1 | <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN"> |
---|
2 | |
---|
3 | <!--Converted with LaTeX2HTML 2002-2-1 (1.70) |
---|
4 | original version by: Nikos Drakos, CBLU, University of Leeds |
---|
5 | * revised and updated by: Marcus Hennecke, Ross Moore, Herb Swan |
---|
6 | * with significant contributions from: |
---|
7 | Jens Lippmann, Marek Rouchal, Martin Wilck and others --> |
---|
8 | <HTML> |
---|
9 | <HEAD> |
---|
10 | <TITLE>Monte Carlo Methods</TITLE> |
---|
11 | <META NAME="description" CONTENT="Monte Carlo Methods"> |
---|
12 | <META NAME="keywords" CONTENT="PhysicsReferenceManual"> |
---|
13 | <META NAME="resource-type" CONTENT="document"> |
---|
14 | <META NAME="distribution" CONTENT="global"> |
---|
15 | |
---|
16 | <META NAME="Generator" CONTENT="LaTeX2HTML v2002-2-1"> |
---|
17 | <META HTTP-EQUIV="Content-Style-Type" CONTENT="text/css"> |
---|
18 | |
---|
19 | <LINK REL="STYLESHEET" HREF="PhysicsReferenceManual.css"> |
---|
20 | |
---|
21 | <LINK REL="next" HREF="node10.html"> |
---|
22 | <LINK REL="previous" HREF="node3.html"> |
---|
23 | <LINK REL="up" HREF="node2.html"> |
---|
24 | <LINK REL="next" HREF="node8.html"> |
---|
25 | </HEAD> |
---|
26 | |
---|
27 | <BODY > |
---|
28 | <!--Navigation Panel--> |
---|
29 | <A NAME="tex2html811" |
---|
30 | HREF="node8.html"> |
---|
31 | <IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next" SRC="next.gif"></A> |
---|
32 | <A NAME="tex2html807" |
---|
33 | HREF="node2.html"> |
---|
34 | <IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up" SRC="up.gif"></A> |
---|
35 | <A NAME="tex2html801" |
---|
36 | HREF="node6.html"> |
---|
37 | <IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous" SRC="prev.gif"></A> |
---|
38 | <A NAME="tex2html809" |
---|
39 | HREF="node1.html"> |
---|
40 | <IMG WIDTH="65" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="contents" SRC="contents.gif"></A> |
---|
41 | <BR> |
---|
42 | <B> Next:</B> <A NAME="tex2html812" |
---|
43 | HREF="node8.html">Status of this document</A> |
---|
44 | <B> Up:</B> <A NAME="tex2html808" |
---|
45 | HREF="node2.html">Introduction</A> |
---|
46 | <B> Previous:</B> <A NAME="tex2html802" |
---|
47 | HREF="node6.html">Status of this document</A> |
---|
48 | <B> <A NAME="tex2html810" |
---|
49 | HREF="node1.html">Contents</A></B> |
---|
50 | <BR> |
---|
51 | <BR> |
---|
52 | <!--End of Navigation Panel--> |
---|
53 | |
---|
54 | <H1><A NAME="SECTION02200000000000000000"></A> <A NAME="secmessel"></A> |
---|
55 | <BR> |
---|
56 | Monte Carlo Methods |
---|
57 | </H1> |
---|
58 | |
---|
59 | <P> |
---|
60 | The Geant4 toolkit uses a combination of the composition and |
---|
61 | rejection Monte Carlo methods. Only the basic formalism of these methods is |
---|
62 | outlined here. For a complete account of the Monte Carlo methods, the |
---|
63 | interested user is referred to the publications of Butcher and Messel, |
---|
64 | Messel and Crawford, or Ford and Nelson [#!m.butch!#,#!m.messel!#,#!m.egs4!#]. |
---|
65 | |
---|
66 | <P> |
---|
67 | Suppose we wish to sample <IMG |
---|
68 | WIDTH="16" HEIGHT="19" ALIGN="BOTTOM" BORDER="0" |
---|
69 | SRC="img1.gif" |
---|
70 | ALT="$ x$"> in the interval <!-- MATH |
---|
71 | $[x_1,\ x_2]$ |
---|
72 | --> |
---|
73 | <IMG |
---|
74 | WIDTH="66" HEIGHT="37" ALIGN="MIDDLE" BORDER="0" |
---|
75 | SRC="img113.gif" |
---|
76 | ALT="$ [x_1, x_2]$"> from the |
---|
77 | distribution <IMG |
---|
78 | WIDTH="41" HEIGHT="37" ALIGN="MIDDLE" BORDER="0" |
---|
79 | SRC="img114.gif" |
---|
80 | ALT="$ f(x)$"> and the <I>normalised</I> probability density function can |
---|
81 | be written as : |
---|
82 | <P></P> |
---|
83 | <DIV ALIGN="CENTER"><!-- MATH |
---|
84 | \begin{equation} |
---|
85 | f(x) = \sum_{i=1}^{n} N_{i} f_{i} (x) g_{i} (x) |
---|
86 | \end{equation} |
---|
87 | --> |
---|
88 | <TABLE CELLPADDING="0" WIDTH="100%" ALIGN="CENTER"> |
---|
89 | <TR VALIGN="MIDDLE"> |
---|
90 | <TD NOWRAP ALIGN="CENTER"><IMG |
---|
91 | WIDTH="197" HEIGHT="71" ALIGN="MIDDLE" BORDER="0" |
---|
92 | SRC="img115.gif" |
---|
93 | ALT="$\displaystyle f(x) = \sum_{i=1}^{n} N_{i} f_{i} (x) g_{i} (x)$"></TD> |
---|
94 | <TD NOWRAP WIDTH="10" ALIGN="RIGHT"> |
---|
95 | (2.1)</TD></TR> |
---|
96 | </TABLE></DIV> |
---|
97 | <BR CLEAR="ALL"><P></P> |
---|
98 | where <IMG |
---|
99 | WIDTH="60" HEIGHT="35" ALIGN="MIDDLE" BORDER="0" |
---|
100 | SRC="img116.gif" |
---|
101 | ALT="$ N_i>0$">, <IMG |
---|
102 | WIDTH="45" HEIGHT="37" ALIGN="MIDDLE" BORDER="0" |
---|
103 | SRC="img117.gif" |
---|
104 | ALT="$ f_i(x)$"> are <I>normalised</I> density functions on <!-- MATH |
---|
105 | $[x_1,\ x_2]$ |
---|
106 | --> |
---|
107 | <IMG |
---|
108 | WIDTH="66" HEIGHT="37" ALIGN="MIDDLE" BORDER="0" |
---|
109 | SRC="img113.gif" |
---|
110 | ALT="$ [x_1, x_2]$"> |
---|
111 | , and <!-- MATH |
---|
112 | $0 \leq g_i (x) \leq 1$ |
---|
113 | --> |
---|
114 | <IMG |
---|
115 | WIDTH="114" HEIGHT="37" ALIGN="MIDDLE" BORDER="0" |
---|
116 | SRC="img118.gif" |
---|
117 | ALT="$ 0 \leq g_i (x) \leq 1$">. |
---|
118 | |
---|
119 | <P> |
---|
120 | According to this method, <IMG |
---|
121 | WIDTH="16" HEIGHT="19" ALIGN="BOTTOM" BORDER="0" |
---|
122 | SRC="img1.gif" |
---|
123 | ALT="$ x$"> can sampled in the following way: |
---|
124 | |
---|
125 | <OL> |
---|
126 | <LI>select a random integer <!-- MATH |
---|
127 | $i \in \{1,2,\cdots n\}$ |
---|
128 | --> |
---|
129 | <IMG |
---|
130 | WIDTH="126" HEIGHT="37" ALIGN="MIDDLE" BORDER="0" |
---|
131 | SRC="img119.gif" |
---|
132 | ALT="$ i \in \{1,2,\cdots n\}$"> |
---|
133 | with probability proportional to <IMG |
---|
134 | WIDTH="25" HEIGHT="35" ALIGN="MIDDLE" BORDER="0" |
---|
135 | SRC="img120.gif" |
---|
136 | ALT="$ N_i $"> |
---|
137 | </LI> |
---|
138 | <LI>select a value <IMG |
---|
139 | WIDTH="23" HEIGHT="33" ALIGN="MIDDLE" BORDER="0" |
---|
140 | SRC="img121.gif" |
---|
141 | ALT="$ x_0$"> from the distribution <IMG |
---|
142 | WIDTH="45" HEIGHT="37" ALIGN="MIDDLE" BORDER="0" |
---|
143 | SRC="img117.gif" |
---|
144 | ALT="$ f_i(x)$"> |
---|
145 | </LI> |
---|
146 | <LI>calculate <IMG |
---|
147 | WIDTH="52" HEIGHT="37" ALIGN="MIDDLE" BORDER="0" |
---|
148 | SRC="img122.gif" |
---|
149 | ALT="$ g_i (x_0)$"> and accept <IMG |
---|
150 | WIDTH="59" HEIGHT="33" ALIGN="MIDDLE" BORDER="0" |
---|
151 | SRC="img123.gif" |
---|
152 | ALT="$ x = x_0$"> with probability <IMG |
---|
153 | WIDTH="52" HEIGHT="37" ALIGN="MIDDLE" BORDER="0" |
---|
154 | SRC="img122.gif" |
---|
155 | ALT="$ g_i (x_0)$">; |
---|
156 | </LI> |
---|
157 | <LI>if <IMG |
---|
158 | WIDTH="23" HEIGHT="33" ALIGN="MIDDLE" BORDER="0" |
---|
159 | SRC="img121.gif" |
---|
160 | ALT="$ x_0$"> is rejected restart from step 1. |
---|
161 | </LI> |
---|
162 | </OL> |
---|
163 | It can be shown that this scheme is correct and the mean |
---|
164 | number of tries to accept a value is <!-- MATH |
---|
165 | $\sum_{i} N_i$ |
---|
166 | --> |
---|
167 | <IMG |
---|
168 | WIDTH="54" HEIGHT="37" ALIGN="MIDDLE" BORDER="0" |
---|
169 | SRC="img124.gif" |
---|
170 | ALT="$ \sum_{i} N_i $">. |
---|
171 | |
---|
172 | <P> |
---|
173 | In practice, a good method of sampling from the distribution <IMG |
---|
174 | WIDTH="41" HEIGHT="37" ALIGN="MIDDLE" BORDER="0" |
---|
175 | SRC="img114.gif" |
---|
176 | ALT="$ f(x)$"> has the |
---|
177 | following properties: |
---|
178 | |
---|
179 | <UL> |
---|
180 | <LI>all the subdistributions <IMG |
---|
181 | WIDTH="45" HEIGHT="37" ALIGN="MIDDLE" BORDER="0" |
---|
182 | SRC="img117.gif" |
---|
183 | ALT="$ f_i(x)$"> can be sampled easily; |
---|
184 | </LI> |
---|
185 | <LI>the rejection functions <IMG |
---|
186 | WIDTH="44" HEIGHT="37" ALIGN="MIDDLE" BORDER="0" |
---|
187 | SRC="img125.gif" |
---|
188 | ALT="$ g_i(x)$"> can be evaluated easily/quickly; |
---|
189 | </LI> |
---|
190 | <LI>the mean number of tries is not too large. |
---|
191 | </LI> |
---|
192 | </UL> |
---|
193 | Thus the different possible decompositions of the distribution |
---|
194 | <IMG |
---|
195 | WIDTH="41" HEIGHT="37" ALIGN="MIDDLE" BORDER="0" |
---|
196 | SRC="img114.gif" |
---|
197 | ALT="$ f(x)$"> are not equivalent from the practical point of view (e.g. they |
---|
198 | can be very different in computational speed) and it can be useful |
---|
199 | to optimise the decomposition. |
---|
200 | |
---|
201 | <P> |
---|
202 | A remark of practical importance : if our distribution is not |
---|
203 | normalised |
---|
204 | <!-- MATH |
---|
205 | \begin{displaymath} |
---|
206 | \int_{x_1}^{x_2} f(x)dx = C > 0 |
---|
207 | \end{displaymath} |
---|
208 | --> |
---|
209 | <P></P> |
---|
210 | <DIV ALIGN="CENTER"> |
---|
211 | <IMG |
---|
212 | WIDTH="173" HEIGHT="63" ALIGN="MIDDLE" BORDER="0" |
---|
213 | SRC="img126.gif" |
---|
214 | ALT="$\displaystyle \int_{x_1}^{x_2} f(x)dx = C > 0$"> |
---|
215 | </DIV><P></P> |
---|
216 | the method can be used in the same |
---|
217 | manner; the mean number of tries in this |
---|
218 | case is <!-- MATH |
---|
219 | $\sum_ {i} N_i/C$ |
---|
220 | --> |
---|
221 | <IMG |
---|
222 | WIDTH="78" HEIGHT="37" ALIGN="MIDDLE" BORDER="0" |
---|
223 | SRC="img127.gif" |
---|
224 | ALT="$ \sum_ {i} N_i/C$">. |
---|
225 | |
---|
226 | <P> |
---|
227 | <BR><HR> |
---|
228 | <!--Table of Child-Links--> |
---|
229 | <A NAME="CHILD_LINKS"><STRONG>Subsections</STRONG></A> |
---|
230 | |
---|
231 | <UL> |
---|
232 | <LI><A NAME="tex2html813" |
---|
233 | HREF="node8.html">Status of this document</A> |
---|
234 | <LI><A NAME="tex2html814" |
---|
235 | HREF="node9.html">Bibliography</A> |
---|
236 | </UL> |
---|
237 | <!--End of Table of Child-Links--> |
---|
238 | <HR> |
---|
239 | <!--Navigation Panel--> |
---|
240 | <A NAME="tex2html811" |
---|
241 | HREF="node8.html"> |
---|
242 | <IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next" SRC="next.gif"></A> |
---|
243 | <A NAME="tex2html807" |
---|
244 | HREF="node2.html"> |
---|
245 | <IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up" SRC="up.gif"></A> |
---|
246 | <A NAME="tex2html801" |
---|
247 | HREF="node6.html"> |
---|
248 | <IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous" SRC="prev.gif"></A> |
---|
249 | <A NAME="tex2html809" |
---|
250 | HREF="node1.html"> |
---|
251 | <IMG WIDTH="65" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="contents" SRC="contents.gif"></A> |
---|
252 | <BR> |
---|
253 | <B> Next:</B> <A NAME="tex2html812" |
---|
254 | HREF="node8.html">Status of this document</A> |
---|
255 | <B> Up:</B> <A NAME="tex2html808" |
---|
256 | HREF="node2.html">Introduction</A> |
---|
257 | <B> Previous:</B> <A NAME="tex2html802" |
---|
258 | HREF="node6.html">Status of this document</A> |
---|
259 | <B> <A NAME="tex2html810" |
---|
260 | HREF="node1.html">Contents</A></B> |
---|
261 | <!--End of Navigation Panel--> |
---|
262 | |
---|
263 | </BODY> |
---|
264 | </HTML> |
---|