# An example of stationary time

Today, I want to talk a little about strong stationary time, which is another useful technique to bound the mixing time of Markov chain. Let ${S}$ be a countable state space, ${\left\{X_n\right\}}$ be a Markov chain with stationary distribution ${\pi}$, a stationary time ${\tau}$ is a random time such that ${P(X_\tau=s)=\pi(s)}$. In general, ${\tau}$ and ${X_\tau}$ are not independent. A more stronger concept is strong stationary time, in which ${\tau}$ and ${X_\tau}$ are independent. Explicitly, this means that ${P(\tau=t,X_t=s)=P(\tau=t)\pi(s)}$. Using the definition of stationarity, one can actually shows that ${P(\tau \leq t, X_t=s)=P(\tau\leq t)\pi(s)}$.

One example of stationary time but not strong stationary time is the following: Consider ${n}$-cycle random walk starting at ${0}$, let ${\tau=0}$ with probability ${\frac{1}{n}}$, and with probability ${\frac{n-1}{n}}$, ${\tau}$ be the time that the random walk hit the last new vertex. One interesting result is that the distribution of last new vertex is uniform on the non-zero vertexes. This verifies that ${\tau}$ is a stationary time. However, it is not strong since when ${\tau=0}$, ${X_\tau=0}$.

I want to apply a basic martingale argument to prove this result. Recall that for a simple random walk on ${\mathbb{Z}}$ starting from 0, with absorbing state ${-a}$ and ${b}$, ${P(\tau_{-a}<\tau_{b})=\frac{b}{a+b}}$, where ${\tau_x}$ is the first time the walk hits ${x}$.

Going back to the ${n}$-cycle random walk, let us calculate the probability that ${k}$ is the last hit new vertex. We can transform ${n}$-cycle random walk to a random walk on ${\mathbb{Z}}$, where each integer ${x}$ corresponds to ${x}$ mod ${n}$. Then the absorbing states are ${k-n}$ and ${k}$. Since ${k}$ is the last new hit vertex on ${n}$-cycle, the random walk on ${\mathbb{Z}}$ must hit ${k+1-n}$ and ${k-1}$ before hitting ${k}$ or ${k-n}$. Hence, the probability is

$\displaystyle P_{0}(\tau_{k+1-n}<\tau_{k-1},\tau_{k-1}<\tau_{k},\tau_{k-1}<\tau_{k-n})+\\ P_{0}(\tau_{k+1-n}>\tau_{k-1},\tau_{k+1-n}<\tau_{k},\tau_{k+1-n}<\tau_{k-n})$

Since the walk starts from ${0}$, ${\tau_{k-1}<\tau_{k}}$ and ${\tau_{k+1-n}<\tau_{k-n}}$. So the probability we are calculating is ${P_{0}(\tau_{k+1-n}<\tau_{k-1},\tau_{k-1}<\tau_{k-n})+P_{0}(\tau_{k+1-n}>\tau_{k-1},\tau_{k+1-n}<\tau_{k})}$. For the first summand, we observe that conditional on ${\tau_{k+1-n}}$, the events ${\tau_{k+1-n}<\tau_{k-1}}$ and ${\tau_{k-1}<\tau_{k-n}}$ are independent. Hence, it is ${P_{0}(\tau_{k+1-n}<\tau_{k-1})P_{k+1-n}(\tau_{k-1}<\tau_{k-n})}$. Using the martingale result, we have that it is ${\frac{k-1}{n-2}\frac{1}{n-1}}$.

Similarly, for the second summand, we see that conditional on ${\tau_{k-1}}$, the events ${\tau_{k+1-n}>\tau_{k-1}}$ and ${\tau_{k+1-n}<\tau_{k}}$ are independent, it is ${P_{0}(\tau_{k+1-n}>\tau_{k-1})P_{k-1}(\tau_{k+1-n}<\tau_{k})}$. Using the martingale result, we get ${\frac{-(k+1-n)}{n-2}\frac{1}{n-1}}$. Summing up two probabilities, we have that ${P(k\; \text{is last new hit vertex})=\frac{k-1}{n-2}\frac{1}{n-1}+\frac{-(k+1-n)}{n-2}\frac{1}{n-1}=\frac{1}{n-1}}$. This implies that the last hit new vertex is uniformly distributed among non-zero vertexes.