Collecting all 100 tickets at 5 Guys Burgers

When you order at 5 guys burgers (which you should if you haven't because they are amazing) you are given a ticket between 1 and 100 which is then use to collect your order. Last time I was there my friend suggested trying to collect all 100 tickets. The question is:

Assuming you receive a random ticket number between 1 and 100 inclusive on every visit. On average, how many visits would it take to collect all 100 tickets?

Solution:

Define $S$ to be a random variable which counts the number of purchases required to get all 100 tickets. Then we are interested in $\mathbb{E} [S]$

To help us analyse $S$ we need to define another collection of random variables.

Let $X_i$ denote the number of purchases required to get the $ith + 1$ ticket given we have already collected $i$ tickets. So if we have collected 2 tickets (say ticket number 33 and ticket number 51) and the next two tickets we get are 33 and 81, then $X_2 = 2$ because it took us 2 attempts to get a new unique ticket.

We can actually view $S$ as the sum of these $X_i$, i.e. $S = \sum\limits_{i=1}^{100}X_i$ (to see that this is the case the number of visit it takes to collect all 100 tickets will be the number of visits to collect the first ticket plus the number of visits to collect the 2nd unique ticket, and so on)

There are two further observations that we need to make before deriving the solution. Firstly, each $X_i$ is independent of $\sum\limits_{k=1}^{{i-1}}X_i$. Secondly, each $X_i$ is actually distributed as a Geometric Distribution where:

$P( X_i = k ) = \frac{i-1}{100}^{k-1} \frac{101-i}{100}$

Since $X_i$ is a geometric random variable, we know that $\mathbb{E} [ X_i ] = \frac{100}{101-i}$

Giving us:

$\mathbb{E} [ S ] = \mathbb{E} [ \sum\limits_{k=1}^{100} X_i ] = \sum\limits_{k=1}^{100} \mathbb{E} [X_i ] = \sum\limits_{k=1}^{100} \frac{100}{101-i} = 100 \sum\limits_{k=1}^{100} \frac{1}{101-i} = 100 \sum\limits_{k=1}^{100} \frac{1}{i}$
How to compute $100 \sum\limits_{k=1}^{100} \frac{1}{i}$ ?
This is a famous sum in mathematics. The value of this sum for a given upper limit is known as a harmonic number. The nth Harmonic number $H_n$ is defined to be $\sum\limits_{k=1}^{n} \frac{1}{i}$.
In this case, using wolfram alpha to look up the value of $H_100$ tells us that $H_{100} = 5.18737751$
Therefore on average it will take us $100 H_{100}$ visits to 5 guys to collect all 100 tickets. This is approximately equal to $519$ visits, which is a lot of burgers!