Markov Chain transition probabilities using proof by induction

Question

Let $\left(X_{n}\right)_{n \geq 0}$ be a Markov chain on the state space $S=\mathbb{N}$ with transition probabilities $p_{12}=1, p_{i, i+1}=$ $i(i+2) /(i+1)^{2}$, and $p_{i 1}=1 /(i+1)^{2}, i>1$, and the remaining zero. Let $T_{i}(1)=\min \left\{n>0 \mid X_{n}=i\right\}$ be the first time in state $i$ after time zero. Show by induction that

1. $$p_{1 j}^{(j-1)}=\frac{2}{3} \frac{j+1}{j}$$

for $j>1$ and

2. $$P\left(T_{1}(1)=k \mid X_{0}=1\right)=\frac{2}{3} \frac{1}{k(k+1)}$$

for $ k \geq 2$.

---

1. First off I am not experienced with induction proofs and I even think my base case is wrong, although most of my worries are with the hypothesis-step which will be seen. I have - at most - done two. However, for the first question it seems that the base case would be for a $j=2$ $$p_{12}^{2-1}=p_{12}^{1}=1=\frac{2}{3}\frac{2+1}{2}=1$$ from the description of the problem. I am stuck from this point for the induction step but I think it would go as such: $$p_{1,j+1}^{(j+1-1)}=p_{1,j}^{(j-1)}p_{i,i+1}=\frac{2}{3}\frac{j+1}{j}\frac{j(j+2)}{(j+1)^{2}}=\frac{2}{3}\frac{j(j+2)}{(j+1)}=\frac{2}{3}\frac{(j+1)+1}{(j+1)}$$

---

2. The second problem would be for the base case $k=2$ that we can rewrite the set $$\{T_{1}(1)=k\}=\{X_0=1,X_1=2,...,X_{k-1}=k,X_0=1\}$$ So that we have \begin{align*} P(T_1(1)=2|X_0=1)&=P(\{X_0=1,X_1=2,X_0=1\}|X_0=1)\\&=\frac{2}{3}\frac{1}{2(2+1)}=\frac{2}{3}\frac{1}{6}=\frac{1}{9}\\&= p_{i1}=p_{21}=\frac{1}{(2+1)^2}=\frac{1}{9} \end{align*} from the description as we are going back to state 2 to 1. I am stuck from this point for the induction step as well. How to do the proof using induction correctly would be really appreciated.

Answer 1

On Problem 1, you are correct. The assertion is claimed to hold for $j>1$, so the base case is the smallest value for $j$, namely $j=2$. In the induction step you argue that if the assertion holds for a given value of $j$, then it holds for $j+1$. In your context you must argue that if you assume $$p_{1 j}^{(j-1)}=\frac{2}{3} \frac{j+1}{j},$$ then $$p_{1 ,j+1}^{((j+1)-1)}=\frac{2}{3} \frac{(j+1)+1}{j+1},$$ which is exactly what you've done. The crucial step is observing that $p_{1,j+1}^{(j+1-1)}=p_{1,j}^{(j-1)}p_{j,j+1}$ (you have a typo in the rightmost factor), i.e., that the only way to reach state $j+1$ from state $1$ in $j$ steps is to first reach state $j$ from state $1$ in $j-1$ steps, and then go from state $j$ to state $j+1$ in the next step. The rest of the argument is substituting what you assumed is true, and doing some algebra.

On Problem 2, no induction is needed; you can use the result of Problem 1. The conditional probability $P\left(T_{1}(1)=k \mid X_{0}=1\right)$ is the probability that the chain, starting in state $1$, returns to state $1$ for the first time in $k$ steps. Since the chain can only move to the right or drop back to $1$, the desired event happens if and only if the chain progresses from state $1$ to state $k$ in $k-1$ steps, and then drops to state $1$ on the next step.