4

We know that,

If $p_{jj}$ is the transition probability of staying in state j at n-th step and j at (n-1)-th step then the state j is said to be recurrent if,

$\sum_{n=0}^\infty p_{jj}^n = \infty$

and transient if,

$\sum_{n=0}^\infty p_{jj}^n \lt \infty$.

My problem of understanding is that if j is a recurrent state then the probability of returning to state j from state j in one step is $p_{jj}^1$ ,in two step is $p_{jj}^2$ and .......so on. So the probability of ever returning to the state j is the sum of the transition probabilities of returning to state j from j where n=1,2,......$\infty$.These probabilities are the probabilities of mutually events. So ,here how the probability of occurring an event is infinity?

I know the proof of the theorem but i don't understand the intuition behind the theorem and why the sum of probability is equal to infinity,if the state is recurrent?.

Can someone explain the theorem intuitively?

Rhafi Sheikh
  • 95
  • 6
  • 1
    Recurrence (as you probably know) means you return to the state infinitely often while transient means that at some point you will never return to that particular state. The summation result must have something to do with these definitions. Does the notation for p_jj mean the probability of return to j within n steps? If so p_jj will be 1 infinitely often for recurrent chains and only eventually 0 beyond some fixed n in thr transient case, maybe?. – Michael R. Chernick Jan 05 '17 at 19:02
  • $p_jj$ means the probability of returning to state j from state j in one step. – Rhafi Sheikh Jan 05 '17 at 19:06
  • That kills my theory. Is the n then there to mean that p_jj is raised to the nth power? With the definition you give p_jj would always be less than 1 in all both cases unless the chain can be caught in a single state (only possible for transient chains). – Michael R. Chernick Jan 05 '17 at 19:15
  • 3
    @Michael The definitions differ from the characterizations given here, which is why there's a valid question. A *transient* state is one to which there is a non-zero chance of never returning once it has been visited. A *recurrent* state is anything else. See https://en.wikipedia.org/wiki/Markov_chain#Transience_and_recurrence. The theorem states that the expected number of visits to a recurrent state (once it is reached the first time) is infinite. The theorem's converse is more revealing: if there's any chance of not returning, then there's no chance of returning infinitely often. – whuber Jan 05 '17 at 19:17
  • @whuber Where does ergodicity come in? Also as I recall recurrent is divided into two categories. One is positive recurrent and the other is null recurrent. – Michael R. Chernick Jan 05 '17 at 19:21
  • @Michael The distinction you are making concerns the *expectation* of the recurrence time. It's not needed here. To that, [ergodicity](https://en.wikipedia.org/wiki/Markov_chain#Ergodicity) adds the assumption of aperiodicity, which again is not needed. – whuber Jan 05 '17 at 19:25
  • @Michael Chernick ergodicity comes from the limiting behavior of a markov chain ,if the states of a markov chain are aperiodic and non-null,then there will be a limiting probability for each state and it will not depend on initial condition and the number of step. – Rhafi Sheikh Jan 05 '17 at 19:32
  • There is a lot I learned about Markov chains in graduate school and a lot that I have forgotten in the intervening 40 years! I went to the following URL just now and found a lot of information on there. I don't know if it will help @RhafiSheikh intuition but it has convinced me to stop asking questions, Thank you both for the answers you gave me. It is called Transience and Recurrence for Discrete Time Chains www.math.uah,edu/stat/markov/Recurrence.html . – Michael R. Chernick Jan 05 '17 at 19:43
  • @josliber Each state has probability 1 ,so these states are aperiodic, So these states has no long term/limiting probability because if we are in state j at n step then we are sure to be in state k at n+1 step because these state has no self transition probability. – Rhafi Sheikh Jan 05 '17 at 19:46
  • A point that can be confusing with these terms is that individual states can be called transient or recurrent and that is different from the chain being transient or recurrent. Another key term that I forgot about is irreducibility. – Michael R. Chernick Jan 05 '17 at 19:50
  • Ditto for aperiodic. I also am remembering the connection between recurrent chains and arrival times of renewal processes from the URL I referennced. – Michael R. Chernick Jan 05 '17 at 19:55
  • If the all states of a markov chain is recurrent then the chain is called recurrent . There will be always at least one recurrent state in a mrkov chain. – Rhafi Sheikh Jan 05 '17 at 19:56
  • @josliber i used the notation & p_{jj} & to indicate the probability of returning to state j from j in one step and & p_{jj}^n & for the probability of returning to state j from j in n-step.The above theorem is true for all recurrent state. – Rhafi Sheikh Jan 05 '17 at 20:33
  • If the markov chain has three state j,k,l then each have .5 probability to go to the other two state,now let we start from state j then we will be in state k and state l in next two state but we will back in state j at 3-th step and at 6th step,9-th,12-th step we will be in state j.so the state j has periodicity 3. Hence the chain has periodicity 3 because the three states are communicative.So the the chain is periodic. – Rhafi Sheikh Jan 05 '17 at 20:33

1 Answers1

3

If the state $j$ is recurrent for the Markov chain $(X_t)$, $$\sum_{n=0}^\infty p_{jj}^n = \infty$$is equivalent to [in the sense that the lhs is the same] $$\sum_{n=0}^\infty \mathbb{P} (X_n=j|X_0=j) = \infty$$and to$$\sum_{n=0}^\infty \mathbb{E} [\mathbb{I}(X_n=j)|X_0=j]= \mathbb{E} \left[ \sum_{n=0}^\infty \mathbb{I}(X_n=j)\Big|X_0=j\right]=\infty$$which means the number of visits of state $j$ when starting from $j$ is on average infinite. (The state is Harris recurrent if the number of visits of state $j$ when starting from $j$ is almost surely infinite. The Markov chain is recurrent if there exists one recurrent state and if the chain is irreducible.)

The statement in the OP question

the probability of ever returning to the state j is the sum of the transition probabilities of returning to state j from j where n=1,2,......∞.These probabilities are the probabilities of mutually [exclusive] events.

is thus incorrect. Returns at times $n$ and $m$ are not exclusive events.

Xi'an
  • 90,397
  • 9
  • 157
  • 575
  • 1
    In questioning the OP about p_jj the answer given was that p_jj was the probability of going from state j to state j in one step. That confused me I didn't think it was right. As you corrected that your answer is very clear . Well done! – Michael R. Chernick Jan 06 '17 at 06:15
  • @MichaelChernick: well $p_{jj}$ is the probability to go from $j$ to $j$ in one step, while $p^n_{jj}$ is the probability to go from $j$ to $j$ in $n$ steps, with no constraint on earlier visits, $p^n_{jj}=\mathbb{P} (X_n=j|X_0=j)$. – Xi'an Jan 06 '17 at 06:18
  • Okay so my confusion was thinking that n meant raising p_jj to the nth power. Nobody clarified that for me until now. Most of this stuff was familiar to me at one time including this notation. – Michael R. Chernick Jan 06 '17 at 06:45
  • 1
    why the expected number of visiting j from j is equivalent to $\sum_{n=o}^\infty p_{jj}^n = \infty$ ? – Rhafi Sheikh Jan 06 '17 at 06:49
  • 1
    As expressed in my answer,$$\sum_{n=0}^\infty p_{jj}^n = \sum_{n=0}^\infty \mathbb{P} (X_n=j|X_0=j) = \sum_{n=0}^\infty \mathbb{E} [\mathbb{I}(X_n=j)|X_0=j] = \mathbb{E} \left[ \sum_{n=0}^\infty \mathbb{I}(X_n=j)\Big|X_0=j\right]$$is the expected number of visits to $j$ when starting from $X_0=j$. – Xi'an Jan 06 '17 at 07:34
  • @Xi'an ,$\sum_{n=o}^\infty p_{jj}^n = \infty$ doesn't indicate probability of an event rather is just a condition for a state being recurrent.The condition is that ,a state will be recurrent if there is always a probability of returning to the state j starting from j no matter how much time step we spent so if we spent infinite time step than on average we return to the state infinitely(if the state is recurrent).So is my interpretation correct?(SORRY FOR MY BAD ENGLISH) – Rhafi Sheikh Jan 06 '17 at 15:08
  • 1
    @Xi'an At first i interpret $\sum_{n=o}^\infty p_{jj}^n = \infty$ as the probability of occurring the event returning to the state j from j in n time step so there is no way it will be greater than 1 but you pointed out that returns at times n and m are not exclusive events. So $\sum_{n=o}^\infty p_{jj}^n$ ,is not a probability rather it just a condition for recurrent state. – Rhafi Sheikh Jan 06 '17 at 15:18
  • Yes, the probability$$\mathbb{P}(X_n=j\text{ for some }n>0|X_0=j)$$is not equal to $$\sum_{n=1}^\infty p_{jj}^n$$ – Xi'an Jan 06 '17 at 15:20