# coupon collector and Markov chains

I need some help with my homework in probability. I need to prove that if $X(n) =$ the number of different coupons that the collector has in time $n$ then $X(n)$ represents a Markov chain.

I proved that $$P(X(m+1)=j)= \cases{ \frac{X(m)}{n}&\text{if j=X(m)}\\\ 1-\frac{X(m)}{n}&\text{if j=X(m)+1}\\\ 0 &\text{otherwise}.}$$ Now I need to show from there that $P(X(m+1)=j|X(m)=Km,\ldots ,X(0)=K0)=P(X(m+1)=j|X(m)=Km)$

thanks for the help. benny.

-
Maybe I'm missing something, since you asked this 12 hours ago and nobody has responded yet, but I think you have it. You have expressed $P(X(m+1) = j)$ in terms of the previous state $X(m)$ without reference to any of the prior states $X(m-1), X(m-2), \ldots, X(0)$. That's enough to show that $X(m)$ is a Markov chain. – Mike Spivey Dec 5 '10 at 21:57

Judging from the upvotes on my comment, it looks like I didn't miss anything, so...

I think you have it. You have expressed $P(X(m+1)=j)$ in terms of the previous state $X(m)$ without reference to any of the prior states $X(m−1),X(m−2), \ldots, X(0)$. That's enough to show that $X(m)$ is a Markov chain.

-
Must downvote, for the reasons explained in the other answer. – Did Sep 13 '12 at 19:06
@did: Thanks for bringing this to my attention. I agree with Byron's criticism of my answer. Unfortunately, the software won't let me delete an accepted answer. – Mike Spivey Sep 13 '12 at 21:26
I know, this would be the OP's task. No big deal, anyway, and kudos from me for your prompt and written reaction. – Did Sep 14 '12 at 5:05

This answer is incomplete and potentially misleading, so I'm posting an extended comment.

First of all, there is something wrong with the OP's formula. The left hand side is a probability which is a non-random number while the right hand side depends on the random variable $X(m)$. Probably what he means is

$$P\big(X(m+1)=j\,|\, X(m)\big)= \cases{ \frac{X(m)}{n}&\text{if X(m)=j}\\[3pt] 1-\frac{X(m)}{n}&\text{if X(m)=j-1}\\[5pt] 0 &\text{otherwise}.}$$

This formula describes the conditional distribution of $X(m+1)$ given $X(m)$. By definition, this depends only on $X(m)$ and not $X(m-1),\dots, X(1), X(0)$, and this is true whether or not the process $X$ satisfies the Markov property.

The OP is correct in asserting that to prove the Markov property, you must consider conditional probabilities of the form $$P(X(m+1)=j\,|\,X(m)=K_m,\ldots ,X(0)=K_0),$$ or alternatively joint probabilities of the form $$P(X(m)=K_m,\ldots ,X(0)=K_0).$$

For the coupon collector's problem, this is a bit of a pain, but it is not terribly difficult and it has to be done to prove that $X$ is Markov.

Added: Here is a simple example that maybe explains my objection a bit better.

Draw cards one at a time, without replacement, from a well-shuffled deck. For $1\leq n\leq 52$, let $X_n$ be the color of the card drawn at time $n$. This is a stochastic process with state space ${\cal S}=\{R,B\}$.

For $1\leq n <52$, using exchangeability you find that $\mathbb{P}(X_{n+1}=j\,|\,X_n=i)$ is the $(i,j)$th entry in the matrix

$$P= \pmatrix{{25\over 51}&{26\over 51}\\[3pt] {26\over 51}&{25\over 51}}.$$

So $(X_n)$ is time homogeneous, and has a "transition matrix" $P$ but, nevertheless, it is not Markov.

Why not? Well, for example $$\mathbb{P}(X_3=B\,|\,X_2=R,X_1=R)={26\over 50}\neq {26\over 51}=\mathbb{P}(X_3=B\,|\,X_2=R).$$

-
+1. Nice example. – Did Sep 13 '12 at 19:07
Thanks. It is a point that my students find confusing, so it's nice to have a concrete example of how things can go wrong. – Byron Schmuland Sep 13 '12 at 19:09
+1. Yes, nice example, and I see now where I went wrong. – Mike Spivey Sep 13 '12 at 21:28