Indeed, I missed the fact that N is an accumulated sum where all votes so far are subtracted. That wasn't obvious from the description and the code wasn't concise.

> As far as I know this is pretty much the standard approach

I'm curious to know how my other objection is handled. The order in a Perl hash is random, but fixed during a run. So this algorithm will be biased to some results.

Do you have a link to this "standard approach" discussing the distribution of picks?

My guess is the list must be sorted in ascending order. Or to be more precise that the choice over ascending or descending decides over popular vs unpopular.

> 0..99 will give alligator, 100..179 will give bear, etc., until 540..549 gives jellyfish.

FWIW, the results you give can only be reproduced with a descending sort.

> > > { alligator => 100, bear => 90, cat => 80, ... jellyfish => 10 }

(well almost s/179/189/ )

NB: the OP has uncommented the sort in his code.

> > > # sort { ($votes{$b} <=> $votes{$a}) } #unnecessary

> I'm curious to know how my other objection is handled. The order in a Perl hash is random, but fixed during a run. So this algorithm will be biased to some results.

OK, after a second coffee I finally got my had wrapped around it.

Definition/Interpretation matters:

The random pick $r between from 0..N-1 represents what the voter $r has chosen.

Hence order doesn't matter as long as it is fixed, since a 100 wide interval will always have the same probability of 100/550, no matter where it occurs.˛

But I don't see any intuitive way to invert this interpretation, because $r has not-voted to all other choices.

Assigning "inverted" votes like suggested in your other post might work, as long as they sum up to 550 again°. But the question of the weighting factor and distribution will come up again.

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}

°) respectively N' is corrected.

update

˛) IOW no matter if voters John and Jim swapped their place, their probability to be chosen stays the same.

I'm curious why the order in which the hash is traversed would matter at all. I tried both sorting and shuffling the hash keys on each roll of the dice and the overall distribution of choices remained (approximately) the same. Seems to me that as long as the percentage of votes remains the same, the randomness of the dice ensures that over time it'll land on each animal that percent of the time.

Example when 'popular' shuffles the candidate list each time. (Note that now the distribution of votes isn't linear.)

==> alligator:1000 bear: 900 cat: 800 dog: 700 elephant: 600 fox: 100 
+giraffe:  10 hippo:   1   (Total votes: 4111)
POP alligator: 977 bear: 933 cat: 804 dog: 720 elephant: 571 fox:  99 
+giraffe:   6 hippo:   1   (Total votes: 4111)
[download]

I also tried sorting the candidates in both ascending and descending order. Same result.