Suppose you need to simulate an event that happens of the time, and all you have is a fair coin. Well, that’s easy enough. Flip the coin twice. Report success if you get 2 heads, and report failure otherwise.
Suppose instead. That may not be a power of 2, but there is still a simple solution. Flip the fair coin twice. Report success on HH, report failure on HT or TH, and try again on TT. Each iteration takes coin flips, and there is a probability of halting, giving expected coin flips.
Now, suppose you need to simulate . Well, nothing is especially wrong with the current scheme. We need coin flips to get enough outcomes. Then, label case as success, as failure, and the rest as retries. For analyzing runtime, these numbers are starting to get messy, but we can at least ballpark the expected number of flips. The probability of halting is , since by construction , meaning the number of retry cases is less than half of all cases. Thus, the expected number of flips is at most . Yes, that is…
(•_•) ( •_•)>⌐■-■ (⌐■_■)
a devilish upper bound, but things could be worse.
(I’m not sorry.)
But, what if you need to simulate ? Or simulate ? In the first case, the number of flips needed is enormous. In the second, the scheme fails completely - there is no way to simulate irrational probabilities.
We’ll get back to the irrational case later.
Recall how we simulated . The scheme reports success only on HH. So, if the first flip lands tails, we can halt immediately, since whatever way the second coin lands, we will report failure anyways. The revised algorithm is
- Flip a coin. If tails, report failure.
- Flip a coin. Report success on heads and failure on tails.
This gives expected flips instead of flips.
As another example, consider . First, plan to flip 3 coins. Divide the 8 outcomes into 1 success case, 4 failure cases, and 3 retry cases. These can be distributed as
- accept: HHH
- failing: THH, THT, TTH, TTT
- retry: HHT, HTH, HTT
If the first coin is T, we can stop immediately. If the first two coins are HT, we can retry immediately. The only case left is HH, for which we need to see the third flip before deciding what to do.
(Some of you may be getting flashbacks to prefix-free codes. If you haven’t seen those, don’t worry, they won’t show up in this post.)
With clever rearrangement, we can bundle outcomes of a given type under as few unique prefixes as possible. This gives some improvement for rational , but still does not let us simulate irrational . For this, we need to switch to a new framework.
A New Paradigm
I did not come up with this method - I discovered it from here. I wish I had come up with it, for reasons that will become clear.
Let be the binary expansion of . Proceed as follows.
- Flip a coin until it lands on heads.
- Let be the number of coins flipped. Report success if and report failure otherwise
The probability the process stops after flips is , so the probability of success is
Regardless of , it takes expected flips for the coin to land heads. Thus, any biased coin can be simulated in expected flips. This beats out the other scheme, works for all instead of only rational , and best of all you can compute bits lazily, making this implementable in real life and not just in theory.
Slick, right? This idea may have been obvious to you, but it certainly wasn’t to me. After thinking about the problem more, I eventually recreated a potential chain of reasoning to reach the same result.
Bits and Pieces
(Starting now, I will use interchangeably with heads and interchangeably with tails.)
Consider the following algorithm.
- Construct a real number in by flipping an infinite number of coins, generating a random number , where is the outcome of coin flip . Let this number be .
- Report success if and failure otherwise.
This algorithm is correct as long as the decimals generated follow a uniform distribution over . I won’t prove this, but for an appeal to intuition: any two bit strings of length are generated with the same probability , and the numbers these represent are evenly distributed over the interval . As this approaches a uniform distribution.
Assuming this all sounds reasonable, the algorithm works! Only, there is the small problem of flipping -ly many coins. However, similarly to the case, we can stop coin flipping as soon as as it is guaranteed the number will fall in or out of .
When does this occur? For now, limit to the case where has an infinite binary expansion. For the sake of an example, suppose . There are 2 cases for the first flip.
The coin lands . Starting from , it is possible to fall inside or outside , depending on how the next flips go. The algorithm must continue.
The coin lands . Starting from , it is impossible to fall outside . Even if every coin lands , . (This is why having an infinite binary expansion is important - it ensures there will be another down the line.) The algorithm can halt and report success.
So, the algorithm halts unless the coin flip matches the in ’s expansion. If it does not match, it succeeds. Consider what happens next. Starting from , there are 2 cases.
- Next coin lands . Since , we can immediately report failure.
- Next coin lands . Similarly to before, the number may or may not end in , so the algorithm must continue.
So, the algorithm halts unless the coin flip matches the in ’s expansion. If it does not match, it fails. This gives the following algorithm.
- Flip a coin until the th coin fails to match
- Report success if and failure otherwise.
Note this is essentially the same algorithm as mentioned above! The only difference is the ending condition. Instead of halting on heads, the algorithm halts if the random bit does not match the “true” bit. Both happen the time, so the two algorithms are equivalent.
(If you wish, you can extend this reasoning to with finite binary expansions. Just make the expansion infinite by expanding the trailing into .)
Here’s a sample run of the algorithm told in pictures. The green region represents the possible values of as bits are generated. Initially, any is possible.
The first generated bit is , reducing the valid region to
This still overlaps , so continue. The second bit is , giving
This still overlaps, so continue. The third bit is , giving
The feasible region for no longer intersects , so the algorithm reports failure.
CS-minded people may see similarities to binary search. Each bit chooses which half of the feasible region we move to, and the halving continues until the feasible region is a subset of or disjoint from .
This scheme is very, very efficient. But, is it the best we can do? Is there an algorithm that does better than expected flips for general ?
It turns out that no, expected flips is optimal. More surprisingly, the proof is not too bad.
For a given , any algorithm can be represented by a computation tree. That tree encodes whether the algorithm succeeds, fails, or continues, based on the next bit and all previously generated bits.
Two sample computation trees for .
With the convention that the root is level , children of the root are level , and so on, let the weight of a node be . Equivalently, the weight is the probability the algorithm reaches that node.
For a given algorithm and , the expected number of flips is the expected number of edges traversed in the algorithm’s computation tree. On a given run, the number of edges traversed is the number of vertices visited, ignoring the root. By linearity of expectation,
To be correct, an algorithm must end at a success node with probability . Thus, the sum of weights for success nodes must be . For with infinitely long binary expansions, we must have an infinitely deep computation tree. If the tree had finite depth , any leaf node weight would be a multiple of , and the sum of success node weights would have at most decimal places.
Thus, the computation tree must be infinitely deep. To be infinitely deep, every level of the tree (except the root) must have at least 2 nodes. Thus, a lower bound on the expected number of flips is
and as we have shown earlier, this lower bound is achievable.
(For with finite binary expansions, you can do better than expected flips. Proving the optimal bound for that is left as an exercise.)
Every coin in your wallet is now an arbitrarily biased bit generating machine that runs at proven-optimal efficiency. If you run into a bridge troll who demands you simulate several flips of a coin that lands heads of the time, you’ll be ready. If you don’t, at least you know one more interesting thing.