Implementing a probability distribution function in Java

Question

I am trying to implement a probability distribution function in java where it returns an i th record in an array with probability:

F i = 6i(ni) / (n 3 - n)

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

P 1 = 3/10, P 2 = 4/10, P 3 = 3/10, P 4 = 0

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

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

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

s -1, so it does not select the last element (i.e., P _n = 0, as in the above formula).

Anyone with ideas or tips for implementing it?

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 have to do discrete sampling of the inverse transform . 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. 

Answer 3

To do this, you want to divide the range [0, 1] into regions with the desired size. So in this case:

 0 -> 0.0 - 0.3 1 -> 0.3 - 0.7 2 -> 0.7 - 1.0 3 -> 1.0 - 1.0 

Then create a random number with Math.random() and look at what interval it falls.

In general, you want to do something like the following pseudocode:

 double r = Math.random(); int i = -1; while (r >= 0) { i++; r -= F(i); } // i is now the value you want. 

You generate a value on [0, 1], and then subtract the size of each interval until you drop below 0, after which you find your random value.

Answer 4

You can try using a navigation map with probability distribution. Unlike regular maps, NaviableMap defines the absolute order over its keys. And if the key is not on the map, it can tell you which is the closest key, or which is the smallest key, which is greater than the argument. I used ceilingEntry , which returns a map entry with the smallest key that is greater than or equal to the given key.

If you use TreeMap as your implementation of NavigableMap, then a distribution search with many classes will be faster because it performs a binary search rather than starting with the first key and then checking each key in turn.

Another advantage of NaviableMap is that you get a data class that you are directly interested in, and not an index to another array or list that can make the code clean.

In my example, I used BigDecimals, since I don’t particularly like using floating point numbers, since you cannot specify the precision you need. But you can use floats or doubles or something else.

 import java.math.BigDecimal; import java.math.RoundingMode; import java.util.Arrays; import java.util.NavigableMap; import java.util.TreeMap; public class Main { public static void main(String[] args) { String[] classes = {"A", "B", "C", "D"}; BigDecimal[] probabilities = createProbabilities(classes.length); BigDecimal[] distribution = createDistribution(probabilities); System.out.println("probabilities: "+Arrays.toString(probabilities)); System.out.println("distribution: "+Arrays.toString(distribution)+"\n"); NavigableMap<BigDecimal, String> map = new TreeMap<BigDecimal, String>(); for (int i = 0; i < distribution.length; i++) { map.put(distribution[i], classes[i]); } BigDecimal d = new BigDecimal(Math.random()); System.out.println("probability: "+d); System.out.println("result: "+map.ceilingEntry(d).getValue()); } private static BigDecimal[] createDistribution(BigDecimal[] probabilities) { BigDecimal[] distribution = new BigDecimal[probabilities.length]; distribution[0] = probabilities[0]; for (int i = 1; i < distribution.length; i++) { distribution[i] = distribution[i-1].add(probabilities[i]); } return distribution; } private static BigDecimal[] createProbabilities(int n) { BigDecimal[] probabilities = new BigDecimal[n]; for (int i = 0; i < probabilities.length; i++) { probabilities[i] = F(i+1, n); } return probabilities; } private static BigDecimal F(int i, int n) { // 6i(ni) / (n3 - n) BigDecimal j = new BigDecimal(i); BigDecimal m = new BigDecimal(n); BigDecimal six = new BigDecimal(6); BigDecimal dividend = m.subtract(j).multiply(j).multiply(six); BigDecimal divisor = m.pow(3).subtract(m); return dividend.divide(divisor, 64, RoundingMode.HALF_UP); } }