Question

Fix the decreasing sequence of nonnegative numbers \(1=b_{0} \geq b_{1} \geq \cdots\) and consider the Markov chain having transition probabilities $$ \boldsymbol{P}_{i j}= \begin{cases}\frac{b_{j}}{b_{i}}\left(\beta_{i}-\beta_{i+1}\right) & j \leq i \\\ \frac{\beta_{i+1}}{\beta_{i}} & j=i+1 \\ 0 & \text { elsewhere, }\end{cases} $$ where \(\beta_{n}=b_{n} /\left(b_{1}+\cdots+b_{n}\right)\). Show that \(P_{00}^{n}=1 / \sigma_{n}\) where \(\sigma_{n}=b_{1}+\cdots+b_{n}\). Thus the chain is transient if and only if \(\sum \frac{1}{\sigma_{n}}<\infty\).

Short answer

The probabilities for returning to an initial state in this Markov chain are given by \(P_{00}^{n}= 1 - 1 / \sigma_{n}\). Moreover, the chain is transient if and only if \(\sum 1 / \sigma_{n} < \infty\).

Step-by-step solution

Understanding the Transition Probabilities

The transition probabilities are given by: \(P_{ij} = \begin{cases} \frac{b_j}{b_i} (\beta_i - \beta_{i+1}) & \text{for } j \leq i \ \frac{\beta_{i+1}}{\beta_{i}} & \text{for } j=i+1 \ 0 & \text{elsewhere}\end{cases}\)where \(\beta_i = \frac{b_i}{b_1 + ... + b_i}\). These probabilities describe the likelihood of moving from one state \(i\) to another state \(j\).

Establish the Expression for \(P_{00}^{n}\)

Using the given transition probabilities, one can write down \(P_{00}\), the probability of transitioning from state 0 to state 0 in one step. It is simply \(P_{00} = \frac{b_0}{b_0} (\beta_0 - \beta_{1}) = \beta_0 - \beta_{1} \).Given that \(P_{00} = \beta_0 - \beta_{1}\), after \(n\) transitions, we get \(P_{00}^{n}= (\beta_0 - \beta_{1})(\beta_1 - \beta_{2})...(\beta_{n-1}-\beta_n)\). This result is derived from the fact that when we start from the beginning state and come back to the same state for the \(n\) times, the multiplication of the respective probabilities gives us the probability of the whole sequence.

Derive \(1/\sigma_n \)

We know \(\beta_n = \frac{b_n}{\sigma_n}\), where \(\sigma_n = b_1 + ... + b_n\). Notice that each \(\beta_i - \beta_{i+1}\) can be written as \(\frac{b_i}{\sigma_i} - \frac{b_{i+1}}{\sigma_{i+1}} = \frac{1}{\sigma_i} - \frac{1}{\sigma_{i+1}}\) where \(\sigma_i\) is the sum of the first \(i\) terms of \(b\). Therefore, we can express \(P_{00}^{n}\) as \(P_{00}^{n}= 1/\sigma_0 - 1/\sigma_1 + 1/\sigma_1 - 1/\sigma_2 + ... + 1/\sigma_{n-1} - 1/\sigma_n = 1/\sigma_0 - 1/\sigma_n\). Because \(\sigma_0 = b_0 = 1\) by the problem statement, we find that \(P_{00}^{n} = 1 - 1/\sigma_n \). Since \(P_{00}^{n} \) should be less than 1, the fraction \(1/\sigma_n\) should be positive. Thus, the proof is established that \(P_{00}^{n} = 1 - 1/\sigma_n \).

Prove the Transience Condition

A Markov chain is transient if it is not guaranteed to return to a particular state after leaving it. For this to be the case, the sum of \( P_{00}^{n}\) from \(n = 1\) to infinity must be less than infinity. This sum can be written as \(\sum_{n=1}^{\infty} (1 - 1/\sigma_n) \). Using the relationship found in the previous step, we can rewrite this as \(\sum_{n=1}^{\infty} 1 - \sum_{n=1}^{\infty} 1/\sigma_n \). As the first term diverges, the chain is transient if and only if \(\sum_{n=1}^{\infty} 1/\sigma_n < \infty\).