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?