Fundamental Matrix of a Reducible Recurrent Markov Chain

169 Views Asked by At

I have a Markov chain with states $\{A,B,C,D,E\}$ and the following transition matrix $P$:

$$ \begin{bmatrix} 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0.2404 & 0 & 0.7596 & 0 & 0 \end{bmatrix} $$

Which, as far as I can say, is aperiodic and reducible. Its communicating classes are $\{\{1,3,5\},2,4\}$, all of which are recurrent.

The following pseudo-code represents the approach I'm using in order to compute the fundamental matrix of a given chain:

function get_fundamental_matrix(chain)
{
    if (chain.is_irreducible)
    {
        // the transition matrix is converted into its canonical form
        // with all the transient states coming first
        p = chain.to_canonical_form().p

        // only one stationary distribution row vector should exist,
        // so it's converted into a squared matrix by tiling it
        // vertically for states_count times
        a = repeat(chain.stationary_distributions[0], chain.states_count)

        // the fundamental matrix is computed using the Kemeny and Snell
        // approach; sometimes Z contains negative values but as far as
        // I can say this is correct and rows always sum to 1
        i = eye(chain.size)
        result = inv(i - p + a) // Z
    }
    else
    {
        // the standard approach is used otherwise; q is a squared matrix
        // containing all the transient states probabilities
        q = chain.p[transient_indices,transient_indices]
        i = np.eye(len(transient_indices))
        result = npl.inv(i - q) // N
    }

    return result
}

I run this function with a lot of test cases and it always managed to produce a coherent result. But with this matrix it's failing because:

  • the matrix it's not irreducible, so the if statements goes into the else case;
  • the matrix contains no transient states, hence $Q$ is empty and $N$ is returned as an empty matrix.

Can someone explain me how I should proceed in order to obtain the fundamental matrix? Maybe it's simply not possible?