[901] | 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> |
---|