Monte Carlo

Instructions: have fun with these Monte Carlo simulations

Throwing Darts

One way can estimate the value of \(\pi\) is by - you guessed it - using a circle! Suppose we inscribed a unit circle (radius = 1) inside a square (side length = 2). The circle would have area \[A = \pi r^2 = \pi\times 1^2 = \pi\] The square would have area \[A = s^2 = 2^2 = 4\] Thus the ratio of the circle's area to the square's area is \(\pi/4\). We can estimate this ratio by "throwing darts" randomly at the square. Most darts will land within the inscribed circle ("hits"), but some will land outside the circle ("misses"). We can set up an equation to solve for \(\pi\). \[ \frac{\pi}{4} \approx \frac{\text{hits}}{\text{total}}\] \[ \pi \approx 4\times\frac{\text{hits}}{\text{total}} \]

Scattering Needles

Another way to estimate the value of \(\pi\) is by - surprisingly - using lines! Suppose we had a needle with length \(L\) on a grid with horizontal lines \(2L\) apart.

Let \(x\) be the position of the center of the needle relative to the nearest grid line. The value of \(x\) ranges from 0 to \(L\) with uniform density. Thus the probability distribution of \(x\) is \[P_x = \frac{1}{L}\] Let \(\theta\) be the (acute) angle the needle makes with the nearest grid line. The value of \(\theta\) ranges from 0 to \(\frac{\pi}{2}\) with uniform density Thus the probability distribution of \(\theta\) is \[P_\theta=\frac{2}{\pi}\] Because the position \(x\) and angle \(\theta\) are independent, we can multiply these probabilities together to get a combined probability distribution of \[P_{x\theta} = \frac{2}{L\pi}\] The needle will cross a line if \(x\leq\frac{L}{2}\sin\theta\). We can use a little calculus to find the probability that this condition is true: \[ \int_{\theta=0}^{\frac{\pi}{2}}\int_{x=0}^{\frac{L\sin\theta}{2}} \frac{2}{L\pi} dxd\theta\] \[ \int_{\theta=0}^{\frac{\pi}{2}}\frac{\sin\theta}{\pi} d\theta\] \[\frac{1}{\pi}\] We see that the probability of a needle crossing a line is \(\frac{1}{\pi}\). We can drop many needles randomly on a grid and count the number of needles that cross a line ("crossing"). We can set up an equation to solve for \(\pi\) \[ \frac{\text{crossing}}{\text{total}} \approx \frac{1}{\pi}\] \[ \pi \approx \frac{\text{total}}{\text{crossing}}\]

Surprise

In this simulation, we will choose a random floating-point number on the interval [0,1]. We will continue to choose numbers until their sum exceeds 1. For example, suppose we randomly chose 0.5, 0.2, 0.42. Choosing 0.42 caused the sum to exceed 1, so we stop and say that the length \(N\) of this sequence is 3. What is the average value of \(N\)? See if you can figure it out! (HINT: The solution may involve factorials and induction!)