随机算法 (Fall 2011)/Conditional Probability

From EtoneWiki
Jump to: navigation, search

Conditional Probability

In probability theory, the word "condition" is a verb. "Conditioning on the event ..." means that it is assumed that the event occurs.

Definition (conditional probability)
The conditional probability that event occurs given that event occurs is

The conditional probability is well-defined only if .

For independent events and , it holds that

It supports our intuition that for two independent events, whether one of them occurs will not affect the chance of the other.

Law of total probability

The following fact is known as the law of total probability. It computes the probability by averaging over all possible cases.

Theorem (law of total probability)
Let be mutually disjoint events, and is the sample space.
Then for any event ,
Proof.
Since are mutually disjoint and , events are also mutually disjoint, and . Then

which according to the definition of conditional probability, is .

The law of total probability provides us a standard tool for breaking a probability into sub-cases. Sometimes, it helps the analysis.

A Chain of Conditioning

By the definition of conditional probability, . Thus, . This hints us that we can compute the probability of the AND of events by conditional probabilities. Formally, we have the following theorem:

Theorem
Let be any events. Then
Proof.
It holds that . Thus, let and , then

Recursively applying this equation to until there is only left, the theorem is proved.