Implementing probability distribution function in Java

Question

I'm trying to implement a probability distribution function in java where it returns the ith entry in the array with probability:

Fi = 6i(n-i) / (n3 - n)

where n is the array length i.e. for an array length 4:

P1 = 3/10, P2 = 4/10, P3 = 3/10, P4 = 0

Note that this function assumes numbering from 1 to n rather 0 to n-1 as in Java.

At the moment I'm just using the uniform distribution i.e.

 int i = (int)(Math.random()*((arraySize)-1));

with the -1 so it doesn't choose the last element (i.e. P_n = 0 as in the above formula).

Anyone with any ideas or tips on implementing this?

Answer 1

double rand = Math.random(); // generate a random number in [0,1]
F=0;
// you test if rand is in [F(1)+..+F(i):F(1)+..+F(i)+F(i+1)] it is in this rnge with proba P(i) and therefore if it is in this range you return i
for (int i=1,i<array.size();i++ ){
   F+=F(i);
   if rand < F
       return i;
}
return array.size(); // you went through all the array then rand==1 (this probability is null) and you return n

Answer 2

This is essentially what thomson_matt says, but a little more formally: You should perform discrete inverse transform sampling. Pseudocode for your example:

p = [0.3, 0.4, 0.3. 0.0]
c = [0.3, 0.7, 1.0, 1.0] // cumulative sum

generate x uniformly in continuous range [0,1]
find max i such that c[i] < x.