\documentclass[a4paper,12pt]{article}
\newcommand{\ds}{\displaystyle}
\newcommand{\pl}{\partial}
\parindent=0pt
\begin{document}


{\bf Question}

The Bernoulli-Laplace model of diffusion describes the flow of two
incompressible liquids between two containers.  It may be
described in terms of $d$ white and $d$ black balls distributed
between two boxes so that each box contains $d$ balls.  At each
independent trial one ball is drawn from each box at random and
placed in the opposite box so that each box always contains $d$
balls. Suppose $X_n$ denotes the number of white balls in box 1
after the $n$-th trial. Show that $\left\{X_n\right\}\ \
(n=1,2,\ldots)$ forms a Markov chain and find the 1-step
transition probabilities. Show that the stationary distribution
for this Markov chain is $$ \pi_k = \left(
\begin{array}{c} d \\ k
\end{array} \right)^2 \pi_0,\ \ k=1,2,\ldots,d,$$

where $$\pi_0 = \left[ \sum_{k=0}^d \left(
\begin{array}{c} d \\ k \end{array} \right)^2 \right]^{-1},\ \  \left( \begin{array}{c} d \\ k
\end{array} \right) = \frac{d!}{k!(d - k)!}.$$




\vspace{.25in}

{\bf Answer}

$X_n$ has possible states $0, 1, 2, \ldots, d.$

$P(X_{n+1} = k)$ depends only on the number of balls in each box
box before the $(n+1)$-th trial i.e. by the value $X_n,$ so we
have a Markov chain.

Suppose $X_n = j$


\begin{center}
\setlength{\unitlength}{.5in}
\begin{picture}(5,2)
\put(0,1){\makebox(0,0){Box 1}}

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

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

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

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

\put(1.1,0.5){\makebox(0,0)[l]{$d - j$}}

\put(1.4,1){\makebox(0,0)[l]{$j$}}

\put(2,0.5){\makebox(0,0)[l]{B}}

\put(2,1){\makebox(0,0)[l]{W}}


\put(4,1){\makebox(0,0){Box 2}}

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

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

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

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

\put(5.4,0.5){\makebox(0,0)[l]{$j$}}

\put(5.1,1){\makebox(0,0)[l]{$d - j$}}

\put(6,0.5){\makebox(0,0)[l]{B}}

\put(6,1){\makebox(0,0)[l]{W}}

\end{picture}
\end{center}

The possible outcomes from the next trial are:

\begin{description}
\item[(i)] W from 1 and W from 2 with probability $\ds \left(
\frac{j}{d} \right) \cdot \left( \frac{d - j}{d} \right)$ giving
$X_{n+1} = j$
\item[(ii)] W from 1 and B from 2 with probability $\ds \left(
\frac{j}{d} \right) \cdot \left( \frac{j}{d} \right)$ giving

$X_{n+1} = j - 1$
\item[(iii)] B from 1 and W from 2 with probability $\ds \left(
\frac{d - j}{d} \right) \cdot \left( \frac{d - j}{d} \right)$
giving $X_{n+1} = j + 1$
\item[(iv)] B from 1 and B from 2 with probability $\ds \left(
\frac{d - j}{d} \right) \cdot \left( \frac{j}{d} \right)$ giving
$X_{n+1} = j$

\end{description}

So $\ds p_{jj} = 2 \cdot \left( \frac{d - j}{d} \right) \left(
\frac{j}{d} \right)$

$\ds p_{j,j+1} = \left( \frac{d - j}{d} \right)^2$

$\ds p_{j,j-1} = \left( \frac{j}{d} \right)^2$

$\ds p_{j,k} = 0$ if $k \not= j - 1, j,j+1$

With special cases: -

$ j = 0:$ only (iii) is possible, with probability 1.

$j = d:$ only (ii) is possible, with probability 1.

$$P = \frac{1}{d} \left( \begin{array}{cccccccc} 0 & d^2 & 0 & 0 &
& \cdots  & 0 & 0 \\ 1 & 2(d-1) & (d-1)^2 & 0 &  & \cdots & 0 & 0
\\ 0 & 2^2 & 2(d-2) \cdot 2 & (d-2)^2  & &  & 0& 0 \\
 \vdots &
\vdots & & & & & &  \vdots \\ 0 & 0 & & & & (d-1)^2 & 2 \cdot
(d-1) & 1 \\ 0 & 0 &  & & & & d^2 & 0
\end{array} \right)$$

The stationary distribution $\pi = (\pi_0, \pi_1, \pi_2, \ldots,
\pi_d)$ satisfies $\pi P = \pi$, so $$\pi_0 = \frac{\pi_1}{d^2}
\hspace{.5in} \pi_d = \frac{\pi_{d-1}}{d^2},$$

and for $j \not=0$ or $d,$

$\ds \pi_j = \pi_{j-1}\left(\frac{d-j+1}{d} \right)^2 + \pi_j 2
\left( \frac{j}{d} \right) \left( \frac{d-j}{d} \right) +
\pi_{j+1} \left( \frac{j+1}{d} \right)^2$

Now $\pi_1 = d^2\pi_0 = \left( \begin{array}{c} d \\ 1 \end{array}
\right)^2 \pi_0$

We proceed by induction

\begin{eqnarray*} \pi_{j+1} & = & \left( \frac{d}{j+1} \right) ^2
\left( \pi_j - \pi_{j-1} \left( \frac{d-j+1}{d} \right)^2 - \pi_j
2 \left( \frac{j}{d} \right) \left( \frac{d-j}{d} \right) \right)
\\ & = & \left( \frac{d}{j+1} \right) ^2 \left[ \left(
\frac{d!}{(d-j)!j!} \right)^2 \right. \\ & & \hspace{.2in} -
\left( \frac{d!}{(d-j+1)!(j-1)!} \right) \left( \frac{d-j+1}{d}
\right)^2 \\ & & \hspace{.4in} \left. -
\left(\frac{d!}{(d-j)!j!}\right)^2 \cdot 2 \left(\frac{j}{d}
\right)\left( \frac{d-j}{d} \right) \right] \pi_0 \\ & = & \left(
\frac{d}{j+1} \right)^2 \left[ \left( \frac{d!}{(d-j)!j!}
\right)^2 - \frac{1}{d^2} \left( \frac{d!}{(d-j)!(j-1)!} \right)^2
\right. \\ & & - \left. \left( \frac{d!}{(d-j)!j!} \right)^2 \cdot
2 \frac{j}{d} \frac{d-j}{d} \right] \pi_0 \\ & = & \pi_0 \left(
\frac{d}{j+1} \right)^2 \left( \frac{d!}{(d-j)!j!} \right)^2
\left[ 1 - \frac{j^2}{d^2} - \frac{2j(d-j)}{d^2} \right] \\ &  = &
\pi_0 \frac{d^2}{(j+1)^2} \left( \frac{d!}{(d-j)!j!}
\right)^2\left( \frac{d^2 - j^2 - 2jd + 2j^2}{d^2} \right) \\ & =
& \pi_0 \left( \frac{d!}{(d-j)!(j+1)!} \right)^2 (d-j)! \\ & = &
\pi_0 \left( \begin{array}{c} d \\ j+1
\end{array} \right)^2
\end{eqnarray*}

So $\ds \pi_{d-1} = \pi_0 \left( \begin{array}{c} d \\ d-1
\end{array} \right)^2 = \pi_0 d^2$

$\ds \pi_d = \pi_0 = \pi_d \left( \begin{array}{c} d \\ d
\end{array} \right)^2$

Since $\ds \sum \pi_j = 1$ we must have $$\pi_0 = \left[ \sum_{j =
0}^d \left( \begin{array}{c} d \\ j \end{array} \right)^2
\right]^{-1} $$



\end{document}
MA222qu1.tex