# 20 - Geometric and Binomial distribution expected values

## New definition for expected values

<u>Lemma:</u> If $X:S \rightarrow \{0,1,2,3,...\}$ is a non-negative integer-valued random variable, then $E(X) = \sum_{i=1}^\infty Pr(X \geq i)$

**Proof:** For each $i \in \{1,2,3,...\}$ Let $P_i = Pr(X=i)$.

$Pr(X \geq i)= \sum_{j=i}^\infty Pr(X=i) = P_i + P_{i+1} + P_{i+2} ...$

$\sum_{i=1}^\infty Pr(X \geq i) = P_1 + P_2 + P_3 + ...$
$+ P_2 + P_3 + ...$
$+ P_3 + P_4 + ...$
$...$

What do we get at the end? We get something like:

$(1\times P_1) + (2 \times P_2) + (3 \times P_3) + .... = \sum_{i=1}^\infty i \cdot P_i = \sum_{i=1}^\infty i \cdot Pr(X=i)$ Which is just the expected value definition.

## Geometric\(p\) random variable
- Imagine a biased coin $Pr(H) = p, \ Pr(T) = 1-p, \ (0 < p < 1)$
- Repeatedly toss the coin until the first $H$
- $X = \text{Number of coin tosses before first heads}$
- The number $X$ of coin tosses is a geometric\(p\) random variable
- $Pr(X=i) = (1-p)^{i-1}\cdot p$ (Probability that $i$ coin tosses are required before the first head is the probability that the first $i-1$ coin tosses came up tails and then then $i$th coin toss came up heads)
- $Pr(X\geq i) = (1-p)^{i-1}$ (Probability that the number of coin tosses is greater than or equal to $i$ is the probability that first $i$th coin tosses are tails)
- $E(X) = \sum_{i=1}^\infty Pr(X \geq i) = \sum_{i=1}^\infty(1-p)^{i-1}$
- $E(X)= \sum_{i=0}^\infty(1-p)^i$
- $E(X) = \frac{1}{1-(1-p)} = \frac{1}{p}$ (check picture above)

What if we didn't have the lemma
$E(X) = \sum_{i=1}^\infty i \cdot Pr(X=i) = \sum_{i=1}^\infty i \cdot (1-p)^{i-1} \cdot p$
$=P \cdot \sum_{i=1}^\infty i \cdot (1-p)^{i-1} = p \cdot \frac{1}{(1-(1-p))^2} = p \cdot \frac{1}{p^2} = \frac{1}{p}$

## Coupon Collector's Problem
- Set of $n$ coupons $\{1,2,3,...,n\}$
- $C_1, C_2, C_3, ...$ is an infinite sequence of coupons
- Probability of getting any coupon is the same and independent $Pr(C_i = j) = \frac{1}{n}$ for any $i$ and $j$
- $X = \text{The minimum } i \text{ such that } C_1 \cup C_2 \cup ... = \{1,...,n\}$
- $X = \text{The number of weeks required to collect all coupons}$
- For each $i \in \{1,...,n\}$ let $X_i = \text{the number of weeks required to get } i \text{ different toys}$


<u>Reminder:</u> $E(geometric(p)) = \frac{1}{p}$

Define $Y_i = X_i - X_{i-1}$, for $i \in {1,...,n} , (X_0=0)$

$Y_i$ is the time between getting the $i$th toy and the $i-1$th toy


$\sum_{i=1}^n Y_i = \sum_{i=1}^n (X_i - X_{i-1})$
$= X_1 - X_0 + X_2 - X_1 + X_3 - X_2$
After cancelling out terms
$= X_n - X_0 = X_n = X$

So

$\sum_{i=1}^n Y_i = X$
$E(\sum_{i=1}^n Y_i) = E(X)$
$= \sum_{i=1}^n E(Y_i)$

What is $Y_i$?
- We already have $i-1$ toys
- $Y_i = \text{how long we have to wait before getting a new toy}$
- Kind of like going to a store each week and tossing a biased coin that comes up heads with probability $\frac{n-(i-1)}{n}$ and tails $\frac{i-1}{n}$
- $\frac{n-(i-1)}{n} = \frac{n-i+1}{n}$
- $Y_i$ is a geometric($\frac{n-1+1}{n}$) random variable
- $E(geometric(p)) = \frac{1}{p}$
- $E(Y_i) = \frac{n}{n-1+1}$

Back to the sum

$= \sum_{i=1}^n E(Y_i) = \sum_{i=1}^n \frac{n}{n-i+1} = n \cdot \sum_{i=1}^n\frac{1}{n-i+1}$

Writing out some terms
 $\frac{1}{n-3}$ should be $\frac{1}{n-2}$
$=n \cdot \sum_{i=1}^{n} \frac{1}{i} = n \cdot H_n$

So the expected number of weeks before collecting all of the prizes is $E(X) = n \cdot H_n$

## Binomial Distribution
$binomial(n,p)$
- Toss a biased $(p)$ coin $n$ times
- $B = \text{the number of heads}$
- $E(B) = \sum_{k=0}^n \binom{n}{k} \cdot (1-p)^{n-k} \cdot p^k$ (Could be 0-n heads)

The number of strings with $k$ heads multiplied by the probability that the string occurs

For each $i \in \{1,...,n\}$ Let:
$B_i = 1 \text{ if the ith coin toss is a head}$
$B_i = 0 \text{ otherwise}$


**Reminder**
<u>Geomtretic</u>: Based around events up to the first success
<u>Binomial</u>: Based on number of successes in $n$ events

###### tags: `COMP2804` `Probability`