Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
How to calculate conditional probabilities with as few loops as possible?

Subject: How to calculate conditional probabilities with as few loops as possible?

From: Dongyang

Date: 10 Nov, 2013 05:53:06

Message: 1 of 3

Hi All,
I guess there must be an algorithm dealing my problem but I know little about algorithms or CS programming. Please be specific to a rookie like me.
Here is the basic problem:
I want to calculate the probability distribution (discrete) of A, Prob(A).
Using conditional probabilities, I need to solve:
Prob(A)=Prob(A|B,C,D)*Prob(B|C,D)*Prob(C|D)*Prob(D)
A,B,C,D are dependent and A can only be solved in the above fashion in my problem. I know the expressions for each terms above.
So I wrote something that might give programmers a heart-attack:
-------------------------------------------------------
result=0;
For a = 0 to max_value_A_can_take
     For b = max_value_B_can_take
           For c= max_value_C_can_take
                 For d=max_value_D_can_take
                   result=result + Prob(A=a|B=b,C=c,D=d)*Prob(B=b|C=c,D=d)*Prob(C=c|D=d)*Prob(D=d)
                end
           end
     end
end
-----------------------------------------------------------

1. I don't know if parallel "for loop" works, because a,b,c,d are not independent.
2. I don't know how to do it with fewer loops
3. In my real program, each iteration involves several functions that do the above. The max values A,B,C,D can take grows by iteration.

I would really appreciate it if someone could be specific about how to improve the efficiency of these code. I asked many of my CS, EE friends, but they are all vague about how to do this. I know I must kill loops, but how?


Any help/idea is appreciated!!
Thank you all very much!
Ester

Subject: How to calculate conditional probabilities with as few loops as possible?

From: Roger Stafford

Date: 10 Nov, 2013 18:03:06

Message: 2 of 3

"Dongyang" wrote in message <l5n702$dsh$1@newscl01ah.mathworks.com>...
> I want to calculate the probability distribution (discrete) of A, Prob(A).
> Using conditional probabilities, ......
> .......
> I would really appreciate it if someone could be specific about how to improve the efficiency of these code. .......
- - - - - - -
  To begin with, your summation process is incorrect for getting the distribution of A. You should be storing the sum in 'result' in some array after each step in the outer 'a' loop and then resetting 'result' to zero. As it stands, you would arrive at the not very surprising conclusion that the final value of the variable 'result' equals 1 (provided your conditional probabilities are correct.) To correct this your code should look like this:

 for a = 0 to max_value_A_can_take
  result = 0; % Reset this for each new value of 'a'
  for b = ...
   for c = ...
    for d = ...
     ...
    end
   end
  end
  %Store 'result' in a distribution array for A for each value of 'a'
 end

  As for being able to eliminate some or all of these for-loops, you should be aware that sometimes nested for-loops constitute the very best way to solve a problem. It all depends on the algorithms involved. It is impossible to determine whether this is true or not in your case without your telling us what the conditional probability expressions look like. There may be methods that can greatly shortcut the computation times but that depends on the nature of your conditional probability space.

Roger Stafford

Subject: How to calculate conditional probabilities with as few loops as possible?

From: Dongyang

Date: 10 Nov, 2013 21:21:12

Message: 3 of 3

Hi Roger and others who might be reading this,
Thanks for the timely reply. Your first suggestion was a great point that I forgot to wrote in my pseudocode - that's the code I am using.

Regarding to your second suggestion, here are the expressions for each piece of the conditional probabilities:

A= max(0, B+C-D)
Prob(A=a|B=b,C=c,D=d)=Prob(max(0, b+c-d)=a) --> which is either 1 or zero

B=min(L, C+D), where L is an independent external Poisson random variable
Prob(B|C,D)=Prob(min(L,c+d)=b) --> a mix of 1 and truncated Poisson

Prob(C|D)--> C|D=d follows a binomial distribution (d,p), p is given

Prob(D)=Prob(D_iteration_t) --> recursively depends on its own distribution in previous iteration Prob(D_iteration_t-1)

So you see, there is no easy close-form expression. A,B,C,D are dependent. Most suggestions I got from friends were exploring independency among variables, so as to eliminate loops, however, as you can see, they are all related in a complicated way.

In general, if using
Prob(A|B,C,D)*Prob(B|,C,D)*Prob(C|D)*Prob(D) to calculate Prob(A), and A,B,C,D are Not independent, is there a less-loopy way?
Or what are the common ways to eliminates loops, when independence is out of the picture?


Thank you all!
Ester

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us