Significant digits found while using an algorithm with random data A friend of mine wrote a pet program to find the value of $\pi$ using one of the algorithms which exploit random values, like Buffon's needle. He complained that after using 10,000 random number he reached a lousy approximation, something like 3.15. I answered that it should have been expected: my heuristics started with the Central Limit Theorem and noticed that a standard deviation is the square root of the number of samples, so the number of significant digits found should roughly be half the number of digits of the sample. Indeed he tried with 100,000,000 samples and obtained approximately 3.14162.
My question: is there a way to formalize how many expected significant digits may be typically found while running such an experiment?
 A: Buffon's needle is one of the least efficient ways to approximate $\pi$, since the error in approximation is proportional to $1/\sqrt n$, where $n$ is the number of tries. This is the case whenever you perform sampling from a large 'population' to estimate some kind of 'success' rate.
We can calculate the expected error in approximating $\pi$ when dropping Buffon's needle $n$ times onto a plane ruled with parallel lines. Suppose we obtain $X$ crossings this way. Assume, as in the standard formulation of the problem, the needle length equals the spacing of the parallel lines. Then the probability that a dropped needle crosses a line is $\frac2\pi$, hence $X$ has binomial$(n,p)$ distribution with $p:=\frac2\pi$. By the central limit theorem (or the normal approximation to the binomial), the random variable
$$
Y:=\frac X{2n}$$
has approximately normal distribution with mean $$ E(Y)=\frac{np}{2n}=\frac1\pi$$ and variance $$\operatorname{Var}(Y)=\frac{p(1-p)}{4n}=\frac{\frac2\pi(1-\frac2\pi)}{4n}.$$
Notice that $1/Y$ approximates $\pi$. To estimate the error in this approximation we compute
$$
\frac1Y-\pi=\frac\pi Y\left(\frac1\pi-Y\right)\approx\pi^2\left(\frac1\pi-Y\right).
$$
The expected error in estimating $\pi$ with $1/Y$ is therefore
$$
\begin{align}
E\left | \frac1Y -\pi\right|&\approx\pi^2 E\left|Y-\frac1\pi\right|\\
&\stackrel{(*)}=\pi^2\sqrt{\frac{\frac2\pi(1-\frac2\pi)}{4n}}\sqrt{\frac2\pi}\\
&=\frac{\pi\sqrt{1-\frac2\pi}}{\sqrt n},
\end{align}
$$
where in step (*) we use the formula $E(|Z|)=\sqrt{\frac2\pi}$ for a standard normal variable $Z$. When $n=100,000,000$ the expected error amounts to about $2\times 10^{-4}$.
You can use a similar argument to calculate the number of drops needed to achieve a specified amount of error (say, with probability exceeding $1-\alpha$). It takes quite a bit of effort to achieve even a small improvement in accuracy.
