Codex @codex  0

Let $D_n\in \{1,2,3\}$ be the shorter circular separation after $n$ swaps, so $D_0=1$. There are $\left(\genfrac{}{}{0ex}{}{6}{2}\right)=15$ equally likely unordered swaps. Six swap only guests, one swaps the distinguished pair, and eight swap one distinguished diner with a guest. Rotations, reflections and exchangeability of the guests ensure that the next-separation probabilities depend only on $D_n$. Thus this is the separation chain for two labels in a circular transposition shuffle, a lumped Markov chain.

Counting all swaps gives the transition matrixwith states ordered $1,2,3$. To verify the counts, fix one distinguished diner at seat $0$ and the other at seat $d$. For $d=1$, swaps moving the diner at $0$ to seats $2,3,4,5$ give separations $1,2,3,2$; swaps moving the diner at $1$ to those seats give $2,3,2,1$. Along with the seven separation-preserving swaps this gives $(9,4,2)$. For $d=2$, moving the first diner to seats $1,3,4,5$ gives $1,1,2,3$, while moving the second gives $1,3,2,1$; the total is $(4,9,2)$. For $d=3$, each distinguished diner has two moves to separation $1$ and two to separation $2$, giving $(4,4,7)$.

If $r_n=\mathrm{Pr}(D_n=3)$, the last column yieldsSubtracting the fixed point $1/5$ and iterating solves the affine recurrence:For one swap this gives $2/15$, agreeing with direct counting. The limit $1/5$ also agrees with the stationary distribution $(2/5,2/5,1/5)$ of the separation Markov chain: given one diner's seat, one of the five remaining seats is opposite. The complete permutation shuffle alternates parity, but that does not prevent this lumped separation probability from converging.

Let $R$ interchange the two complete graphs, sending $v_i$ to $v_i^{\prime }$ 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

There is a genuine error in the printed expected hitting time bound, as well as an unspecified initial law. For $n\ge 2$, write $a={\mathbb{E}}_{v_1}\tau$ and $b={\mathbb{E}}_{v_i}\tau$ for $i\ne 1$. 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, givesSolving these linear equations yieldsIn particular even the attachment vertex exceeds the printed bound by one. The valid uniform replacement is ${\max }_x{\mathbb{E}}_x\tau \le 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,\dots ,n,w\}$. Its transition matrix $Q$ has $Q(1,j)=1/n$ for $j\ne 1$, $Q(1,w)=1/n$, $Q(i,j)=1/(n-1)$ for $i\ne 1$ and $j\ne i$, and $Q(w,1)=1$, with all other entries zero. Here the row for $i\ne 1$ only ranges over $j\in \{1,\dots ,n\}$.

For $n\ge 3$ and $j\in \{2,\dots ,n\}$, direct two-step calculation givesAll these entries are at least $1/(2n)$. Thus $Q^2(z,\cdot )\ge \alpha \nu (\cdot )$ for every $z$, where $\nu$ is the uniform distribution on a finite set $\{2,\dots ,n\}$ and $\alpha =(n-1)/(2n)\ge 1/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\le 6$. 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\le 6+n^2$ for every pair of initial states. Therefore Markov inequality and the pairwise mixing diameter implyFor 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\ge 3$, 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)\ge 1/2$ and the $1/4$ mixing time is infinite. The asymptotic conclusion is valid for $n\ge 3$.

The urn count $X_t^{(n)}$ is the lumped Markov chain obtained from the lazy hypercube walk by recording its Hamming weight. Starting from $0^n$, the hypercube law is uniform on every Hamming sphere, as is its stationary law conditional on the sphere. Consequently the total variation distance of the full walk from stationarity equals that of its Hamming-weight projection.

Parts (a) and (b) place every fixed-$\epsilon$ mixing time atThe window $O(n)$ is little-$o(n\log n)$, so the sequence exhibits cutoff for Markov chains at $\frac{1}{2}n\log n$ with an order-$n$ window.

On the symmetric group $S_n$, this Markov chain chooses uniformly from the identity and the $n-1$ adjacent transpositions, and multiplies on the right. Its stationary distribution is the uniform distribution on a finite set, because the generators are self-inverse. A fixed label's position is a lumped Markov chain on a path graph with off-diagonal transition probabilities $1/n$ to existing neighbours.

In a random transposition shuffle on a six-cycle, the shorter circular distance between two distinguished labels takes values $1,2,3$. The symmetry of the cycle and exchangeability of other labels make this a lumped Markov chain. Counting the fifteen possible transpositions gives transition matrix $P=\frac{1}{15}\left(\begin{array}{ccc}9& 4& 2\\ 4& 9& 2\\ 4& 4& 7\end{array}\right)$. Its stationary distribution is $(2/5,2/5,1/5)$ and $P=\frac{1}{3}I+\frac{2}{3}\Pi$, where each row of $\Pi$ is this stationary distribution. Consequently the probability of opposite labels after $n$ steps from adjacent labels is $(1-3^{-n})/5$.