Markov Hitting Times - probability of hitting state 11 before state 1

Question

Let $(X_n)_{n \geq 0}$ be a markov chain on $I=${ $1,...,12$ }, with stochastic matrix:

$$p_{i,j}=\begin{cases} p & if \ j=i+1 \ mod \ 12 \\ q=(1-p) & if \ j=i-1 \ mod \ 12 \\ 0 & o/w \end{cases}$$, where $p\in(0,1)$.

Suppose we begin with $X_0 = 6$, then what is the probability the chain hits state 11 before state 1?

My thoughts:

If $p=q=\frac{1}{2}$, then probability = $\frac{1}{2}$

If $p=1, q=0$, then probability = $1$

Similarly if $p=0,q=1$, then probability = $0$

With the other case more difficult. I know that we are trying to find $\mathbb{P}_6(h^{11} < h^1). $ I thought writing $\mathbb{P}((\frac{p}{q})^i<(\frac{q}{p})^i)$ may help, but then I do not know what to do with this?

Is there another way to approach this?

Answer 1

Remodel your questio where we remove state $0$ and view state $1$ and state $11$ as absorbing states.

Let $p_i$ be the probability of ending up at state $11$ starting from state $i$, we are interested in $p_6$.

$p_1=0, p_{11}=1$.

For $2 \le i \le 10$,

$$p_i = pp_{i+1}+qp_{i-1}$$

Now, this is a linear system and we can solve the linear system.

---

This is equivalent to the Gambler's ruin formula,

$$p_6 = \frac{1-\left(\frac{q}p \right)^5}{1-\left( \frac{q}p\right)^{10}}$$

Answer 2

Treating it as a random walk where $A$ "loses" is at $1,$ is currently at $6$, and needs to take $5$ steps to the right to reach $11$ to "win", let us derive a formula

$L = $ left bound , $R=$ right bound, $n =$ steps away from "loss" for $A$,
$p = Pr$ (step to right), $q = Pr$ (step to left), $k = q/p,$

Then $P(n) = a + bk^n$ is the general solution,
with $P(L) = 0, P(R) = 1$ as the boundary conditions.

$\displaylines{a+bk^L = 0, a + bk^R = 1\\bk^R - bk^L = 1,\;\;b = \dfrac{1}{k^R-k^L}\\a +bk^n = bk^n -bk^L = \dfrac{k^n-k^L}{k^R-k^L}=\dfrac{k^6-k^1}{k^{11}-k^1}\\= \dfrac{k^5-1}{k^{10}-1}}$,

PS

This can, of course also be solved using first step analysis, but then a lot of linear equations will be involved of the type below

$x_6 = p.x_7 + (1-p)x_5$
$x_7 = p.x_8 + (1-p)x_6$ etc etc