Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Can anyone help me with this question, maybe by giving a hint.

Consider a Markov chain with state space $\{0,1,2....\}$. A sequence of positive numbers $p_1,p_2,...$ is given with $\sum p_i=1$. Whenever the chain reaches 0 it chooses a new state according to the $p_i$. Whenever the chain is at a state other than $0$ it proceeds deterministically one step at a time towards $0$. Under what condition on $p_i$ is the chain positive recurrent?

Thanks for your help.

share|cite|improve this question
up vote 3 down vote accepted

Consider a state $k$. We are interested in the first return time to this state: $$ T_k = \inf\left\{ n \geqslant 1 \colon X_n = k \mid X_0 = k \right\} $$ The state $k$ is called recurrent if $\mathbb{P}\left(T_k < \infty\right) = 1$, and positive recurrent if $\mathbb{E}\left(T_k\right) < \infty$.

With $X_0=k$, the system transitions to the origin in $k$ steps with probability 1, and from there it either jumps to a state $0 \leqslant m < k$ in which case it returns to the origin and we start over again, or it jumps to a state $m \geqslant k$ in which case it returns to the state $k$.

The mean first passage time from the origin to the state $k$ is clearly $\mathbb{E}(T_k)-k$. Conditioning on whether the jump occurs to left of $k$ or not:

$$ \mathbb{E}\left(T_k\right) - k = \underbrace{\sum_{m=0}^{k-1} m p_m + \left(\mathbb{E}\left(T_k\right) -k\right) \sum_{m=0}^{k-1} p_m}_{ \text{transition to } m < k} + \underbrace{\sum_{m=k}^\infty (m-k) p_m}_{\text{transition to } m\geqslant k} $$ giving: $$ \mathbb{E}\left(T_k\right) \left(1-\sum_{m=0}^{k-1} p_m\right) = \sum_{m=0}^\infty m p_m \qquad \therefore \quad \mathbb{E}\left(T_k\right) = \frac{\sum_{m=0}^\infty m p_m}{\sum_{m=k}^\infty p_m} $$ Implying that any state $k$ is positive recurrent provided $$ \sum_{m=0}^\infty m p_m < \infty $$ Here we assume that for all $k \geqslant 0$, $\sum_{m=k}^\infty p_m > 0$.

share|cite|improve this answer
Don't you also need there to be infinitely many $m$ such that $p_m>0$? Otherwise, for sufficiently large $k$, $\sum_{m=k}^\infty p_m=0$. – Ilmari Karonen Mar 2 '13 at 18:27
@IlmariKaronen Actually, if there exist $k_0$ such that $p_m=0$ for all $m \geqslant k_0$, the system is finite state space, and being irreducible all states are recurrent, and therefore positive recurrent. – Sasha Mar 2 '13 at 18:44
Only if we restrict our attention only to the states reachable from 0, which I see no good reason to do. After all, nothing in the description says that we can't start at a state $k \ge k_0$. Indeed, it explicitly defines the state space as $\{0,1,2,\dots\}=\mathbb N$. – Ilmari Karonen Mar 2 '13 at 18:53
@IlmariKaronen Yes, I agree. – Sasha Mar 2 '13 at 18:59

Your Answer


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.