# Many Coin Flips

In this section we are going to consider the number of heads on $n$ coin flips. This thought experiment is going to be a basis for much probability theory! It goes far beyond coin flips.

Say a coin comes up heads with probability $p$. Most coins are fair and as such come up heads with probability $p=0.5$. There are many events for which coin flips are a great analogy that have different values of $p$ so lets leave $p$ as a variable. You can try simulating coins here. Note that H is short for Heads and T is short for Tails. We think of each coin as distinct:

Coin Flip Simulator

Number of flips $n$:
Probability of heads $p$:
Simulator results:

Let's explore a few probability questions in this domain.

## Warmups

What is the probability that all $n$ flips are heads?

Lets say $n=10$ this question is asking what is the probability of getting:
H, H, H, H, H, H, H, H, H, H
Each coin flip is independent so we can use the rule for probability of and with independent events. As such, the probability of $n$ heads is $p$ multiplied by itself $n$ times: $p^n$. If $n=10$ and $p=0.6$ then the probability of $n$ heads is around 0.006.

What is the probability that all $n$ flips are tails?

Lets say $n=10$ this question is asking what is the probability of getting:
T, T, T, T, T, T, T, T, T, T
Each coin flip is independent. The probability of tails on any coin flip is $1-p$. Again, since the coin flips are independent, the probability of tails $n$ times on $n$ flips is $(1-p)$ multiplied by itself $n$ times: $(1-p)^n$. If $n=10$ and $p=0.6$ then the probability of $n$ tails is around 0.0001.

First $k$ heads then $n-k$ tails

Lets say $n=10$ and $k=4$, this question is asking what is the probability of getting:
H, H, H, H, T, T, T, T, T, T
The coins are still independent! The first $k$ heads occur with probability $p^k$ the run of $n-k$ tails occurs with probability $(1-p)^{n-k}$. The probability of $k$ heads then $n-k$ tails is the product of those two terms: $p^k \cdot (1-p)^{n-k}$

## Exactly $k$ heads

Next lets try to figure out the probability of exactly $k$ heads in the $n$ flips. Importantly we don't care where in the $n$ flips that we get the heads, as long as there are $k$ of them. Note that this question is different than the question of first $k$ heads and then $n-k$ tails which requires that the $k$ heads come first! That particular result does generate exactly $k$ coin flips, but there are others.

There are many others! In fact any permutation of $k$ heads and $n-k$ tails will satisfy this event. Lets ask the computer to list them all for exactly $k=4$ heads within $n=10$ coin flips. The output region is scrollable:

(H, H, H, H, T, T, T, T, T, T)
(H, H, H, T, H, T, T, T, T, T)
(H, H, H, T, T, H, T, T, T, T)
(H, H, H, T, T, T, H, T, T, T)
(H, H, H, T, T, T, T, H, T, T)
(H, H, H, T, T, T, T, T, H, T)
(H, H, H, T, T, T, T, T, T, H)
(H, H, T, H, H, T, T, T, T, T)
(H, H, T, H, T, H, T, T, T, T)
(H, H, T, H, T, T, H, T, T, T)
(H, H, T, H, T, T, T, H, T, T)
(H, H, T, H, T, T, T, T, H, T)
(H, H, T, H, T, T, T, T, T, H)
(H, H, T, T, H, H, T, T, T, T)
(H, H, T, T, H, T, H, T, T, T)
(H, H, T, T, H, T, T, H, T, T)
(H, H, T, T, H, T, T, T, H, T)
(H, H, T, T, H, T, T, T, T, H)
(H, H, T, T, T, H, H, T, T, T)
(H, H, T, T, T, H, T, H, T, T)
(H, H, T, T, T, H, T, T, H, T)
(H, H, T, T, T, H, T, T, T, H)
(H, H, T, T, T, T, H, H, T, T)
(H, H, T, T, T, T, H, T, H, T)
(H, H, T, T, T, T, H, T, T, H)
(H, H, T, T, T, T, T, H, H, T)
(H, H, T, T, T, T, T, H, T, H)
(H, H, T, T, T, T, T, T, H, H)
(H, T, H, H, H, T, T, T, T, T)
(H, T, H, H, T, H, T, T, T, T)
(H, T, H, H, T, T, H, T, T, T)
(H, T, H, H, T, T, T, H, T, T)
(H, T, H, H, T, T, T, T, H, T)
(H, T, H, H, T, T, T, T, T, H)
(H, T, H, T, H, H, T, T, T, T)
(H, T, H, T, H, T, H, T, T, T)
(H, T, H, T, H, T, T, H, T, T)
(H, T, H, T, H, T, T, T, H, T)
(H, T, H, T, H, T, T, T, T, H)
(H, T, H, T, T, H, H, T, T, T)
(H, T, H, T, T, H, T, H, T, T)
(H, T, H, T, T, H, T, T, H, T)
(H, T, H, T, T, H, T, T, T, H)
(H, T, H, T, T, T, H, H, T, T)
(H, T, H, T, T, T, H, T, H, T)
(H, T, H, T, T, T, H, T, T, H)
(H, T, H, T, T, T, T, H, H, T)
(H, T, H, T, T, T, T, H, T, H)
(H, T, H, T, T, T, T, T, H, H)
(H, T, T, H, H, H, T, T, T, T)
(H, T, T, H, H, T, H, T, T, T)
(H, T, T, H, H, T, T, H, T, T)
(H, T, T, H, H, T, T, T, H, T)
(H, T, T, H, H, T, T, T, T, H)
(H, T, T, H, T, H, H, T, T, T)
(H, T, T, H, T, H, T, H, T, T)
(H, T, T, H, T, H, T, T, H, T)
(H, T, T, H, T, H, T, T, T, H)
(H, T, T, H, T, T, H, H, T, T)
(H, T, T, H, T, T, H, T, H, T)
(H, T, T, H, T, T, H, T, T, H)
(H, T, T, H, T, T, T, H, H, T)
(H, T, T, H, T, T, T, H, T, H)
(H, T, T, H, T, T, T, T, H, H)
(H, T, T, T, H, H, H, T, T, T)
(H, T, T, T, H, H, T, H, T, T)
(H, T, T, T, H, H, T, T, H, T)
(H, T, T, T, H, H, T, T, T, H)
(H, T, T, T, H, T, H, H, T, T)
(H, T, T, T, H, T, H, T, H, T)
(H, T, T, T, H, T, H, T, T, H)
(H, T, T, T, H, T, T, H, H, T)
(H, T, T, T, H, T, T, H, T, H)
(H, T, T, T, H, T, T, T, H, H)
(H, T, T, T, T, H, H, H, T, T)
(H, T, T, T, T, H, H, T, H, T)
(H, T, T, T, T, H, H, T, T, H)
(H, T, T, T, T, H, T, H, H, T)
(H, T, T, T, T, H, T, H, T, H)
(H, T, T, T, T, H, T, T, H, H)
(H, T, T, T, T, T, H, H, H, T)
(H, T, T, T, T, T, H, H, T, H)
(H, T, T, T, T, T, H, T, H, H)
(H, T, T, T, T, T, T, H, H, H)
(T, H, H, H, H, T, T, T, T, T)
(T, H, H, H, T, H, T, T, T, T)
(T, H, H, H, T, T, H, T, T, T)
(T, H, H, H, T, T, T, H, T, T)
(T, H, H, H, T, T, T, T, H, T)
(T, H, H, H, T, T, T, T, T, H)
(T, H, H, T, H, H, T, T, T, T)
(T, H, H, T, H, T, H, T, T, T)
(T, H, H, T, H, T, T, H, T, T)
(T, H, H, T, H, T, T, T, H, T)
(T, H, H, T, H, T, T, T, T, H)
(T, H, H, T, T, H, H, T, T, T)
(T, H, H, T, T, H, T, H, T, T)
(T, H, H, T, T, H, T, T, H, T)
(T, H, H, T, T, H, T, T, T, H)
(T, H, H, T, T, T, H, H, T, T)
(T, H, H, T, T, T, H, T, H, T)
(T, H, H, T, T, T, H, T, T, H)
(T, H, H, T, T, T, T, H, H, T)
(T, H, H, T, T, T, T, H, T, H)
(T, H, H, T, T, T, T, T, H, H)
(T, H, T, H, H, H, T, T, T, T)
(T, H, T, H, H, T, H, T, T, T)
(T, H, T, H, H, T, T, H, T, T)
(T, H, T, H, H, T, T, T, H, T)
(T, H, T, H, H, T, T, T, T, H)
(T, H, T, H, T, H, H, T, T, T)
(T, H, T, H, T, H, T, H, T, T)
(T, H, T, H, T, H, T, T, H, T)
(T, H, T, H, T, H, T, T, T, H)
(T, H, T, H, T, T, H, H, T, T)
(T, H, T, H, T, T, H, T, H, T)
(T, H, T, H, T, T, H, T, T, H)
(T, H, T, H, T, T, T, H, H, T)
(T, H, T, H, T, T, T, H, T, H)
(T, H, T, H, T, T, T, T, H, H)
(T, H, T, T, H, H, H, T, T, T)
(T, H, T, T, H, H, T, H, T, T)
(T, H, T, T, H, H, T, T, H, T)
(T, H, T, T, H, H, T, T, T, H)
(T, H, T, T, H, T, H, H, T, T)
(T, H, T, T, H, T, H, T, H, T)
(T, H, T, T, H, T, H, T, T, H)
(T, H, T, T, H, T, T, H, H, T)
(T, H, T, T, H, T, T, H, T, H)
(T, H, T, T, H, T, T, T, H, H)
(T, H, T, T, T, H, H, H, T, T)
(T, H, T, T, T, H, H, T, H, T)
(T, H, T, T, T, H, H, T, T, H)
(T, H, T, T, T, H, T, H, H, T)
(T, H, T, T, T, H, T, H, T, H)
(T, H, T, T, T, H, T, T, H, H)
(T, H, T, T, T, T, H, H, H, T)
(T, H, T, T, T, T, H, H, T, H)
(T, H, T, T, T, T, H, T, H, H)
(T, H, T, T, T, T, T, H, H, H)
(T, T, H, H, H, H, T, T, T, T)
(T, T, H, H, H, T, H, T, T, T)
(T, T, H, H, H, T, T, H, T, T)
(T, T, H, H, H, T, T, T, H, T)
(T, T, H, H, H, T, T, T, T, H)
(T, T, H, H, T, H, H, T, T, T)
(T, T, H, H, T, H, T, H, T, T)
(T, T, H, H, T, H, T, T, H, T)
(T, T, H, H, T, H, T, T, T, H)
(T, T, H, H, T, T, H, H, T, T)
(T, T, H, H, T, T, H, T, H, T)
(T, T, H, H, T, T, H, T, T, H)
(T, T, H, H, T, T, T, H, H, T)
(T, T, H, H, T, T, T, H, T, H)
(T, T, H, H, T, T, T, T, H, H)
(T, T, H, T, H, H, H, T, T, T)
(T, T, H, T, H, H, T, H, T, T)
(T, T, H, T, H, H, T, T, H, T)
(T, T, H, T, H, H, T, T, T, H)
(T, T, H, T, H, T, H, H, T, T)
(T, T, H, T, H, T, H, T, H, T)
(T, T, H, T, H, T, H, T, T, H)
(T, T, H, T, H, T, T, H, H, T)
(T, T, H, T, H, T, T, H, T, H)
(T, T, H, T, H, T, T, T, H, H)
(T, T, H, T, T, H, H, H, T, T)
(T, T, H, T, T, H, H, T, H, T)
(T, T, H, T, T, H, H, T, T, H)
(T, T, H, T, T, H, T, H, H, T)
(T, T, H, T, T, H, T, H, T, H)
(T, T, H, T, T, H, T, T, H, H)
(T, T, H, T, T, T, H, H, H, T)
(T, T, H, T, T, T, H, H, T, H)
(T, T, H, T, T, T, H, T, H, H)
(T, T, H, T, T, T, T, H, H, H)
(T, T, T, H, H, H, H, T, T, T)
(T, T, T, H, H, H, T, H, T, T)
(T, T, T, H, H, H, T, T, H, T)
(T, T, T, H, H, H, T, T, T, H)
(T, T, T, H, H, T, H, H, T, T)
(T, T, T, H, H, T, H, T, H, T)
(T, T, T, H, H, T, H, T, T, H)
(T, T, T, H, H, T, T, H, H, T)
(T, T, T, H, H, T, T, H, T, H)
(T, T, T, H, H, T, T, T, H, H)
(T, T, T, H, T, H, H, H, T, T)
(T, T, T, H, T, H, H, T, H, T)
(T, T, T, H, T, H, H, T, T, H)
(T, T, T, H, T, H, T, H, H, T)
(T, T, T, H, T, H, T, H, T, H)
(T, T, T, H, T, H, T, T, H, H)
(T, T, T, H, T, T, H, H, H, T)
(T, T, T, H, T, T, H, H, T, H)
(T, T, T, H, T, T, H, T, H, H)
(T, T, T, H, T, T, T, H, H, H)
(T, T, T, T, H, H, H, H, T, T)
(T, T, T, T, H, H, H, T, H, T)
(T, T, T, T, H, H, H, T, T, H)
(T, T, T, T, H, H, T, H, H, T)
(T, T, T, T, H, H, T, H, T, H)
(T, T, T, T, H, H, T, T, H, H)
(T, T, T, T, H, T, H, H, H, T)
(T, T, T, T, H, T, H, H, T, H)
(T, T, T, T, H, T, H, T, H, H)
(T, T, T, T, H, T, T, H, H, H)
(T, T, T, T, T, H, H, H, H, T)
(T, T, T, T, T, H, H, H, T, H)
(T, T, T, T, T, H, H, T, H, H)
(T, T, T, T, T, H, T, H, H, H)
(T, T, T, T, T, T, H, H, H, H)

Exactly how many outcomes are there with $k=4$ heads in $n=10$ flips? 210. The answer can be calculated using permutations of indistinct objects: $$N = \frac{n!}{k! (n-k)!} = {n \choose k}$$

The probability of exactly $k=4$ heads is the probability of the or of each of these outcomes. Because we consider each coin to be unique, each of these outcomes is "mutually exclusive" and as such if $E_i$ is the outcome from the $i$th row, $$\p(\text{exactly k heads}) = \sum_{i=1}^N \p(E_i)$$

The next question is, what is the probability of each of these outcomes?

Here is a arbitrarily chosen outcome which satisfies the event of exactly $k=4$ heads in $n=10$ coin flips. In fact it is the one on row 128 in the list above:

T, H, T, T, H, T, T, H, H, T

What is the probability of getting the exact sequence of heads and tails in the example above? Each coin flip is still independent, so we multiply $p$ for each heads and $1-p$ for each tails. Let $E_{128}$ be the event of this exact outcome: $$\p(E_{128}) = (1-p) \cdot p \cdot (1-p) \cdot (1-p) \cdot p \cdot (1-p) \cdot (1-p) \cdot p \cdot p \cdot (1-p)$$ If you rearrange these multiplication terms you get: \begin{align} \p(E_{128}) &= p \cdot p \cdot p \cdot p \cdot (1-p) \cdot (1-p) \cdot (1-p) \cdot (1-p) \cdot (1-p) \cdot (1-p)\\ &= p^4 \cdot (1-p)^{6} \end{align} There is nothing too special about row 128. If you chose any row, you would get $k$ independent heads and $n-k$ independent tails. For any row $i$, $\p(E_i) = p^k \cdot (1-p)^{n-k}$. Now we are ready to calculate the probability of exactly $k$ heads: \begin{align} \p(\text{exactly k heads}) &= \sum_{i=1}^N \p(E_i) && \text{Mutual Exclusion}\\ &= \sum_{i=1}^N p^k \cdot (1-p)^{n-k} && \text{Sub in }\p(E_i) \\ &= N \cdot p^k \cdot (1-p)^{n-k} && \text{Sum N times} \\ &= {n \choose k} \cdot p^k \cdot (1-p)^{n-k} && \text{Perm of indistinct objects} \end{align}

## More than $k$ heads

You can use the formula for exactly $k$ heads to compute other probabilities. For example the probability of more than $k$ heads is: \begin{align} \p(\text{more than k heads}) &= \sum_{i=k+1}^n \p(\text{exactly i heads}) && \text{Mutual Exclusion}\\ &= \sum_{i=k+1}^n {n \choose i} \cdot p^i \cdot (1-p)^{n-i} && \text{Substitution}\\ \end{align}