Let $X_t$ be an ergodic (time-homogeneous) Markov process (in discrete or continuous time) on a finite state space $\{1,\dots,n\}$. Let $T(X_0)$ be the stopping time given by the infimum of times such that $X$ has covered the space (i.e., for all $j$ with $1 \le j \le n$ there exists some $t_j \le T(X_0)$ s.t. $X_{t_j} = j$) and $X_{T(X_0)} = X_0$. Clearly $T(X_0)$ dominates the cover time of $X$. I would expect it to be dominated in turn by the sum of the cover time and the expected hitting time of $X_0$ starting from a state chosen w/r/t the invariant distribution $p$.

Define the *recurrence time* as $\sum_{X_0} p(X_0) \cdot \mathbb{E}_{X_0} T(X_0)$, where again the first term is the invariant distribution of $X$.

Now it has been quite a while (early 2000s) since I looked at cover and hitting times, but I recall that while the fundamental matrix (in discrete time) or the "deviation matrix" (in continuous time) give lots of information about hitting times, computing the cover time is hard. I am aware of the Matthews bound, but I do not know of a simpler way to compute the cover time than by simulating the chain. In particular, I don't know of an analytical approach to this quantity.

I am in the same situation w/r/t the recurrence time, and it is this quantity that interests me much more than the cover time *per se*. But both are of some interest/utility to me.

So my questions are:

- Has the recurrence time (or a similar quantity besides the cover time or first return time) been treated anywhere?
- Are there known analytical results on computing or at least (besides the Matthews bound) bounding cover times or recurrence times?