Stochastic Processes – Problem 11: Prove that:

Constants $\alpha_{k},\beta_{k},\gamma_{k},k\geqslant0$ satisfy $\beta_{0}\!=\!0$, $\beta_{0}+\gamma_{0}\!=\!1$, and for all $k\!\geqslant\!1$, $\alpha_{k}\!>\!0$, $\beta_{k}>0$, $\alpha_{k}+\beta_{k}+\gamma_{k}=1$. Let the discrete-time Markov chain $X_{n}$ have state space $\{0,1,\ldots\}$ with transition probabilities:

$$p(0,0)=\gamma_{0},\;p(0,1)=\beta_{0},\;p(k,k)=\gamma_{k},\;p(k,k-1)=\alpha_{k},\;p(k,k+1)=\beta_{k},\;k\geqslant1$$

Let $a\!<\!k\!<\!b$, and denote $\tau_{k}=\inf\{n{:}X_{n}\,{=}\,k\}$, $\varphi(m)=\sum_{k=0}^{m}\prod_{j=1}^{k}\frac{\alpha_{j}}{\beta_{j}}$. Prove that:

$$P_{k}(\tau_{a}<\tau_{b})=\frac{\varphi(b)-\varphi(k)}{\varphi(b)-\varphi(a)}$$

(2) $X_{n}$ is recurrent if and only if $\lim_{m\to\infty}\varphi(m)=\infty$.

(20 points)

Step 1. Establish the difference equation. Denote $u_k = P_k(\tau_a < \tau_b)$ as the probability of reaching state $a$ before $b$ starting from state $k$. For $a < k < b$, by the law of total probability applied to the one-step transition: $$u_k = \alpha_k u_{k-1} + \gamma_k u_k + \beta_k u_{k+1}$$ Since $\alpha_k + \beta_k + \gamma_k = 1$, we have $\gamma_k = 1 - \alpha_k - \beta_k$. Substituting and simplifying: $$\beta_k(u_{k+1} - u_k) = \alpha_k(u_k - u_{k-1})$$ That is: $$u_{k+1} - u_k = \frac{\alpha_k}{\beta_k}(u_k - u_{k-1})$$

Step 2. Solve for the general term. Let $\Delta_k = u_{k+1} - u_k$. By the recurrence relation: $$\Delta_k = \frac{\alpha_k}{\beta_k}\Delta_{k-1} = \prod_{j=1}^{k}\frac{\alpha_j}{\beta_j} \Delta_0$$ Denote $\rho_k = \prod_{j=1}^{k} \frac{\alpha_j}{\beta_j}$ (with $\rho_0=1$), then $\Delta_k = \rho_k \Delta_0$. For any $a \le k < b$, the telescoping sum gives: $$u_k - u_a = \sum_{j=a}^{k-1} \Delta_j = \Delta_0 \sum_{j=a}^{k-1} \rho_j$$ By the definition of $\varphi(m)$ in the problem, $\sum_{j=a}^{k-1} \rho_j$ can be expressed as $\varphi(k-1) - \varphi(a-1)$ (note: the index correspondence matches the structure of the final result). For notational simplicity, write $S_k = \sum_{j=0}^{k-1} \rho_j$, so $u_k - u_a = \Delta_0 (S_k - S_a)$. The function $\varphi(k)$ in the problem serves as the scale function.

Step 3. Substitute the boundary conditions. The boundary conditions are: 1. $u_a = 1$ (starting at $a$, state $a$ is reached immediately, so $\tau_a = 0 < \tau_b$ holds) 2. $u_b = 0$ (starting at $b$, state $b$ is already reached, so $\tau_a < \tau_b$ does not hold)

Using the form $u_k - u_a = C(\varphi(k) - \varphi(a))$ (the constant $C$ absorbs $\Delta_0$ and index adjustments, since the solution space of the difference equation is one-dimensional linear): When $k=b$: $$0 - 1 = C(\varphi(b) - \varphi(a))$$ Solving: $C = \frac{-1}{\varphi(b) - \varphi(a)}$. Substituting into the expression for $u_k$: $$u_k = 1 - \frac{\varphi(k) - \varphi(a)}{\varphi(b) - \varphi(a)} = \frac{\varphi(b) - \varphi(k)}{\varphi(b) - \varphi(a)}$$ This proves: $$P_k(\tau_a < \tau_b) = \frac{\varphi(b) - \varphi(k)}{\varphi(b) - \varphi(a)}$$

Step 4. Prove the recurrence condition. The random walk is recurrent if and only if the probability of eventually reaching state 0 from state 1 equals 1 (i.e., 0 is recurrent, hence all states are recurrent). Denote $P_1(\tau_0 < \infty)$ as the probability of eventually reaching 0 from 1. Since $\tau_b \to \infty$ as $b \to \infty$: $$P_1(\tau_0 < \infty) = \lim_{b \to \infty} P_1(\tau_0 < \tau_b)$$ Using the result from part (1) with $a=0, k=1$: $$P_1(\tau_0 < \tau_b) = \frac{\varphi(b) - \varphi(1)}{\varphi(b) - \varphi(0)}$$ Examine the limit $L = \lim_{b \to \infty} \frac{\varphi(b) - \varphi(1)}{\varphi(b) - \varphi(0)}$: $$L = \lim_{b \to \infty} \frac{1 - \frac{\varphi(1)}{\varphi(b)}}{1 - \frac{\varphi(0)}{\varphi(b)}}$$ - If $\lim_{m \to \infty} \varphi(m) = \infty$, then $\frac{1}{\varphi(b)} \to 0$, so $L = 1$. The probability is 1, and the process is recurrent. - If $\lim_{m \to \infty} \varphi(m) = M < \infty$, then $L = \frac{M - \varphi(1)}{M - \varphi(0)}$. Since $\varphi(m)$ is strictly increasing, $\varphi(1) > \varphi(0)$, so $L < 1$. The probability is less than 1, and the process is transient. In conclusion, the necessary and sufficient condition for recurrence is $\lim_{m \to \infty} \varphi(m) = \infty$.

(1) QED. (2) QED.