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](http://en.wikipedia.org/wiki/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](http://books.google.com/books?id=KF0LgxRCgQsC&pg=PA226) (in discrete time) or the ["deviation matrix"](http://doc.utwente.nl/62339/) (in continuous time) give lots of information about hitting times, computing the cover time is hard. I am aware of the [Matthews bound](http://arxiv.org/abs/math.PR/0005121), 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: 



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



Is there a way to analytically compute the recurrence time of a finite Markov process?
This is a response to a comment.


The [coupon collector's problem](http://en.wikipedia.org/wiki/Coupon_collector%27s_problem) is elementary. I don't have a particular scholarly reference in mind, but rather the technique of the proofs. There are a few proofs of the $n H\_n$ expected time to collect all coupons. One possibility is that you can compute the expected time to collect the $k$th new coupon, 
$n/(n-k+1)$. That uses a lot of symmetry you don't have for a general Markov process. Here, you have transition probabilities and times on (current location, subset visited so far). 


Analogous to what I did [here](https://mathoverflow.net/questions/13171/how-many-trial-picks-expectedly-sufficient-to-cover-a-sample-space/13217#13217), you can use inclusion-exclusion. The expected time to cover everything (with discrete time) is the sum of the probability that you haven't covered everything by time $t-1$, which you can express as 


$$\sum\_t \sum\_{S\subset V} -1^{|S|+1}Prob(\{X\_i\}\_{i\lt t}\cap S = \emptyset) $$


where $V$ = $\{1,...,n\}$. You can switch the order of summation to get about $2^n$ analytically solvable problems about avoiding particular subsets.


$$\sum\_{S\subset V} -1^{|S|+1} A(S)$$


where $A(S)$ = expected time before you first enter $S$.


The same holds for continuous time. 


