Algorithm for an arbitrary number of nested for loops to calculate a discrete probability distribution

Tadeo Hepperle 0
Viewed 22

This question is not specific to any programming language

Let's say I have a List<Hashmap<int,float>>, where each Hashmap<int,float> represents the discrete probability distribution of a random variable. For example the dsitribution of a fair coin could be represented by the Hashmap {0:0.5, 1:0.5} (head=1,tail=0). If we have n discrete random variables, we could store their distributions as a List of n Hashmaps.

Question: How could we now iterate over this List to obtain the distribution of the sum of the random variables?

More Information: For e.g. three random variables X,Y,Z, where we want the distribution of W=X+Y+Z we could do something like this:

hashmap_w = {}
for (kx,vx) in hashmap_x:
    for (ky,vy) in hashmap_y:
        for (kz,vz) in hashmap_z:
            k = kx+ky+kz
            v = vx*vy*vz
            if(hashmap_w.contains_key(k)):
                hashmap_w[k]+=v
            else:
                hashmap_w[k]=v

How could we generalize this code to not only work for 3 random variables but for an arbitrary number?

distribution probability algorithm
1 Answers

Use dynamic programming.

sum_prob = {0: 1}
for hashmap in hashmaps:
    next_sum_prob = {}
    for kh, vh in hashmap.items():
        for ks, vs in sum_prob.items():
            k = kh + ks
            v = vh * vs
            if k in next_sum_prob:
                next_sum_prob[k] += v
            else:
                next_sum_prob[k] = v
    sum_prob = next_sum_prob
btilly0
Related