# How to calculate the long run proportion of time spent at a certain state, given that the Markov chain starts at a different state?

I have a Markov chain with an n * n matrix starting with all elements equal to 0. At each step, one of the elements is chosen uniformly at random and flipped, (that is, 0 is changed to 1, or 1 is changed to 0).

Now I am trying to find the long run proportion of times the matrix is the identity matrix. Here, we have a total number of 2^(n^2) states.

I tried the following:

The long run proportion of times the matrix is the identity matrix

= The stationary distribution value at the identity state

= no. of moves possible from the identity state / total number of moves possible from all states

= 1/ (2^(n^2)).

Is this argument reasonable ? But what makes me doubtful is that here, we are not starting from the identity matrix. Instead, the Markov chain starts at the matrix where all entries are 0. Does the starting state make a difference in finding the long run proportion of time spent at a given state?

I also think this chain is periodic. And I read that the chain converges to its stationary distribution only if the chain is aperiodic. Thanks a lot for any help.

I wonder if it relates to the concept of limiting probabilities... If so, how can I use limiting probability to find the long run proportion of time spent at a certain state, given that the chain starts from a different state?

You are right, there is a slight problem caused by periodicity. However, it turns out you still get the same answer in the end. Basically, periodicity is not a problem, because we are looking at the long-term average, so the effect of constantly bouncing between the two parts gets averaged out and does not matter.

If a Markov chain is ergodic (meaning every state can reach every other) and aperiodic, then every initial distribution will converge to the unique stationary distribution. This means that it does not matter what state you start at, or even what probability distribution you initially have for the first state; the distribution of the states at a given time will always converge. For a periodic chain, you do not quite get convergence. Instead, you will get a separate stationary distribution for each of the periodic parts of the chain, and the whole state will alternate between these distributions.

Instead of proving all that in general, I will just discuss how this applies to your case. Let $$G=(V,E)$$ be a simple connected bipartite graph. Let $$A$$ and $$B$$ be the parts of this graph, so $$V=A\sqcup B$$, and every edge in $$E$$ connects a vertex in $$A$$ to a vertex in $$B$$. We will have a random walk on this graph, where if you are currently at vertex $$v\in V$$, then the next vertex is uniformly chosen from the neighbors of $$v$$. Your problem is an example of this; $$V$$ is the set of all matrices, while $$A$$ is the set of matrices with an even number of ones, and $$B$$ is the set of matrices with an even number of ones.

Suppose that, initially, you start at a vertex in the $$A$$ part. This vertex is state number zero. This means that, certainly, state $$1$$ will be in the $$B$$ part, state $$2$$ in the $$A$$ part, and so on. In general, even numbered states are in $$A$$, and odd numbered states are in $$B$$. I claim that the following is true:

Whenever $$t$$ is even, the probability of being at a vertex $$v\in A$$ at time $$t$$ converges to $$(\deg v)/|E|$$ as $$t\to\infty$$.

Whenever $$t$$ is odd, the probability of being at a vertex $$v\in B$$ at time $$t$$ converges to $$(\deg v)/|E|$$ as $$t\to\infty$$.

So, for your matrix question, you start from the all-zeroes matrix. If $$n$$ is even, then the identity matrix is in the same part as the starting matrix. Therefore, at even numbered turns, the probability is $$1/2^{n^2-1}$$ of being in the identity matrix, and zero for odd turns. If $$n$$ is odd, then you switch those two answers.

Now, let us compute the long-run probability of being in the identity matrix state. In the general setting of random walks on a bipartite graph, let $$v\in V$$, and let $$X_0,X_1,X_2,\dots$$ be the random state at each time. I will first assume that $$v$$ is in the $$A$$ part, but the proof for the $$B$$ part is similar. Then \begin{align} \text{long run prob. of being at v} &=\lim_{n\to\infty} \frac1n \sum_{t=0}^n {P(X_t=v)} \\ &=\lim_{n\to\infty} \frac1n \left(\sum_{t=0}^{\lceil n/2\rceil} {P(X_{2t}=v)}+\sum_{t=0}^{\lfloor n/2\rfloor}P(X_{2t-1}=v)\right) \end{align} Since $$v$$ is in the $$A$$ part, we have $$P(X_{2t-1}=v)=0$$. On the other hand, $$P(X_{2t}=v)$$ converges to $$(\deg v)/|E|$$. Therefore, the above converges to $$\frac1n\cdot \left(\lceil n/2\rceil \frac{\deg v}{|E|}\right)\to \frac{\deg v}{2|E|}$$ This is exactly the same as the answer for the aperiodic case. Therefore, for your matrix problem, the answer is still $$1/2^{n^2}$$.

• This explanation is very helpful to understand the underlying concept. Thank you so much for your time and insights... Commented Oct 21, 2023 at 0:38