# Mean value collision time of two random walks in a line

Let $$X_n$$ and $$Y_n$$ be two simple random walk on the integer such that

1. They start at $$-1$$ and $$1$$
2. They are independent
3. The probability for them going right or left are equal at any time $$n$$

The problem I have trouble solving is the following: At what average time does the two walk collide?

We know that if Y_n doesn't move, the mean value time isn't finite. The resolution of this problem seems to greatly change from only adding a second random walk, I suspect it is also not finite

The expected time for collision time is infinite. By taking the difference of the positions of the walks at time $$n$$, we will get a random walk which starts at $$2$$ and having increments taking values $$-2, 0, 2$$ with probabilities $$\alpha, 1- 2\alpha$$ and $$\alpha$$ respectively with $$0 \leq \alpha \leq 1/2$$. Now what you are interested in is the stopping time that this new random walk hits $$0$$ for the first time.
I will just give a sketch how to get the generating function of the stopping time. Set, for $$\lambda \in \mathbb{R}$$, $$\begin{equation*} \phi (\lambda) = \alpha ( \exp (-2\lambda ) + \exp ( 2 \lambda) ) + 1- 2\alpha = \alpha \bigl( \exp(\lambda) - \exp(-\lambda) \bigr)^2 + 1. \end{equation*}$$ Hence, $$\phi (\lambda) > 1$$ for any $$\lambda$$. Further, by continuity of $$\phi$$, we have $$\phi (\lambda) \to 1$$ as $$\lambda \downarrow 0$$.
Now, let $$D_n$$ be the difference of the random walks at time $$n$$. We have $$D_0 = 2$$. Then, $$\begin{equation*} M_n = \exp ( - \lambda D_n ) \bigl( \phi(\lambda) \bigr)^{-n} \end{equation*}$$ is a martingale with respect to standard $$\sigma$$-algebra. Note $$M_0 = \exp ( - \lambda D_0 ) = \exp (-2\lambda).$$
Now, specilize to the case of $$\lambda > 0$$. If we denote $$\tau$$ as the stopping time, to then $$M_{ n \wedge \tau }$$ is also a martingale. Therefore, we obtain $$\begin{equation*} \mathbb{E} (M_{ n \wedge \tau} ) = \mathbb{E} (M_{ 0 \wedge \tau} ) = \mathbb{E} (M_0 ) = \exp ( - 2 \lambda ). \end{equation*}$$
Now, you need to use DCT on the LHS in the above to show that $$\begin{equation*} \mathbb{E} \bigl[ \mathbb{I} ( \tau < \infty ) \bigl(\phi(\lambda) \bigl)^{- \tau} \bigr] = \exp ( -2\lambda) \end{equation*}$$ for $$\lambda > 0$$. Now letting $$\lambda$$ decrease to 0, observe that $$\mathbb{E} \bigl[ \mathbb{I} ( \tau < \infty ) \bigr] = \mathbb{P} ( \tau < \infty ) = 1$$. Thus, we obtain that $$\begin{equation*} \mathbb{E} \bigl[ \bigl(\phi(\lambda) \bigl)^{- \tau} \bigr] = \exp ( -2\lambda). \end{equation*}$$ Setting $$s = 1/\phi(\lambda)$$ and denoting the inverse function by $$\lambda = \psi ( s)$$, the above equation can be rewritten as $$\begin{equation*} \mathbb{E} (s^{\tau} ) = \exp ( -2 \psi (s) ) \end{equation*}$$ which provides the generating function of the stopping time. You can get all information from this. For example, to see that the expectation is infinite you just need to differentiate the RHS and let $$s \to 1$$ and see that the expression goes to infinity. In fact, you may find the tail behaviour and it behaves as inverse of square root of $$n$$.