# 2 people on a random walk

Say you have a building of $HJ$ rooms, where $H$ and $J$ are positive integers (a rectangular grid of rooms of size $H$ times $J$). You can label the rooms $(h,j)$ where $1 \le h \le H$ and $1 \le j \le J$. One person enters the building of rooms at $(1,j_0)$ and the other person enters at $(h_0,1)$. After each minute, they choose randomly another room which must be adjacent to it ; i.e. if you are at coordinate $(h,j)$, you can go to $(h \pm 1, j)$ or to $(h, j \pm 1)$ with probability $1/4$, but the probability goes to $1/3$ if you are on a "side" (i.e. at coordinate $(1,j)$ you go to $(2,j)$ or $(1, j \pm 1)$ with probability $1/3$, and at coordinate $(1,1)$ you go to $(2,1)$ or $(1,2)$ with probability $1/2$). When the person that entered at $(1,j_0)$ reaches the room $(h_0,1)$, she "exits" the building using the entrance the other person used (this is not the case if the person at $(1,j_0)$ goes back to $(1,j_0)$). The same applies to the other person ; if person 2 goes back to the entrance of person 1 she exits the building.

The question is : What is the probability that the two persons are in the same room at some point during their walk?

My attempts : for $H=J=1$, the probability is $1$. For $H=2$ and $J=1$ (or the opposite) and $h_0 = H$, the probability is zero, since the two persons will just switch rooms and leave, without meeting (the hallways don't count :P). So it seems that it depends a lot on $H$ and $J$. Actually, if $H = 1$ and $J \ge 1$ then the probability is $1$ if $j_0$ is odd and $0$ if $j_0$ is even, because then the number of rooms between the two is always even, so for this number to reach $0$ we must have $j_0$ odd. Conversely, if $j_0$ is odd then since the two persons are forced to cross the same rooms they must meet at some point. The same goes by symmetry if $J = 1$.

Obviously it cannot only depend on the parity of $H$ and $J$ ; when $H$ and $J$ are not $1$ there always exists paths where the two persons meet and don't meet. I can do by hand the computations for $H=J=h_0=j_0=2$ but in the general case I have no idea how to tackle this problem. This is actually a question in my friend's homework, and there is nothing in the course about stochastic processes.

-
The computations by hand for $H=J=h_0=j_0=2$ gives a probability of $6/7$ that they meet in one room at least once before leaving. –  Patrick Da Silva Jun 3 '12 at 16:39
Clearly if $h_0$ and $j_0$ are of opposite parity, then the probability is $0$. Otherwise this seems pretty hard. –  Chris Eagle Jun 3 '12 at 16:43
So I was not wrong thinking this teacher was crazy after all... Hm. They can barely compute expectations and they give them this... poor students. –  Patrick Da Silva Jun 4 '12 at 0:22
are you sure the students aren't supposed just to simulate it? this sounds crazy. –  leonbloy Jun 6 '12 at 1:57
@PatrickDaSilva: Pro Tip: Ask cool questions about Tetris to get upvotes. –  Eric Naslund Jun 6 '12 at 16:54

Even though the following would be very difficult in practice, in principle it doesn't look too hard. I thought of the following:

Fix the lengths $H, J$ and the starting rooms $(1, j_0), (h_0, 1)$ for persons $1, 2$. Then at any given time the chance of meeting in the future depends on the current positions $(x_1, y_1)$ and $(x_2, y_2)$. Let's call it $P(x_1, y_1, x_2, y_2)$. (Technically there should be a way to specify that person $1$ or person $2$ has left the building, but it's clear $P(\text{outside}, x_2, y_2) = 0$ and so on.)

My idea is to write $P(x_1, y_1, x_2, y_2)$ in terms of $P(x_1 \pm 1, y_1 \pm 1, x_2 \pm 1, y_2 \pm 1)$ (where exactly one of $x_1, y_1$ changes and one of $x_2, y_2$ changes) for $1 \leq x_i \leq H$ and $1 \leq y_i \leq J$. In general there will be $4 \times 4 = 16$ such terms, but this approach gets ugly because of the building's walls and corners (in these special cases one of the factors becomes $3$ or $2$ accordingly). The entrances/exits are special too but easy to handle.

Now we set up the linear system. It's simple but tedious, so I'll use your toy example where $H = J = 2$ and $(1, j_0) = (1, 2)$ and $(h_0, 1) = (2, 1)$ (this may basically use the same computations you did, but I think you'll see how to generalise). In this case there are $3$ possible non-exit positions for each person and thus $9 - 2 = 7$ (for the $2$ non-exit rooms to meet in) equations and unknowns. Written out (and keeping in mind the order of the arguments in $P(x_1, y_1, x_2, y_2)$), we have:

$$P(1,1,1,1) = 1 \\ P(2,1,1,1) = 0 \text{ (exit)} \\ P(1,2,1,1) = \frac{1}{4}(P(2,2,2,1) + P(2,2,1,2) + P(1,1,2,1) + P(1,1,1,2)) \\ P(2,2,1,1) = \frac{1}{4}(P(1,2,2,1) + P(1,2,1,2) + P(2,1,2,1) + P(2,1,1,2)) \\ \\ P(1,1,1,2) = 0 \text{ (exit)} \\ P(2,1,1,2) = 0 \text{ (exit)} \\ P(1,2,1,2) = 1 \text{ (even if exit)} \\ P(2,2,1,2) = 0 \text{ (exit)} \\ \\ P(1,1,2,1) = \frac{1}{4}(P(2,1,1,1) + P(2,1,2,2) + P(1,2,1,1) + P(1,2,2,2)) \\ P(2,1,2,1) = 1 \text{ (even if exit)} \\ P(1,2,2,1) = \frac{1}{4}(P(2,2,1,1) + P(2,2,2,2) + P(1,1,1,1) + P(1,1,2,2)) \\ P(2,2,2,1) = \frac{1}{4}(P(1,2,1,1) + P(1,2,2,2) + P(2,1,1,1) + P(2,1,2,2)) \\ \\ P(1,1,2,2) = \frac{1}{4}(P(2,1,1,2) + P(2,1,2,1) + P(1,2,1,2) + P(1,2,2,1)) \\ P(2,1,2,2) = 0 \text{ (exit)} \\ P(1,2,2,2) = \frac{1}{4}(P(2,2,1,2) + P(2,2,2,1) + P(1,1,1,2) + P(1,1,2,1)) \\ P(2,2,2,2) = 1$$

After substituting all the obvious values into the seven non-trivial equations, we get:

$$P(1,2,1,1) = \frac{1}{4}(P(2,2,2,1) + P(1,1,2,1)) \\ P(2,2,1,1) = \frac{1}{4}(2 + P(1,2,2,1)) \\ \\ P(1,1,2,1) = \frac{1}{4}(P(1,2,1,1) + P(1,2,2,2)) \\ P(1,2,2,1) = \frac{1}{4}(2 + P(2,2,1,1) + P(1,1,2,2)) \\ P(2,2,2,1) = \frac{1}{4}(P(1,2,1,1) + P(1,2,2,2)) \\ \\ P(1,1,2,2) = \frac{1}{4}(2 + P(1,2,2,1)) \\ P(1,2,2,2) = \frac{1}{4}(P(2,2,2,1) + P(1,1,2,1))$$

For the probabilities in this order, this system has the unique solution $\frac{1}{7}(0,5,0,6,0,5,0)$, and the value $P(1, j_0, h_0, 1) = P(1,2,2,1) = \frac{6}{7}$ is the answer you obtained earlier. For larger buildings, the system will just be bigger.

(Looking at the solution, we evidently could have eliminated about half of the equations using parity considerations: at any time, $x_1 + y_1 + x_2 + y_2 \equiv 1 + j_0 + h_0 + 1 \equiv j_0 + h_0 \text{ (mod } 2)$. It might help a little in solving the system.)

Of course, this wouldn't be as elegant as desired, but that's all I know. Maybe they intended for your friend to represent things using $H \times J$ matrices. (I'd be interested to know their answer, for sure.)

-
FYI, that is precisely the point of the stochastic process method ; you just outlined it by hand. Usually one determines the matrix of the process, i.e. the one that has $p(i,j)$ as the $p_{ij}^{\text{th}}$ coefficient for the probability of going from state $i$ to state $j$. From this matrix one can deduce many things, and the above can also be done. I haven't tried though ; my stochastic process is rusty. But I appreciate your work for sure! Confirming my $6/7$ is always comforting. +1 –  Patrick Da Silva Jun 7 '12 at 12:40
I'm sorry this wasn't too informative; in fact I'm not surprised you tried something like it. I didn't know this was the stochastic process method you were referring to. –  Vandermonde Jun 7 '12 at 16:56
I still appreciate the fact that people look at my question and try to answer for it. I appreciate your work, as I mentioned ; you have nothing to be sorry about. You can't know that you don't know unless you try to ask! –  Patrick Da Silva Jun 7 '12 at 17:19
I need to attribute the bounty to someone if I don't want to waste the reputation... you don't have much reputation compared to the three others, and I liked your answer. The teacher confirmed to me that he expected a numerical solution and that he didn't expect many students to answer it because of that ; so I'll give you the bounty. Grats! –  Patrick Da Silva Jun 12 '12 at 6:44

With the help of a GP program, I obtained the probability when $J=2$ and $j_0=h_0=2$, for $H$ between $2$ and $10$. The first values are :

$$p_2=\frac{6}{7} (\ {\rm this \ was \ already \ mentioned \ by \ several \ other \ people \ here })$$

$$p_3=\frac{58925}{79311}$$

$$p_4=\frac{667042459265}{982993299201}$$

$$p_5=\frac{1195623797792938901759}{1790700722288716572625}$$

The fractions get more and more complicated, and I see no point in reproducing them all here. It seems the $(p_H)$ decrease and converge to a limit around $0.663$.

Some programming details : by the theory of stochastic processes, all is reduced to the computation of the kernel of a $(JH)^2 \times (JH)^2$ matrix (and additionnally $J=2$ in the values above). For the longest computation I have made, for $p_{10}$, we have a $400 \times 400$ matrix and it takes GP two minutes to compute everything.

-
The students don't know stochastic processes. I know them too. It's good for me that you did the work though ; I didn't want to do it at first because I was lazy.. and I only found the $6/7$ in your numbers ; the fact that your numbers increase in a very "random" way (i.e. I see no pattern in the numbers) is a good indicator that our intuition that as the numbers get larger, the guess is harder to make. Thanks a lot for this. –  Patrick Da Silva Jun 7 '12 at 12:32
If you can just make your computer run for a few more tests I'd like that ; as the number of rooms grow, I expected the probability to converge to something smaller than $2/3$... say maybe zero (the probability is never zero, but it gets arbitrarily small) if the grid is large enough and the two guys don't start off so close. –  Patrick Da Silva Jun 7 '12 at 12:35
And what is GP? I don't know. And.. +1 :P –  Patrick Da Silva Jun 7 '12 at 12:37
@PatrickDaSilva : actually, the "random" nature of this sequence made me think there is no simple closed formula, that the teacher was wrong, and discouraged me from using more my computer resources on this problem. I can send the GP code though, and you can re-use it on larger values if you like. –  Ewan Delanoy Jun 7 '12 at 14:31
@PatrickDaSilva : you can either download GP or use it online, at sagenb.org –  Ewan Delanoy Jun 7 '12 at 14:35

For a particular $H$ and $J$, there is a standard "brute force" method to compute this sort of probability that doesn't require any cleverness. First off, count how many configurations there are. One method is to say that a configuration is of one of three types:

• The statement that the first person is in room $(a,b)$ and the second person is in room $(c,d)$, and they haven't met
• The statement that the two people have met
• The statement that one person has exited the building

There are ways to use fewer configurations, but I'm aiming to explain the idea in the simplest manner. Also, fewer might not be better.

Suppose there are $M$ configurations in all. We can write down an $M \times M$ matrix $A$ with the property that the $m$-th component of the vector $A \mathbf{\hat{e}}_n$ is the probability that the configuration $n$ will transition to the configuration $m$, where $\mathbf{\hat{e}}_n$ is a standard basis vector.

With this matrix $A$, it is easy to write down various probabilities. For example, if configuration #1 is the starting confiruation and configuration #M is the statement that the two people have met, then $\mathbf{\hat{e}}_M^t A^k \mathbf{\hat{e}}_1$ is the probability that the two people meet sometime within $k$ minutes of starting. Note that by diagonalizing $A$, you can get a 'direct' formula for this probability.

To find the probability they meet over all time, you can take the limit as $k \to \infty$. In fact, the limit $\lim_{k \to \infty} A^k$ should exist, which I will call $A^\infty$. The vector $A^\infty \mathbf{\hat{e}}_1$ should actually be the 'steady state' distribution. Given the particular problem, it ought to have only two nonzero components, corresponding to the possibilities that they've met or that one has exited the building.

-
This is even more precisely a stochastic process method. As I said to the two other answerers, you are not teaching me anything new, this technique is known ; if you could guess the formula for the matrix in general, diagonalize it, and then find the formula for the probability as a function of $(1,j_0)$, $(h_0,1)$, $H$ and $J$ then perhaps it is worth $100$ rep, but as it is now I don't have much faith in going in that direction ; plus, the teacher in the course only gives probability, not stochastic processes ; he doesn't expect students to come up with a matrix to diagonalize. –  Patrick Da Silva Jun 7 '12 at 12:45
But I believe you may not have taken a stochastic process class... have you? Anyway, this still deserves +1. =) –  Patrick Da Silva Jun 7 '12 at 12:45