\documentclass[a4paper,12pt]{article}
\newcommand{\un}{\underline}
\newcommand{\undb}{\underbrace}
\newcommand{\ds}{\displaystyle}
\newcommand{\pl}{\partial}
\newcommand{\df}{\ds\frac}
\parindent=0pt
\begin{document}


{\bf Question}

Define a stationary distribution of a Markov chain.

The following is a modification of the Ehrenfest model of the
exchange of heat or of gas molecules between two isolated bodies.

Suppose there are two boxes,  labelled $A$ and $B$, and $N$ balls
labelled $1,\ 2,\ 3,\ \cdots,\ N$. Initially some of the three
balls are in box $A$ and the remainder are in box $B$. A trial is
performed in which an integer is selected at random from $1,\ 2,\
3,\ \cdots,\ N$ and the ball labelled by that integer is removed
from its box; one of the boxes is selected at random and the
removed ball is placed in this box. The trails are repeated
indefinitely, and the selections made are independent. If $X_n$
denotes the number of balls in box $A$ after the nth trial,
explain why $\{X_n\}_{n=0,1,\cdots}$ constitutes a Markov chain
and write down its state space.

Show that the conditional probability of $(i+1)$ balls in box $A$
after the nth trial, given there are $i$ balls in $A$ after the
previous trial and $0 \leq i \leq n$, is

$$\df{N-i}{2N}$$

Obtain the remaining 1-step transition probabilities. Show that
the stationary distribution is Binomial with parameters $N$ and
$\df{1}{2}$.

Deduce the mean number of trials between occasions on which box
$A$ is empty.



\vspace{.25in}

{\bf Answer}

If a Markov chain has transition matrix $M$, then the probability
vector $\un{\pi}$ is a stationary distribution if
$\un{\pi}M=\un{\pi}$. If $X_n$ denotes the number of balls in Box
$A$ at step $n$,\ the number of balls in Box $A$ at step $n+1$
depends only on the location of the balls at stage $n$, and the
next choice of box. It does not depend on hoe stage $n$ was
arrived at. The state space is $\{0,\ 1\, 2,\ \cdots,\ N\}$.

Stage $n$:

\setlength{\unitlength}{.5in}
\begin{picture}(8,2)
\put(0,1){\line(1,0){2}}

\put(2,1){\line(0,1){1}}

\put(0,2){\line(1,0){2}}

\put(0,1){\line(0,1){1}}

\put(5,1){\line(1,0){2}}

\put(7,1){\line(0,1){1}}

\put(5,2){\line(1,0){2}}

\put(5,1){\line(0,1){1}}

\put(1,1.5){\makebox(0,0){$i$}}

\put(6,1.5){\makebox(0,0){$N-i$}}

\put(0,0.5){\makebox(0,0)[l]{Box $A$}}

\put(5,0.5){\makebox(0,0)[l]{Box $B$}}
\end{picture}

after the next change there will be $i+1$ balls in box $A$ if the
integer chosen corresponds to a ball in box $B$, which happens
with probability $\df{(N-i)}{N}$, and if box $A$ is selected,
which happens with probability $\df{1}{2}$. So

$$p_{i,\ i+1}=\df{1}{2}\df{N-i}{N}\ \ 0 \leq i \leq N$$

Similarly

$$p_{i,\ i-1}=\df{1}{2}\df{i}{N}\ \ 0 \leq i \leq N$$

$p_{01}=1-p_{01}=1-\df{1}{2}=\df{1}{2}$ and $p_{NN}=\df{1}{2}$

For $0<i<N,\ p_{ii}=1-p_{i,\ i+1}-p_{i,\ i-1}=\df{1}{2}$.

So the transition matrix is $N+1 \times N+1)$

$\left(\begin{array}{ccccccc} \frac{1}{2} & \frac{1}{2} & 0 & 0 &
\cdots & 0 & 0\\ \frac{1}{2}\frac{1}{N} & \frac{1}{2} &
\frac{1}{2}\frac{N-1}{N} & 0 & \cdots\\ 0 & \frac{1}{2}\frac{2}{N}
& \frac{1}{2} & \frac{1}{2}\frac{N-2}{N} & \cdots\\ \vdots\\ 0 &
\cdots & & & \frac{1}{2}\frac{N-1}{N} & \frac{1}{2} &
\frac{1}{2}\frac{1}{N}\\ 0 & \cdots & & & 0 & \frac{1}{2} &
\frac{1}{2} \end{array}\right)$

\newpage
So if $\un{\pi}\ (\pi_0, \cdots,\ \pi_N)$ is a stationary
distribution, it satisfies $\un{\pi}M=\un{\pi}$, giving the
following equations

$\pi_0\df{1}{2}+\pi_1\df{1}{2}\df{1}{n}=\pi_0$

$\pi_0\df{1}{2}+\pi_1\df{1}{2}+\pi_2\df{1}{2}\df{2}{N}=\pi_1$

$\pi_1\df{1}{2}\df{N-1}{N}+\pi_2\df{1}{2}+\pi_3\df{1}{2}\df{3}{N}=\pi_2$

\ \ \vdots

$\pi_{k-1}\df{1}{2}\df{N-(k-1)}{N}+\pi_k\df{1}{2}+\pi_{k+1}\df{1}{2}\df{k+1}{N}=\pi_k$

\ \ \vdots

$\pi_{N-1}\df{1}{2}\df{1}{N}+\pi_N\df{1}{2}=\pi_N$

i.e. \begin{eqnarray*} \pi_0 & = & \pi_1\df{1}{N}\\ \pi_1 & = &
\pi_0+\pi_2\df{2}{N}\\ \vdots\\ \pi_N & = & \pi_{N-1} \cdot
\df{1}{N} \end{eqnarray*}

We need to prove by induction that

$$\pi_k=\left(\begin{array}{c}N\\k\end{array}\right)\pi_0$$

True for $k=0,\ 1$.

For $1<k<N$

$\begin{array}{rcl} \pi_{k+1} & = &
\df{N}{k+1}\left(\pi_k-\pi_{k-1}\df{N-k+1}{N}\right)\\ & = &
\df{N}{k+1}\left(\left(\begin{array}{c}N\\ k
\end{array}\right)-\left(\begin{array}{c}N\\ k-1
\end{array}\right)\df{N-k+1}{N}\right)\pi_0 \end{array}$

which reduces to $\left(\begin{array}{c} N\\ k+1
\end{array}\right)\pi_0$.

Finally $\pi_N=\df{1}{N}\pi_{N-1}$ fits with these results.

The Markov chain is finite irreducible, so the standard deviation
is the eq.dist. $\mu_0=\df{1}{\pi_0}=2^N$



\end{document}