Simple Applications; Monte-Carlo Estimators

First we recall two simple problems that can be solved by means of Monte-Carlo simulation and have already been discussed in the course ,,Wahrscheinlichkeitsrechnung''.

1. Algorithm to determine the number $\pi$ 
   • A simple computer algorithm for the Monte-Carlo simulation of $\pi$ is the following improved version of Buffon's needle experiment; see Sections 2.5 and 5.2.3 of the course ,,Wahrscheinlichkeitsrechnung''.

   • This algorithm is based on the following geometrical facts.

     • We consider the square
       $$B=(-1,1]\times(-1,1]\subset\mathbb{R}^2\,,$$

     • the circle $C$ inscribed into $B$, where
       $$C=\{(x,y):\, (x,y)\in B,\, x^2+y^2<1\}\,,$$

     • and arbitrarily toss a point into the set $B$.
   • Translated into the language of stochastics this means:
     • We consider two independent random variables $S$ and $T$ that are uniformly distributed on the interval $(-1,1]$ and
     • determine the probability of the event
       $$A=\{(S,T)\in C\}=\{S^2+T^2<1\}\,,$$
       i.e. that the ,,random point'' $(S,T)$ is in $C\subset B$.

     • Then
       $$P(A)=P(S^2+T^2<1)=\frac{\vert C\vert}{\vert B\vert}=\frac{\pi}{4}\;,$$
       where $\vert B\vert$ and $\vert C\vert$ denote the area of $B$ and $C$, respectively.
   • Similarly to Buffon's needle experiment the equation $P(A)=\pi/4$ yields a
     • method for the statistical estimation of $\pi$,
     • which is based on the strong law of large numbers (SLLN) and can be easily implemented.
   • Let $(S_1,T_1),\ldots,(S_n,T_n)$ be independent and identically distributed random vectors,
     • whose distribution coincides with the one of $(S,T)$
     • and which are regarded as a stochastic model for $n$ (independent) experiments.
     • Then $X_1,X_2,\ldots,X_n$ where
       $$X_i=\left\{\begin{array}{cc} 1 &\mbox{if $S_i^2+T_i^2<1$,}\\ 0 & \mbox{else} \end{array}\right.$$
       are independent and identically distributed random variables with expectation ${\mathbb{E}\,}X_i=\pi/4$.
   • Furthermore, the SLLN (see Theorem WR-5.15) implies
     • that the arithmetic mean
       $$Y_n=n^{-1}\sum\limits_{i=1}^n X_i$$
       converges to $\pi/4$ almost surely.
     • Thus, $Y_n$ is an unbiased and (strongly) consistent estimator for $\pi/4$,
     • i.e., the probability of $4Y_n$ to be a good approximation for $\pi$ is very high if $n$ is large.

     
     

   • For the implementation of this simulation algorithm one can proceed as follows
     • Use a random number generator to generate $2n$ pseudo-random numbers $u_1,\ldots,u_{2n}$ that are realizations of random variables being uniformly distributed on $(0,1]$.

     • Put $s_i=2u_i-1$ and $t_i=2u_{n+i}-1$ for $i=1,\ldots,n$.
     • Define
       $$x_i=\left\{\begin{array}{cc} 1 &\mbox{if $s_i^2+t_i^2<1$,}\\ 0 & \mbox{else} \end{array}\right.$$

     • Compute $4(x_1+\ldots+x_n)/n$.

   
   

2. Monte Carlo Integration 
   • Let $\varphi:[0,1]\to[0,1]$ be a continuous function.
     • Our goal is to find an estimator for the value of the integral $\int_0^1\varphi(x)\, dx$ that can be determined by Monte-Carlo simulation.
     • We consider the following stochastic model.
   • Let the random variables $X_1,X_2,\ldots:\Omega\to\mathbb{R}$ be independent and uniformly distributed on $(0,1]$, with probability density $f_X$ given by
     $$f_X(x)=\left\{\begin{array}{ll} 1 &\mbox{if $x\in[0,1]$,}\\ 0 & \mbox{else.} \end{array}\right.$$
     • Let $Z_k=\varphi(X_k)$ for all $k=1,2,\ldots$.
     • By the transformation theorem for independent and identically distributed random variables (see Theorem WR-3.18) the random variables $Z_1,Z_2,\ldots$ are independent and identically distributed
     • with
       $${\mathbb{E}\,}Z_1 = \int_0^1 \varphi(x) f_X(x)\, dx\\ = \int_0^1\varphi(x)\, dx\,.$$

   • Furthermore the SSLN (see Theorem WR-5.15) implies that for $n\to\infty$
     $$\frac{1}{n}\sum\limits_{k=1}^n Z_k\stackrel{{\rm a.s.}}{\longrightarrow}\int_0^1 \varphi(x)\, dx\,.$$
     • Hence $\frac{1}{n}\sum_{k=1}^n Z_k$ is an unbiased and (strongly) consistent estimator for $\int_0^1\varphi(x)\, dx$,
     • i.e., the probability for $\frac{1}{n}\sum_{k=1}^n Z_k$ to be a good approximation of the integral $\int_0^1\varphi(x)\, dx$ is high for sufficiently large $n$.

     
     

   • For the implementation of this simulation algorithm one can proceed similarly to Example 1:
     • Use a random number generator to generate $n$ pseudo-random numbers $x_1,\ldots,x_n$ that are realizations of random variables being uniformly distributed in $(0,1]$.
     • Define $z_k=\varphi(x_k)$ for $k=1,\ldots,n$.
     • Compute $\frac{1}{n}\sum_{k=1}^n z_k$.