I have a random walk problem that has 8 states, (1, 2, 3, 4, 5, 6, 7, 8).
The agent is currently at the original state 1. For the next move, it has a probability of p1 moving to state 2, and a probability of 1-p1 staying at state 1.
When the agent is at state i (for all i that belong to {2, 3, ..., 7}), it always has a probability of p1 moving to i+1, a probability of p2 moving back to i-1, and a probability of 1-p1-p2 staying at state i.
When the agent is at state 8, its probability to move back to state 7 is p2, and its probability of staying at state 8 is 1 - p2.
For this problem, my questions is that: Assume the agent is currently at the original state 1, what is the agent's probability of first visiting state 8 before he/she moves back to the current state 1.
TO THE ANSWER GIVEN BELOW:
"I have a more challenging question which is similar but the agent could diverge to another route at state d (d is bigger than 1 and smaller than n). At state d, the agent changes its probability of moving to state d+1 to p2, and keep the same probability of moving up to state n, its probability of moving back one state is always p1 down back to state d.
However, at state d, the agent can diverge to another route d -> n+1 -> n+2 -> ... -> n+m, which follows the similar transition probability of the route between state 1 to state d.
I have uploaded a picture that draws the Markov chain of this random walk problem. Now, the question is that: if the agent starts at state 2, what is his/her probability of visiting state n before he/she visits state 1 or state n+m. Note that state n+m is an absorbing state.
Following the equation given by Ionza, I believe a probability can be calculated for this. However, does anybody know that some work has been done for such a problem before? Is there a clean formula that can describe such a probability. Thank you very much."
This is a version of the gambler's ruin problem, whose standard solution can be adapted to solve it as shown below.
Consider the more general problem with $\ n\ $ states and the same transition probabilities. Let $\ \pi_i\ $ be the probability, given that the agent is in state $\ i\ $, $i=2,3,\dots,n-1\ $, that he or she will visit state $\ n\ $ before state $1$. Then $\ \pi_2, \pi_3, \dots,\pi_{n-1}\ $ satisfy the equations \begin{eqnarray} \pi_2&=& p_1\pi_3 + \left(1-p_1-p_2\right)\pi_2\ ,\\ \pi_i&=& p_1\pi_{i+1} + \left(1-p_1-p_2\right)\pi_i + p_2\pi_{i-1}\\ && \mathrm{\ for\ \ } i=3,4,\dots,n-2\ ,\mbox{ and}\\ \pi_{n-1}&=& p_1 + \left(1-p_1-p_2\right)\pi_{n-1} + p_2\pi_{n-2}\ . \end{eqnarray} If we set $\ \xi_i=\pi_i\ $ for $\ i=2,3,\dots,n-1\ $, $\ \xi_1=0\ $, and $\ \xi_n=1\ $, then the $\ \xi_i\ $ satisfy the linear recurrence $$ p_1\xi_{i+1} -\left(p_1+p_2\right)\xi_i + p_2\xi_{i-1}\ , $$ with boundary conditions $\ \xi_1=0, \xi_n=1\ $. If $\ p_1\ne p2\ $, this has solution $$ \xi_i=\frac{1-\left(\frac{p_2}{p_1}\right)^{i-1}}{1 - \left(\frac{p_2}{p_1}\right)^{n-1}}=\frac{\left(\frac{p_2}{p_1}\right)^{i-1}-1}{\left(\frac{p_2}{p_1}\right)^{n-1}-1}\ , $$ while if $\ p_1=p_2\ $, it has solution $$ \xi_i = \frac{i-1}{n-1}\ .$$ If staying in state $1$ for one or more steps before leaving it does not constitute a "visit" to that state before state $\ n\ $, then the probability of visiting state $\ n\ $ before revisiting state $1$ is just $\ \xi_2\ $. On the other hand, if the agent must leave state $1$ immediately to retain the possibility of being able to visit state $\ n\ $ first, then the probability of visiting state $\ n\ $ before revisiting state $1$ is $\ p_1\xi_2\ $.