Probability of two people meeting in a given square grid.

Amy will walk south and east along the grid of streets shown. At the same time and at the same pace, Binh will walk north and west. The two people are walking in the same speed. What is the probability that they will meet?

I tried using Pascal’s triangle but I have no idea how to proceed.

Solutions Collecting From Web of "Probability of two people meeting in a given square grid."

Here’s one possible way that Amy and Binh can meet:

Together, the red and blue path make up a path from point $A$ to point $B$. There are $\binom{10}{5} = \frac{10!}{5!\,5!}$ such paths, because each path consists of $5$ vertical steps and $5$ horizontal steps, and there are $\binom{10}{5}$ ways to choose which steps are vertical.

There are $2^{5+5}$ ways to choose which $5$ steps Amy takes, and which $5$ steps Binh takes. Of them, $\binom{10}{5}$ result in them meeting. So the probability is $\binom{10}{5}/2^{10} = \frac{252}{1024} = \frac{63}{256}.$

It’s first worth noting that the number of ways to make $Y$ moves vertically and $X$ moves horizontally is $\binom{X+Y}{Y}$ (think of it like writing $X+Y$ move-slots and choosing $Y$ of them to be vertical movements, which means the rest are horizontal).

Amy and Binh must make $10$ moves each, which means they can only meet after
$5$ moves.

Assuming they meet: If Amy makes $Y$ moves down and $X$ moves to the right (cumulatively), Binh must make $X$ moves up and $Y$ moves to the left (cumulatively). There are $\binom{X+Y}{Y}^2 = \binom{5}{Y}^2$ ways for both people to arrive at such a meeting point.

This value is the numerator of our probability, and the denominator is the total number of possible paths after $5$ moves, which is $2^5$ per person. Over all $Y$, we have:

$$P = \sum_{Y=0}^{5} \frac{\binom{5}{Y}^2}{(2^5)^2} = \frac{63}{256}$$

Amy walks north and east while Bing walks south and west, so if they meet at all it will be on the diagonal which runs from northwest to southeast.

So consider the probability that they meet in the southwest corner. This requires Amy to walk 5 squares to the south while Bing walks five squares to the east. Assume that Amy walks south and east with equal probability of 1/2 at each step, and similarly Bing walks north and east with equal probability. Then Amy will go to that square with probability $(1/2)^5$, and so will Bing; they’ll meet at that square with probability $(1/32)^2 = 1/1024$.

You can do a similar computation for each square along the diagonal and add up the results.

If they meet at all, they do on the (rising) diagonal.
The number of “successfull” (pairs of) paths equals the number of paths from top left to bottom rigth, which is $10\choose 5$. The total number of (pairs) of paths is $2^{10}$.

Just a silly piece of code, approximating the answer…

#!/usr/bin/python3

from random import choice

A = [0, 0]
B = [5, 5]

N = 100000  # Number of simulations
n = 0       # Number of meetings
for _ in range(N) :
a = A[:]
b = B[:]
while (b != A) & (a != B) & (a != b) :
a[choice([i for (i, t) in enumerate(a) if (t != B[i])])] += 1
b[choice([j for (j, t) in enumerate(b) if (t != A[j])])] -= 1
n += (a == b)

print(n / N)