Random Sampling

The goal of random sampling is to generalize hard random variables from easy RVs. This allows us to compute hard integrals by using sampling to solve deterministic problems.

Definition (Random Sampling RVs)

Let $X\in \mathbb{R}$ be a random variable with $X\sim f,X\sim F$ the PDF and CDF respectively. We accomplish our goal of sampling from the PDF $f$ by producing independent and identically distributed (iid) RVs with PDF $f$.

In practice, sampling RVs in $\mathbb{R}$ means generating numbers with likelihood defined by $f$.

Example 1 (Monte Carlo Estimation of Pi)

Suppose we wanted to find the area of a unit circle in a plane. Let

$$\begin{array}{rl}{U}_1& \sim U(-1,+1)\\ U_2& \sim U(-1,+1)\end{array}$$

Let

$$X=\{\begin{array}{ll}0& \text{if }(U_1,U_2)\text{ is outside the circle}\\ 1& \text{if }(U_1,U_2)\text{ is inside the circle}\end{array}$$

Note that $U(-1,+1)$ is the Uniform Distribution. Now, the area of th sample space, $U_1\times U_2$ is $4$. Thus,

$$P(X=1)=\frac{A}{4}P(X=0)=1-\frac{A}{4}$$

where $A$ is the area of the unit circle. Since $X$ is a Bernoulli RV, then $\mathbb{E}\left\{X\right\}=A/4$.

After $N$ trials, we have $X_1,X_2,\dots ,X_N$ iid random variables. Using the Strong Law of Large Numbers, we see

$$\underset{N\to \infty }{\lim }\frac{1}{N}\sum _{i=1}^{\infty }{X}_i\to \frac{A}{4}=\frac{\pi }{4}$$

Effectively, we are counting the number of the dots that hit the circle with the summation, and finding the mean.

Example 2 (Multidimensional Hypercube Integral)

Compute the integral $I$ of a function $g:[0,1{]}^d\to \mathbb{R}$ over a $d-$dimensional hypercube $[0,1{]}^d$. Let

$$I={\int }_{[0,1{]}^d}g(x)dx={\int }_0^1{\int }_0^1\cdots {\int }_0^{1}g(x_1,x_2,\dots ,x_d)d{x}_{1}d{x}_2\cdots d{x}_d$$

Numerically, integrating this is the same as doing this over a grid, dividing the domain into $N^d$ boxes of size $(1/N{)}^d$. Let the center of each box be $x^{(i)}$ be $g(x^{(i)})$. The sum is our integral,

$$I\approx \sum _{i=1}^{N^d}g(x^{(i)}){\left(\frac{1}{N}\right)}^d$$

The term $N^d$ means we need many points. Even with $d=10$ and $N=10$ total divisions, we need $10^{10}$ or $10$ billion points (which is computationally expensive!)

Instead, we can do Monte Carlo Integration. First, generate $N$ iid RVs $X_1,\dots ,X_N\sim U(0,1)$. Since the PDF of each RV is $p(x)=1$, then

$$\begin{gathered} I={\int }_{[0,1{]}^d}g(x)dx={\int }_{[0,1{]}^d}g(x)\cdot 1dx={\int }_{[0,1{]}^d}g(x)\cdot p(x)dx \\ =\mathbb{E}\left\{g(X)\right\} \end{gathered}$$

Note that $X$ is the RV of any value of this distribution since they are identical. Then we can define an experiment with $N$ trials. Let

$$I_N=\frac{1}{N}\sum _{i=1}^{N}g(x_i)$$

Again, by Strong LLN, as $N\to \infty$, then $I_N\to I$. We can create an Estimator for $I_N$ and get an error of $\approx 1/\sqrt{N}$.

Example 3 (Ising Model)

See Ising Model.