Collections of Events¶

Probability theory is based on the addition and mulitplication rules, both of which we have stated as rules about two events. We have defined joint distributions of two random variables. Our definition of independence, too, refers to two events or two random variables.

But we naturally want to use – and have used – extensions of these results to several events. For example, we have routinely used $$ P(A \cup B \cup C) = P(A) + P(B) + P(C) ~~~ \text{if } A, B, C \text{ are mutually exclusive} $$ when we have found probabilities by partitioning events into three disjoint pieces.

In this chapter we will study a common method of extending results, and develop methods that will allow us to work with collections of events. In doing so we will encounter some classical applications that arise in data science.

The main method of extension that we will use is the method of mathematical induction.

Induction¶

The method of mathematical induction can be used to prove results when:

• you have guessed a result for all positive integers $n$;
• you can prove the result directly for small $n$; and
• you need to prove it for general $n$.

Then the method says that if you can show that the result is true for $n+1$ by assuming the induction hypothesis that it is true for $n$, then your proof is complete.

The method often applies when you find yourself writing, "In the same way," or "$\ldots$" to justify a step in a calculation. Induction can help turn the "$\ldots$" into math.

Here is a quick example from math that has been used already in this course. More examples will appear later in this chapter and in the course.

The Sum of the First $n$ Positive Integers¶

To prove that $$ \sum_{i=1}^n i = \frac{n(n+1)}{2} $$ first notice that the formula can be checked easily for $n=2$. Even checking it for $n=1$ is enough as a "base" case. Now assume the induction hypothesis that the formula is true for $n$ as stated above, and show that it is true for $n+1$. That is, show that $$ \sum_{i=1}^{n+1} i = \frac{(n+1)(n+2)}{2} $$

To show this, notice that

\begin{align*} \sum_{i=1}^{n+1} i &= \sum_{i=1}^n i ~ + ~ (n+1) \\ \\ &= \frac{n(n+1)}{2} ~ + ~ (n+1) ~~~ \text{(induction hypothesis)} \\ \\ &= (n+1)\big{(} \frac{n}{2} + 1\big{)} \\ \\ &= \frac{(n+1)(n+2)}{2} \end{align*}