The Bernoulli-Laplace and Ehrenfest urn diffusion models

Intuition Beginner

Imagine two boxes and a pile of balls. The Ehrenfest urn has $n$ balls split between the two boxes. At each step you pick one ball at random and move it to the other box. Over time the count in the left box wanders up and down, but it spends most of its time near half-full. The question is: starting from all balls on the left, how many steps until you can no longer tell which box things began in?

The Bernoulli-Laplace model is the swapping cousin. Now each box holds exactly $n$ balls, one box red and one box white at the start. At each step you grab one ball from each box and swap them. The number of red balls in the left box slowly settles toward an even mix.

Both models ask the same thing: how long until the system forgets where it started? The remarkable fact is that the exact answer comes from a classical family of polynomials.

Visual Beginner

Picture the count of balls in the left urn as a marker hopping along a line of positions from $0$ to $n$. Near the ends the marker is strongly pulled back toward the middle; near the middle it drifts almost freely. The distribution of the marker starts as a spike at one end and spreads into a bell shape centered at $n/2$.

The arrows of the restoring pull get shorter as you approach the center. That shrinking pull is what the eigenvalues $1-2k/n$ record: small wiggles relax slowly, big swings relax fast.

Worked example Beginner

Take the Ehrenfest urn with $n=4$ balls. The left urn can hold $0,1,2,3,$ or $4$ balls. If the left urn has $j$ balls, then with probability $j/4$ you move one out (count drops to $j-1$) and with probability $(4-j)/4$ you move one in (count rises to $j+1$).

Start with all $4$ on the left. Step 1: a ball must leave, so the count goes to $3$ for certain. Step 2: from $3$, the count drops to $2$ with probability $3/4$ or returns to $4$ with probability $1/4$.

The long-run distribution is the binomial: position $j$ has probability $\left(\genfrac{}{}{0ex}{}{4}{j}\right)/16$, giving $1/16,4/16,6/16,4/16,1/16$. The center is six times as likely as either end.

The smallest eigenvalue gap is $2/4=0.5$. So the leading correction to stationarity shrinks by a factor of $0.5$ each step, and after a handful of steps the memory of starting at $4$ is mostly gone.

Check your understanding Beginner

Formal definition Intermediate+

The Ehrenfest urn. Identify a configuration of $n$ labelled balls across two urns with a point of the hypercube ${\mathbb{Z}}_2^n$: coordinate $i$ is $0$ or $1$ according to which urn holds ball $i$. One step picks a coordinate uniformly and flips it. This is the (lazy-free) random walk on ${\mathbb{Z}}_2^n$ driven by the measure $Q$ uniform on the $n$ standard generators $e_1,\dots ,e_n$. The Hamming-weight projection $X_t={\sum }_i{\omega }_i$ collapses the walk to a birth-death chain on $\{0,1,\dots ,n\}$ with transition kernel

$$P(j,j+1)=\frac{n-j}{n},P(j,j-1)=\frac{j}{n}.$$

This projected chain is the Ehrenfest chain. Its stationary distribution is $\pi (j)=\left(\genfrac{}{}{0ex}{}{n}{j}\right)2^{-n}$, and it is reversible with respect to $\pi$.

The Bernoulli-Laplace diffusion. Fix $n$ and $k$. Take two urns of $k$ balls each (so $n=2k$ balls in all), with $k$ marked balls distributed between them. One step draws a ball from each urn uniformly and swaps them. The number $Y_t$ of marked balls in the left urn is a birth-death chain on $\{0,\dots ,k\}$ with

$$P(j,j+1)=(\frac{k-j}{k}{)}^2,P(j,j-1)=(\frac{j}{k}{)}^2,$$

and the holding probability $P(j,j)=1-P(j,j+1)-P(j,j-1)$ accounts for swaps that exchange like-colored balls. For unequal urn sizes the rates carry the obvious mixed denominators. The chain lives on the Johnson scheme $J(n,k)$: states are the $k$-subsets of an $n$-set, and the walk is the natural $S_n$-symmetric chain on $S_n/(S_k\times S_{n-k})$. Its stationary distribution is hypergeometric, $\pi (j)=\left(\genfrac{}{}{0ex}{}{k}{j}\right)\left(\genfrac{}{}{0ex}{}{n-k}{k-j}\right)/\left(\genfrac{}{}{0ex}{}{n}{k}\right)$.

Eigenfunctions. The Ehrenfest chain is diagonalized by the Krawtchouk polynomials $K_m(j)$, orthogonal with respect to the binomial weight; the Bernoulli-Laplace chain is diagonalized by the dual-Hahn polynomials, orthogonal with respect to the hypergeometric weight. In both cases these are the spherical functions of the underlying association scheme 07.05.06, and the eigenvalue attached to the degree-$m$ polynomial is

$${\beta }_m=1-\frac{2m}{n}(\text{Ehrenfest}),{\beta }_m=1-\frac{m(n-m+1)}{k(n-k)}(\text{Bernoulli-Laplace, balanced }n=2k).$$

The sign convention is the standard probabilist's one: eigenvalues lie in $[-1,1]$, with ${\beta }_0=1$ for the constant eigenfunction.

Counterexamples to common slips

• Confusing the hypercube walk with its projection. The walk on ${\mathbb{Z}}_2^n$ has $2^n$ states; the Ehrenfest chain is its lumping to $n+1$ states by Hamming weight. They share eigenvalues $1-2k/n$ but the multiplicities differ — the hypercube has $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ eigenfunctions at level $k$, the projected chain has one.
• Laziness changes the spectrum, not the eigenfunctions. Adding a holding probability replaces ${\beta }_m$ by a convex combination with $1$; the Krawtchouk and dual-Hahn eigenvectors are unchanged. Cutoff statements depend on which version is used.
• The Bernoulli-Laplace eigenvalues are not $1-2m/n$. The swap dynamics give a quadratic-in-$m$ gap structure (dual Hahn), unlike the linear Krawtchouk gaps of Ehrenfest. Reading off the Ehrenfest formula for Bernoulli-Laplace gives the wrong cutoff constant.

Key theorem with proof Intermediate+

Theorem (Krawtchouk diagonalization of the Ehrenfest chain). Let $P$ be the Ehrenfest transition kernel on $\{0,\dots ,n\}$. For $m=0,1,\dots ,n$ the Krawtchouk polynomial

$$K_m(j)=\sum _{i=0}^m(-1{)}^i(\genfrac{}{}{0ex}{}{j}{i}\left)\right(\genfrac{}{}{0ex}{}{n-j}{m-i})$$

is a right eigenfunction of $P$ with eigenvalue ${\beta }_m=1-2m/n$:

$$\sum _{j^{\prime }}P(j,j^{\prime })K_m(j^{\prime })=\left(1-\frac{2m}{n}\right)K_m(j).$$

Proof. Lift to the hypercube. On ${\mathbb{Z}}_2^n$ the walk averages a function over single-coordinate flips: $(Pf)(\omega )=\frac{1}{n}{\sum }_{i=1}^{n}f(\omega +e_i)$. The characters of ${\mathbb{Z}}_2^n$ are ${\chi }_S(\omega )=(-1{)}^{{\sum }_{i\in S}{\omega }_i}$ for $S\subseteq \{1,\dots ,n\}$, and they are an eigenbasis: flipping coordinate $i$ multiplies ${\chi }_S$ by $-1$ when $i\in S$ and by $+1$ otherwise, so

$$(P{\chi }_S)(\omega )=\frac{1}{n}(\sum _{i\in S}(-1){\chi }_S(\omega )+\sum _{i\notin S}{\chi }_S(\omega ))=\frac{(n-|S|)-|S|}{n}{\chi }_S(\omega )=(1-\frac{2|S|}{n}){\chi }_S(\omega ).$$

Thus every character of weight $|S|=m$ is an eigenfunction with eigenvalue $1-2m/n$. Project: an eigenfunction of $P$ on the hypercube that depends only on the Hamming weight $j={\sum }_i{\omega }_i$ descends to an eigenfunction of the lumped chain with the same eigenvalue. Summing ${\chi }_S$ over all $S$ of size $m$ produces a weight-only function,

$$\sum _{|S|=m}{\chi }_S(\omega )=K_m(j),$$

since the number of $S$ of size $m$ meeting the support of $\omega$ in $i$ points contributes the alternating count above. This $K_m$ is the degree-$m$ Krawtchouk polynomial, and it inherits eigenvalue $1-2m/n$. $\square$

Bridge. This computation builds toward the upper-bound-lemma estimate of 07.05.05 specialized to a commutative walk: because ${\mathbb{Z}}_2^n$ is abelian, the character sum over irreducible representations collapses to a single sum over Krawtchouk polynomials, and this is exactly the abelian face of the non-abelian Fourier program. The foundational reason the orthogonal polynomials appear is that they are the spherical functions of the Hamming association scheme 07.05.06, so this is dual to the Gelfand-pair zonal-spherical theory of 07.05.13: the central insight is that diagonalizing a symmetric Markov chain is computing the spherical functions of its scheme, and it appears again in the dual-Hahn analysis of Bernoulli-Laplace, where the same projection from $S_n/(S_k\times S_{n-k})$ generalises the hypercube case.

Exercises Intermediate+

Advanced results Master

Theorem 1 (Bernoulli-Laplace cutoff — Diaconis-Shahshahani 1987). For the balanced Bernoulli-Laplace diffusion on $J(2k,k)$ with $n=2k$, the total variation distance to stationarity exhibits a cutoff at $t_n=\frac{1}{4}n\log n$: for any fixed $c$,

$$\underset{n\to \infty }{\lim }\Vert P_{\ast }^{t_n+cn}-\pi {\Vert }_{\mathrm{TV}}=f(c),$$

a fixed profile $f$ decreasing from $1$ to $0$, so the walk is mixed at $\frac{1}{4}n\log n$ and not before. The proof diagonalizes the chain by dual-Hahn polynomials 07.05.06, identifies the leading eigenvalue ${\beta }_1=1-2/k$, and feeds the eigenvalue spectrum into the upper-bound lemma 07.05.05; the matching lower bound uses the variance of the slowest dual-Hahn eigenfunction (a second-moment / Wilson argument).

Theorem 2 (Ehrenfest cutoff). The lazy Ehrenfest walk on ${\mathbb{Z}}_2^n$, equivalently the random walk that flips a uniform coordinate, mixes with a cutoff at $\frac{1}{4}n\log n$ in total variation. The Krawtchouk eigenvalues $1-2m/n$ make the upper-bound sum ${\sum }_m\left(\genfrac{}{}{0ex}{}{n}{m}\right)(1-2m/n{)}^{2t}$ a single elementary expression whose transition occurs at $\frac{1}{4}n\log n$; the same constant governs the projected birth-death chain on Hamming weights. This is the canonical hypercube cutoff of 07.05.08.

Theorem 3 (spectral gap and relaxation time). The Ehrenfest gap is $2/n$ with relaxation time $n/2$; the balanced Bernoulli-Laplace gap is $2/k=4/n$ with relaxation time $n/4$. In both cases the relaxation time is order $n$ while the mixing time is order $n\log n$, the logarithmic factor being the signature of cutoff: many eigenvalues near the spectral edge conspire so that mixing takes a $\log n$ multiple of the relaxation time.

Theorem 4 (Ornstein-Uhlenbeck scaling limit). Center and rescale the Ehrenfest count: $Z_s^{(n)}=(X_{\lfloor ns/2\rfloor }-n/2)/\sqrt{n/4}$. As $n\to \infty$, $Z^{(n)}$ converges weakly to the stationary Ornstein-Uhlenbeck process $d{Z}_s=-Z_{s}ds+\sqrt{2}d{B}_s$, whose generator has Hermite-polynomial eigenfunctions with eigenvalues $-m$. The Krawtchouk polynomials converge to Hermite polynomials under this scaling, and the discrete eigenvalues $1-2m/n$ become the continuous $e^{-ms\cdot (2/n)\cdot (n/2)}=e^{-ms}$, matching the OU spectrum.

Synthesis. These two models are the foundational reason representation theory and classical orthogonal polynomials are the same subject viewed from two sides: the Ehrenfest chain is diagonalized by Krawtchouk polynomials and the Bernoulli-Laplace chain by dual-Hahn polynomials, and this is exactly the statement that the spherical functions of the Hamming and Johnson schemes 07.05.06 are these polynomial families. Putting these together with the upper-bound lemma 07.05.05, the entire mixing analysis reduces to estimating one elementary sum, and the central insight is that the abelian (or Gelfand-pair) symmetry forces the matrix Fourier transform to collapse to a single orthogonal-polynomial eigenvalue at each level. The pattern generalises: every reversible chain with a transitive symmetry group is diagonalized by the spherical functions of its association scheme, so Ehrenfest and Bernoulli-Laplace are the worked prototypes that build toward the general theory, and the Ornstein-Uhlenbeck limit shows the bridge is to continuous diffusions, where Krawtchouk degenerates to Hermite and the cutoff constant $\frac{1}{4}n\log n$ persists as the relaxation-to-mixing logarithmic gap. The Bernoulli-Laplace quadratic-gap structure is dual to the Ehrenfest linear-gap structure exactly as the Johnson scheme is dual to the Hamming scheme.

Full proof set Master

Proposition 1 (stationarity and reversibility of the Ehrenfest chain). The binomial law $\pi (j)=\left(\genfrac{}{}{0ex}{}{n}{j}\right)2^{-n}$ is reversible for the Ehrenfest kernel $P(j,j+1)=(n-j)/n$, $P(j,j-1)=j/n$.

Proof. Reversibility is the detailed-balance identity $\pi (j)P(j,j+1)=\pi (j+1)P(j+1,j)$. The left side is $\left(\genfrac{}{}{0ex}{}{n}{j}\right)2^{-n}\frac{n-j}{n}$ and the right side is $\left(\genfrac{}{}{0ex}{}{n}{j+1}\right)2^{-n}\frac{j+1}{n}$. Using $\left(\genfrac{}{}{0ex}{}{n}{j+1}\right)=\left(\genfrac{}{}{0ex}{}{n}{j}\right)\frac{n-j}{j+1}$,

$$\left(\genfrac{}{}{0ex}{}{n}{j+1}\right)\frac{j+1}{n}=\left(\genfrac{}{}{0ex}{}{n}{j}\right)\frac{n-j}{j+1}\cdot \frac{j+1}{n}=\left(\genfrac{}{}{0ex}{}{n}{j}\right)\frac{n-j}{n}.$$

Both sides agree, so $\pi$ is reversible, hence stationary. $\square$

Proposition 2 (the abelian upper-bound lemma is exact at the leading order for Ehrenfest). For the Ehrenfest walk on ${\mathbb{Z}}_2^n$ started at $0$, the total variation distance satisfies, for $t=\frac{1}{4}n(\log n+c)$ with $c\to \infty$ slowly,

$$\Vert P_0^t-\pi {\Vert }_{\mathrm{TV}}=\frac{1}{2}(1+o(1))e^{-c/2}.$$

Proof sketch. The upper bound of Exercise 7 gives $4\Vert \cdot {\Vert }_{\mathrm{TV}}^2\le {\sum }_{m\ge 1}\left(\genfrac{}{}{0ex}{}{n}{m}\right)(1-2m/n{)}^{2t}$. With $t=\frac{1}{4}n(\log n+c)$ the $m=1$ term is $e^{-c}(1+o(1))$ and the tail is ${\sum }_{m\ge 2}\frac{e^{-mc}}{m!}=e^{-c}(e^{-c}-\cdots )=o(e^{-c})$, so the bound is $e^{-c}(1+o(1))$, giving $\Vert \cdot {\Vert }_{\mathrm{TV}}\le \frac{1}{2}{e}^{-c/2}(1+o(1))$. The matching lower bound applies the second-moment method to the linear eigenfunction $K_1(j)=n-2j$: under $P_0^t$ its mean is $n(1-2/n{)}^t\approx n^{1/2}{e}^{-c/2}$ while under $\pi$ it has mean $0$ and standard deviation $\sqrt{n}$, so the two laws are separated by a constant multiple of $e^{-c/2}$ standard deviations, which Chebyshev converts into the lower bound. The two bounds match to leading order. $\square$

Proposition 3 (Bernoulli-Laplace eigenvalues are the dual-Hahn spectrum). For the balanced model $n=2k$, the eigenvalues of the swap chain are ${\beta }_m=1-\frac{m(n-m+1)}{k(n-k)}$, $m=0,\dots ,k$, with the degree-$m$ dual-Hahn polynomial as eigenfunction.

Proof. The swap operator is $S_n$-invariant on $L^2(J(n,k))$, and $(S_n,S_k\times S_{n-k})$ is a Gelfand pair, so $L^2(J(n,k))$ decomposes multiplicity-free into $S_n$-irreducibles $V_0\oplus V_1\oplus \cdots \oplus V_k$ with $V_m$ indexed by the two-row partition $(n-m,m)$. The swap operator acts as the scalar ${\beta }_m$ on $V_m$ by Schur's lemma. Evaluating the operator on the spherical function (the zonal eigenvector), which is the degree-$m$ dual-Hahn polynomial in the overlap variable $j$, computes the scalar: the action of swapping one pair changes the overlap by $\pm 1$ with the stated quadratic rates, and the dual-Hahn three-term recurrence forces the eigenvalue $1-m(n-m+1)/(k(n-k))$. The multiplicity-free decomposition guarantees these are all the eigenvalues. $\square$

Connections Master

• Association schemes and Krawtchouk/Hahn polynomials 07.05.06. The eigenfunctions of both urn chains are the spherical functions of the Hamming scheme (Krawtchouk) and the Johnson scheme (dual Hahn). That unit supplies the Bose-Mesner algebra and the orthogonal-polynomial families; this unit is its first dynamical payoff, turning the $P/Q$ eigenvalue matrices into Markov-chain spectra.

• Random walk on a finite group; Upper Bound Lemma 07.05.05. The mixing bounds here are the commutative specialization of the upper-bound lemma: because ${\mathbb{Z}}_2^n$ is abelian and $(S_n,S_k\times S_{n-k})$ is a Gelfand pair, the matrix character sum collapses to a single orthogonal-polynomial eigenvalue per level, making the bound an elementary sum.

• Cutoff phenomenon 07.05.08. The $\frac{1}{4}n\log n$ transitions of Ehrenfest and Bernoulli-Laplace are two of the original cutoff examples; this unit supplies the orthogonal-polynomial diagonalization that the abstract cutoff machinery of that unit consumes, and the Ehrenfest hypercube walk is the cutoff prototype stated there.

• Partially ranked data and Gelfand pairs 07.05.13. Bernoulli-Laplace lives on the same coset space $S_n/(S_k\times S_{n-k})$ as partially ranked data; the zonal spherical functions used there to analyze ranking statistics are exactly the dual-Hahn eigenfunctions diagonalizing the swap chain here, so the two units share their harmonic analysis.

• De Finetti exchangeability 07.05.14. The Bernoulli-Laplace stationary law is exchangeable on the $k$-subset, and the urn dynamics are the canonical finite exchangeable Markov chain; this connects the equilibrium analysis here to the exchangeability theory of that unit.

Historical & philosophical context Master

Paul and Tatiana Ehrenfest introduced their urn model in 1907 ^{[Ehrenfest 1907]} to answer Loschmidt's and Zermelo's objections to Boltzmann's $H$-theorem: a finite, fully reversible, recurrent Markov chain can nonetheless display apparently irreversible relaxation toward equilibrium, with Poincaré recurrence times so long as to be physically unobservable. The model made the statistical-mechanical reconciliation of microscopic reversibility and macroscopic irreversibility concrete and computable. Mark Kac later popularized it as the standard pedagogical model for approach to equilibrium. The exact spectral analysis via Krawtchouk polynomials was carried out by Karlin and McGregor in 1965 ^{[Karlin McGregor 1965]} within their broader program of diagonalizing birth-death chains by orthogonal polynomials.

The Bernoulli-Laplace model descends from Daniel Bernoulli's and Laplace's eighteenth-century urn schemes for diffusion and mixing. Diaconis and Shahshahani's 1987 paper ^{[Diaconis Shahshahani 1987]} computed its exact mixing time, proving the sharp $\frac{1}{4}n\log n$ cutoff using the dual-Hahn polynomials as the spherical functions of the Johnson scheme, and Diaconis's 1988 monograph ^{[Diaconis 1988]} set both urn models within the representation-theoretic framework, presenting them as the commutative worked examples that parallel the non-abelian random-transposition and riffle-shuffle analyses.

Bibliography Master

@article{Ehrenfest1907,
  author = {Ehrenfest, Paul and Ehrenfest, Tatiana},
  title = {Über zwei bekannte Einwände gegen das Boltzmannsche H-Theorem},
  journal = {Physikalische Zeitschrift},
  volume = {8},
  year = {1907},
  pages = {311--314},
}

@article{DiaconisShahshahani1987,
  author = {Diaconis, Persi and Shahshahani, Mehrdad},
  title = {Time to reach stationarity in the {Bernoulli}-{Laplace} diffusion model},
  journal = {SIAM Journal on Mathematical Analysis},
  volume = {18},
  year = {1987},
  pages = {208--218},
}

@book{Diaconis1988,
  author = {Diaconis, Persi},
  title = {Group Representations in Probability and Statistics},
  publisher = {Institute of Mathematical Statistics},
  year = {1988},
  series = {IMS Lecture Notes--Monograph Series},
  volume = {11},
}

@article{KarlinMcGregor1965,
  author = {Karlin, Samuel and McGregor, James},
  title = {Ehrenfest urn models},
  journal = {Journal of Applied Probability},
  volume = {2},
  year = {1965},
  pages = {352--376},
}

@book{LevinPeres2017,
  author = {Levin, David A. and Peres, Yuval},
  title = {Markov Chains and Mixing Times},
  edition = {2nd},
  publisher = {American Mathematical Society},
  year = {2017},
}

@book{CeccheriniSilberstein2008,
  author = {Ceccherini-Silberstein, Tullio and Scarabotti, Fabio and Tolli, Filippo},
  title = {Harmonic Analysis on Finite Groups},
  publisher = {Cambridge University Press},
  year = {2008},
}