Stochastic Processes – Problem 22: Prove:

Constants $\alpha_k, \beta_k, \gamma_k$, $k \geq 0$, satisfy $\beta_0 = 0$, $\beta_0 + \gamma_0 = 1$, and for all $k \geq 1$, $\alpha_k > 0$, $\beta_k > 0$, $\alpha_k + \beta_k + \gamma_k = 1$. Let $X_n$ be a discrete-time Markov chain with state space $\{0, 1, \ldots\}$ and 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 \geq 1.$$

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:

$$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. Let $u_k = P_k(\tau_a < \tau_b)$ be the probability of reaching $a$ before $b$ starting from state $k$. For $a < k < b$, by the total probability formula for one-step transitions: $u_k = \alpha_k u_{k-1} + \gamma_k u_k + \beta_k u_{k+1}.$ Since $\alpha_k + \beta_k + \gamma_k = 1$, simplifying yields: $\beta_k(u_{k+1} - u_k) = \alpha_k(u_k - u_{k-1}),$ i.e., $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: $\Delta_k = \frac{\alpha_k}{\beta_k} \cdot \frac{\alpha_{k-1}}{\beta_{k-1}} \cdots \frac{\alpha_1}{\beta_1} \Delta_0.$ Setting $\rho_k = \prod_{j=1}^{k} \frac{\alpha_j}{\beta_j}$ ($\rho_0 = 1$), we get $\Delta_k = \rho_k \Delta_0$. Summing: $u_k - u_a = \Delta_0 \sum_{j=a}^{k-1} \rho_j$. The function $\varphi(k)$ from the problem serves as the scale function.

Step 3. Apply boundary conditions. Boundary conditions: $u_a = 1$ (starting at $a$, immediately reached), $u_b = 0$ (starting at $b$, $\tau_a < \tau_b$ fails). Using $u_k - u_a = C(\varphi(k) - \varphi(a))$: At $k = b$: $0 - 1 = C(\varphi(b) - \varphi(a))$, so $C = \frac{-1}{\varphi(b) - \varphi(a)}$. Substituting: $u_k = 1 - \frac{\varphi(k) - \varphi(a)}{\varphi(b) - \varphi(a)} = \frac{\varphi(b) - \varphi(k)}{\varphi(b) - \varphi(a)}.$ Hence $P_k(\tau_a < \tau_b) = \frac{\varphi(b) - \varphi(k)}{\varphi(b) - \varphi(a)}.$

Step 4. Prove the recurrence criterion. The random walk is recurrent if and only if the probability of returning to $a$ from any state is 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 part (1) with $a=0, k=1$: $P_1(\tau_0 < \tau_b) = \frac{\varphi(b) - \varphi(1)}{\varphi(b) - \varphi(0)}.$ Examining the limit $L = \lim_{b \to \infty} \frac{1 - \varphi(1)/\varphi(b)}{1 - \varphi(0)/\varphi(b)}$: - If $\lim_{m \to \infty} \varphi(m) = \infty$, then $L = 1$, so the process is recurrent. - If $\lim_{m \to \infty} \varphi(m) = M < \infty$, then $L = \frac{M - \varphi(1)}{M - \varphi(0)} < 1$, so the process is transient. Therefore, recurrence holds if and only if $\lim_{m \to \infty} \varphi(m) = \infty$.

(1) QED. (2) QED.