Take $N$ balls numbered $1$ to $N$ and two urns, A and B. Every second, draw a number uniformly at random from $1$ to $N$ and move the ball with that number to the other urn. Start with all $N$ balls in A. The count in A drops, at first by nearly one ball per step, then more slowly, and settles into fluctuations around $N/2$ that never stop. Run the film backward and the same rule describes it: the process is reversible, and every configuration, the starting one included, is revisited eventually with probability one. This is the Ehrenfest urn, proposed by Paul and Tatiana Ehrenfest in 1907 as a model in which the approach to equilibrium and the recurrence of the initial state can both be computed, and in which the apparent conflict between them turns out to be a statement about time scales. Every quantity below is exact.

A walk on the corners of the cube

The state of the system is the set of balls in A, a binary vector $x \in \{0,1\}^N$ with $x_i = 1$ when ball $i$ is in A. One step flips one uniformly chosen coordinate. So the urn process is the simple random walk on the corners of the $N$-dimensional cube, each corner joined to its $N$ neighbors at Hamming distance $1$, and the number of balls in A is the Hamming weight of the current corner, the level $\ell$ of the post on the spiky cube.

Every corner has the same number of neighbors, so the stationary distribution of the walk is uniform over the $2^N$ corners, and the stationary distribution of the count $X_t$ of balls in A is the number of corners at each level, normalized:

The equilibrium of the urn is the binomial distribution, the spiky cross-section of the earlier post: in the long run the process spends time at level $k$ in proportion to the width of that drawing at level $k$. The count itself is a Markov chain on $\{0, \ldots, N\}$, moving from $k$ to $k-1$ with probability $k/N$ (a ball in A was drawn) and to $k+1$ with probability $(N-k)/N$. That $\pi$ is stationary for it is the detailed balance identity $\binom{N}{k}(N-k) = \binom{N}{k+1}(k+1)$, whose two sides both count the edges of the cube between levels $k$ and $k+1$.

The binomial has mean $N/2$ and standard deviation $\sqrt{N}/2$. For $N = 100$ the equilibrium count is $50 \pm 5$; the stationary probability of finding $70$ or more balls in A is $3.9 \times 10^{-5}$, and of finding all $100$ there, $2^{-100} \approx 7.9 \times 10^{-31}$. In equilibrium, the state the process was started in is, together with its mirror image, the least probable state there is.

The mean relaxes exponentially

From level $k$, the next count is $k - 1$ with probability $k/N$ and $k + 1$ otherwise, so

The same recursion holds for the imbalance $X_t - N/2$. Subtract $N/2$ from both sides and use $1 - \tfrac{N}{2} = -\big(1 - \tfrac{2}{N}\big)\tfrac{N}{2}$ to get

Iterating, $\mathbb{E}[X_t] - N/2 = (1 - 2/N)^t\,(X_0 - N/2)$. The expected imbalance between the urns decays geometrically, with time constant $N/2$ steps. This is Newton’s law of cooling for two bodies exchanging heat, and it has been obtained from a reversible rule by taking an expectation; nothing irreversible was put in. Starting from all balls in A, the expected imbalance $N/2$ shrinks to the size of the equilibrium fluctuations, $\sqrt{N}/2$, after $t \approx \frac{N}{4}\ln N$ steps: about $115$ steps for $N = 100$. The same $\frac14 N \ln N$ is the mixing time of the cube walk: Diaconis, Graham and Morrison (1990) proved that the walk (in a version allowed to stay put) is far from uniform before $\frac14 N\ln N$ steps and close to uniform shortly after.

The factor $1 - 2/N$ is the second largest eigenvalue of the transition matrix, and the full spectrum is also explicit. On the cube, the walk is diagonalized by the parity functions $\chi_S(x) = (-1)^{\sum_{i \in S} x_i}$, one for each subset $S$ of coordinates: flipping a random coordinate changes the sign of $\chi_S$ exactly when the coordinate lies in $S$, which happens with probability $|S|/N$, so $\chi_S$ is an eigenvector with eigenvalue $1 - 2|S|/N$. The eigenvalues of the count chain are therefore

a result of Kac (1947), and on the cube the eigenvalue $\lambda_j$ has multiplicity $\binom{N}{j}$: the binomial coefficient appears a third time, now as a spectral multiplicity. The second moment obeys a recursion of the same kind, $\mathbb{E}[X_{t+1}^2 \mid X_t = k] = (1 - 4/N)k^2 + 2k + 1$, with $\lambda_2 = 1 - 4/N$ as its factor, so the variance of the count at every time is also a closed computation, and the widget below uses both recursions.

Reversibility gives a statement about the past as well. In the stationary process, detailed balance means the film run backward has the same law as the film run forward, so $\mathbb{P}(X_{t-s} = j \mid X_t = k) = \mathbb{P}(X_{t+s} = j \mid X_t = k)$ for every $j$, $k$, and $s$, and in particular

Conditional on an unusual count now, the expected past is the mirror image of the expected future: the count rose to $k$ along the same exponential curve it is about to descend. An imbalance observed in equilibrium is, in expectation, the top of a symmetric peak, not the start of a decay. This is the picture Boltzmann gave in his 1896 reply to Zermelo, and here it is a two-line consequence of detailed balance.

Return times

The return times follow from a formula of Kac. For an irreducible Markov chain with stationary distribution $\pi$, the expected time to return to a state $k$, starting from $k$, is

For the proof, run the chain in its stationary regime. For each $t \ge 1$, the event that the most recent visit to $k$ at or before time $0$ occurred exactly $t - 1$ steps ago has probability $\pi_k\,\mathbb{P}_k(\tau_k^+ \ge t)$ by stationarity. These events are disjoint and, since the chain visits $k$ infinitely often, their union is certain, so $\pi_k \sum_{t \ge 1}\mathbb{P}_k(\tau_k^+ \ge t) = 1$, and the sum is $\mathbb{E}_k[\tau_k^+]$. (Periodicity is no obstacle: the count chain alternates parity, and the formula holds regardless.)

For the urn, then,

The all-in-A state returns, on average, after exactly $2^N$ steps. The balanced state returns after $2^N/\binom{N}{N/2} \approx \sqrt{\pi N / 2}$ steps. As a function of the level, the expected return time is the binomial turned upside down: on a logarithmic scale it is $N \log 2 - \log \binom{N}{k}$, a U with its floor at $\tfrac12 \log(\pi N/2)$ in the middle and its rims at $N \log 2$. The spiky cube, seen through return times, is a valley with two cliffs.

The last column is the expected number of steps to go from the all-in-A state down to the balanced state for the first time, from the standard formula for hitting times of a birth–death chain: the expected time to step from $j$ to $j+1$ is $\frac{1}{\pi_j p_j}\sum_{i \le j}\pi_i$ with $p_j = (N-j)/N$, and the reverse direction is the mirror image. Summing these over the levels between $N$ and $N/2$ gives $146.9$ for $N = 100$; summing the reverse formula from $N/2$ up to $N$ gives $1.28 \times 10^{30}$, a little more than $2^N$ itself. Going down takes a hundred-odd steps and going back up takes $10^{30}$, and both numbers come from the same reversible rule.

With $N = 20$ balls and one move per microsecond, the initial state recurs about once a second, and the recurrence is observable. With $N = 50$ and one move per nanosecond, the expected wait is $2^{50}$ nanoseconds, thirteen days. With $N = 100$ it is $4 \times 10^{13}$ years, three thousand times the age of the universe; a mole of molecules puts $N$ near $10^{23}$. Recurrence is a theorem, and for $N$ of macroscopic size it is unobservable. The widget computes the exact mean and variance of the count from the all-in-A start, and the exact return-time landscape, for any $N$:

The two objections

Boltzmann’s H-theorem of 1872 derived, from the kinetic equation for a dilute gas, a quantity $H$ that can only decrease in time. Two objections followed. Loschmidt’s, in 1876, is the reversibility objection: the equations of mechanics are symmetric under time reversal, so for every motion in which $H$ decreases there is a reversed motion in which it increases, and a monotone $H$ cannot follow from mechanics alone. Zermelo’s, in 1896, is the recurrence objection: by Poincaré’s recurrence theorem (1890), an isolated mechanical system with bounded energy returns arbitrarily close to its initial state, so $H$ cannot decrease forever. Boltzmann’s replies of 1896 and 1897 made the statistical position explicit: the theorem is about overwhelmingly probable behavior, the recurrence times of macroscopic systems are far longer than any observation, and the $H$-curve of a system in equilibrium is a sequence of symmetric fluctuation peaks.

In the urn, each of these statements is a calculation. It is reversible (detailed balance holds), and its expected count nevertheless decays monotonically toward $N/2$ from any start, with the decay curve’s mirror image as the expected past. It is recurrent, with the initial state returning after exactly $2^N$ steps on average, and $2^N$ steps exceed any feasible observation for $N$ in the hundreds, while the relaxation takes $\frac14 N \ln N$ steps. The 1907 paper of Paul and Tatiana Ehrenfest was written to exhibit this, and the mathematics was completed by Kac in 1947: the spectrum $1 - 2j/N$ in one paper and the recurrence formula $1/\pi_k$ in another, both in 1947. Siegert (1949) treated the approach to equilibrium in related gas models. The urn is now a standard textbook example, both of a reversible chain with a computable spectrum and of a chain obtained by projecting a larger one (the cube walk onto the count), in Levin, Peres and Wilmer.

References

• Paul Ehrenfest, Tatiana Ehrenfest. Über zwei bekannte Einwände gegen das Boltzmannsche H-Theorem. Physikalische Zeitschrift, 8:311–314, 1907. The urn, introduced to answer the reversibility and recurrence objections.
• Mark Kac. Random walk and the theory of Brownian motion. The American Mathematical Monthly, 54(7):369–391, 1947. The eigenvalues $1 - 2j/N$ and the full solution of the urn.
• Mark Kac. On the notion of recurrence in discrete stochastic processes. Bulletin of the American Mathematical Society, 53(10):1002–1010, 1947. The return-time formula $\mathbb{E}_k[\tau_k^+] = 1/\pi_k$.
• Arnold J. F. Siegert. On the approach to statistical equilibrium. Physical Review, 76:1708–1714, 1949. The approach to equilibrium in related gas models.
• Persi Diaconis, Ronald L. Graham, John A. Morrison. Asymptotic analysis of a random walk on a hypercube with many dimensions. Random Structures & Algorithms, 1(1):51–72, 1990. The cutoff at $\frac14 N \ln N$.
• David A. Levin, Yuval Peres, Elizabeth L. Wilmer. Markov Chains and Mixing Times. 2nd edition, American Mathematical Society, 2017. Section 2.3, the hypercube and the Ehrenfest urn; Section 2.5, hitting times of birth–death chains; Chapter 21, the return-time lemma.
• Ludwig Boltzmann. Entgegnung auf die wärmetheoretischen Betrachtungen des Hrn. E. Zermelo. Annalen der Physik, 293(4):773–784, 1896. The reply to the recurrence objection.
• Ernst Zermelo. Ueber einen Satz der Dynamik und die mechanische Wärmetheorie. Annalen der Physik, 293(3):485–494, 1896. The recurrence objection.