= Shift-refresh chain on a hypercube
A homogeneous shift-refresh chain on a dimension-$m$ <hypercube graph>[hypercube] has state $x=(x_1,\ldots,x_m)\in\{0,1\}^m$ and transition
$$
(x_1,\ldots,x_m)\longmapsto(x_2,\ldots,x_m,U),
$$
where each fresh $U$ is an <independent> fair <Bernoulli random variable>. It rotates the old coordinates and refreshes the final one. The <uniform distribution> on <bit vector>[bit vectors] is stationary, because shifting <independent and identically distributed>[iid] fair bits and appending another fair bit preserves their joint law.
After exactly $m$ steps, every coordinate consists of a distinct fresh fair bit, independently of the starting state. Thus the deterministic <Stopping time> $\tau=m$ is a <strong stationary time>. Starting at a fixed <vector>, at time $t<m$ there are $m-t$ deterministic retained coordinates and $t$ <independent> fair coordinates. The law is uniform on a subset of $2^t$ states, giving the exact <total variation distance>
$$
d_m(t)=1-2^{t-m}\quad(0\leq t<m),\qquad d_m(t)=0\quad(t\geq m).
$$
Consequently the family has <cutoff for Markov chains>[cutoff] at $m$ with a bounded window: at $(1-\varepsilon)m$ the distance tends to one for every fixed $\varepsilon>0$, whereas at $m$ it is zero.
A pointer description must specify which variables belong to the state. If a pointer itself is included in an augmented chain, refreshing all bits makes the bits uniform conditional on the pointer history, but does not by itself make the pointer stationary or <independent> of the <Stopping time>. Coverage alone is therefore insufficient to establish a <strong stationary time> for that augmented chain.
Back to article page
