6
$\begingroup$

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.

  • 3
    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.2010-12-05

2 Answers 2

2

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.

  • 0
    I know, this would be the OP's task. No big deal, anyway, and kudos from me for your prompt and written reaction.2012-09-14
8

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

  • 0
    +1. Yes, nice example, and I see now where I went wrong.2012-09-13