= Solution
For a nonregular graph, use the degree-weighted Hamming metric
$$
W_t=\sum_{v\in V}\deg(v)
\mathbf1_{\{\sigma_t(v)\ne\sigma_t'(v)\}}.
$$
Under the same coupling,
$$
\begin{aligned}
\mathbb E[W_{t+1}-W_t\mid\sigma_t,\sigma_t']
={}&-\frac1n\sum_{v\in D_t}\deg(v)\\
&+\frac{1-p}{n}\sum_v\deg(v)
\frac{|N(v)\cap D_t|}{\deg(v)}\\
={}&-\frac pnW_t.
\end{aligned}
$$
Here the final double sum equals $\sum_{u\in D_t}\deg(u)=W_t$. Since $W_0\leq\sum_v\deg(v)=2|E|$ and $W_t\geq1$ whenever the chains differ,
$$
\boxed{\max_{\sigma,\sigma'}
\|P^t(\sigma,\cdot)-P^t(\sigma',\cdot)\|_{\mathrm{TV}}
\leq2|E|\left(1-\frac pn\right)^t.}
$$
Back to article page
