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 be a countable state space, be a Markov chain with stationary distribution , a stationary time is a random time such that . In general, and are not independent. A more stronger concept is strong stationary time, in which and are independent. Explicitly, this means that . Using the definition of stationarity, one can actually shows that .

One example of stationary time but not strong stationary time is the following: Consider -cycle random walk starting at , let with probability , and with probability , 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 is a stationary time. However, it is not strong since when , .

I want to apply a basic martingale argument to prove this result. Recall that for a simple random walk on starting from 0, with absorbing state and , , where is the first time the walk hits .

Going back to the -cycle random walk, let us calculate the probability that is the last hit new vertex. We can transform -cycle random walk to a random walk on , where each integer corresponds to mod . Then the absorbing states are and . Since is the last new hit vertex on -cycle, the random walk on must hit and before hitting or . Hence, the probability is

Since the walk starts from , and . So the probability we are calculating is . For the first summand, we observe that conditional on , the events and are independent. Hence, it is . Using the martingale result, we have that it is .

Similarly, for the second summand, we see that conditional on , the events and are independent, it is . Using the martingale result, we get . Summing up two probabilities, we have that . This implies that the last hit new vertex is uniformly distributed among non-zero vertexes.

### Like this:

Like Loading...