Generic algorithm for probability any propositional formula

Click For Summary

Discussion Overview

The discussion revolves around the question of whether there exists a generic algorithm to compute the probability of a propositional formula based on the probabilities of its constituent atomic propositions. The scope includes theoretical aspects of probability and its application to propositional logic.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested

Main Points Raised

  • One participant inquires about a generic algorithm to compute the probability P(A) of a propositional formula A, given the probabilities of its atomic components.
  • Another participant suggests applying Bayes' rule but notes the challenge of obtaining necessary cross probabilities for the terms involved.
  • A follow-up question seeks clarification on the difficulties mentioned regarding obtaining cross probabilities.
  • It is pointed out that if the atomic propositions are independent, the problem simplifies significantly.
  • One participant requests an example or reference to better understand the application of the concepts discussed.
  • Another participant recommends a standard probabilities textbook as a resource for further learning.
  • There is a suggestion that the basic rules of probability for independent events can be generalized to compute probabilities for more than two events.
  • A participant questions the definition of an "algorithm" in this context and suggests that a simple algorithm could be written in any programming language.

Areas of Agreement / Disagreement

Participants express differing levels of understanding regarding the application of Bayes' rule and the concept of independence in probability. There is no consensus on a specific algorithm, and the discussion remains unresolved regarding the best approach to compute the probabilities.

Contextual Notes

The discussion highlights limitations in the availability of cross probabilities and the potential complexity of the problem when not all probabilities are easily accessible. The need for clarity on what constitutes an algorithm in this context is also noted.

Aldebaran2
Messages
6
Reaction score
0
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 independent 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 ..) ) ?
 
Physics news on Phys.org
Just repeatedly apply Bayes' rule. But you will have difficulty usually coming up with numbers for all of the required terms.
 
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"


?
 
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.
 
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)?
 
Any standard probabilities textbook would be a good place to start. My personal favourite is Probability Theory by E.T. Jaynes.
 
Well, if the a's are independent, that simplifies the problem considerably.
 
Ciao EnumaElish,

Do you have an algorithm? eventually a reference to it?
 
Aldebaran2 said:
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.
 
  • #10
Last edited:

Similar threads

Undergrad Formal derivation of statement from Peano Arithmetic system
  • · Replies 10 ·
Replies
10
Views
2K
Undergrad Combination Formula with a lockout twist
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Combination Formula with a lockout twist
  • · Replies 1 ·
Replies
1
Views
2K
High School The Paradox of 1 – 1 + 1 – 1 + 1 – 1 + …
  • · Replies 5 ·
Replies
5
Views
3K
Graduate Concrete examples of randomness in math vs. probability theory
  • · Replies 11 ·
Replies
11
Views
3K
A discrete-time queue Markov Chain problem
  • · Replies 12 ·
Replies
12
Views
2K
Graduate Getting as close as possible to a solution (system of equations)?
  • · Replies 4 ·
Replies
4
Views
2K
Undergrad Measurement problem in simple experiment
  • · Replies 38 ·
2
Replies
38
Views
6K
Matrix Chain Multiplication: Optimal way of multiplying
  • · Replies 8 ·
Replies
8
Views
3K
Undergrad Understanding extinction probability in simple GWP
  • · Replies 1 ·
Replies
1
Views
3K