Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 215 / 3

Couple two noisy voter model chains by choosing the same update vertex, the same refresh coin and refreshed spin, and, for a voter update, the same chosen neighbor. Let $D_t$ be their Hamming distance. If $G$ is $r$-regular, conditioning on the current disagreement set givesbecause every disagreeing vertex is counted in exactly $r$ neighbor sets. ThereforeThe coupling inequality for total variation and $1_{\{{\sigma }_t\ne {\sigma }_t^{\prime }\}}\le D_t$ give

For a nonregular graph, use the degree-weighted Hamming metricUnder the same coupling,Here the final double sum equals ${\sum }_{u\in D_t}\mathrm{deg}(u)=W_t$. Since $W_0\le {\sum }_v\mathrm{deg}(v)=2|E|$ and $W_t\ge 1$ whenever the chains differ,