0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – Henry Nov 10 '13 at 10:23
0
$\begingroup$

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.)

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.