Monte Carlo Simulation

Monte Carlo Simulation

Monte Carlo simulation is a computational method used to calculate the properties of a probabilistic event by repeating a random sampling process many times. A probabilistic problem may well be solvable analytically in closed form, but it can be very complex. Monte Carlo simulation then applies the concept of randomness to solve such problems approximately.

As an example, you are given the following problem:

A die has 6 faces with the values $\{1,2,3,4,5,6\}$. Each face value has the same probability of appearing in a throw of the die (equally likely). A person then carries out a die-throwing experiment by throwing the die repeatedly until an even number appears. It is assumed that a throw of the die does not depend on the previous throws (independent). What is the expectation (mean, or expected value) of the number of die throws made until an even number finally appears?

The problem above can be solved analytically as follows:

First, we need to calculate the probability that an even number appears in a single throw of the die. This event is calculated as:

\begin{equation} P({2,4,6}) = P({2}) + P({4}) + P({6}) = \frac{3}{6} = 0{,}5 , . \end{equation}

Second, we define a random variable $X$ that represents "the number of die throws made until an even value appears (including the last throw, which shows the even value)". Let us also write $p = P(Genap) = p(\{2,4,6\})$ (Genap = even). The value of the random variable $X$ is always positive:

\begin{equation} P(X=1) = p \ P(X=2) = (1-p) \times p \ P(X=3) = (1-p) \times (1-p) \times p = (1-p)^2 \times p \ \dots \ P(X=n) = (1-p) \times \dots \times (1-p) \times p = (1-p)^{n-1} \times p \end{equation}

Finally, the expectation, or expected value, of $X$, denoted by $\mathbf{E}[X]$, is calculated as:

\begin{align} \mathbf{E}[X] &= \sum_{i=1}^{\infty} i . P(X = i) \ &= \sum_{i=1}^{\infty} i . (1-p)^{i-1} . p \ &= \frac{1}{1-p} \end{align}

So the expected number of die throws until an even number appears for the first time is $1 / (1-p) = 1 / (1 - 0,5) = 2$.

The problem above can also be solved approximately using Monte Carlo simulation. One experiment reproduces the activity of throwing the die repeatedly and stopping at the first throw that gives an even value. This experiment is repeated $N$ times, where $N$ usually has to be sufficiently large. After that, we calculate the mean number of die throws over all experiments. This process is reproduced by the following Python code:

You will see that the result of the program fragment above is $\approx 2$.

Problem A (30 points)

Write a Monte Carlo simulation program to answer the following question:

What is the expected number of die throws needed for the total of the face values obtained to be at least $12$?

In this problem, some example experiments are:

1. $2$, $1$, $2$, $5$, $6$ $\rightarrow$ $5$ throws with a total of $16$
2. $6$, $6$ $\rightarrow$ $2$ throws with a total of $12$
3. $\dots$

Problem B (70 points)

Write a Monte Carlo simulation program to answer the following question:

Suppose we carry out a die-throwing experiment and stop when a $6$ appears. Given that we made $5$ die throws (the last throw being a $6$), what is the expected number of odd numbers that appear?