1D random-walker terminating position chance

Question

I understand that the title is a bit unclear, but here is my problem.

Bob, a Random-Walker, is standing at position X. When he reaches position 0, he would be so happy that he would live there forever. (i.e. stop walking).

But if he reaches position N, he would have a curse which makes him stay there forever.

Every second, Bob has a chance, T, to walk left one unit. He also has a chance (1 - T) to walk right one unit.

Determine the probability that he would find position 0 before he went into the curse (position N).

Also, X, N are given as integers and T is given as p/q. I shall output the probability as a reduced fraction A/B with B>0.

Here is my question, but I have no clue how to tackle it. There are 3 subtasks:

Default constraints: 0 < X < N ≤ 10 (so N ≥ 2 ), 0 ≤ p ≤ q ≤ 50 , q > 0 .
1. N = 2 .

N = 2 is pretty trivial, just output the given p/q.

2. N <= 3 .

   N = 3 is already hard for me to get the logic.
   Test Case 1: X = 1, N = 3, p = 1, q = 2 .
   It turns out that there is 1/2 chance of getting it the first walk, 1/8 chance of getting it the third walk, ... (infinite geometric series)
   so the answer should be 2/3

3. No additional constraints. (No idea on how to solve)

Default constraints: 0 < X < N ≤ 10 (so N ≥ 2 ), 0 ≤ p ≤ q ≤ 50 , q > 0 .
General case... No idea. Any idea or help would be great!

Test Case for reference:
X = 8, N = 9, p = 49, q = 50 Probability = 33232930569601 / 33925283289801

EDIT: I realise that markov-chains might be useful for this. Not sure how though...

Answer 1

This is a discrete-time Markov chain with state space $I = \{0,\dots,N\}$. $\require{extpfeil} \Newextarrow{\xlr}{5,10}{0x21CC}$ $$\Large 0 \underset{T}{\leftharpoondown} 1 \xlr[T]{1-T} 2 \xlr[T]{1-T} \cdots \xlr[T]{1-T} N-1 \overset{1-T}{\rightharpoonup} N $$ The absorbing states are $0$ and $N$. The transition probabilities are \begin{align} p_{i,i+1} &= 1-T \quad \forall i \in \{1,\dots,N-1\} \\ p_{i,i-1} &= T \quad \forall i \in \{1,\dots,N-1\} \\ p_{00} &= p_{NN} = 1 \end{align}

The transition matrix is $$ P= \left. \underbrace{\begin{pmatrix} 1 & 0 & 0 & 0 & \cdots & 0 & 0 & 0 & 0 \\ T & 0 & 1-T & 0 & \cdots & 0 & 0 & 0 & 0 \\ 0 & T & 0 & 1-T & \cdots & 0 & 0 & 0 & 0 \\ 0 & 0 & \ddots & \ddots & \ddots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & \cdots & \ddots & \ddots & \ddots & \ddots & 0 & 0 \\ 0 & 0 & 0 & 0 & \cdots & T & 0 & 1 - T & 0 \\ 0 & 0 & 0 & 0 & \cdots & 0 & T & 0 & 1 - T \\ 0 & 0 & 0 & 0 & \cdots & 0 & 0 & 0 & 1 \end{pmatrix}.}_{N \text{ columns}} \right \} N \text{ rows} $$

Let $h^0 = (h^0_i)_{i \in I}$ be the hitting probability of state $0$. We have $h_0^0 = 1$ and $h_N^0 = 0$. To find a relation between $h_i^0$'s, we condition on $X_1$. For $i \in \{1, \dots, N-1\}$,

\begin{align} h_i^0 &= P(\text{hit } 0 \mid X_0 = i) \\ &= P(\text{hit } 0 \mid X_1 = i-1) p_{i,i-1} + P(\text{hit } 0 \mid X_1 = i+1) p_{i,i+1} \\ &= p_{i,i-1} h_{i-1}^0 + p_{i,i+1} h_{i+1}^0 \\ &= T h_{i-1}^0 + (1-T) h_{i+1}^0 \end{align}

This gives the system $h^0 = P h^0$, but $\det P = \det(I - P) = 0$, so we can't take the inverse of $I-P$ to solve for $h^0$. Usual techniques for recurrence sequences don't work here.

The trick is to take $u_i = h_{i-1}^0 - h_{i}^0$, so that for $i \in \{1, \dots, N-1\}$, \begin{align} (T + (1-T)) h_i^0 &= T h_{i-1}^0 + (1-T) h_{i+1}^0 \\ (1-T) u_{i+1} &= T u_i, \text{ so that} \\ u_{i+1} &= \frac{T}{1-T} u_i = \left( \frac{T}{1-T} \right)^i u_1. \\ h_0^0 - h_i^0 &= \sum_{k=0}^{i-1} \left( \frac{T}{1-T} \right)^k u_1 \quad \forall\, i \in \{1,\dots,N\} \\ &= \left\{ \begin{aligned} \frac{1-\left(\frac{T}{1-T}\right)^i}{1-\frac{T}{1-T}}\,u_1 & \text { if } T \ne \frac12 \\ i \,u_1 & \text { if } T = \frac12 \end{aligned} \right. \\ h_i^0 &= \left\{ \begin{aligned} 1 - \frac{1-\left(\frac{T}{1-T}\right)^i}{1-\frac{T}{1-T}}\,u_1 & \text { if } T \ne \frac12 \\ 1 - i \,u_1 & \text { if } T = \frac12 \end{aligned} \right. \end{align} To compute $u_1$, choose $i = N$ so that \begin{align} 0 &= \left\{ \begin{aligned} 1 - \frac{1-\left(\frac{T}{1-T}\right)^N}{1-\frac{T}{1-T}}\,u_1 & \text { if } T \ne \frac12 \\ 1 - N \,u_1 & \text { if } T = \frac12. \end{aligned} \right. \\ u_1 &= \left\{ \begin{aligned} \frac{1-\frac{T}{1-T}}{1-\left(\frac{T}{1-T}\right)^N} & \text { if } T \ne \frac12 \\ \frac1N & \text { if } T = \frac12 \end{aligned} \right. \end{align} Conclusion $$ h_i^0 = \left\{ \begin{aligned} 1 - \frac{1-\left(\frac{T}{1-T}\right)^i}{1-\left(\frac{T}{1-T}\right)^N} & \text { if } T \ne \frac12 \\ 1 - \frac{i}{N} & \text { if } T = \frac12 \end{aligned} \right. $$

Answer 2

I have got an answer from AoPS, and I would like to share it here. Simply setup a system of equations:

Let P_X be the probability when starting at position X. and T be the probability to hop left and N be the cursed earth position.

P_0 = 1
P_(n + 1) = T * P_n + (1 - T) * P_(n + 2)
P_N = 0

From that, solve for P_X and that's your probability.

Elegant!