Hitting time of Markov chain is minimal solution to quadratic equation

119 Views Asked by At

Let $(X_n)_{n\geq 0}$ be a random walk on the natural numbers with probability $p$ of going from $i$ to $i+1$ and $q$ of going from $i$ to $i-1$. Let $T_0:=\inf\{n\geq 0 \,|\, X_n =0\}$ and $h_i:=\mathbb{P}_i(T_0<\infty)$, where the subscript $i$ means that the chain is started at $X_0=i$. Using the strong Markov property one easily gets that $h_1$ satisfies $$ h_1=p h_1^2+q. $$ Of course this generally gives two possible values for $h_1$. In my textbook it is claimed, without proof, that the correct one is always the minimal positive solution. I tried to prove this claim mimicking the proof in James Norris, Markov Chains, Theorem $1.3.2$ but had no success. Any help or hint is appreciated.

1

There are 1 best solutions below

7
On

Let's solve for $h_1$, using the relation that $p = 1-q$. The quadratic formula dictates that if $h_1$ is our solution, $$h_1 = \frac{1 \pm \sqrt{1-4pq}}{2p}.$$ Let's look under the discriminant. $$1-4pq = 1-4p(1-p) = 1-4p+4p^2 = (2p -1)^2.$$ If $p \geq 1/2$, our solutions are $$h_1 = \frac{1 \pm (2p-1)}{2p} = \{1, q/p\}.$$ We can eliminate the solution $h_1 = 1$ on the grounds that there is a nonzero probability our chain ends up at $\infty.$