Week 11-12: Estimating Pi with a RNG

Week 11-12: Estimating Pi with a RNG#

Laboratory 8
Last updated July 30, 2023

00. Content #

Mathematics

Probability Density Function
Expectation and Variance
Integrals in One Dimension

Programming Skills

Arrays

Embedded Systems

MicroPython and Thonny

0. Required Hardware #

Required Hardware of your “best” RNG method from lab 7

Write your name and email below:

Name:

Email:

A Monte Carlo Experiment #

Recall that a uniform random variable $U$ on the interval $(0,1)$ has a probability density function defined as follows:

\[\begin{split} f_U(u) = \begin{cases} 1 , &0<u<1 \\ 0 , &\text{ otherwise} \end{cases} \end{split}\]

So the probability $U$ takes a value in a subinterval $(s,t)$ of $(0,1)$ is exactly the length $t-s$ of the subinterval.

More genrerally, a uniform random variable $V$ on the interval $(a,b)$ has probability density function

\[\begin{split} f_V(v) = \begin{cases} \frac{1}{b-a}, &a<v<b \\ 0, &\text{ otherwise} \end{cases} \end{split}\]

Exercise 1#

If $U_1$ and $U_2$ are uniform random variables on the interval $(0,1)$, then the ordered pair $(U_1,U_2)$ follows a uniform distribution within the square of side length 1 centered at $\left(\frac12,\frac12\right)$.

Let’s define two variables:

\[\begin{align*} X = 2U_1 - 1 \\ Y = 2U_2 - 1 \end{align*}\]

Determine how $(X,Y)$ is distributed.

Write Answers for Exercise 1 Below

A Monte Carlo experiment is a technique used to study a response by using random samples. In our initial estimation of $\pi$, we will generate a large number of uniform samples inside a square. By inscribing a circle within the square and counting the number of points that fall inside the circle, the proportion of points within the circle will approximate the proportion of the circle’s area relative to the area of the square. Let’s assume the circle has a radius of $r$. Intuitively, the probability that a randomly chosen point lands inside the circle is given by:

\[ \frac{\text{area of circle}}{\text{area of square}} = \frac{\pi r^2}{(2r)^2} = \frac{\pi r^2}{4r^2} = \frac{\pi}{4} \]

You can visualize an example of this experiment with 500 samples below. In the accompanying image, 377 points are marked in red, representing the points falling within the circle’s boundary. By taking the proportion of points within the circle and multiplying it by 4, we can approximate the value of $\pi$. In this particular case, calculating $4 \cdot \frac{377}{500} = 3.016$, which is not particularly close to the value of $\pi$. To obtain a better estimation, let’s use a larger number of samples.

Exercise 2#

Using the $(X,Y)$ definition from Exercise 1, let’s generate $n=10,000$ random pairs $(X,Y)$ using the random.uniform() or np.random.uniform() function. We will then create a scatter plot to visualize these points. Additionally, we’ll modify the color or marker of the points that fall inside the inscribed circle. You don’t have to draw the circle on the plot.

Write Answers for Exercise 2 Below

Exercise 3#

We will use the proportion of points falling inside the circle to estimate the value of $\pi$. Report the relative and absolute error of your approximation when $n=$ 5,000; $n=$ 10,000; $n=$ 50,000; and $n=$ 100,000.

Write Answers for Exercise 3 Below

Another approach to consider for estimating $\pi$ involves using a sum of random variables. We begin by randomly generating $n$ points within the square. Let’s define the random variables $Z_1,Z_2,\dots,Z_n$ as follows:

\[\begin{split}Z_i = \begin{cases} 1 ,& \text{ if random point $i$ is in the circle} \\ 0 ,& \text{ otherwise} \end{cases} \quad \text{ for } i=1,2,\dots,n\end{split}\]

We say $Z_1,Z_2,\dots,Z_n$ are indicator variables. Our approximation for $\pi$ is then

\[ 4\cdot\frac{Z_1 + Z_2 + \cdots + Z_n}{n}\]

The expected value of $4Z_i$ is

\[\begin{align*} E[4Z_i] &= (4\cdot 1)\cdot P(\text{point $i$ is in the circle}) + (4\cdot 0)\cdot P(\text{point $i$ is not in the circle}) \\ &= 4\cdot \frac{\pi}{4} + 0 \\ &= \pi \end{align*}\]

Exercise 4#

Compute the expected value $E[(4Z_i)^2]$.

Write Answer for Exercise 4 Below

Exercise 5#

We know for a random variable $X$ that $Var(X)=E[X^2]-(E[X])^2$. Use the formula below to compute the variance of the random variable $4Z_i$.

\[ Var(4Z_i) = E[(4Z_i)^2] - (E[4Z_i])^2\]

Write Answer for Exercise 5 Below

Recalling that for two independent random variables, $X$ and $Y$, and constants, $a$ and $b$, we have the following properties:

\[ Var(X+Y)= Var(X)+Var(Y) \quad \text{and}\quad Var(aX+b) = a^2 Var(X) \]

Now, let’s compute the variance in our estimation of $\pi$ using these properties:

\[\begin{align*} Var\left(4\cdot\frac{Z_1 + Z_2 + \cdots + Z_n}{n} \right) &= Var\left(\frac{4Z_1 + 4Z_2 + \cdots + 4Z_n}{n} \right) \\ &= \frac{1}{n^2}Var(4Z_1 + 4Z_2 + \cdots + 4Z_n) \\ &= \frac{1}{n^2}[Var(4Z_1) + Var(4Z_2) + \cdots + Var(4Z_n)] \\ &= \frac{1}{n^2}nVar(4Z_1), \quad\quad\text{ since $Var(4Z_i)$ is the same for $i=1,2,\dots,n$}\\ &= \frac{Var(4Z_i)}{n} \end{align*}\]

Another Estimation #

In our Monte Carlo experiment, we initially required $2n$ samples from a uniform distribution to generate $n$ random points within the square. Now, we aim to enhance our estimation of $\pi$ using only $n$ uniform samples.

Consider the integral: $ \int_{-1}^1 2 \sqrt{1-x^2}dx = \pi $

We will rearrange this integral as an expected value. First, let’s recall the following fact: If $X$ is a continuous random variable with a probability density function $f_X(x)$, and $g$ is any real-valued function, then the expected value of $g(X)$ is given by:

\[ E[g(X)] = \int_{-\infty}^\infty g(x)f(x)dx \]

Exercise 6#

Suppose $X$ is a uniform random variable on $(-1,1)$. What function $g$ would make

\[ E[g(X)] = \int_{-\infty}^\infty g(x)f(x)dx = \int_{-1}^1 2 \sqrt{1-x^2}dx = \pi \]

Write Answers for Exercise 6 Below

NOTE

This is a 2-week lab. Turn in the exercises above. Pick up from here during the next lab session.

By choosing an appropriate function $g$, we can approximate $\pi$.

Let $X_1,X_2,\dots,X_n$ be independent uniform random variables on the interval $(-1,1)$. Then,

\[ E\left[ \frac{g(X_1)+g(X_2)+\cdots + g(X_n)}{n} \right] = \frac 1n E[g(X_1)+g(X_2)+\cdots + g(X_n)] = \frac{nE[g(X_1)]}{n} = \pi\]

Exercise 7#

Generate $n$ uniform random samples $x_1,x_2,\dots,x_n$ and calculate the average

\[ \frac{g(x_1)+g(x_2)+\cdots + g(x_n)}{n} \]

Report the absolute error of your approximation using this method when $n=$ 5,000; $n=$ 10,000; $n=$ 50,000; and $n=$ 100,000. How does it compare to our first method with the circle in the square?

Write Answers for Exercise 7 Below

Similar to how we computed the expected value of $g(X)$, we can also calculate the expected value of $g(X)\cdot g(X) = (g(X))^2$ by evaluating the integral

\[ E[(g(X))^2] = \int_{-\infty}^\infty (g(x))^2f(x)dx \]

Exercise 8#

What is the value of $Var(g(X))$?

Write Answers for Exercise 8 Below

Now, let’s compute the variance in our alternative estimation of $\pi$.

\[\begin{align*} Var\left(\frac{g(X_1)+g(X_2)+\cdots + g(X_n)}{n} \right) &= \frac{1}{n^2} Var(g(X_1)+g(X_2)+\cdots + g(X_n)) \\ &= \frac{1}{n^2} n Var(g(X_1)), \quad\quad\text{ since $Var(g(X_i))$ is the same for $i=1,2,\dots,n$}\\ &= \frac{Var(g(X_1))}{n} \end{align*}\]

Exercise 9#

How much smaller is the variance in this second method of approximating $\pi$ compared to the first method?

Write Answers for Exercise 9 Below

Exercise 10#

If we generate a sequence of 16 binary digits, it is straightforward to convert it into a floating-point number ranging from 0 to 1. First, convert the binary number to base-10 and then divide it by $2^{16}-1$. Now, we have a method to simulate a uniform random variable on the interval $(0, 1)$ or any other interval of our choosing.

Using the “best” RNG as determined in the previous lab on RNGs, estimate $\pi$ using both methods described here for different values of $n$. Do your estimations of $\pi$ improve if you use 32 binary digits instead of 16?

Write Answers for Exercise 10 Below

Reflection #

Can you think of any other ways of estimating $\pi$?
Which part of the lab did you find the most challenging?
Which part of the lab was the easiest?