Math Help Forum - View Single Post - looking for algorithm for weighted random choice

awkward · #2 November 22nd, 2008, 04:28 PM

Quote:

Originally Posted by m3p

The subject line probably doesn't quite call it what it's supposed to be called but, anyway, here's the problem:

Just for the sake of argument, say there are 5 possibilities (each "possibility" represents someone's blog feed for instance.) Over the course of time, each feed receives votes on how interesting it is to the audience reading the feeds.

So, feed1 has received 41 votes, feed2 - 25, feed3 - 14, feed4 - 10, feed5 -8.

What would be the formula for randomly choosing one of the five feeds, while at the same time giving the feeds with a higher number of votes, a better chance at getting selected? In other words, how to randomly choose one of the feeds while factoring in their popularity (or unpopularity, as the case may be.)

Thanks in advance for any replies.

Hi m3p,

If I may generalize your question slightly, I think you are asking for an algorithm for making a random choice from 1 of n objects in such a way that the probability of choosing object $i$ is $p_i$ , where $0 \leq p_i$ and $p_1 + p_2 + ... + p_n = 1$ .

On a computer, one way to do this is to generate a pseudo-random number $u$ from a Uniform(0,1) distribution. Then choose object $m$ where $m$ is the least integer such that
$\sum_{i=1}^m p_i > u$ .

For your example, you would take $p_i$ to be the number of votes for feed $i$ , divided by the total number of votes.