# How to solve the large state Markov Chain

I am solving a paper, in which there is a very large Markov chain. How can I find the steady state probability of a very large Markov chain since solving it through eigenvector process is proving to very difficult. I have attached the Markov chain in the link below

The authors claim that the steady state is following:

The Steady-State Probabilities as stated by authors

$$\pi_{i,j}= \begin{cases} \pi_{-1,-1} \cdot q, & \text{for }i=0 \text{ and } j=0 \\ \pi_{-1,-1} \cdot q \cdot p^i, & \text{for }i \in [1,M] \text{ and } j=0 \\ \pi_{-1,-1} \cdot q \cdot \frac{W-j}{W}, & \text{for }i \in [1,M] \text{ and } j \in [0, W-1] \\ \end{cases}$$

• It isn't clear from your image/diagram how "large" the Markov state transition matrix is. The diagram suggests there is considerable "substructure" in the transition states, and that may well play a role in computing eigenvalue/eigenvector pairs. Feb 19, 2017 at 20:56
• I would expect to see $p$ and $i$ in the third part of the expression Feb 19, 2017 at 21:15
• @hardmath I also had this feeling... The authors have taken another approach... They have considered $\Sigma_{i=-1}^M\Sigma_{j=-1}^{W-1} \pi_{i,j} = 1 = \pi_{-1,-1} + \pi_{0,0} + \Sigma_{i=1}^M\Sigma_{j=0}^{W-1} \pi_{i,j}$ Then the authors have given the simplified form of the third term in the above expression. I cannot understand how they went in there. I am trying to come to solution, but haven't succeeded as yet
– SJa
Feb 19, 2017 at 23:00
• @Henry Yes I also expect the same
– SJa
Feb 19, 2017 at 23:02
• The paper title is 'Enhancement of LTE RACH through extended random access process'. Published in IEEE ELectronics letters, Authors : JS Km, D Munir, SF Hasan, and MY Chung
– SJa
Feb 20, 2017 at 3:45

Let $s$ be a state in the Markov chain. An excursion from $s$ is a sample from the Markov chain that starts in $s$ and then follows the transition probabilities as usual until it returns to $s$. Let's denote by $\tau_s$ the expected number of steps in an excursion from $s$.
Then in general it's true that for any state $x$, $\pi_x \cdot \tau_s$ is the expected number of visits to state $x$ in an excursion from $s$. We say that the number of visits to state $s$ itself is always $1$ in an excursion, so $\pi_s \cdot \tau_s = 1$.
In this problem, if we let $s = (-1,-1)$, then excursions from $s$ are easy to understand. The expected number of visits to state $(0,0)$ in an excursion is $q$, because we visit state $(0,0)$ only once (if at all) and we do so with probability $q$: the probability that we don't return to $(-1,-1)$ immediately. The expected number of visits to state $(i,j)$ is, similarly, the probability that we ever see the state $(i,j)$, since we can never loop around without returning to $(-1,-1)$. That probability is $$q \cdot p^i \cdot \frac{W-j}{W}$$ because:
• The probability is $q \cdot p^i$ that we reach the $i^{\text{th}}$ "column" of the Markov chain before looping around;
• The probability is $\frac{W-j}{W}$ that when we enter the $i^{\text{th}}$ column, we do it in one of the states $(i,j), (i,j+1), \dots, (i,W-1)$ from which state $(i,j)$ will eventually be reached.
As a result, $$\pi_{i,j} \cdot \tau_{-1,-1} = q \cdot p^i \cdot \frac{W-j}{W} \implies p_{i,j} = \frac{1}{\tau_{-1,-1}} \cdot q \cdot p^i \cdot \frac{W-j}{W}.$$ Since $\frac1{\tau_{-1,-1}}$ is just $\pi_{-1,-1}$, this gives the formula we wanted.
Note that there is a typo (both in the question, and in the original paper): for state $(i,j)$ with $j \ne 0$, the limiting probability should still have a factor of $p^i$.