+\overlays{9}{
+\begin{slide}{monte carlo methods}
+ \begin{itemstep}
+ \item algorithms for solving computational problems using random numbers
+ \item deterministic pseudo-random sequences
+ \item applications:
+ \begin{itemize}
+ \item monte carlo integration
+ \item metropolis algorithm
+ \item simulated annealing
+ \end{itemize}
+ \item advantages:
+ \begin{itemize}
+ \item more efficient than other methods
+ \item no need fo simplifying assumptions
+ \end{itemize}
+ \end{itemstep}
+\end{slide}}
+
+\overlays{5}{
+\begin{slide}{random number generator}
+linear congruential generator:
+ \begin{itemstep}
+ \item $I_{j+1} = ( a I_{j} + c ) \, mod \, m$ \\
+ $a$: multiplier, $c$: increment \\
+ $m$: modulus, $I_0$: seed
+ \item minimal standard by park and miller: \\
+ $a = 7^5 = 16807, \quad m = 2^{31} - 1 = 2147483647, \quad c = 0$
+ \item always seed the rng
+ \end{itemstep}
+\FromSlide{4}{
+$\Rightarrow$ sequence of integers $\in [0,m[$ \\
+}
+\vspace{2pt}
+\FromSlide{5}{
+division by modulus $\Rightarrow$ uniform deviates : \\
+\[
+ p(x)dx = \left\{
+ \begin{array}{ll}
+ dx & 0 \leq x < 1 \\
+ 0 & \textrm{sonst}
+ \end{array} \right.
+\]
+}
+\end{slide}}
+
+\overlays{8}{
+\begin{slide}{special deviates}
+ \begin{itemstep}
+ \item transformation method:
+ \begin{itemize}
+ \item arbitrary probability distribution $\rho(y)$
+ \item trafo: $p(x) dx = \rho(y) dy \Rightarrow x = \int_{- \infty}^y \rho(y) dy$
+ \item get inverse of $x(y) \Rightarrow y(x)$
+ \end{itemize}
+ \item rejection method: \\
+ \begin{minipage}{5cm}
+ \begin{itemize}
+ \item $p(x) \in [a,b]$ mit $p(x) \geq 0 \quad \forall x \in [a,b]$
+ \item uniformly distributed $x \in [a,b]$ und $y \in [0,p_m]$
+ \item if $y \leq p(x)$ use $x$, else reject $x$
+ \end{itemize}
+ \end{minipage}
+ \begin{minipage}{5cm}
+ \includegraphics[width=5cm]{rej_meth.eps} \\
+ \end{minipage}
+ \end{itemstep}
+\end{slide}}
+
+\overlays{5}{
+\begin{slide}{monte carlo integration}
+ basics:
+ \begin{itemstep}
+ \item $I = \int_{\Omega} f d \Omega$
+ \item instead of regular $x_i$, choose them at random
+ \item $I \approx \Omega <f> \pm \Omega \sqrt{\frac{<f^2> - <f>^2}{N}}$ \\
+ $<f> = \frac{1}{N} \sum_{i=1}^{N} f(\vec{x_i})$ \\[6pt]
+ $<f^2> = \frac{1}{N} \sum_{i=1}^{N} f^2(\vec{x_i})$
+ \end{itemstep}
+\FromSlide{4}{
+ example: gambling for $\pi$ \\
+}
+\FromSlide{5}{
+ \[
+ \begin{array}{l}
+ \pi = \int_{-1}^1 \int_{-1}^1 p(x,y) dx dy \approx \frac{4}{N} \sum_{i=1}^N p(x_i,y_i) \\[6pt]
+ \textrm{with } p(x,y) = \left\{
+ \begin{array}{ll}
+ 1 & x^2 + y^2 \leq 1 \\
+ 0 & \textrm{sonst}
+ \end{array} \right.
+ \end{array}
+ \]
+}
+\end{slide}}
+
+\overlays{5}{
+\begin{slide}{metropolis algorithm}
+ising model:
+ \begin{itemstep}
+ \item $d$-dimensional periodic lattice
+ \item two possible states for magnetic moment at site $i$: \\
+ $\mu_i = \mu S_i \qquad S_i = \pm 1 \quad \forall i$
+ \item nearest neighbors moments interact, \\
+ interaction strength $\frac{J_{ij}}{\mu^2}$
+ \end{itemstep}
+\FromSlide{4}{
+$\Rightarrow$ hamiltonian: $H = - \sum_{(i,j)} J_{ij} S_i S_j$ \\
+}
+\FromSlide{5}{
+partition function: \\
+\[
+Z = \sum_{i=1}^N e^{\frac{-E_i}{k_B T}} = Tr(e^{-\beta H})
+\]
+}
+\end{slide}}
+
+\overlays{2}{
+\begin{slide}{metropolis algorithm}
+ \begin{itemstep}
+ \item importance sampling: \\
+ $<A> = \sum_i p_i A_i \approx \frac{1}{N} \sum_{i=1}^N A_i$ , with \\[6pt]
+ $\qquad p_i = \frac{e^{- \beta E_i}}{Z}$
+ \item detailed balance \\[6pt]
+ sufficient condition for equilibrium: \\
+ \[
+ W(A \rightarrow B) p(A) = W(B \rightarrow A) p(B)
+ \]
+ $\Rightarrow \frac{W(A \rightarrow B)}{W(B \rightarrow A)} = \frac{p(B)}{p(A)} = e^{\frac{- \Delta E}{k_B T}}$ \\[6pt]
+ with $\Delta E = E(B) - E(A)$
+ \end{itemstep}
+\end{slide}}
+
+\overlays{5}{
+\begin{slide}{metropolis algorithm}
+ \begin{itemstep}
+ \item choose $W$: \\
+ \[
+ W(A \rightarrow B) = \left\{
+ \begin{array}{ll}
+ e^{- \beta \Delta E} & : \Delta E > 0 \\
+ 1 & : \Delta E < 0
+ \end{array} \right.
+ \]
+ \item algorithm:
+ \begin{itemize}
+ \item visit every lattice site
+ \item calculate $\Delta E$ for spin flip
+ \item flip spin if $r \leq e^{\frac{-\Delta E}{k_B T}}$
+ \end{itemize}
+ \end{itemstep}
+\end{slide}}
+
+\begin{slide}{summary}
+ \begin{itemize}
+ \item importance of computational physics
+ \item things to keep in mind when doing computational physics
+ \item euler's method for solving o.d.e.
+ \item introduction to monte carlo methods
+ \end{itemize}