1
$\begingroup$

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?

$\endgroup$

2 Answers 2

1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Hi, do you mind elaborating a bit more on the recurrence? $\endgroup$
    – user107224
    Commented Feb 21, 2020 at 0:51
  • $\begingroup$ @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)$. $\endgroup$
    – Math1000
    Commented Feb 21, 2020 at 1:28
1
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .