Proportional random number

Problem Statement:

Given an array of unsorted positive integers, return randomly an integer from the array, such that the probability of choosing the integer is linearly proportional to its value. For example, if the array is [1,2], \(2\) should be returned twice as often as \(1\).

I found it easier to solve this problem by first mapping it to something in the real life.

Imagine you have \(n\) pieces of string, each of a certain length, and your task is the same - to choose a piece of string with a probability proportional to its length. Lay down all your pieces of string side by side, and find the total length \(S\). Now pick a number between \(0\) and \(S\) inclusive, and measure out which piece of string this number corresponds to - this is your solution.

Imagine another alternative solution. Each number \(n\) is a large bucket with \(n\) units of liquid. Arrange the buckets in a row, and again find the total amount of liquid you have, \(S\). Pick a random number \(r\) between \(0\) and \(S\) inclusive. Starting from the leftmost bucket, start pouring out water until you pour out \(r\) units of liquid. When that happens, the bucket you are working with is your number.

Translating the above to code is relatively easy.

def prop_random(r):
  S = sum(r)
  i = -1
  rand = random.randint(1,S)
  while(rand > 0):
    i = i + 1
    rand = rand - r[i]

  return r[i]

We test the code with the list [5,2,1,4,3] and \(100000\) iterations, and see whether we get the expected results.

mm = dict()

N = 100000
for i in range(N):
  o = prop_random([5,2,1,4,3])
  if(o in mm):
    mm[o] += 1
  else:
    mm[o] = 1

for a,b in mm.iteritems():
  print a, " --> ", b/float(N)

The result is:

1  -->  0.06667
2  -->  0.13589
3  -->  0.19916
4  -->  0.26537
5  -->  0.33291

which confirms that our algorithm is correct.

The code is available as a gist here