weighted biased dice roll

sys0p has asked for the wisdom of the Perl Monks concerning the following question:

I've been asked to come up with an algorithm to do a biased weighted dice roll function, I couldn't do it from the top of my head and after searching how to do it I've stumbled upon this piece of code from O'Reilly's Perl Cookbook:

sub biased_die_roll {
    my %dist = (1=>0.01,2=>0.01,3=>0.01,4=>0.01,5=>0.48,6=>0.48);
    my ($key, $weight);

    my $rand = rand;
    while ( ($key, $weight) = each %dist ) {
             return $key if ($rand -= $weight) < 0;
    }
}
[download]

As I've verified, this function indeed does what it's supposed to but I can't get my head around the inner while... For each dice face value ($key), if $rand = $rand - $weight is below zero, return $key. From what I understand, it will always produce less than zero output at the return line statement.

What's going on?

Update: I was misinterpreting the weighted distribution hash, using actual weights instead of probabilities, once I realized that, it was easy to understand the algorithm.

Comment on weighted biased dice roll Download Code

Replies are listed 'Best First'.
Re: weighted biased dice roll (bugs) by tye (Sage) on Aug 05, 2014 at 17:41 UTC
That code is wrong in three ways, as far as I can tell. The biggest problem is that you need to pass the sum of all of the weights to rand(). If the weights happen to all add up to 1, then rand() with no arguments is fine. (Update: The original code didn't have weights that added up to 1.) You don't really need the outer while(1) loop. Instead, just return the last item even if subtracting its weight from $rand doesn't quite get you to 0. Using each means you need to reset the iterator, preferably both before and after. No, none of that is necessarily going to help you understand the code. I might take a stab at explaining at a later time, if nobody else does. :) - tye	[reply]
Re^2: weighted biased dice roll (bugs) by ikegami (Patriarch) on Aug 05, 2014 at 17:49 UTC
Each call of the function iterates over a new hash, so the iterator doesn't need resetting.	[reply]
Re^2: weighted biased dice roll (bugs) by sys0p (Novice) on Aug 05, 2014 at 17:47 UTC
I have figured it out, thanks anyway!	[reply]
Re: weighted biased dice roll by ikegami (Patriarch) on Aug 05, 2014 at 17:37 UTC
[No longer applies] The code you posted doesn't compile. Once that's fixed, it still doesn't work. Because all of weights are larger than the maximum value returned by `rand` (slightly less than one), It always prints the first value returned by `each`.	[reply] [d/l] [select]
Re^2: weighted biased dice roll by sys0p (Novice) on Aug 05, 2014 at 17:42 UTC
I've just figured it out. And updated the question to a compiling state. Thank you anyways! The problem was misinterpretation of the weights.	[reply]