1. Conditional Probability

1.1 To understand conditional probability, we need to know the definition of event first.

An event A is a subset of a sample set S. Each elementary event is a possible outcome of an experiment.

1.2 Probability Axioms

a.  P{A} >= 0          // P{A} denotes the probability that event A occured

b.  P{S} = 1            

c.  P{A} + P{!A} = 1    // P{!A} denotes the probability that event A didn't not occur.

1.3 Conditional Probability

Given two events A,B in a sample set S, the conditional probability of A given B is P{A | B}    

// P{A | B} is called the conditional probability of A given B. It means the probability of A occurs under the condition that B has already occur. 

P{A | B} = P{A n B} / P{B}  if P{B} != 0      // P{A n B} denotes the probability of A intersect B, which means both event A and event B occurs

1.4 Two events A, B are independent  ⇔  P{A n B} = P{A} P{B}

so if two events A, B are independent, we can also write P{A | B} = P{A}

1.5 A finite number of events A1,A2,A3,...,Am are mutually independent ⇔

P{A1 n A2 n A3 n ... Am} = ¶ P{Ai}      // P{A1}P{A2}P{3}...P{Am}

Week 4 originally included videos that reviewed probability. Those have been removed. Week 4 now focuses on graphs and the random contraction algorithm. The proof of the probability of success of that algorithm depends on knowledge of probability as described in the earlier post. We won't be asking you to reproduce that proof. But it won't hurt you to understand it.