Steve's Tech Talk

Weighted Random Numbers

Maybe it’s all how many of the geeky kids in my generation played D&D, but there’s something about random numbers that brings out the geeks in droves.

I answered a question on stack overflow on how to weight random numbers more in a particular range.  Let’s discuss the math.

I’ll define a transform function T(x), where x is in the half-open range [0..1) (x may go from 0 up to but not including 1) such that for every x, y = T(x) is also in the same range.

The Random class in .NET has method, NextDouble, which returns a number conveniently in the range [0..1).  This means that if we apply some T(x) to NextDouble, we’ll get a number in the same range.

Based on that, I can write the following:

public abstract class DelegatedRandom
{
    private Random _r = new Random();
    public int Next(int low, int high)
    {
        if (high >= low)
            throw new ArgumentOutOfRangeException("high");
        double rand = _r.NextDouble();
        rand = Transform(rand);
        if (rand >= 1.0 || rand < 0) throw new Exception("internal error - expected transform to be between 0 and 1");
        return (int)((high - low) * rand) + low;
    }
    protected abstract Func<double, double> Transform { get; }
}

T(x) is built into the abstract property Transform, which is a Func<double, double>.  Transform returns a function that when applied to a double returns a double.  At runtime, I range check the results.

This lets me define subclasses that simply implement Transform.  For example, consider using exponentiation.  When the exponent is in the range [0..1), raising x to the exponent also yields a number in [0..1).  This is essentially gamma correction as used in image processing (by the way, dotImage has a GammaCommand to do just this image transform).  A gamma adjusted version of Random would look like this:

public class GammaRandom : DelegatedRandom
{
    private double _gamma;
    public GammaRandom(double gamma)
    {
        if (gamma <= 0) throw new ArgumentOutOfRangeException("gamma");
        _gamma = gamma;
    }
    protected override Func<double, double> Transform
    {
        get { return r => Math.Pow(r, _gamma); }
    }
}

If gamma is < 1, the weighting is greater on the lower end.  If gamma > 1, the weighting is more on the upper end.  You can also do this with trig functions.  Sin(x) in the range [0..π/2) returns a value in the range [0..1), so we can use that as well:

public class SinRandom : DelegatedRandom
{
    private static double pihalf = Math.PI / 2;
    protected override Func<double, double> Transform
    {
        get { return r => Math.Sin(r * pihalf); }
    }
}

DelegatedRandom gives you a nice little tool to play with random distributions.  Gaussian, anyone?