= Bernoulli-Laplace diffusion model
{c}
{title2=$P(r,r+1)=(n-r)^2/n^2,\quad P(r,r-1)=r^2/n^2$}
Two urns each contain $n$ balls, with $n$ red and $n$ blue balls in total. Independently choose one ball uniformly from each urn and exchange them. The red count $R_k$ in the first urn is a <Markov chain> on $\{0,\ldots,n\}$. Its upward and downward probabilities are displayed above, and the probability of remaining at $r$ is $2r(n-r)/n^2$. Thus $\mathbb E[R_{k+1}\mid R_k=r]=1+(1-2/n)r$. Starting from $R_0=n$, <linearity of expectation> gives $\mathbb E[R_k]=n/2+(n/2)(1-2/n)^k$, with the initial value separately understood when $n=2,k=0$. Random exchanges drive the expected imbalance toward zero.
Back to article page
