# Random Walk with state-dependent probability

Let $\{X_n\}_{n=0,1,\ldots}$ be a DTMC with states space $S = \mathbb{Z}$ and one-step transition matrix given by:

$P_{i,i-1} = \frac{1}{2i}, P_{i,i+1} = \frac{1}{2(i + 2)}, P_{i,i} = 1- P_{i,i-1} - P_{i,i+1}$ for all $i \ge 1$

and

$P_{i,i+1} = \frac{1}{2|i|}, P_{i,i-1} = \frac{1}{2(|i| + 2)}, P_{i,i} = 1- P_{i,i-1} - P_{i,i+1}$ for all $i \le -1$

and

$P_{0,1} = P_{0,-1} = \frac{1}{4}, P_{0,0} = \frac{1}{2}$

Is this chain positive recurrent, null recurrent or transient?

My trial: It is easy to obverse that this chain is irreducible, then we just need to classify the state $0$, and the intuition is : as the chain goes far away from the origin (say it is in state $i$), the probability it will stay in this state $i$ is becoming higher and higher as $|i|$ increasing. And as $|i| \to \infty$, it seems it becomes harder for the chain to leave the state $i$ given it starts in state $i$, so I guess this chain is positive recurrent, but how to make the proof rigorously? Thank you for your help!

Edit: Thanks to @Math1000 help, I proved that this chain cannot be positive recurrent, but how can I show this chain is not transient?

• If $\pi$ is a stationary distribution for $X$, then it must satisfy the detailed balance equations \begin{align} \pi_iP_{i,i+1} &= \pi_{i+1}P_{i+1,i}\\ \pi_iP_{i,i-1} &= \pi_{i-1}P_{i-1,i}, \end{align} along with $\sum_{i\in\mathbb Z}\pi_i = 1$. – Math1000 Oct 12 '17 at 22:05
• @Math1000 Thank you! So I think the stationary distribution should not exists which implies this chain is not positive recurrent, bu how I can show this chain is not transient? Thanks! – user370220 Oct 12 '17 at 22:30

The chain glues together two copies of the same chain on $\mathbb Z_+$ and one already knows it is not positive recurrent hence it suffices to compute the probability of hitting $0$ starting at $1$, that is, $$p_1=P(T_0<\infty\mid X_0=1)$$ To do so, one considers the family $$p_i=P(T_0<\infty\mid X_0=i)$$ indexed by $i\geqslant1$. Then, the Markov property after one step shows that $(p_i)$ solves the system $$p_i=P_{i,i-1}p_{i-1}+P_{i,i+1}p_{i+1}+P_{i,i}p_i$$ for every $i\geqslant1$, with the convention that $p_0=1$. Reordering, one gets $$p_{i-1}-p_i=\frac{P_{i,i+1}}{P_{i,i-1}}(p_i-p_{i+1})$$ thus, for every $n$, $$1-p_1=(p_n-p_{n+1})R_n\leqslant R_n$$ where $$R_n=\prod_{i=1}^n\frac{P_{i,i+1}}{P_{i,i-1}}$$ In the present case, $$\frac{P_{i,i+1}}{P_{i,i-1}}=\frac{i}{i+2}$$ hence $$R_n=\frac2{(n+1)(n+2)}$$ Thus, $R_n\to0$ when $n\to\infty$, hence $p_1=1$, that is, the chain is (null) recurrent.