Cover time in Markov Chain from transition matrix

75 Views Asked by At

Given a process on a graph $X_{n} = \{x_{1}, ..., x_{n}\}$, is there a way to obtain the cover time, starting at any state $x_{i}$, from the transition matrix $\mathbf{P}$?

I've obtained the expected number of steps to reach any state $x_{j}$ by solving the following linear system:

$$ \mathbf{E}_{x} = (\mathbf{I}_{n} - \mathbf{P})^{-1} \mathbf{1}_{n} $$

But now I'm not sure how I could obtain the cover time directly from either $\mathbf{E}_{x}$ (which is a column vector with all expected numbers of steps) or $\mathbf{P}$.

Thank you very much.