🔒 Locked

Probability Problem

Started by intrest86 Sep 23, 2008 at 9:11 PM 3 replies 750+ views

Original Post

Sep 23, 2008 at 9:11 PM

Hey everyone, I've got a probability problem that has been stumping me for the last two days, and I'm hoping you can help. If you want to know what it is for, I'm writing a barcode decoder for fun (Its actually been pretty interesting so far). Anyways, the problem is this: Given multiple finite discrete random variables {X,Y,Z}, how do you enumerate the possible combinations from most probable to least probable? For example, the most probable combination is just the set of most probable outcomes for each variable. But how do you find the second most probable, and then the third, etc etc? I've tried searching for a solution, but I'm not narrowing down my search very well. Any ideas for the problem, or what to look into?

ToohrVyk

Sep 24, 2008 at 3:03 AM

The easiest way is to enumerate all possibilities and then sort them by probability.

Should that prove too difficult, remember that (a,b,c) is more likely than (a',b',c') if p(a) ≥ p(a') and p(b) ≥ p(b') and p(c) ≥ p(c'), meaning that at any given point in time, the set where you have to look for the next possibility is comprised only of the (a,b,c) triples such that either (a+1,b,c), (a,b+1,c) or (a,b,c+1) have already been stored in the list (assuming that you've sorted your events by probability). Or, if you prefer, store a priority queue of possibilities sorted by probability, and whenever you pop (a,b,c) off the queue, add (a-1,b,c), (a,b-1,c) and (a,b,c-1) to the queue (ignoring duplicates, of course).

clb

Sep 24, 2008 at 3:12 AM

You seem to be interested in all the cases, so the simplest idea is to just create a list that has all the possible joint events (x,y,z) along with their probabilities P(X=x)*P(Y=y)*P(Z=z). Then you just sort the list descending to probability.

If you don't want to generate the whole list for the joint probability function, you could generate three lists for X, Y and Z, and then sort those by descending probability. Then the following holds:
(X[0], Y[0], Z[0]) is the most probable event.

One of (X[1], Y[0], Z[0]), (X[0], Y[1], Z[0]) or (X[0], Y[0], Z[1]) is the secondmost probable event.

Generalizing the above (it gets a bit more complicated),
the n'th most probable event is of the form (X, Y[j], Z[k]), where i+j+k <= n-1. (zero-based indexing on i,j,k and one-based indexing on n).

So, to find the 4th most probable event, you'd need to generate a list of at most 4^3 entries. Depending on the actual probabilities and that the lists X, Y and Z are descending by the probability, you could get away with less. The idea is to rely on the property that the mapping (i,j,k) -> P(X=X)*P(Y=Y[j])*P[Z=Z[k]) is nonincreasing with respect to the partial ordering (i,j,k) < (I,J,K) iff (i < I or j < J or k < K) and i <= I and j <= J and k <= K.

intrest86

Sep 24, 2008 at 8:06 AM

Thanks guys, I arrived at the same idea too. I really couldn't check all possibilities, just because there are 10^11. Most of those have negligible probability, so I needed to find only those with a chance over an arbitrary threshold.

alvaro

Sep 24, 2008 at 11:18 AM

The problem of generating all combinations with probability over a certain threshold is easier to code up than getting them in order. For instance, you can do this (assume all distributions list their events from most likely to least likely):

for(x=0; x<X.n_outcomes(); ++x) {  double Px = X.P(x);  if(Px < threshold)    break;  for(y=0; y<Y.n_outcomes(); ++y) {    double Pxy = Px * Y.P(y);    if(Pxy < threshold)      break;    for(z=0; z<Z.n_outcomes(); ++z) {      double Pxyz = Pxy * Z.P(z);      if(Pxyz < threshold)        break;      do_something(x,y,z);    }  }}

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.