Lesson 9

The formula \(\Pr[A \mid B]=\frac{\Pr[A \cap B]}{\Pr[B]}\) can be rewritten as: \[\Pr[A \cap B] = \Pr[B] \cdot \Pr[A \mid B] \ .\] Then it reads as follows: the probability of both events \(A\) and \(B\) occurring is equal to the probability of event \(B\), multiplied by the conditional probability of event \(A\) given \(B\). (In fact, we have already used conditional probability when drawing trees: when several edges emerge from the next vertex, the sum of probabilities on which is equal to one, these are precisely conditional probabilities! The condition in this case is that we arrived at this vertex.) This naturally generalizes to an arbitrary number of events. Namely, for any \(n\) events \(A_{1}, \dotsc, A_{n}\), it holds that \[\Pr[A_{1} \cap \dotsb \cap A_{n}]=\Pr[A_{1}]\cdot\Pr[A_{2} \mid A_{1}] \cdot \Pr[A_{3} \mid A_{1} \cap A_{2}] \dotsb = \prod_{i \in [n]}\Pr\left[A_{i} \mid \bigcap_{j \in [i-1]}A_{j}\right]\] Of course, the formula remains valid for conditional probabilities: \[\Pr[A_{1} \cap \dotsb \cap A_{n} \mid B] = \prod_{i \in [n]}\Pr\left[A_{i} \mid \left(B \cap \bigcap_{j \in [i-1]}A_{j}\right)\right].\]