Conditioning on meeting on random walk?

Question

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?

Answer 1

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}$.

Answer 2

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$.