= Stationary-reset perturbation of a Markov chain
Let $P$ be a <transition matrix> with <Stationary distribution> $\pi$, and let $\Pi$ have every row equal to $\pi$. For $0\leq a\leq1$, the stationary-reset perturbation
$$
\widetilde P=(1-a)P+a\Pi
$$
follows the original transition with <Probability> $1-a$ and independently resamples from <stationary distribution>[stationarity] with <Probability> $a$. Since $P\Pi=\Pi P=\Pi$ and $\Pi^2=\Pi$,
$$
\widetilde P^t=\Pi+(1-a)^t(P^t-\Pi),\qquad
\widetilde d(t)=(1-a)^t d(t).
$$
The <total variation distance>[total variation] identity is exact: subtracting <stationary distribution>[stationarity] multiplies every signed row difference by the same nonnegative factor. Once the first reset occurs the distribution remains stationary, so the factor also has a direct no-reset <Probability> interpretation.
This can destroy <pre-cutoff for Markov chains>[pre-cutoff]. Take the dimension-$m$ <Shift-refresh chain on a hypercube>, whose distance is $d_m(t)=1-2^{t-m}$ for $t<m$ and zero for $t\geq m$. Use reset <Probability> $a_m=c/m$ for fixed $c>0$ and $m>c$. For $0<s<1$, $\widetilde d_m(\lfloor sm\rfloor)\to e^{-cs}$, while at $s\geq1$ the distance is zero. A positive fraction of the mixing scale therefore already causes a nonvanishing decrease from one. Any scale capable of making the later distance tend to zero must be at least order $m$, and its earlier fixed positive multiple cannot have distance tending to one. Thus this perturbed family lacks <pre-cutoff for Markov chains>[pre-cutoff] even though the original has a sharp <cutoff for Markov chains>[cutoff].
Back to article page
