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

hi, I'm sorry if the question is silly, but I couldn't get my head around it for a while now.

In Markov Chains (MC) proving that a state is either recurrent or transient is through Borel-Cantelli lemma (BCL): the event (state) happens infinitely often (i.o.) if the series diverges and vice versa.

The question is, how to apply BCL to prove that the state is absorbing.

The problem is that if the state is absorbing (i.e. once we got there we're stuck in it) then, at least intuitively, it is an event that happens almost always (a.a.) rather than i.o., which means that BCL isn't applicable here, at least not directly (since BCL applies only to events that happen i.o.).

1ce again, sorry if the question is too silly.

share|improve this question

2 Answers 2

up vote 3 down vote accepted

Short answer:

Don't.

In fact, one never shows that a state is absorbing through Borel-Cantelli lemma. Or that a state is recurrent, since this would mean using the part of Borel-Cantelli lemma where a series diverges, which needs independence, and the successive times of visits of a given state by a Markov chain are hardly independent.

share|improve this answer
    
Correct me if I'm wrong, but the issue with independence is solved using BCL+Kolmogorov 0-1 Law. Therefore, 'visit state A i.o.' is an intersect of events 'visit state A k or more times', and the sum of probailities of these events A_{k} must diverge for recurrence. At least this is how Iosifescu and Shiryaev treat the matter. Nevertheless the problem with absorbing states remains. –  sigma_z_1980 Feb 7 '11 at 9:18
2  
@sigma: Indeed, the sum of probabilities must diverge for recurrence. That is, recurrence implies divergence of the series, that is, convergence of the series implies transience. This part is correct / does not require independence / uses the (so-called) easy part of Borel-Cantelli lemma. But to show recurrence would require the (so-called) difficult part. –  Did Feb 7 '11 at 9:32
    
@Didier: so, if I got you right, it is not enough to show divergence of seies to prove recurrence, not to mention absorbing property? –  sigma_z_1980 Feb 7 '11 at 10:38
3  
@sigma: 1. The recurrence of a state of a Markov chain is equivalent to the divergence of a series but the proof of this result does not rely on a naive application of B-C lemma because the successive times of visits of a given state are not independent (to recover an independent structure one usually considers successive cycles of the path). 2. The absorbing property has nothing to do with B-C lemma nor with the convergence of a series: the fact that $x$ is absorbing simply means that the transition from $x$ to $x$ has probability one. –  Did Feb 7 '11 at 11:27
1  
@sigma: Like Ori said. The essentials are in chapter 1 of Markov chains by James Norris statslab.cam.ac.uk/~james/Markov. More detailed is Markov chains: Gibbs fields, Monte Carlo simulation, and queues by Pierre Brémaud books.google.com/books?id=KF0LgxRCgQsC. –  Did Feb 7 '11 at 22:47

I don't think you can. BCL is a test for recurrence. Absorbing states tend to be recurrent but recurrent states need not be absorbing. Take the 1 dimensional random walk for example. Any state is recurrent but none are absorbing.

share|improve this answer
    
Absorbing states are a subset of recurrent, not 'tend to'. They are an extreme form of them, if you want. But since the MC (e.g. discrete) is run for infinity, an absorbing state becomes visited a.a., which is a problem - BCL doesn't apply. –  sigma_z_1980 Feb 7 '11 at 9:20
    
@Daniel: You write that BCL is a test for recurrence. Any example? –  Did Feb 7 '11 at 9:20
    
@sigma: Absorbing states can be visited with probability less than one. –  Did Feb 7 '11 at 9:23
    
I recon what he means is that the state is recurrent if the sum of probabilites of visiting it diverges (BCL). Essentially this is a definition of recurrence vs transience (converges) –  sigma_z_1980 Feb 7 '11 at 9:23

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.