Probability that two random walks on the line do not intersect.

Question

Let $\xi_1^1,\xi_2^1,\ldots$ and $\xi_1^2,\xi_2^2,\ldots$ be two sequences of random variables such that $\xi_1^1,\xi_2^1,\xi_1^2,\xi_2^2,\ldots$ are pairwise independent. Let $\mathbb{P}(\xi_i^j=-1)=\mathbb{P}(\xi_i^j=1)=1/2$ for all $i\in\mathbb{N}$ and $j\in\{1,2\}$. Denote $S_k^j=\sum_{i=1}^k\xi_i^j$. Could someone help me to find probability of the event $A_n:=\{S_k^1\neq S_k^2\quad \forall k\in\{1,\ldots,n\}\}$. In other words, what is the probability that two random walks do not intersect during first $n$ steps?

Answer 1

Let $G_n:=k+(S_n^{1}-S_n^2)/2$, which is a random walk starting at $k$ and whose increments are $-1$, $0$, $1$ with probabilities $1/4$, $1/2$, and $1/4$, respectively. Also let $T_0:=\inf\{n:G_n=0\}$. For $k\ge 1$, $$ \mathsf{P}_k(T_0=n)=\frac{k}{n}\mathsf{P}_k(G_n=0), $$ where $\mathsf{P}_k$ is the law of $G_n$ starting at $k$ (see Theorem 1 here). It is clear that $\mathsf{P}_0(T_0=1)=0.5$. For $n>1$, $$ \mathsf{P}_0(T_0=n)=\frac{1}{2}\mathsf{P}_1(T_0=n-1)=\frac{1}{2(n-1)}\mathsf{P}_1(G_{n-1}=0). $$ The probability on the RHS is given by $$ \frac{1}{2^{-n+2}}\sum_{k=1}^{n/2}\frac{(n-1)!}{(k-1)!(n-2k)!k!}4^{-k}=\binom{n-3/2}{n-1}\times\frac{n-1}{n}. $$ Finally, $$ \mathsf{P}_0(T_0>n)=\sum_{m>n}\mathsf{P}_0(T_0=m)=\binom{n-1/2}{n} .$$

Answer 2

Consider the difference in the position of these two walks, $S_k^1-S_k^2$. At each step, this difference is $0$ with probability $\frac12$ and $\pm2$ with probability $\frac14$ of going in either direction. So, up to rescaling, we can think of this as performing a random walk but flipping a coin at every step to decide whether to proceed.

So long as the first step of this difference walk is not stationary (that is, the two original random walks do not step in the same direction), we can ignore all subsequent stationary points (except insofar as they use of some of our $n$ steps). So if we have taken $n$ steps in the difference walk, with the first such step necessarily nonzero, we can break down the possibilities based on how many nonzero steps $k$ were taken. Letting $p(n)$ be the probability that a standard $\pm1$ walk avoids $0$ after $n$ steps, our answer is:

$$\frac12 \cdot \sum_{k=1}^n {n-1\choose k-1}2^{1-n} \cdot p(k) = \sum_{k=1}^n {n-1\choose k-1}2^{-n} \cdot p(k)$$

(That is, the initial step is $1/2$ chance to fail, and of the $n-1$ non-initial steps in our walk, the number of them that are nonzero follows a binomial distribution.)

$p(n)$ is known to be ${n-1\choose \lfloor(n-1)/2\rfloor}2^{-(n-1)}$, so substituting and shifting our indices:

$$\sum_{k=0}^{n-1} {n-1\choose k} \cdot {k\choose \lfloor k/2\rfloor }\cdot 2^{-n-k}$$

Empirically, this seems to be ${2n\choose n}4^{-n}$, but I'm not sure how to prove this; probably it follows by application of the right combinatorial identities.