Generic algorithm for probability any propositional formula

[Aldebaran2]

Ciao all,

Is there a generic algorithm to compile the probability P(A)
of any propositional formula A (provided that we have only the probability of each atoms constituting A)?

For example, we have that A= a1 and not (a2 and a3 and ( not a4 and not a5 and not a6 ..) , or any other complicated formula.
The an are independant here!

I know pr(a1), pr(a2)... and so on...

Is there an algorithm to compute pr(a1 and not (a2 and a3 and ( not a4 and not a5 and not a6 ..) ) ?

 

[genneth]

Just repeatedly apply Bayes' rule. But you will have difficulty usually coming up with numbers for all of the required terms.

 

[Aldebaran2]

Applying Bayes.

Thank you for the advice! I shall try it.

What did you exactly mean by:

"you will have difficulty usually coming up with numbers for all of the required terms"


?

 

[genneth]

Essentially you'll need all the cross probabilities -- all the and's and or's of the all the possible pairs of propositions. Usually, these numbers aren't easy to come up with.

 

[Aldebaran2]

I do not get it.

Could you provide an example?

or do you have a reference where that is well explained ( I am not an expert of Probabiliies)?

 

[genneth]

Any standard probabilities textbook would be a good place to start. My personal favourite is Probability Theory by E.T. Jaynes.

 

[EnumaElish]

Well, if the a's are independent, that simplifies the problem considerably.

 

[Aldebaran2]

Ciao EnumaElish,

Do you have an algorithm? eventually a reference to it?

 

[genneth]

Ciao EnumaElish,

Do you have an algorithm? eventually a reference to it?

I'm fairly sure nothing beyond a textbook would even bother to spell it out:

given two independent events, A and B, pr(A and B) = pr(A) pr(B), pr(A or B) = pr(A) + pr(B). Generalise in the obvious way for more than 2 events.

 

[EnumaElish]

Ciao EnumaElish,

Do you have an algorithm? eventually a reference to it?

What exactly do you mean by an "algorithm"? For a basic problem like this you can write one in any programming language; e.g. Basic.

See http://www.nist.gov/dads/ and http://mathworld.wolfram.com/Algorithm.html