[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- Subject: Re: random toss of discrete values with (integer) probability distribution
- From: Dirk Laurie <dirk.laurie@...>
- Date: Fri, 26 Oct 2012 21:48:36 +0200
> 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