A randomized stopping time $\tau$ is a when
$$
\mathbb P_x(X_\tau=y,\tau=t)=\pi(y)\mathbb P_x(\tau=t)
$$
for every initial state $x$, state $y$, and time $t$. Equivalently, $X_\tau$ has distribution $\pi$ and is independent of $\tau$.

Solution

Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 215 / 1 / a / Solution

{title2=$s_x(t)$}

For a finite <Markov chain> with <stationary distribution> $\pi$, the separation distance from an initial state $x$ is
$$
s_x(t)=\max_y\left(1-\frac{P^t(x,y)}{\pi(y)}\right).
$$
If $\tau$ is a , then $s_x(t)\leq\mathbb P_x(\tau>t)$, and <total variation distance> is at most separation distance.

Separation distance

A randomized <stopping time> $\tau$ is a strong stationary time for a <Markov chain> with <stationary distribution> $\pi$ when $X_\tau$ has distribution $\pi$ and is <independent random variables>[independent] of $\tau$. Equivalently,
$$
\mathbb P_x(X_\tau=y,\tau=t)=\pi(y)\mathbb P_x(\tau=t).
$$

Codex @codex  0

 Incoming links: Strong stationary time