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

[Rena <hyperhacker@...>]

On Fri, Oct 26, 2012 at 1:22 PM, spir <denis.spir@gmail.com> wrote:
> Hello,
>
> This is more an algorithmic question than a Lua-related one, however I
> thought others may be interested, since it touches a recurring issue in
> game-programming, i guess.
>
> 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).
> To make things more concrete, say there are 3 choices a,b,c, which
> probability law (distribution) looks like this:
>
>           X
>         X X
>         X X X
>         -----
>         a b c
>
> What we want is toss according to these relative probabilities.
>
> A simple solution is to make a "sampling set"
>         {a,a, b,b,b, c}
> and randomly toss in there.
>
> However, this may be very costly due to the construction of the set-table.
> It's only good when tossing multiple times from the same set, which is not
> the general case. In my case, values are terrain codes for a map generator.
> I want each tile to be tossed according to user-given probabilities for each
> terrain, but above all taking into account types of already defined
> surrounding tiles, and weighted by a homogeneity factor (which multiplies
> cardinality of each terrain code of defined neighbour tiles). This means a
> sampling set should be constructed for each tile, and it can be big (0 <=
> homogeneity <= 100, meaning max size is 600 for a hex map).
> I could have a table of max size, and just override its items, then toss
> among actual number of codes. But this still seems a bit stupidly costly.
>
> Another solution I thought at is to use a multiset, with cardinalities
> represents relative probabilities of codes:
>         {{a,2}, {b,3}, {c,1}}
> Actually, if codes are plain ordinals, then it can just be:
>         {2, 3, 1}       -- sum = 6
> I'd just toss random(6), then iterate on cardinalities (summing on the way)
> until I reach a value >= toss result.
>
> This is the best I could find for now. But I still have the impression of
> missing an obvious point...
> What do you think?
>
> Thank you,
> Denis
>
>

I may be misunderstanding, but if I want to select randomly from a set
like {a, a, a, b, b, c}, what I do is something like:
n = math.random(1,6)
if n == 6 then return c -- 1/6 c
elseif n >= 4 then return b --2/6 b
else return a --3/6 a
end

-- 
Sent from my Game Boy.