Random weighted choice

Question

Consider the class below that represents a Broker:

public class Broker {     public string Name = string.Empty;     public int Weight = 0;      public Broker(string n, int w)     {         this.Name = n;         this.Weight = w;     } } 

I'd like to randomly select a Broker from an array, taking into account their weights.

What do you think of the code below?

class Program     {         private static Random _rnd = new Random();          public static Broker GetBroker(List<Broker> brokers, int totalWeight)         {             // totalWeight is the sum of all brokers' weight              int randomNumber = _rnd.Next(0, totalWeight);              Broker selectedBroker = null;             foreach (Broker broker in brokers)             {                 if (randomNumber <= broker.Weight)                 {                     selectedBroker = broker;                     break;                 }                  randomNumber = randomNumber - broker.Weight;             }              return selectedBroker;         }           static void Main(string[] args)         {             List<Broker> brokers = new List<Broker>();             brokers.Add(new Broker("A", 10));             brokers.Add(new Broker("B", 20));             brokers.Add(new Broker("C", 20));             brokers.Add(new Broker("D", 10));              // total the weigth             int totalWeight = 0;             foreach (Broker broker in brokers)             {                 totalWeight += broker.Weight;             }              while (true)             {                 Dictionary<string, int> result = new Dictionary<string, int>();                  Broker selectedBroker = null;                  for (int i = 0; i < 1000; i++)                 {                     selectedBroker = GetBroker(brokers, totalWeight);                     if (selectedBroker != null)                     {                         if (result.ContainsKey(selectedBroker.Name))                         {                             result[selectedBroker.Name] = result[selectedBroker.Name] + 1;                         }                         else                         {                             result.Add(selectedBroker.Name, 1);                         }                     }                 }                   Console.WriteLine("A\t\t" + result["A"]);                 Console.WriteLine("B\t\t" + result["B"]);                 Console.WriteLine("C\t\t" + result["C"]);                 Console.WriteLine("D\t\t" + result["D"]);                  result.Clear();                 Console.WriteLine();                 Console.ReadLine();             }         }     } 

I'm not so confident. When I run this, Broker A always gets more hits than Broker D, and they have the same weight.

Is there a more accurate algorithm?

Thanks!

Answer 1

Your algorithm is nearly correct. However, the test should be < instead of <=:

if (randomNumber < broker.Weight) 

This is because 0 is inclusive in the random number while totalWeight is exclusive. In other words, a broker with weight 0 would still have a small chance of being selected – not at all what you want. This accounts for broker A having more hits than broker D.

Other than that, your algorithm is fine and in fact the canonical way of solving this problem.