Asymptotic Chance Encounters

You and your friend stand at opposite corners of an $n \times n$ grid. You are at the bottom left; your friend is at the top right.

Every second, you will randomly (according to a coin flip) move either right one space or up one space (though if you can’t move in one of these directions because you are at that edge of the grid then you can only proceed in the other). At the same time, your friend will randomly move either left one space or down one space.

Problem. What is the probability that you and your friend will meet at some point in time?

Let’s solve an easier problem together and then you can do the harder one by yourself.

Let’s get rid of this pesky $n$ . Specifically, let’s set $n = 4$ and consider the problem for a $4 \times 4$ grid.

I’ll draw a pretty picture so that you dont have to:

Here’s an example of the paths that you and your friend might take to get to the opposite corner.

Note that in the above example, you and your friend do not meet! Your paths intersect but at different points in time.

There are, in fact, only five points that you can meet your friend on your way to the opposite corner. As the full walk must be eight lengths long, you can only meet your friend at grid points that are exactly four lengths away from where you both start.

We want to work out the probability that you will meet your friend at some point in your walk. This is equivalent to the probability that after four steps your friend is at the same point as you.

We will break this down into steps. First, for each of the possible meeting points, what is the probability that you will end up at each? Let’s label them:

Working out these probabilities is quite doable. Let’s say that you move Up on Heads and Right on Tails. Then the only way to get to point A is with HHHH. There is a $\frac{1}{16}$ chance that this happens.

We can argue by symmetry that the probability of getting to E is the same as getting to point A. This is because one needs the complementary sequence TTTT.

What is the probability that we get to point B? In this case, the possible coin flip sequences are HHHT, HHTH, HTHH, THHH. There are four of these, each with a $\frac{1}{16}$ chance of happening. Therefore, there is a $\frac{4}{16}$ probability that we meet at B (and, by symmetry, the same probability must hold for D).

Finally, we need to work out C. This is pretty easy. The probabilities for each of the five paths must sum to 1 (as we must be at one of those points after four lengths!). We know the probabilities of arriving at A, B, D and E and so a bit of arithmetic gets us that the probability of arriving at C is $\frac{6}{16}$ .

Alternatively, any sequence consisting of two Heads and two Tails will get you to C. There are 6 possible sequences (from 4 choose 2) out of a total of 16 sequences.

Now, to start, let’s work out the probability that you and your friend meet at A. This is actually really easy now, due to the fact that we know the probability that you will get to A is $\frac{1}{16}$ . Likewise, the probability that your friend will get to A is also $\frac{1}{16}$ . As your path is independent to your friend’s, the probability that you will meet at A is $\frac{1}{16} \times \frac{1}{16} = \frac{1}{256}$ .

We have to do this for each path and then add them all together. So, all we really have to do is square each probability and then sum. The calculation we are doing looks like this:

Firstly, this is equal to $70/256$ which is a probability of about 27%. So we have solved the easier problem we set out to solve.

Secondly, and importantly, it is fairly straightforward to generalise all of the above from a $4 \times 4$ grid to an $n \times n$ grid. Look at the numbers in the above sum. Can you see the patterns?

Once you have done the generalising, you will find an application of Stirling’s formula will give you a really nice little asymptotic solution for the $n \times n$ case!