character limit is hard:
the problem overview is "turn an unknown biased RNG into a unbiased, uniformly distributed RNG"
25.04.2023 05:16
👍 1
🔁 0
💬 0
📌 0
character limit is hard:
the problem overview is "turn an unknown biased RNG into a unbiased, uniformly distributed RNG"
clarifying rules:
you can't use external sources of randomness
every time you run your algorithm it should run RNG some number of times and output a single value
you're given a size N at the start, every value outputted should have a 1 / N chance of occuring
fun problem i can't stop thinking about:
you have a biased RNG that outputs a 1 or a 0 offset by some unknown value P%
you need to use it to produce a value that is uniformly distributed over some given N
you can call the RNG some finite number of times
no error is allowed (you can't estimate P)