Let $\{X_n\}$ be a symmetric random walk on integers and $\{Y_n\}$ be a random walk on integers with transition probabilities:
$$p(k,k+1)=p,~p(k,k-1)=q=1-p.$$
Suppose $\{X_n\}$ and $\{Y_n\}$ are independent. If $X_0=a>0,~Y_0=0$, evaluate the probability that $\{X_n\}$ and $\{Y_n\}$ will ever meet.
Attempt. Let $\{(X_n,Y_n)\}$ be the $2D$ random walk on
$\mathbb{Z}^2$ with transition probabilities:
$$p\big((k,m),(k\pm 1,m+1)\big)=\frac{p}{2},~p\big((k,m),(k\pm 1,m-1)\big)=\frac{q}{2}.$$
If $T=\inf\{n\geqslant 0: (X_n,Y_n)\in \Delta\}$ is the time the two random walks first meet and
$$h(k,m)=P\big((X_n,Y_n)\in \Delta|(X_0,Y_0)=(k,m)\big)$$ then we seek for $h(a,0).$ We know that:
$$h(k,m)=\frac{p}{2}\,h(k+1,m+1)+\frac{p}{2}\,h(k-1,m+1)
+\frac{1-p}{2}\,h(k+1,m-1)+\frac{1-p}{2}\,h(k-1,m-1)$$
and $h(m,m)=0$ for all integers $m,~k$. How can we procced to the solution of this recurrence equation?
Best Answer
Following the guideline by @Rhys Steele, let's take the $1D$ random walk $Z_n=\frac{X_n-Y_n}{2}$, defined by the semi-differences of $X_n,\,Y_n$, with transition probabilities: $$p(k,k+1)=\frac{q}{2},~~p(k,k-1)=\frac{p}{2},~~p(k,k)=\frac{1}{2}.$$ Under this modelling we are looking for $P(T_0<+\infty|Z_0=a/2),$ where $$T_0=\inf\{n\geqslant 0: Z_n=0\}$$ the first time $Z_n$'s hit $0$, in other wording, $X_n$'s and $Y_n$'s coincide. Obviously the desired probability equals $0$, if $a$ is odd. For the case $a$ is even, set $h(k)=P(T_0<+\infty|Z_0=a)$ and $h$ is the least non-negative solution of the equation:
$$h(k)=\frac{q}{2}\,h(k+1)+\frac{1}{2}\,h(k)+ \frac{p}{2}\,h(k-1)$$ equivalently: $$q\,h(k+1)-h(k)+p\,h(k-1)=0,$$
along with $h(0)=0.$ The solution to the above problem is not unique, but under the condition that $h$ is the least non-negative solution we get the formula: $$P_{a/2}(T_0<+\infty)=\left \{\begin {array}{ll} 1&~,~~0<p \leqslant 1/2\\ \displaystyle \left(\frac{p}{1-p}\right)^{\frac{a}{2}}&~,~~1/2<p<1\\ \end{array} \right..$$