Bernoulli-Laplace

The Bernoulli-Laplace model of diffusion describes the flow of two incompressible liquids between two containers. It may be described as two urns that contain $k$ balls each. Initially, the balls in the left urn are all red and the balls in the right urn are all blue. At each step, pick a ball at random from each urn and exchange them so that each box always contains $d$ balls. Let $X_n$ be the number of blue balls in the left urn at step $n = 0,1,2,...$ , find the transition matrix, and the stationary distribution, $\boldsymbol{\pi}$ .

Transition Matrix

Initially, $X_0 = 0$ and the complete state space of $X_n = \{0,1,2,...,d\}$ . Furthermore, to understand the transition matrix, the transition probabilities, $P(X_{n+1} = i | X_n = j)$ , between states must be known.

Suppose $X_n = j$ , there are 4 possible outcomes to $X_{n+1} = i$ from $X_n = j$ of any given step:

Blue from the left and blue from the right with probability $\left ( \frac{ j}{k} \right ) \left ( \frac{k-j}{k} \right )$ giving $X_{n+1} = j$ .
Blue from the left and red from the right with probability $\left ( \frac{j}{k} \right ) \left ( \frac{j}{k} \right )$ giving $X_{n+1} = j- 1$ .
Red from the left and red from the right with probability $\left ( \frac{k-j}{k} \right ) \left ( \frac{j}{k} \right )$ giving $X_{n+1} = j$ .
Red from the left and blue from the right with probability $\left ( \frac{k-j}{k} \right ) \left ( \frac{k-j}{k} \right )$ giving $X_{n+1} = j+1$ .

Moreover, these outcomes can be shown as,

$\begin{equation*} \begin{array}{llll} P_{jj} = 2\frac{j(k-j)}{k^2} \\ \\ P_{j,j+1} = \left ( \frac{k-j}{k} \right )^2\\ \\ P_{j,j-1} = \left ( \frac{j}{k} \right ) ^2 \\ \\ P_{j,k} = 0 \; \mathrm{if} \; k \neq j -1 , j , j + 1 \end{array} \end{equation*}$

Consequently, the complete transition matrix,

Stationary distribution

Similar to the Ehrenfest urn model that was solved previously, the long term probability that $j$ blue marbles are in the left urn is an essential question to be solved.

To begin with, $\pi_0 = \frac{\pi_1}{k^2}$ and $\pi_d = \frac{\pi_{k-1}}{k^2}$ (using $\pi_j = \sum_i \pi_i P_{ij}$ ). Next, for $j\neq 0 \; \mathrm{or} \; d$ ,

$\begin{equation*} \pi_j = \pi_{j-1} \left ( \frac{k-j + 1}{k} \right )^2 + \pi_j \frac{2j(k-j)}{k^2} + \pi_{j+1} \left ( \frac{j+1}{k} \right ) ^2 \end{equation*}$

Incidentally, $\pi_1 = k^2 \pi_0$ , can be written as $\pi_1 = {k \choose 1} ^2\pi_0$ . Next solve using induction,

$\begin{align*} \pi_{j+1} &= \left ( \frac{k}{j+1} \right )^2 \left [ \pi_j - \pi_{j-1} \left (\frac{k-j + 1}{k} \right )^2 - \pi_j \frac{2j(k-j)}{k^2} \right ] \\ &= \left ( \frac{k}{j+1} \right )^2 \left [ {k \choose j} ^2 - {k \choose {j -1}}^2 \left (\frac{k-j + 1}{k} \right )^2 \right \\ &\qquad \left - {k \choose j}^2 \frac{2j(k-j)}{k^2} \right ] \pi_0 \\ &=\left ( \frac{k}{j+1} \right )^2 \left [ {k \choose j} ^2 - \frac{1}{k^2} \left ( \frac{k!}{(k-j)!(j-1)!} \right )^2 \\ \right & \qquad \left - {k \choose j}^2 \frac{2j(k-j)}{k^2} \right ] \pi_0 \\ &= \left ( \frac{k}{j+1} \right )^2 {k \choose j} ^2 \left [ 1 - \frac{j^2}{k^2} - \frac{2 j(k-j)}{k^2} \right ] \pi_0\\ &=\left ( \frac{k}{j+1} \right )^2 {k \choose j} ^2 \left [ \frac{k^2 - j^2 -2 j k -2 j^2}{k^2} \right ] \pi_0\\ &= \pi_0 \left ( \frac{k!}{(k-j)!(j+1)!} \right ) ^2 (k-j)! \implies \\ \pi_{j+1} &= \pi_0 { k \choose j+1 } \end{align*}$

Since, $\pi_0 = \pi_k = {k \choose k} ^2 \pi_k$ and $\sum_j \pi_j = 1$ ,

$\pi_0 = \left [ \sum_{j=0}^k {k \choose j } ^2 \right ] ^{-1} = {2k \choose k}$

Finally, the unique limiting distribution for the Bernoulli-Laplace Urn model

$\pi_j = {k \choose j}{2k \choose k}^{-1}$

As a final point it’s important to note that the final form of $\pi_j$ requires a good understanding of combinatorics and lots of scratch paper to simplify. Save for Bernoulli and Laplace like intuition of these types of problems, it is difficult to recognize the mathematical trick to write $k^2 = {k \choose 1}^2$ and work from there.

Bernoulli-Laplace Model of Diffusion

Bernoulli-Laplace

Transition Matrix

Stationary distribution

Monte Carlo simulation

Leave a comment Cancel reply