Difficulty: Intermediate | Prerequisites: Basic probability, indicator random variables, Markov's inequality
Monte Carlo methods use randomness to estimate deterministic quantities. Here, you throw darts at a square with an inscribed circle and use the hit ratio to estimate pi. The accuracy of this estimate depends on how many darts you throw, and Chernoff bounds give you a rigorous way to calculate the number of trials needed for a given confidence level. This ties together indicator random variables, concentration inequalities, and randomised algorithms, all core themes of the probabilistic analysis unit in EECS 376.
You can estimate pi by randomly throwing darts at a circle inscribed in a square: the fraction that land inside the circle, multiplied by 4, has expected value pi. Chernoff bounds then tell you exactly how many darts you need for a desired accuracy at a given confidence level. The two-sided Chernoff bound follows directly from the union bound applied to the one-sided versions.
Monte Carlo method
A technique that uses repeated random sampling to estimate a numerical result. In simple terms, you run a randomised experiment many times and average the outcomes to approximate something deterministic.
Indicator random variable
A random variable that takes the value 1 when an event occurs and 0 otherwise. Think of it as a coin flip that records whether a specific condition was met on each trial.
DART (as used in this problem)
A subroutine that throws a dart uniformly at random onto a square with an inscribed circle, returning 1 if the dart lands inside the circle, 0 otherwise. Each call to DART is one independent Bernoulli trial with success probability pi/4.
Chernoff bound (lower-tail)
For Y = Y_1 + ... + Y_n, where each Y_i is an independent indicator with P[Y_i = 1] = p, and for any epsilon > 0: P[Y/n <= p - epsilon] <= e^(-2 epsilon^2 n). In simple terms, it bounds how unlikely it is that your sample average falls far below the true mean.
Chernoff bound (upper-tail)
The mirror image: P[Y/n >= p + epsilon] <= e^(-2 epsilon^2 n). It bounds how unlikely it is that the sample average overshoots the true mean.
Chernoff bound (two-sided)
Combines both tails via the union bound: P[|Y/n - p| >= epsilon] <= 2e^(-2 epsilon^2 n). In simple terms, this is your go-to bound for saying "my estimate is within epsilon of the truth with high probability."
Confidence level
The probability that your estimate falls within the desired accuracy. A 99% confidence level means P[estimate is accurate] >= 0.99, equivalently P[estimate is inaccurate] <= 0.01.
Estimating pi with dart throwing
A circle of radius r is inscribed in a square of side 2r.
Area of the circle: pi r^2. Area of the square: (2r)^2 = 4r^2.
A uniformly random dart lands inside the circle with probability (pi r^2) / (4r^2) = pi/4.
Each call to DART is an independent indicator variable X_i with P[X_i = 1] = pi/4.
Algorithm: throw n darts, count the hits S = X_1 + X_2 + ... + X_n, output p = 4S/n.
E[p] = 4 * E[S/n] = 4 * (pi/4) = pi. The expected value of the output is exactly pi.
Applying Chernoff bounds for accuracy
Let Y_i = X_i (the indicator variables from the dart throws), so Y/n = S/n is the sample fraction of hits, with true mean p_0 = pi/4.
To get |p - pi| < delta with at least 99% confidence:
|p - pi| < delta means |4S/n - 4 * pi/4| < delta, which gives |S/n - pi/4| < delta/4.
Set epsilon = delta/4 in the two-sided Chernoff bound.
We need 2e^(-2 epsilon^2 n) <= 0.01 (since we want at most 1% failure probability).
Solving: e^(-2 epsilon^2 n) <= 0.005, so n >= ln(200) / (2 epsilon^2).
Worked examples:
For |p - pi| < 0.1: epsilon = 0.025, so n >= ln(200) / (2 * 0.000625) = ln(200) / 0.00125. This gives n >= approx 4,239.
For |p - pi| < 0.01: epsilon = 0.0025, so n >= ln(200) / (2 * 0.00000625) = ln(200) / 0.0000125. This gives n >= approx 423,888.
For |p - pi| < 0.001: epsilon = 0.00025, so n >= ln(200) / 0.000000125. This gives n >= approx 42,388,801.
Notice that tightening the accuracy by a factor of 10 increases the required sample size by a factor of 100 (quadratic scaling).
Proving the upper-tail Chernoff bound from the lower-tail
This is a symmetry argument. Given Y = Y_1 + ... + Y_n with P[Y_i = 1] = p:
Define Z_i = 1 - Y_i. Then P[Z_i = 1] = 1 - p, and Z = Z_1 + ... + Z_n = n - Y.
Z/n = 1 - Y/n, and E[Z/n] = 1 - p.
Y/n >= p + epsilon is equivalent to Z/n <= (1 - p) - epsilon.
Apply the lower-tail bound to Z with mean (1 - p) and the same epsilon: P[Z/n <= (1 - p) - epsilon] <= e^(-2 epsilon^2 n).
Therefore P[Y/n >= p + epsilon] <= e^(-2 epsilon^2 n).
Proving the two-sided bound from the one-sided bounds
This follows from the union bound:
P[|Y/n - p| >= epsilon] = P[Y/n >= p + epsilon OR Y/n <= p - epsilon].
By the union bound: this is <= P[Y/n >= p + epsilon] + P[Y/n <= p - epsilon].
Apply the upper-tail and lower-tail bounds: <= e^(-2 epsilon^2 n) + e^(-2 epsilon^2 n) = 2e^(-2 epsilon^2 n).
Pi estimation formula
p = \frac{4}{n} \sum_{i=1}^{n} X_iwhere each X_i is an independent indicator with P[X_i = 1] = pi/4.
Lower-tail Chernoff bound
\Pr\left[\frac{Y}{n} \leq p - \varepsilon\right] \leq e^{-2\varepsilon^2 n}Upper-tail Chernoff bound
\Pr\left[\frac{Y}{n} \geq p + \varepsilon\right] \leq e^{-2\varepsilon^2 n}Two-sided Chernoff bound
\Pr\left[\left|\frac{Y}{n} - p\right| \geq \varepsilon\right] \leq 2e^{-2\varepsilon^2 n}Sample size formula (for desired accuracy delta at confidence 1 - alpha)
Set epsilon = delta/4 (for the pi problem), then solve 2e^(-2 epsilon^2 n) <= alpha:
n \geq \frac{\ln(2/\alpha)}{2\varepsilon^2}Students often forget to multiply by 4. The fraction of darts landing in the circle estimates pi/4, not pi. You must multiply the sample average by 4 to get an estimator with expected value pi.
Students sometimes apply the Chernoff bound directly to p = 4S/n with epsilon = 0.1, rather than converting to the underlying indicator variables first. The bound applies to S/n (the raw sample average of indicators), so you must set epsilon = delta/4 when the desired accuracy is on the 4S/n scale.
Students mix up the one-sided and two-sided bounds. If you want |p - pi| < delta (a two-sided guarantee), you need the factor of 2 in front: 2e^(-2 epsilon^2 n). Forgetting this gives you 99.5% confidence instead of 99%.
The symmetry trick for proving the upper-tail bound trips people up. The key step is defining Z_i = 1 - Y_i and observing that the complement of a Bernoulli(p) variable is Bernoulli(1 - p). Some students try to apply the lower-tail bound directly to Y without this substitution.
The dart-throwing pi estimation is a canonical example of Monte Carlo estimation. Expect exam questions that swap the geometric setup (different shapes, different ratios) but use the same structure: indicator variables, scaling, then Chernoff bounds.
Proving the upper-tail from the lower-tail using the complement trick (Z_i = 1 - Y_i) is a classic exam question. Know this proof cold.
The two-sided bound via union bound is a one-liner, but exams often ask you to justify the union bound step explicitly.
Sample size calculations (solving for n given epsilon and confidence) appear frequently. Practise the algebra so you can do it quickly under time pressure.
The quadratic relationship between accuracy and sample size (10x tighter accuracy requires 100x more samples) is a conceptual point that comes up in short-answer or true/false questions.
True or False: Each call to DART returns 1 with probability pi/4. (True)
Fill in the blank: To estimate pi, you compute p = ____ * S/n, where S is the number of darts that land in the circle. (4)
True or False: Doubling the desired accuracy (halving delta) requires doubling the number of darts. (False, it requires quadrupling them.)
True or False: The two-sided Chernoff bound is tighter than either one-sided bound alone. (False, it is looser by a factor of 2.)
Fill in the blank: To prove the upper-tail bound from the lower-tail bound, define Z_i = ____. (1 - Y_i)
Q: Describe an algorithm that uses n calls to DART and produces an output whose expected value is pi.
A: Throw n darts. Let S be the number that land in the circle. Output p = 4S/n. Since E[X_i] = pi/4 for each dart, E[S/n] = pi/4, so E[p] = 4 * pi/4 = pi.
Q: Using the two-sided Chernoff bound, how many darts are needed so that |p - pi| < 0.01 with at least 99% confidence?
A: We need |S/n - pi/4| < 0.0025. Set epsilon = 0.0025 in the two-sided bound: 2e^(-2 * 0.0025^2 * n) <= 0.01. Solving: n >= ln(200) / (2 * 0.0000625) = ln(200) / 0.0000125, which gives n >= approximately 423,888.
Q: Prove the upper-tail Chernoff bound assuming the lower-tail bound.
A: Define Z_i = 1 - Y_i. Then Z_i are independent indicators with P[Z_i = 1] = 1 - p, and Z/n = 1 - Y/n. The event Y/n >= p + epsilon is equivalent to Z/n <= (1 - p) - epsilon. Applying the lower-tail bound to Z gives P[Z/n <= (1 - p) - epsilon] <= e^(-2 epsilon^2 n), which completes the proof.
Q: Prove the two-sided Chernoff bound from the one-sided bounds.
A: P[|Y/n - p| >= epsilon] = P[Y/n >= p + epsilon or Y/n <= p - epsilon]. By the union bound, this is at most P[Y/n >= p + epsilon] + P[Y/n <= p - epsilon] <= e^(-2 epsilon^2 n) + e^(-2 epsilon^2 n) = 2e^(-2 epsilon^2 n).
Q: Why does tightening the accuracy by a factor of 10 increase the required sample size by a factor of 100?
A: The exponent in the Chernoff bound is -2 epsilon^2 n. Since epsilon = delta/4, halving epsilon (tightening accuracy by 2x) requires 4x the samples to keep the exponent the same. Tightening by 10x means epsilon shrinks by 10x, so n must grow by 10^2 = 100x.
This material connects directly to randomised complexity classes (RP, BPP) because those classes are defined by algorithms that succeed with high probability, and Chernoff bounds are the tool you use to amplify their success probability by repeating trials. The random graph problems in this same homework set use the same Chernoff machinery to bound estimates of edge probability.
More broadly, Monte Carlo estimation is the foundation of randomised algorithms throughout computer science, from approximate counting to randomised rounding in optimisation.
Monte Carlo method, Monte Carlo estimation, estimating pi, dart throwing algorithm, indicator random variable, Bernoulli trial, Chernoff bound, Hoeffding bound, concentration inequality, lower-tail bound, upper-tail bound, two-sided bound, union bound, sample complexity, confidence interval, randomised algorithm, EECS 376, Foundations of Computer Science, University of Michigan