\chapter[Monte Carlo Methods]
{Monte Carlo Methods}    \label{secmessel}

The Geant4 toolkit uses a combination of the composition and
rejection Monte Carlo methods.  Only the basic formalism of these methods is 
outlined here.  For a complete account of the Monte Carlo methods, the 
interested user is referred to the publications of Butcher and Messel, 
Messel and Crawford, or Ford and Nelson \cite{m.butch,m.messel,m.egs4}.

\noindent
Suppose we wish to sample $x$ in the interval $[x_1,\ x_2]$ from the 
distribution $f(x)$ and the {\it normalised} probability density function can 
be written as :
\begin{equation}
f(x)  = \sum_{i=1}^{n} N_{i} f_{i} (x) g_{i} (x)
\end{equation}
where $N_i>0$, $f_i(x)$ are {\it normalised} density functions on $[x_1,\ x_2]$ 
, and $0 \leq g_i (x) \leq 1$.

\noindent
According to this method, $x$ can sampled in the following way:
\begin{enumerate}
\item
select a random integer $i \in \{1,2,\cdots n\}$
with probability proportional to $N_i $
\item
select a value $x_0$ from the distribution $f_i (x)$
\item
calculate $g_i (x_0)$ and accept $x = x_0$ with probability $g_i (x_0)$;
\item if $x_0$ is rejected restart from step 1.
\end{enumerate}
It can be shown that this scheme is correct and the mean
number of tries to accept a value is $ \sum_{i} N_i $.

\noindent
In practice, a good method of sampling from the distribution $f(x)$ has the 
following properties:
\begin{itemize}
\item all the subdistributions $ f_i (x)$ can be sampled easily;
\item the rejection functions $ g_i(x)$ can be evaluated easily/quickly;
\item the mean number of tries is not too large.
\end{itemize}
Thus the different possible decompositions of the distribution
$f(x)$ are not equivalent from the practical point of view (e.g. they
can be very different in computational speed) and it can be useful
to optimise the decomposition.

\noindent
A remark of practical importance : if our distribution is not
normalised 
$$\int_{x_1}^{x_2} f(x)dx = C > 0$$ 
the method can be used in the same
manner; the mean number of tries in this
case is $\sum_ {i} N_i/C$.

\section{Status of this document}
18.01.02 created by M.Maire. \\

\begin{latexonly}
  
\begin{thebibliography}{99}
\bibitem{m.butch} J.C. Butcher and H. Messel.
  {\em Nucl. Phys. 20} 15 (1960)   
\bibitem{m.messel} H. Messel and D. Crawford.
  {\em Electron-Photon shower distribution, Pergamon Press} (1970)
\bibitem{m.egs4} R. Ford and W. Nelson.
  {\em SLAC-265, UC-32} (1985)
\bibitem{m.pdg}
  Particle Data Group. Rev. of Particle Properties.
  {\em Eur. Phys. J. C15. (2000) 1.} http://pdg.lbl.gov         
\end{thebibliography}

\end{latexonly}

\begin{htmlonly}

\section{Bibliography}

\begin{enumerate}
\item J.C. Butcher and H. Messel {\em Nucl. Phys. 20} 15 (1960).   
\item H. Messel and D. Crawford {\em Electron-Photon shower distribution, Pergamon Press} (1970).
\item R. Ford and W. Nelson {\em SLAC-265, UC-32} (1985).
\item Particle Data Group. Rev. of Particle Properties {\em Eur. Phys. J. C15. (2000) 1.} http://pdg.lbl.gov .         
\end{enumerate}

\end{htmlonly}