# Intersection of two simple random walks

Suppose that $X_n$ and $Y_n$ are independent, symmetric, one-dimensional simple random walks, where $X_0 = 0$ and $Y_0 = N$ for some $N \in \mathbb{N}$ where $N$ is even. I would like to show that the two random walks intersect with each other; that is, $P(X_n = Y_n \text{ for some$n \in \mathbb{N}$}) = 1$.

One way to reformulate the problem is to consider a new martingale $S_n = Y_n - X_n$ and show its recurrence property. Rather than consider each case ($S_n$ increases by -2, -1, 0, 1, 2 with each corresponding probability) and use a similar technique to show the recurrence of one-dimensional simple random walks, I am looking for a proof that uses the fact that the increments of $X_n$ and $Y_n$ have the same distribution like this:

$X_n = \sum_{i \leq n} \xi^X_i$, $Y_n = N + \sum_{i \leq n} \xi^Y_i$ where each $\xi^X_i$ and $\xi^Y_i$ represent a single step. Note that $S_n = Y_n - X_n = N + \sum_{i \leq n} (\xi^Y_i - \xi^X_i)$ has the same distribution as $S_n = Y_n - X_n = N+ \sum_{i \leq n} (\xi^Y_i + \xi^X_i)$ as $X_n$ is a symmetric random walk. This is exactly a simple random walk whose initial point is $N$ and is indexed for each even number, which is recurrent by the recurrence of a simple random walk.

• If $X_n$ and $Y_n$ are both taking steps equal to $1$ or $-1$ and $N$ is odd, then they will never intersect.
– kccu
Commented Feb 26, 2016 at 15:40
• The case you describe does not imply that they will meet. Are the allowed values for moves only between 0 and N? Are the move infinite? Is each step 1? If not, Is a jump over each other regarded an intersection?
– Moti
Commented Feb 26, 2016 at 18:54

Presuming that both $X_n$ and $Y_n$ take steps at each $n$, then the increment distribution of $S_n$ is even simpler than you describe; it will go up or down by 2 with probability 1/4 and will stay where it is with probability 1/2. Therefore, if you ignore the steps on which it stays, the resulting random walk is a genuine simple random walk on $2 \mathbb{Z}$ which is recurrent.
To formalize this: define the sequence of times $\{t_n\} \subset \mathbb{N}$ where $S_n$ moves; that is, $t_0 = 0$ and $t_n = \inf\{n > t_{n-1} \colon S_n \neq S_{n-1}\}$ for $n > 0$. The process $M_n := \frac 1 2 S_{t_n}$ can be shown to be a genuine simple random walk on $\mathbb{Z}$.