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?
Probability that two random walks on the line do not intersect.
probabilityrandom walk
Related Solutions
$$P(\xi_1 - \xi_2 = k) = \sum_{i=1}^{\infty} P(\xi_2 = i,\xi_1 = k+i) = \sum_{i=1}^{\infty}P(\xi_1=i)P(\xi_2 = k+i),$$ and you can calculate this sum easily using the mass functions of $\xi_1$ and $\xi_2$.
The fact that this involves "convolutions" and sums of i.i.d. random variables makes me think of trying to deduce the distribution from Moment generating functions. Using the independence of the $\xi_i$, we have (for $t<\lambda$),
$$ \begin{eqnarray*} \mathbb{E}\left[e^{t\sum\limits_{n=1}^{\nu}\xi_{n}}\right]&{}={}&\sum\limits_{r=1}^{\infty}\int{\textbf{1}}_{\left\{\xi_{1}\leq 1,\,\ldots\,,\,\xi_{r-1}\leq 1\,,\,\xi_{r}>1 \right\}}e^{t\left(\sum\limits_{n=1}^{r}z_{n}\right)}f_{z_1}\ldots f_{z_r}dz_1\ldots dz_r\newline &{}={}&\sum\limits_{r=1}^{\infty}\left(\dfrac{\lambda}{\lambda{}-{}t}\right)^r e^{t-\lambda}\left(1{}-{}e^{t-\lambda}\right)^{r-1}\newline &{}={}&e^{t-\lambda}\dfrac{\lambda}{\lambda{}-{}t}\sum\limits_{r=1}^{\infty}\left(\dfrac{\lambda}{\lambda{}-{}t}\right)^{r-1} \left(1{}-{}e^{t-\lambda}\right)^{r-1}\newline &{}={}&\left(\dfrac{e^{t-\lambda}\dfrac{\lambda}{\lambda{}-{}t}}{1{}-{}\left(\dfrac{\lambda}{\lambda{}-{}t}\right) \left(1{}-{}e^{t-\lambda}\right)}\right)\,\newline &{}={}&\dfrac{1}{1{}-{}e^{\lambda{}-{}t}t/\lambda}\,. \end{eqnarray*} $$
This looks like $\sum\limits_{n=1}^{\nu}\xi_{n}$ is trying to be exponentially distributed with "rate" $\lambda/e^{\lambda{}-{}t}$, but I do not know this functional form by heart. Any ideas?
Edit: Not knowing the explicit inverse of the final generating function form above, I thought of examining each term in the equivalent series representation: perhaps the individual terms have nicer inverses. If this is the case, then a series representation might be sufficient. If we perform the substitution $u{}={}t/\lambda$, so that $u<1$, note that the moment generating function may be re-written as
$$ \sum\limits_{r=1}^{\infty}\left(\dfrac{1}{1-u}\right)^r\left(1-e^{\lambda\left(u-1\right)}\right)^{r-1}e^{\lambda\left(u-1\right)}{}={}\sum\limits_{r=1}^{\infty}\sum\limits_{k=0}^{r-1}{r-1\choose k}\left(\dfrac{1}{1-u}\right)^r(-)^ke^{(k+1)\lambda(u-1)}\,. $$
A series representation may be obtained, therefore, if we can invert the "atomic" moment generating functions
$$ \left(\dfrac{1}{1-u}\right)^r e^{(k+1)\lambda(u-1)}\,. $$
Heuristically, we wish to solve an integral of the kind
$$ \int\limits_{-\infty}^{1}\left(\dfrac{1}{1-u}\right)^r e^{(k+1)\lambda(u-1)-xu}\,\,\mbox{d}u\,. $$
For $x<\lambda(k+1)$, the integral's solution has the form $$ (-\lambda)^{r}e^{-x}\left(\dfrac{x^{r-1}}{(r-1)!}\log(\lambda(k+1)-x){}+{}f_{r-1}(k)\right) $$
where $f_{r-1}(k)$ is a rational function involving terms of, at most, degree "$r-1$" in $k$.
(Note: the explicit solution can be obtained by integrating the expression $\dfrac{(-\lambda)^re^{-x}}{\lambda(k+1)-x}$, "$r$"-times, w.r.t "$k$". A justification of this follows by differentiating the integral we wish to solve. Note, also, that our "$u$" substitution above was merely to make this presentation look nicer and puts this solution "off" by a factor of $\lambda$: the actual solution follows analogous operations using the $t$ variable, instead).
Best Answer
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.