Question

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:

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?

Answer 1

This is a response to a comment.

The coupon collector's 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, 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.

Answer 2

http://arxiv.org/abs/1004.4371 might be useful.

A note regarding your remark: "Clearly T(X0) 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 X0 starting from a state chosen w/r/t the invariant distribution p."

This is false (unless I'm misreading it). If you start from 0 on the discrete interval {0,1,..,n}, then after covering you have to return to 0 from n, which takes longer than returning to 0 from a uniformly random point.