Consider a gambling process $(X_n)_{n∈\mathbb{N}}$ on the state space $S = {0, 1, . . . , N}$, with probability $p$, resp. $q$, of moving up, resp. down, at each time step. For $x = 0, 1, . . . , N$, let $τ_x$ denote the first hitting time, $τ_x := \inf\{n ≥ 0 : X_n = x\}$
Let $p_x := P(τ_{x+1} < τ_0 | X_0 = x), x = 0, 1, . . . , N − 1$
Explain why $p_x$ satisfies the recursion $p_x = p + qp_{x−1}p_x$ for $x = 1, . . . , N − 1$.
I apply the first step analysis, whereby
$P(τ_{x+1} < τ_0 | X_0 = x) = P(τ_{x+1} < τ_0 | X_0 = x_1, X_1=x+1) \cdot P(X_1=x+1 |X_0 = x) + P(τ_{x+1} < τ_0 | X_0 = x_1, X_1=x-1) \cdot P(X_1=x-1 |X_0 = x)$
By the time homogeneous property, the equation reduces to,
$P(τ_{x+1} < τ_0 | X_0 = x+1) \cdot P(X_1=x+1 |X_0 = x) + P(τ_{x+1} < τ_0 | X_0 =x-1) \cdot P(X_1=x-1 |X_0 = x)$
Given that initial state is $x+1$, we have already "hit" $x+1$ before hitting $0$. So the equation is now
$1 \cdot p + P(τ_{x+1} < τ_0 | X_0 =x-1) \cdot q$
Now all left to do is to find $P(τ_{x+1} < τ_0 | X_0 =x-1)$
The Event $\{τ_{x+1} < τ_0 \}$ given that $X_0 =x-1$ can be pictured as paths with the following trends in the picture below.
I think the graph on the right correctly portrays the 2 general trends of the outcomes in the event.
It can be described as the paths starting at $x_1$, going up and down in any way except reaching $0$ before hitting $x+1$, and then eventually hitting either the absorption state $0$ or $N$.
But, i was told that we should IGNORE the presence absorption state $N$ and do the following,
Consider the graph on the left,
First treat $x$ as an absorption state and thus the green line has probability $p_{x_1}$.
Then treat $x+1$ as an absorption state and thus the blue line has the probability $p_{x}$. It stops here since it is an absorption state.
Is the above approach valid? It seems very strange as $0$ and $N$ are defined to be the absorption states in the gambling process.
If the above approach is valid, why so? (Edit: DEFINITELY NOT, Why did the person even tell me this).
If not, what is the proper approach here? (Edit: The accepted answer).
Let us write $\mathbb P_x(\cdots) = \mathbb P(\cdots \mid X_0 =x)$. Let $$A_{x+1} = \{\tau_{x+1} < \tau_0 \}=\{\text{hit $x+1$ before 0}\}$$ be the desired event. We have \begin{align*} p_x = \mathbb P_x(A_{x+1}) &= \mathbb P_x(X_1 = x+1) \mathbb P(A_{x+1} \mid X_1 = x+1)+ \mathbb P_x(X_1 = x-1) \mathbb P(A_{x+1} \mid X_1 = x-1) \\ &= p \cdot 1 + q \;\mathbb P(A_{x+1} \mid X_1 = x-1) \\ &= p \cdot 1 + q \mathbb P_{x-1}(A_{x+1}) \\ \end{align*} It only remains to compute the probability of hitting $x+1$ before zero starting at $x-1$. But this is equivalent to hitting $x$ before zero starting at $x-1$, then hitting $x+1$ before zero as if we started again from $x$, and by strong Markov property these two events are independent (this is hand-waving, see details below!), hence the probability is $p_{x-1} p_x$.
If you want more details: \begin{align} \mathbb P_{x-1}(\tau_{x+1} <\tau_0) &\stackrel{(a)}{=} \mathbb P_{x-1} (\tau_{x} < \tau_0, \tau_{x+1} < \tau_0) \\ &\stackrel{(b)}{=} \mathbb P_{x-1} (\tau_{x} < \tau_0) \,\mathbb P( \tau_{x+1} < \tau_0 \mid \tau_x < \tau_0, X_0 = x-1) \\ &\stackrel{(c)}{=}\mathbb P_{x-1} (\tau_{x} < \tau_0)\, \mathbb P_x( \tau_{x+1} < \tau_0). \end{align} Equality (a) is since if you start at $x-1$, you have to hit $x$ before $x+1$, that is $$\{\tau_{x+1} < \tau_0\} \cap \{X_0 = x-1\} \subset \{\tau_{x} < \tau_0\} \cap \{X_0 = x-1\}.$$
More details: Equality (b) above is basic conditional probability: $$\mathbb P(A_x \cap A_{x+1} \mid X_0 = x-1) = \mathbb P(A_x \mid X_0 = x-1)\, \mathbb P(A_{x+1} \mid A_{x} \cap \{X_0 = x-1\}).$$ Equality (c) is tricky. Let us unpack: We can write $$\{\tau_{x} < \tau_0\} = \{\tau_x < \infty,\, \tau_0 = \infty\} \cup \{\tau_x < \tau_0 < \infty\}$$ and these two events are disjoint. However, note that both imply that $\tau_x$ is finite, that is, we hit state $x$ at some point. Now, let us define $X'_n := X_{\tau_x + n},\; n\ge 0$ and let $\tau'_{x}$ be the hitting time of state $x$ in this new process $\{X'_n\}$ (similar to $\tau_x$ which is the hitting time of $x$ by $\{X_n\}$). Also note that $\{X'_n\}$ is well-defined on the event $\tau_x < \infty$.
Let $B_x = \{\tau_x < \tau_0, \, X_0=x-1\}$. We want to calculate $\mathbb P (\tau_{x+1} < \tau_0 \mid B_x)$. As argued above, on $B_x$, $\tau_x$ is finite, that is, $B_x \subset \{\tau_x < \infty\}$. Given $B_x$, considering the first times $X'_n$ and $X_n$ hit $x+1$, by definition, we have $\tau_{x+1} = \tau_x + \tau'_{x+1}$. Similarly, on $B_x$, $\tau_0 = \tau_x + \tau'_0$. Thus, \begin{align} \mathbb P (\tau_{x+1} < \tau_0 \mid B_x) &= \mathbb P (\tau_{x+1} < \tau_0 \mid B_x \cap \{\tau_x < \infty\}) \\ &= \mathbb P (\tau'_{x+1}+\tau_x < \tau_0'+\tau_x \mid B_x \cap \{\tau_x < \infty\}) \\ &= \mathbb P (\tau'_{x+1} < \tau'_0 \mid B_x \cap \{\tau_x < \infty\}) \\ &\stackrel{(d)}{=} \mathbb P (\tau'_{x+1} < \tau'_0 \mid B_x \cap \{\tau_x < \infty, X'_0 = x\}) \\ &\stackrel{(e)}{=} \mathbb P (\tau'_{x+1} < \tau'_0 \mid \{\tau_x < \infty, X'_0 = x\}) \\ &\stackrel{(f)}{=} \mathbb P (\tau_{x+1} < \tau_0 \mid X_0 = x) = p_x \end{align} where (d) is true by definition of $\tau_x$ (assuming $\tau_x < \infty$) since $X'_n = X_{\tau_x} = x$, and (e) and (f) follow from strong Markov property: Given $\tau_x < \infty, X'_0 = y$, the process $\{X'_n\}$ is independent of $X_1,\dots,X_{\tau_x}$ and has the same distribution as $\{X_n\}$ with $X_0 = y$. Note that $B_x$ only depends on $X_1,\dots,X_{\tau_x}$ (there should be no state 0 in there) hence using independence clause of strong Markov, can be dropped (equality (e)).