Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

Re^2: Randomly choosing from a set of alternatives with varying popularity

by ibm1620 (Hermit)
on Mar 29, 2022 at 22:43 UTC ( [id://11142517]=note: print w/replies, xml ) Need Help??


in reply to Re: Randomly choosing from a set of alternatives with varying popularity
in thread Randomly choosing from a set of alternatives with varying popularity

Thank you - I had a hunch reciprocals might be the way to reverse popularity, but wasn't sure the 'popular()' algorithm would work with them. (Was never entirely comfortable with floating point arithmetic :-)
  • Comment on Re^2: Randomly choosing from a set of alternatives with varying popularity

Replies are listed 'Best First'.
Re^3: Randomly choosing from a set of alternatives with varying popularity
by hv (Prior) on Mar 30, 2022 at 01:57 UTC

    Well yeah, me neither: you know where you are with integers. :)

    If it reaches the stage that the maths becomes important, you would certainly want to take a lot more care. One way to do that would be to avoid the simplistic "walk a list of (floating-point) weights" algorithm, and instead work to make each reciprocal exact: for each of the options in turn, give it an exact 1/votes chance to get chosen, and if it fails proceed to the next. On reaching the end of the list without a choice, start again (which doesn't necessarily have to be in the same order).

    Getting an exact "1/votes" chance requires understanding a specific invariant of the RNG, the number of bits that it generates - exposed by perl via use Config; print $Config{randbits}. When something has 3 votes, for example, an RNG that generates 16 bits will slightly favour the value 0 (mod 3) by the ratio 21846:21845:21845. So for each option you would calculate $valid_lim = $votes * int(2**RNGbits / $votes) == 65535 in advance, and then re-roll any random value while ($rand = int(rand(2**$RNGbits))) >= $valid_lim before doing the modulus check choose_me() if ($rand % $votes) == 0, to remove that bias.

    That means doing more work (and using up more of the available entropy), so you won't want to do this unless the vote requires this sort of critical accuracy.

      Point taken! However, given that I'm looking for ways to control the 'silliness' of a dissociated-press algorithm, critical accuracy isn't necessary. :-)

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://11142517]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others chanting in the Monastery: (8)
As of 2024-04-19 12:27 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found