Problem bank

Problem 200 of 333HardStochastic CalculusP200

Importance sampling a rare coin event

  1. You want P(at least 80 heads in 100 fair flips)P(\text{at least 80 heads in 100 fair flips}) by Monte Carlo. The true value is about 5.6×10−105.6 \times 10^{-10}, so plain simulation almost never sees the event. Instead you simulate with a coin that lands heads with probability 0.80.8.

    (a) What weight must each simulated sequence carry so the estimator is unbiased? Write it in terms of the number of heads HH.

    (b) Why does this work, and why is 0.80.8 a sensible choice for the biased coin?

    (c) Roughly how many samples does each method need for a 1% relative error?