Re: random toss of discrete values with (integer) probability distribution

[Dirk Laurie <dirk.laurie@...>]

> The problem is, how to toss a choice in a set of discrete values, each
> having a relative probability (represented by an integer, sometimes a %age).

If the total of the integers is small, you make a table with as many copies
of each value as its probability and generate a random index.

Otherwise, it does not help that you have integers, they may as well be
any numbers.  You make two lists: one for the values V, the other for the
probabilities P.

Then

local n=#P
for i=2,n do P[i]=P[i]+P[i-1] end  -- cumulative counts
for i=1,n do P[i]=P[i]/P[n] end  -- range is now [0,1]

function toss(P,V)
local lo,hi=0,#P
local r=math.random()  -- random number in [0,1)
while hi-lo>1 do -- binary search
   local m=math.floor((hi+lo)/2)
   if r>=P[m] then lo=m else hi=m end
end -- now P[hi-1] <= r < P[hi]
if V then return V[hi] else return hi end
end