Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?
share|improve this question
    
The coupon-collecting approach is exponential. Does that count as analytic? –  Douglas Zare Feb 3 '10 at 16:04
    
Can you provide a reference? –  Steve Huntsman Feb 3 '10 at 17:04
    
arxiv.org/abs/1001.0609 –  Steve Huntsman Mar 2 '10 at 16:13
    
arxiv.org/abs/1004.4371 –  Steve Huntsman Jul 29 '10 at 21:26
add comment

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
Those sums should be over the nonempty subsets. –  Douglas Zare Feb 4 '10 at 8:07
    
Douglas, thanks. Do you know of a reference that deals with this approach for generic finite ergodic Markov processes? –  Steve Huntsman Feb 4 '10 at 14:49
    
Sorry, I don't. The method of estimating the time to visit the kth new vertex of a graph is present in "Short Random Walks On Graphs" by Greg Barnes and Uriel Feige. –  Douglas Zare Feb 4 '10 at 15:46
add comment

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.

share|improve this answer
    
Thanks; I caught this myself, see comments to my question. –  Steve Huntsman Sep 1 '10 at 9:22
    
Also I had in mind a cover time of the form used in this paper, otherwise you're quite correct. –  Steve Huntsman Sep 1 '10 at 9:23
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.