= Solution
Let $R$ interchange the two <complete graphs>, sending $v_i$ to $v_i'$ and fixing $w$. This <involution> preserves the <transition matrix> of the <simple random walk>. A <mirror coupling under an involution> starts $X$ at $v_i$, keeps $Y_t=R(X_t)$ until the <hitting time> $\tau$ of $w$, and then makes the two walks move identically. Each coordinate has the correct <transition probabilities>, and they coalesce precisely at $\tau$. The <coupling inequality for total variation> gives
$$
\boxed{\|P^t(v_i,\cdot)-P^t(v_i',\cdot)\|_{\mathrm{TV}}\leq\mathbb P_{v_i}(\tau>t).}
$$
There is a genuine error in the printed <expected hitting time> bound, as well as an unspecified initial law. For $n\geq2$, write $a=\mathbb E_{v_1}\tau$ and $b=\mathbb E_{v_i}\tau$ for $i\ne1$. From every clique vertex there is a positive chance of reaching $w$ within two steps, uniformly over the finite state space for each fixed $n$, so $\tau$ has finite <expected value>. <First-step analysis>, using the <degree of a vertex> $n$ at $v_1$ and $n-1$ at the other clique vertices, gives
$$
a=1+\frac{n-1}{n}b,\qquad b=1+\frac{a+(n-2)b}{n-1}.
$$
Solving these <linear equations> yields
$$
\boxed{a=n^2-n+1,\qquad b=n^2,\qquad \mathbb E_w\tau=0.}
$$
In particular even the attachment vertex exceeds the printed bound by one. The valid uniform replacement is $\max_x\mathbb E_x\tau\leq n^2$, the <hitting time of the bridge vertex between two cliques> formula.
We must also handle arbitrary starting states, including $w$, before applying the mirror argument. Identify related vertices and consider the <lumped Markov chain> $Z$ on $\{1,\ldots,n,w\}$. Its <transition matrix> $Q$ has $Q(1,j)=1/n$ for $j\ne1$, $Q(1,w)=1/n$, $Q(i,j)=1/(n-1)$ for $i\ne1$ and $j\ne i$, and $Q(w,1)=1$, with all other entries zero. Here the row for $i\ne1$ only ranges over $j\in\{1,\ldots,n\}$.
For $n\geq3$ and $j\in\{2,\ldots,n\}$, direct two-step calculation gives
$$
\begin{aligned}
Q^2(w,j)&=1/n, &Q^2(1,j)&=(n-2)/(n(n-1)),\\
Q^2(i,i)&=(n-2)/(n-1)^2+1/(n(n-1)),\quad&i\geq2,\\
Q^2(i,j)&=(n-3)/(n-1)^2+1/(n(n-1)),\quad&i,j\geq2,\ i\ne j.
\end{aligned}
$$
All these entries are at least $1/(2n)$. Thus $Q^2(z,\cdot)\geq\alpha\nu(\cdot)$ for every $z$, where $\nu$ is the <uniform distribution on a finite set> $\{2,\ldots,n\}$ and $\alpha=(n-1)/(2n)\geq1/3$. This is a <Doeblin condition>. At each two-step block couple the two quotient endpoints to the same sample from $\nu$ with probability $\alpha$, using the residual <probability distributions> otherwise. The first successful block has <expected value> at most $1/\alpha$, so the alignment time $A$ has $\mathbb E A\leq6$. Lift each endpoint <coupling of probability distributions> to the original walks by their conditional two-step path laws; this preserves every marginal path law. The success test uses fresh block randomness and so permits restarting the walks with their original <transition matrix> at the aligned endpoints.
At alignment the original walks are equal or related. Use identical transitions in the first case and the <mirror coupling under an involution> in the second. The resulting <coalescing coupling> has coalescence time $T$ satisfying $\mathbb E T\leq6+n^2$ for every pair of initial states. Therefore <Markov inequality> and the <pairwise mixing diameter> imply
$$
d(t)\leq\bar d(t)\leq\sup_{x,y}\mathbb P_{x,y}(T>t)\leq\frac{n^2+6}{t},\qquad
\boxed{t_{\mathrm{mix}}(1/4)\leq\lceil4(n^2+6)\rceil=O(n^2).}
$$
For the hint's particular starting states, the quotient one-step laws from two different clique indices have a common component of mass at least $1-2/n$: for two ordinary indices it is $(n-2)/(n-1)$; for one attachment index it is $(n-2)/n$. A <maximal coupling> therefore aligns those indices with probability $1-O(1/n)$, as suggested. The two-step argument above additionally covers $w$.
The nonlazy walk is an <aperiodic Markov chain> for $n\geq3$, because the connected <graph> contains a <triangle>. For $n=1,2$ it is a <periodic Markov chain> on a <bipartite graph>; each bipartition class has stationary mass $1/2$, and the walk stays on a single class at each time. Hence $d(t)\geq1/2$ and the $1/4$ <mixing time> is infinite. The asymptotic conclusion is valid for $n\geq3$.
Back to article page
