Distributed probability random number generator

Do this only once:

• Write a function that calculates a cdf array given a pdf array. In your example pdf array is [150,40,15,3], cdf array will be [150,190,205,208].

Do this every time:

• Get a random number in [0,1) , multiply with 208, truncate up (or down: I leave it to you to think about the corner cases) You'll have an integer in 1..208. Name it r.
• Perform a binary search on cdf array for r. Return the index of the cell that contains r.

The running time will be proportional to log of the size of the given pdf array. Which is good. However, if your array size will always be so small (4 in your example) then performing a linear search is easier and also will perform better.

The general approach is to feed uniformly distributed random numbers from 0..1 interval into the inverse of the cumulative distribution function of your desired distribution.

Thus in your case, just draw a random number x from 0..1 (for example with Random.NextDouble()) and based on its value return

• 1 if 0 <= x < 150/208,
• 2 if 150/208 <= x < 190/208,
• 3 if 190/208 <= x < 205/208 and
• 4 otherwise.