[computer-go] [OT] All-integer scalable distribution algorithm.

[Thomas Nelson]

On Tue, 6 Nov 2007, Mike Hill wrote:

> int choose( int range, int degree-of-randomness)
>
> Returns an integer in [0-range] distributed depending on the value of 
> degree-of-randomness.  At degree-of-randomness 100, I want the distribution 
> to be uniform.  At degree-of-randomness 0, I want the distribution to be  -- 
> I don't even know what to call this -- half-of-a-normal-distribution  with 
> the steepness proportionately related to degree-of-randomness.

This seems not so much the degree of randomness as the skew.  Because a 
normal distribution has an infinite continuous range, I don't think that's 
what you want.  You say "half a normal"; is something like a geometric 
distribution close enough?  You might check it out, at least it's 
discrete.

But when I have a problem like this, I tend to use what I think of as the 
"weight, bisect" algorithm.  See if this solves your problem.  Basically, 
skew can go from 0 to infinity, and the higher it is, the steeper the skew 
and the less likely you are to choose 0, the more likely you are to choose 
size-1.

[begin python code]
from bisect import bisect
from random import random

def draw(weights):
     sigma = 0.0
     ps = []
     for p in weights:
         sigma += p
         ps.append(sigma)
     return (ps,random()*sigma)

def choose(size, skew):
     '''
     skew=0 gives uniform distribution
     skew=1 gives linear, skew = 2 quadratic, and so on.
     '''
     weights = [i**skew for i in range(size)]
     return draw(weights)
[end python code]


HTH,
Tom