Opensource Implementation of the Alias Method

I am doing a project at the moment, and in the interest of code reuse, I went looking for a library that can perform some probabilistic accept/reject of an item:

i.e., there are three people (a, b c), and each of them have a probability P{i} of getting an item, where p{a} denotes the probability of a. These probabilities are calculated at run time, and cannot be hardcoded.

What I wanted to do is to generate one random number (for an item), and calculate who gets that item based on their probability of getting it. The alias method (http://books.google.com/books?pg=PA133&dq=alias+method+walker&ei=D4ORR8ncFYuWtgOslpVE&sig=TjEThBUa4odbGJmjyF4daF1AKF4&id=ERSSDBDcYOIC&output=html) outlined here explained how, but I wanted to see if there is a ready made implementation so I wouldn't have to write it up.

From stackoverflow Chii

• Would something like this do? Put all p{i}'s in the array, function will return an index to the person who gets the item. Executes in O(n).

  public int selectPerson(float[] probabilies, Random r) {
   float t = r.nextFloat();
   float p = 0.0f;
  
   for (int i = 0; i < probabilies.length; i++) {
    p += probabilies[i];
    if (t < p) {
     return i;
    }
   }
  
   // We should not end up here if probabilities are normalized properly (sum up to one)
   return probabilies.length - 1;  
  }
  

  EDIT: I haven't really tested this. My point was that the function you described is not very complicated (if I understood what you meant correctly, that is), and you shouldn't need to download a library to solve this.

  From finalman

• i just tested out the method above - its not perfect, but i guess for my purposes, it ought to be enough. (code in groovy, pasted into a unit test...)

      void test() {
          for (int i = 0; i < 10; i++) {
              once()
          }
      }
      private def once() {
          def double[] probs = [1 / 11, 2 / 11, 3 / 11, 1 / 11, 2 / 11, 2 / 11]
          def int[] whoCounts = new int[probs.length]
          def Random r = new Random()
          def int who
          int TIMES = 1000000
          for (int i = 0; i < TIMES; i++) {
              who = selectPerson(probs, r.nextDouble())
              whoCounts[who]++
          }
          for (int j = 0; j < probs.length; j++) {
              System.out.printf(" %10f ", (probs[j] - (whoCounts[j] / TIMES)))
          }
          println ""
      }
      public int selectPerson(double[] probabilies, double r) {
          double t = r
          double p = 0.0f;
          for (int i = 0; i < probabilies.length; i++) {
              p += probabilies[i];
              if (t < p) {
                  return i;
              }
          }
          return probabilies.length - 1;
      }
  
  outputs: the difference betweenn the probability, and the actual count/total 
  obtained over ten 1,000,000 runs:
    -0.000009    0.000027    0.000149   -0.000125    0.000371   -0.000414 
    -0.000212   -0.000346   -0.000396    0.000013    0.000808    0.000132 
     0.000326    0.000231   -0.000113    0.000040   -0.000071   -0.000414 
     0.000236    0.000390   -0.000733   -0.000368    0.000086    0.000388 
    -0.000202   -0.000473   -0.000250    0.000101   -0.000140    0.000963 
     0.000076    0.000487   -0.000106   -0.000044    0.000095   -0.000509 
     0.000295    0.000117   -0.000545   -0.000112   -0.000062    0.000306 
    -0.000584    0.000651    0.000191    0.000280   -0.000358   -0.000181 
    -0.000334   -0.000043    0.000484   -0.000156    0.000420   -0.000372
  

  From Chii