blog

Fair randomness

2016-05-16

Evolution

This is an addendum to my last post about randomness and fairness. As I was implementing a randomizer in the spirit of the random threshold model discussed before, a nice simplification occurred to me. I knew the probabilities p in my use case would be small, between 5% and 30%, and long streaks of bad luck can feel like a bug to the user. Therefore I wanted a tight upper bound for a streak of bad luck, so I chose c = 0.5, which results in an upper bound of 2 / p, while still allowing a two-streak of good luck. The code looked simple enough:

public bool Random(float probability) {
    entropy += probability;
    if (entropy >= random(0.5, 1.5)) {
        entropy -= 1;
        return true;
    }
    return false;
}

I noticed a couple of problems though.

1. It is somewhat likely to return true for probability p = 0% and below
2. It is somewhat likely to return false for probability p = 100% and above
3. The first call can never return true for small p, if entropy is initialized to 0.

It is easy enough to handle points #1 and #2 explicitly, but what about the initialization of entropy? Of course I want the probability of returning true on the first call to be equal to p. It is easy to see that entropy = 0.5 guarantees exactly that. But then one can just subtract 0.5 from both sides of the threshold test and obtain the following simplified randomizer:

Elegance

public class FairRandomizer {
    private float entropy = 0;

    public bool Random(float probability) {
        // handle edge cases
        if (probability <= 0) {
            return false;
        } else if (probability >= 1) {
            return true;
        }

        // randomize with entropy
        entropy += probability;
        if (entropy > random()) {
            entropy -= 1;
            return true;
        }
        return false;
    }
}

Simply elegant, isn’t it? Feel free to use the code above.

This site is open source. Improve this page.