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?
CodePudding user response:
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