# Coupon collector's problem as Random Walk

I see in a book the following as coupon collector's problem. We have $N$ coupons labelled $1,2,\dots,N$ from which we pick with replacement. I could not understand what is the random walk here.

• As you sample each time, the number of types of coupon seen so far either stays the same or increases by one. So you could see this as a random walk where you either make one step horizontally to the right (sample up by one, no new type of coupon) or diagonally right and up (sample up by one, one new type of coupon) – Henry Nov 10 '13 at 10:23

## 2 Answers

The state space is $\{0,1,\ldots,N\}$ and the steps of the random walk are $0$ and $+1$. When at some state $k$, the transition $k\to k+1$ has probability $1-\frac{k}N$ and the transition $k\to k$ has probability $\frac{k}N$. Thus, the transitions $0\to1$ and $N\to N$ both have probability $1$ and the state $N$ is absorbing. (Note that this process is not usually described as a (inhomogenous) random walk but rather as a Markov chain.)

You can also see this as a random walk on the complete graph on $$N$$ vertices with self-loops at each vertex, where you want to know when you’ve visited all vertices. See Find the expected number of steps needed until every point has been visited at least once. for the variant without self-loops.