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.
 A: 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).$$
A: 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. 
