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

[Frank Meier-Dörnberg <frank@...>]

Am 26.10.2012 19:22, schrieb spir:
> ... 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.
> ...

Just ti ad-hoc ideas:
So far so good. And from this point, you can
a) sort the card.-table {3, 2, 1}  (and the value table correspondingly 
to {b,a,c})
b) replace the entries in the card.-table by their cumulate sum: 
cumsum-table {3, 5, 6}
then your scan "cumsum >= toss ?" end early with higher probability.

Instead of linear probing,  one can use an heuristic like 
cumsum[toss/sum] as pivot
or one can setup a btree...

(Just ad-hoc ideas)
Cheers
Frank