Coin Tossing

This is an example that everyone has seen at some point in their studies. Let us take a formal view on it. If we toss a coin $k$ times, we represent an outcome by a string $s \in \{0,1\}^k$ where $s_i = 1$ means that the $i$-th coin toss turns up head.

Define $\Omega_n = \{0,1\}^n$ (so we have $|\Omega_n| = 2^n$). For $s \in \Omega_n$, define $k(s) = \sum_i s_i$ (so this counts the number of heads occurring in $s$). For $p \in (0,1)$, define the function $f_p: \Omega_n \rightarrow {\mathbb R}$ by

$f_p(s) = p^{k(s)} (1-p)^{n - k(s)}$

Theorem 37

$(\Omega_n, f_p)$ defines a probability space.

Let us show this kind of proof once 🙂 (after this, it is your own exercise).

Proof:

We just need to show that $\sum_s f_p(s) = 1$. This can be done by induction on $n$. The base case when $n=1$ is obvious (i.e., $(1-p) + p=1$). Now assume that it is true that $(\Omega_n, f_p)$ is a probability space. Consider $(\Omega_{n+1}, f_p)$, and we want to prove that $\sum_{s \in \Omega_{n+1}} f_p(s) = 1$. We break the strings in $\Omega_{n+1}$ into two sets $Z$ and $O$ containing those strings where the last bit is zero and one respectively. Therefore,

$\sum_{s\in \Omega_{n+1}} f_p(s) = \sum_{s \in Z} f_p(s) + \sum_{s \in O}f_p(s)$

We will see that the first sum is $(1-p)$ and the second is $p$, which would imply our claim. For $s \in Z$, if we write $s = t 0$ (the last bit is zero), we have $f_p(s) = p^{k(s)} (1-p)^{n+1- k(s)} = f_p(t)(1-p)$. Therefore, the sum $\sum_{s \in Z} f_p(s) = (1-p) \cdot (\sum_{t \in \Omega_n} f_p(t)) = (1-p)$ (using the induction hypothesis). The second equality is left as an exercise.

Exercise 85

Finish the previous proof, that is, prove that $\sum_{s \in O}f_p(s) = p$ in the induction step.

Notice that when $p = 1/2$, this is a uniform distribution. Let us see some examples of events in this probability space.

• Consider the event $A$ of getting the same results in $n$ coin tosses. So $A = \{0^n, 1^n\}$ and the probability is $f_p(A) = p^n + (1-p)^n$. (obtained by summing the probabilties of atomic events).

• Now the event $B$ consists of the outcomes that have exactly two heads, i.e., $B= \{s: k(s) = 2\}$. Each $s$ occurs with probability $p^2 (1-p)^{n-2}$, so we have $f_p(B) = {n \choose 2} p^2 (1-p)^{n-2}$.

• We can further define $C_r$ to consist of outcomes with exactly $r$ heads, so this partitions $\Omega_n$ into $\bigcup_r C_r$, where the probability of event $C_r$ is ${n \choose r} p^r (1-p)^{n-r}$.

Now let us discuss a bit how our intuition about probabilities fits into the picture here. For instance, if we want to calculate the probability that the first and second coin tosses are the same, we would immediately focus on just two tosses and say that this is $p\cdot p + (1-p)\cdot (1-p)$ (we use the fact that the first and second tosses are independent, which we haven't defined here yet).

In the exercises below, you will be asked to do these calculations using only the definitions we have seen so far, i.e., you can only use the fact that the probability of an event is the sum of its atomic events.

Exercise 86

Calculate the following probabilities:

• View a string as $s = s_1 s_2 \cdots s_n \in \Omega_n$. Prove that ${\mathbb P}[s_i =1] = p$.

• Let $i \neq j$.

  • Prove that ${\mathbb P}[s_i = 1 \land s_j = 1] = p^2$.
  • Prove that ${\mathbb P}[s_i = s_j] = p^2 + (1-p)^2$.

The following is a bit more difficult.

Exercise 87

Consider the case when $p=1/2$. What is the probability that the number of heads is even?

Hint: You may benefit from the binomial theorem.