To produce the probability $1/\pi$, the following algorithm can be used (Flajolet et al. 2010), which is based on a series expansion by Ramanujan:
- Set $t$ to 0.
- Flip two fair coins. If both show heads, add 1 to $t$ and repeat this step. Otherwise, go to step 3.
- Flip two fair coins. If both show heads, add 1 to $t$ and repeat this step. Otherwise, go to step 4.
- With probability 5/9, add 1 to $t$. (For example, generate a uniform random integer in [1, 9], and if that integer is 5 or less, add 1 to $t$.)
- Flip a fair coin $2t$ times, and return 0 if heads showed more often than tails or vice versa. Do this step two more times.
- Return 1.
Then, run the algorithm above until you get 1, then let $X$ be the number of runs including the last. Then it holds that $\mathbb{E}[X] = \pi$.
Note that the algorithm doesn't involve fractions at all.
See also: https://math.stackexchange.com/questions/4189867/obtaining-irrational-probabilities
REFERENCES:
- Flajolet, P., Pelletier, M., Soria, M., "On Buffon machines and numbers", arXiv:0906.5560 [math.PR], 2010.