8
$\begingroup$

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.

Thanks in advance,

  • 0
    @Vandermonde : I don't know, that's why I'm asking here, because if the teacher gives this question to students I believe it's because he can solve the problem himself, or at least he believes he can.2012-06-07

3 Answers 3

1

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

  • 0
    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!2012-06-12
1

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.

  • 0
    @Vandermonde : In other words, something that's more conclusive than saying "Well, I can do it in the small cases, but for large cases it just becomes complicated and I don't wanna go into it."2012-06-11
1

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.

  • 0
    But I believe you may not have taken a stochastic process class... have you? Anyway, this still deserves +1. =)2012-06-07