Question

Consider an irreducible finite Markov chain with states \(0,1, \ldots, N\). (a) Starting in state \(i\), what is the probability the process will ever visit state \(j\) ? Explain! (b) Let \(x_{i}=P\) [visit state \(N\) before state 0 |start in \(\left.i\right\\}\). Compute a set of linear equations that the \(x_{i}\) satisfy, \(i=0,1, \ldots, N\). (c) If \(\sum_{j} j P_{i j}=i\) for \(i=1, \ldots, N-1\), show that \(x_{i}=i / N\) is a solution to the equations in part (b).

Short answer

In summary, to answer the question: (a) The probability of ever visiting state \(j\) from state \(i\) is given by the sum: \(\sum_{n = 1}^{\infty}f_{ij}^{(n)}\). (b) The set of linear equations for \(x_i\), the probability of visiting state \(N\) before state \(0\), is given by: \(x_{i} = \sum_{j = 1}^{N-1} P_{i j} x_j\). (c) If \(\sum_{j} j P_{i j}=i\) for \(i=1, \ldots, N-1\), then \(x_i = i/N\) is a solution to the equations in part (b).

Step-by-step solution

Define First Passage Probability

First passage probability is the probability that a system will reach a given state for the first time after a certain number of steps. Let \(f_{ij}^{(n)}\) denote the probability that the process will visit state \(j\) for the first time in \(n\) steps, starting from state \(i\).

(a) Probability of ever visiting state \(j\) from state \(i\)

To find the probability of ever visiting state \(j\) from state \(i\), we can sum up the probabilities of visiting state \(j\) for the first time at any number of steps. That is, $$\sum_{n = 1}^{\infty}f_{ij}^{(n)}$$ The probability of ever visiting state \(j\) from state \(i\) can be found using this sum.

(b) Find linear equations for \(x_i\)

Let \(x_i\) be the probability of visiting state \(N\) before state \(0\), starting from state \(i\). Notice that \(x_0 = 0\) (since we are already in state 0) and \(x_N = 1\) (since we are already in state \(N\)). Now, let's set up a system of linear equations based on the Markov chain properties. For each state \(i\), we can write: $$x_{i} = \sum_{j = 1}^{N-1} P_{i j} x_j$$ Here, \(P_{ij}\) is the transition probability from state \(i\) to state \(j\). Since \(i\) can range from \(1\) to \(N-1\), we can construct a set of linear equations with \(N - 1\) unknowns.

(c) Prove \(x_i = i/N\) is a solution

We are given that \(\sum_{j} j P_{i j}=i\) for \(i=1, \ldots, N-1\). Our goal is to show that if this condition holds, then the previously derived set of linear equations has the solution \(x_i = i / N\). For each state \(i\), we have: $$x_{i} = \sum_{j = 1}^{N-1} P_{i j} x_j = \sum_{j = 1}^{N-1} P_{i j} \frac{j}{N}$$ Now, replace the summation with the given condition: $$x_i = \frac{1}{N} \sum_{j} j P_{i j} = \frac{i}{N}$$ This shows that \(x_i = i / N\) is indeed a solution to the set of linear equations derived in part (b), given the specified condition.