Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 2 down vote accepted

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.

share|cite|improve this answer
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).$$

share|cite|improve this answer
+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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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