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

[the question got downvoted on MO with the recommendation to ask here]

In many books Ehrenfest Urn is used as an example of a homogeneous Markov chain, where entries in transition probabilities depend on the state, e.g.

$$ p_{i,i+1} = \frac{i}{n}, q_{i,i-1} = 1- \frac{i}{n} $$

or, in recurrent notation, for period $t$:

$$ S_t = S_{t-1} + \xi_{t-1} $$ where $\xi_{t-1}$ is a random variable. What I have never seen is the proof that this process satisfies weak Markov property:

$$ P(S_{t+1} = i_{t+1}\mid S_t = i_t,\ldots,S_0=i_0) = P(S_{t+1} = i_{t+1}\mid S_t = i_t) $$

Only in Flajolet, Dumas,Puyhaubert(2006) on p.70 it is mentioned that Ehrenfest urn can be viewed as a random walk on N-dimensional cube, but I can't relate it.

I'd massively appreciate suggestion on how to approach this proof.

share|cite|improve this question
up vote 2 down vote accepted

The question is empty since the commonest presentation of the Ehrenfest process is that it is a Markov chain $(S_t)_t$ on the set $L=\{0,1,\ldots,n\}$, whose transition probabilities are, for every $i$ in $L$, $p_{i,i+1}=(n-i)/n$ and $p_{i,i-1}=i/n$ (and not what you wrote).

This Markov chain $(S_t)_t$ is a birth-and-death chain and, as such, $S_{t+1}=S_t+\xi_{t+1}$ for every $t$, where $\xi_{t+1}$ depends on $(S_k)_{k\leqslant t}$ through $S_t$ only, with the distribution one can guess.

The result you mention at the end of your post refers to something different, which is the fact that the process $(S_t)_t$ is a projection of a simpler process with values in a hypercube $K=\{0,1\}^I$ where $I$ is any set of size $n$. To wit, consider the simple random walk $(X_t)_t$ on the graph with vertex set $K$ and the usual edge set. Thus, all the coordinates of $X_{t+1}$ are those of $X_t$ except one, and the exception is chosen, randomly uniformly in $I$. If $S_t$ counts the number of ones amongst the coordinates of $X_t$, one recovers the Ehrenfest process with values in $L$. And in fact, this $K$-valued process is the one the physicists Paul and Tatiana Ehrenfest introduced as a toy model to explain the macroscopic irreversibility of some microscopically reversible dynamics...

The funny thing is that, by the Ehrenfests' construction, $(S_t)_t$ can be realized from $(X_t)_t$ as $S_t=u(X_t)$, for the Markov chain $(X_t)_t$ on $K$ above and the non injective function $u:K\to L$ one can imagine, and that $(S_t)_t$ is still a Markov chain although, in general, such a non injective lumping of a Markov chain does not produce a Markov chain but rather what is called a hidden Markov chain. But a sufficient condition on the lumping to produce a Markov chain is well known and the Markov process $(X_t)_t$ on $K$ and the Ehrenfest function $u$ from $K$ to $L$ happen to satisfy this condition!

share|cite|improve this answer
by 'sufficient condition' do you mean weak Markov property? – sigma.z.1980 Feb 26 '12 at 23:55
For discrete-time discrete-space processes, there is no difference between weak Markov property and strong Markov property, so no, this is certainly not the issue. – Did Feb 27 '12 at 0:02
what is it then? Can you refer me to a paper discussing this condition? – sigma.z.1980 Feb 27 '12 at 0:31
Lumpability is at best tangential to your post... Anyway, a reference is the book by Kemeny and Snell. – Did Feb 27 '12 at 1:10
do you mean 'Finite Markov chains' (1960) or 'Denumerable Markov chains' (1976)? – sigma.z.1980 Feb 27 '12 at 1:37

I think the answer by Did is quite nice for an advanced audience, but I feel the following needs to be said to reach a less advanced public. I only address the part of the question that asks why the (Weak) Markov Property is satisfied. Because the process is discrete time discrete state, we do not have to distinguish between weak/strong Markov Property as per a comment by Did.

When you specify that a process is a Markov Chain (and optionally specify probabilities like you have), you have created a process that trivially satisfies the Markov Property, as every (stochastic process that is a) Markov Chain satisfies the Markov property by definition.

share|cite|improve this answer

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.