Here is an exercise from Olle Haggstrom's "Finite Markov Chains and Algorithmic Applications" from the chapter "Fast Convergence of MCMC Algorithms".
The exercise is based on random $q$-colorings of a finite graph with $k$ vertices. You have a color set with $q$ colors: $\{1,2,...,q\}$. You color the vertices so that no two adjacent vertices have same color.
You start from some configuration. At $n$-th step, you choose a vertex uniformly from $k$ vertices at random, call it $v$, then check the colors on the neighbors of that vertex. Generate a random permutation of $\{1,2,...,q\}$, say $R_n=\{i_1,i_2,...,i_q\}$ and look at the minimum $i$ such that $i$ is NOT on the neighbors of $v$, and give $v$ the color $i$.
This evolution of the coloring of a graph with time $n$ is a Markov Chain $X_n$. Let us have two independent starting graphs $X_n$ and $Y_n$ with equal set of vertices and same structure, but possibly different colors. We want to couple the graphs and see at what time the coupling happens.
The process to be followed is this: At $n$-th step, choose a vertex $v$ uniformly at random from $k$ vertices. Then look at the colour set on the neighborhood of $v$ in both graphs, call these two sets $N_1$ and $N_2$.Generate a random permutation of $[q]$, call it $R_n$. Give the minimum color in $R_n$ not on $N_1$ to $v$ in $X_n$, and if this color is not in $N_2$ also, give it to $v$ in $Y_n$. Otherwise, give the minimum color of $R_n$ not in $N_2$ to $v$ in $Y_n$.
At each step, change the color of ONE vertex only in this manner. In case the vertex $v$ has two different colors in $X_n$ and $Y_n$, call the $n$-th update a failed update.
Haggstrom has shown that $P(Failed \space update)\leq \dfrac{2d}{q}$.
The exercise: Show that the coupling can be done such that after $k$ stages of the algorithm, $P(X_k(v)\neq Y_k(v))\leq e^{-1}+(1-e^{-1})\dfrac{2d}{q}$ where $v$ is a fixed vertex.
I wrote $P(X_k(v)\neq Y_k(v))=P(X_k(v)\neq Y_k(v)), v\space not\space updated\space at\space all)+P(X_k(v)\neq Y_k(v), v\space updated\space at\space least\space once\space in\space k\space steps)\leq P(v\space not\space updated) +P(...)$
Note, $P(v\space not\space updated)=\dfrac{(k-1)^k}{k^k}=\left(1-\dfrac{1}{k}\right)^k\leq e^{-1}$ so I have bounded the first probability (which happens to also be the first part in the answer).
How do I bound the second probability i.e. $P(X_k(v)\neq Y_k(v), v\space updated\space at\space least\space once\space in\space k\space steps)$?