# Conditioning on meeting on random walk?

A one-dimensional path comprises seven steps, labelled $$-3$$ to $$3$$ (including $$0$$). Two people, A and B, are placed at positions $$-1$$ and $$1$$ respectively, and independently perform a random walk. What is the probability that A and B meet on the same step before either one reaches one end of the random walk?

My understanding is that since the random walk is one-dimensional, the probability that they must meet, ignoring the condition, is $$1$$ (this probability is not $$1$$ for transient walks which occur in $$D\geq3$$ dimensions). However, with the added condition, how does one draw the Markov chain, and how do the iterations work out? Is the way to finding the expected number of steps also equivalent?

I wrote some $$\texttt{R}$$ code to simulate this:

rm(list=ls())

N <- 100000
meets <- 0

for(i in 1:N) {
A <- -1
B <- 1

while(A>-3 && B < 3) {
A <- A + 2*(rbinom(1,1,1/2)-1/2)
B <- B + 2*(rbinom(1,1,1/2)-1/2)

if(A==B) {
meets <- meets + 1
break
}
}
}

print(meets/N)


which is giving a result of $$~0.46$$.

This agrees with the recurrence I derived: $$p = \frac14 +\frac12\left(\frac14+\frac14 p\right) + \left(\frac14\right)^2p$$ which yields $$p=\frac6{13}$$.

• Hi, do you mind elaborating a bit more on the recurrence? Commented Feb 21, 2020 at 0:51
• @user107224 It is obtained by first-step analysis. For example, the $\frac14$ term is the probability that $A_1=B_1=0$, the factor of $\frac12$ comes from the symmetry in $\{(A_1,B_1) = (-2,0)\}$ and $\{(A_1,B_1) = (0,2)\}$, the $\frac14$ term within the parentheses is the probability that $A_2=B_2$, the $\frac14p$ term within the parentheses is the contributing probability of returning to the original state, and the $\left(\frac14\right)^2p$ term is the contributing probability of the case when $(A_1,B_1)=(-2,2)$. Commented Feb 21, 2020 at 1:28

You could define states $$(i,j)$$, where $$i$$ denotes the location of $$A$$ and $$j$$ denotes the location of $$B$$. Then the initial state would be $$(-1,1)$$, and you want to find the probability that $$A$$ and $$B$$ reaches a state that looks like $$(k,k)$$ before reaching $$(i,3)$$, $$(i,-3)$$, $$(3,j)$$, or $$(-3,j)$$. You would then have a system of equations to solve. For example, let $$P_{i,j}$$ denotes that probability that $$A$$ and $$B$$ meet on the same step before reaching any end, then one of the equations would be $$P_{-1,1}=\frac{1}{4}P_{-2,0}+\frac{1}{4}P_{-2,2}+\frac{1}{4}+\frac{1}{4}P_{0,2}$$ where the third term is multiplied by $$1$$ since $$P_{0,0}=1$$. Similarly, $$P_{m,3}=P_{m,-3}=P_{3,m}=P_{-3,m}=0$$ for any $$m$$.

• I think this is correct, but by symmetry we can reduce things to a single equation. Commented Feb 20, 2020 at 4:26
• Yes, I agree! Your recurrence is way more elegant. Commented Feb 20, 2020 at 4:53