I want to estimate $\pi$ using the following method
- let $Z$ be $0$ to start with
- repeated $N$ times:
- draw $u_1, u_2 \in [0, 1]$ and calculate whether or not $(u_1)^2 + (u_2)^2 < 1$, if so add $1$ to $Z $
- divide $Z$ by $N$ - this gives the estimate for $\pi$
Which makes sense to me. However, I would like to develop a bound for the error. Specfically I would like to work out how many trials (what value of $N$) I need so that
$$ \Pr[|4Z - \pi| \geq \varepsilon] \leq \delta $$
(i.e. that my estimate differs from $\pi$ by an arbitrarily small amount).
First I tried to define some things
- Let $Y_i = 1$ if in the $i$th trial the sum was greater than 1 and 0 otherwise
- Therefore $Z = \frac{1}{N} \sum_{i = 1}^{N} Y_i$ or if $X \sim B(N, \pi/4)$, we know $Z = \frac{X}{N}$
So I thought that I could use a Chernoff bound here as $Z$ is sort of binomially distributed.
Therefore, I would like to find something in the shape
$$\Pr(|Z - \mu| \geq \epsilon \mu)$$
so to get this I tried
$$ \Pr\left(\left|Z - \frac{\pi}{4}\right| \geq \frac{\pi}{4} \frac{\epsilon}{\pi}\right) \leq \delta $$
and redefined $\epsilon = \frac{\varepsilon}{4}$.
From this I can say that
$$ \Pr\left(\left|Z - \frac{\pi}{4}\right| \geq \frac{\pi}{4} \frac{\epsilon}{\pi}\right) \leq 2\exp\left(-\mu\left(\frac{\varepsilon}{\pi}\right)^2 \times \frac{1}{3}\right) $$
So if I could prove that
$$ 2\exp\left(-\mu\left(\frac{\varepsilon}{\pi}\right)^2 \times \frac{1}{3}\right) \leq \delta $$
then I would be done, but I'm not sure how to prove this.
Any help/hints/direction about how to solve this problem would be greatly appreciated.