pr.probability - Is there a way to analytically compute the recurrence time of a finite Markov process?

Sunday, 9 July 2006

pr.probability - 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 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_{Ssubset V} -1^{|S|+1}Prob({X_i}_{ilt 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_{Ssubset V} -1^{|S|+1} A(S)$

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

The same holds for continuous time.

AnswerDesk

Sunday, 9 July 2006