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

Could anyone give me an example of a problem where it is requested to prove rather than assume that a stochastic process forms a Markov chain. I can think of something like this: if $X_{n+1} = X_{n} + \xi_{n}$ it is necessary to prove that $ \mathbf{E}[\xi_{n}|\xi_{n-1}] = \mathbf{E}[\xi_{n}]$, random walk-type process.

I would be especially grateful if one could come up with an example where a function of MC created by lumping some states is proven to be an MC.

share|cite|improve this question
Got something from my answer? – Did Apr 2 '12 at 17:16
yes thanks Didier – user19821 Jun 29 '12 at 2:54
up vote 2 down vote accepted

A famous example is the Ehrenfest process, introduced in 1911 by the physicists Paul Ehrenfest and Tatyana Ehrenfest-Afanaseva as a toy model to explain the macroscopic irreversibility of some microscopically reversible dynamics. The process is defined as follows.

Start with a hypercube $K=\{0,1\}^I$ of dimension $n$, thus $I$ can be any set of size $n$. The simple random walk $(X_t)_{t\geqslant0}$ on the graph with vertex set $K$ and the usual edge set is a Markov chain, such that, for every $t\geqslant0$, all the coordinates of $X_{t+1}$ are those of $X_t$ except one, and the exception is chosen randomly uniformly in $I$.

Now, let $S_t$ count the number of ones amongst the coordinates of $X_t$. The surprising fact is that $(S_t)_{t\geqslant0}$ is also a Markov chain (and more precisely, a birth-and-death chain). This new chain is defined on the set $L=\{0,1,\ldots,n\}$ and has transition probabilities, for every $i$ in $L$, $$ Q(i,i-1)=i/n=1-Q(i,i+1). $$ The funny thing is that $S_t=u(X_t)$ for the non injective function $u:K\to L$ one can imagine, and that, as said above, $(S_t)_{t\geqslant0}$ 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.

A sufficient condition on any lumping to produce a Markov chain, which the Markov process $(X_t)_{t\geqslant0}$ on $K$ and the Ehrenfest function $u$ from $K$ to $L$ happen to satisfy, is well known. Call $q$ the transition matrix of $(X_t)_{t\geqslant0}$. Then, the sufficient condition is that the sum $$ \sigma(x,s)=\sum\limits_{y:u(y)=s}q(x,y) $$ depends on $u(x)$ and $s$ only, but not on $x$. In other words, one asks that $\sigma(x,s)=\sigma(x',s)$ as soon as $u(x)=u(x')$. Then $(S_t)_{t\geqslant0}$ is a Markov chain whose transition matrix $Q$ is defined by $Q(r,s)=\sigma(x,s)$ for any $r$ and $s$ and any $x$ such that $u(x)=r$.

share|cite|improve this answer
Thanks. Is there some proof that this $\sigma$ is satisfied for Ehrenfest function? – user19821 Mar 6 '12 at 6:21
Yes: start from $x$ in $K$ and count how many of its neighbors in $K$ have exactly one $1$-coordinate more and how many have exactly one $1$-coordinate less. – Did Mar 6 '12 at 6:52

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.