Probability of going into an absorbing state

Question

If I have a random walk Markov chain whose transition probability matrix is given by

$$ \mathbf{P} = \matrix{~ & 0 & 1 & 2 & 3 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & 0.3 & 0 & 0.7 & 0 \\ 2 & 0 & 0.3 & 0 & 0.7\\ 3 & 0 & 0 & 0 & 1 } $$

I'm supposed to start in state 1, and determine the probability that the process is absorbed into state 0. I'm supposed to do so using the basic first step approach of equations: \begin{align*} u_1&=P_{10} + P_{11}u_1 + P_{12}u_2\\ u_2&=P_{20} + P_{21}u_1 + P_{22}u_2 \end{align*}

I also should use the results for a random walk given by: $$u_i = \begin{cases} \dfrac{N-i}{N} & p=q=1/2\\\\ \dfrac{(q/p)^i-(q/p)^N}{1-(q/p)^N} & p\neq q \end{cases}$$

Can I have some suggestions on how to proceed? Thanks for any and all help!

Answer 1

The probability that we get to state zero immediately is $0.3$. The next possibility is that we get to state two then we get back to state one and then to state zero, the probability of which event is $0.7\cdot0,3\cdot0.3=0.7\cdot0.3^2$. The probability of the next possibility is $0.7\cdot0.3\cdot0.7\cdot0.3\cdot0.3=0.7^2\cdot0.3^3$, and so on.

The probability that we get to state zero once in the future is then $$\sum_{i=0}^{\infty} 0.7^{\ i}0.3^{\ i+1}=0.3\sum_{i=0}^{\infty} 0.21^{\ i}=0.3\frac{1}{1-0.21}.$$

Answer 2

Let $L_i$ be the likelihood that you terminate at node $0$ given that you start at node $i$.

Clearly, $L_0 = 1,\ L_3 = 0$. In your case $p = p_{i,i-1} = 0.3 = 1 - p_{i-1,i}$, in general it can be shown that $$L_1 = pL_0 + (1-p)L_2\text{, and }L_2 = pL_1 + (1-p)L_3$$

It's clear then that $L_1 = (1)p+(1-p)L_2 = p + (1-p)(pL_1 + (1-p)(0))$, so $$L_1 = p + (1-p)pL_1 \implies L_1 = \frac{p}{1 - (1-p)p}$$ $$L_2 = pL_1 = \frac{p^2}{1 - (1-p)p}$$

Answer 3

Hint:

Another approach to solving this problem is to see what the sum of the amounts that are absorbed at each step are.

Let $S$ be the initial state and $$ M=\begin{bmatrix} 0&0&0&0\\ 0.3&0&0.7&0\\ 0&0.3&0&0.7\\ 0&0&0&0 \end{bmatrix} $$ Then the absorbent terms (the left and right elements) of $SM^k$ are the amounts that gets absorbed at step $k$. Thus, the absorbent terms of $$ S\left(M+M^2+M^3+M^4+\cdots\right)=SM(I-M)^{-1} $$ tell how much has been absorbed in total.

Answer 4

An approach that may be along the lines of what you suggest you need to use is the following:

If you denote the probability $P \{\text{ETS C} | X_0 = i\}$ by $q_{iC}$ , where ETS is "eventually the state", then using the Law of Total Probability gives

$ q_{iC} = \sum_{j \in S} P \{\text{ETS C}, X_1 = j | X_0 = i\}$

and using the definition of conditional probability we have $P \{ \text{ETS C}, X_1 = j | X_0 = i\} = P \{\text{ETS C} | X_1 = j, X_0 = i\} P\{X_1 = j | X_0 = i\}$.

Then use the Markov property to write the first term in the above as $P \{\text{ETS C} | X_1 = j\}$ giving the final result

$q_{iC} = \sum_{j \in S} p_{i,j} q_{jC}$

where the $p_{i,j}$ are the given transition probabilities.

It is natural to use the boundary conditions

$q_{iC} = \begin{cases} 1 i \in \text{C } & \\ 0 i \in \text{other closed classes} \end{cases} $

since if you start in another closed class other than C you will stay there and never be able to reach the desired C.

In your problem (I hope you do not mind but I have re-labelled the states by {1, 2, 3, 4}), you have the absorbing state is C = 1, so that $q_{1C} = 1$, and for the other absorbing state, state 4, $q_{4C} = 0$.

This yields the equations: $q_1 = p_{1,1} q_1 = q_1$ (so nothing new, though with $q_1 = 1$),

$q_2 = 0.3 q_1 + 0.7 q_3$

$q_3 = 0.3 q_2$ (using the term $0.7 q_4 = 0.7 \times 0 = 0$)

and the final equation gives $q_4 = q_4 (= 0 \text{ by assumption})$.

The desired probability is $q_2 = \frac{0.3}{1 - 0.7 \times 0.3}$, since you are told you start in state {2}. If you had started from state {3} the desired probability is $q_3 = 0.3 q_2 = 0.3 \times \frac{0.3}{1 - 0.7 \times 0.3}$