Hello codeforces! A while back I presented myself with a challenge to build a random function from only random bits. However, in the process of doing so, I realized that not only was this much more difficult than I expected, I ended up wondering whether it is possible at all. So here's what I did and the challenges I faced before asking you for a solution:
Creating 1/powers of 2 is trivial, since flipping n coins can create 2^n random possibilities.
Similarly, the same thing would be possible with dice, for example flipping two die and then multiplying one dice by 6 and adding them together can yield a 1/36 chance.
This seems to be limited to the factors given though, a dice can create 1/12 or 1/18 as well, using mod.
I don't want to have to flip potentially infinite coins. So, I can't get a 1/8 chance and then reroll on an 8 to get a 1/7 chance.
I first attempted to use different flips of powers of two using the binary representation. For example, for a 1/7 chance I thought to flip 4, then 2, then 1 coin. However, it seems this distribution is not even, you have to play plinko to get 0 or 7.
So my next idea was to create a super large value from say 1000 coins and then divide to the value. Effectively a 1/7 chance but, not perfect either way. This just minimizes rerolls, since it minimzies the ratio when creating a 1/n chance since as a value k gets bigger 2^k % n is smaller relative to 2^k.
Apologies if this is a solved problem, or if this is a well known unsolved problem. This was on my mind for a while now.
You can use rejection sampling. For example if you want to generate a random number in [0, 4] with equal probability, you could generate a random number from 0 to 2^k-1 (for convenience i'll use 65535) and take it mod 5. But there's a slightly higher chance of getting the value 0 because 65535 is a multiple of 5, so there are 13107 ways to generate the numbers from 1 to 4 and 13108 to get 0. Wouldn't it be awesome to just get rid of that extra way? yes! If your rng outputs 65535, you can reject it and roll again until you get a different value. since you always rerolll at 65535 and all other values are equally likely you get a uniform distribution from 0 to 65534, which allows you to get a uniform distribution from 0 to 4.
this can technically TLE if your RNG rolls 65535 over and over but this is so astronomically improbable that you're more likely to have a cosmic ray hit the CF server and change your username to BarViz
The "potentially infinite coins" thing I said wasn't really to prevent it from running too long (I think even without using bigger sums like just going to 8 for 5 worst case scenario is ~2x average time using summation to calculate) but more so to just single out rejection sampling, it doesn't feel like a complete solution to me and I am wondering whether it is possible without it.
It's not possible to flip a finite number of coins and have any single event have a probability with denominator that's not a power of 2. Because the sample space has size 2^k and is uniformly distributed. Even if you potentially allow changing the number of flips, you can just treat the samples with less coinflips as groups of samples with the maximum number. So like if your sample space was $$${000, 001, 010, 011, 10, 11}$$$, you can treat $$$10$$$ as $$${100, 101}$$$ and the same for $$$11$$$.
I feel like it could be possible somehow though. Like if there's random libraries it might already be a solved thing.
They use rejection sampling. https://lemire.me/blog/2019/09/28/doubling-the-speed-of-stduniform_int_distribution-in-the-gnu-c-library/