Product chains mix at time $\frac{n\log n}{2\gamma}$

For $i=1,\dots,n$ let $P_i$ be an irreducible, reversible Markov chain on a finite space $W_i$ of at least two states, with stationary distribution $\pi_i$ (detailed balance $\pi_i(x)P_i(x,y)=\pi_i(y)P_i(y,x)$). The product chain on $W_1\times\cdots\times W_n$ picks a uniformly random coordinate and updates it by its own chain, $P=\tfrac1n\sum_i\widetilde P_i$; its stationary distribution is the product $\pi(x)=\prod_i\pi_i(x_i)$. Mixing is measured in continuous time: with the heat kernel $H_t=\sum_ke^{-t}\tfrac{t^k}{k!}P^k$ and the total variation distance $\|\mu-\nu\|_{TV}=\max_A|\mu(A)-\nu(A)|$, the continuous mixing time $t^{\mathrm{cont}}_{\mathrm{mix}}(\varepsilon)$ is the first real time at which $\max_x\|H_t(x,\cdot)-\pi\|_{TV}\le\varepsilon$. Each factor's spectral gap is $\gamma_i=1-\lambda_2(P_i)$, with $\lambda_2$ the largest eigenvalue $\ne1$ (Mission VII); irreducibility together with at least two states is what makes this the book's $\gamma_i$.

The theorem (Theorem 20.7 of Levin–Peres–Wilmer) asserts, for $0<\varepsilon<1$, $n\ge2$:

1. if every $\gamma_i\ge\gamma$ and every factor satisfies $\sqrt{\min_x\pi_i(x)}\ge c_0$, then $\displaystyle t^{\mathrm{cont}}_{\mathrm{mix}}(\varepsilon)\le\frac{n\log n}{2\gamma}+\frac n\gamma\log\frac{1}{c_0\varepsilon}$;
2. if moreover $\gamma_i=\gamma$ exactly for every $i$, then $\displaystyle t^{\mathrm{cont}}_{\mathrm{mix}}(\varepsilon)\ge\frac{n}{2\gamma}\Bigl(\log n-\log\bigl(8\log\tfrac1{1-\varepsilon}\bigr)\Bigr)$.

The product of $n$ independent chains mixes at time $\tfrac{n\log n}{2\gamma}$, not $\tfrac n\gamma$: a coupon-collector logarithm beyond the obvious slowdown, because the last coordinate to equilibrate is what matters. This is the abstract form of the hypercube's $\tfrac12n\log n$ (the hypercube is the product of $n$ two-state chains with $\gamma=1$), and the template computation behind the cutoff of Mission XI.