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
    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.2012-06-03
  • 5
    Clearly if $h_0$ and $j_0$ are of opposite parity, then the probability is $0$. Otherwise this seems pretty hard.2012-06-03
  • 0
    @Chris Eagle : Yes, quite right. It could be proved by noticing that if $x$ denotes the number of rooms between the two persons horizontally and $y$ denotes the number of rooms between them vertically, then $x+y$ does not change parity at each step, because it becomes $(x \pm 1) + (y \pm 1)$.2012-06-03
  • 0
    So for $H=J=2$, we have $$ \begin{cases} 6/7 & \text{if } h_0 = j_0 = 2, \\ 1 & \text{if } h_0 = j_0 = 1, \\ 0 & \text{if } h_0 \neq j_0. \end{cases} $$ Sigh.2012-06-03
  • 1
    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.2012-06-04
  • 0
    @PatrickDaSilva Maybe you should first tell us what the course *is* about.2012-06-04
  • 0
    @Phira : It's an introductory course to probability for engineers.2012-06-04
  • 2
    are you sure the students aren't supposed just to simulate it? this sounds crazy.2012-06-06
  • 0
    It also sounds crazy for me, and no, it was not about simulation. That's why I wondered if a solution was well-known. If not, then I'm gonna make sure this teacher knows.2012-06-06
  • 0
    I can't figure out why this only has 5 upvotes. This is a really cool question.2012-06-06
  • 0
    @unit3000-21 : Welcome to MSE! (Kidding.) You don't get upvotes because the question IS cool, but because people look at it and take the time to read it and upvote it. I'm certainly annoyed by this when I see cool questions getting something like 2-3 upvotes... and I definitely upvote them.2012-06-06
  • 1
    @PatrickDaSilva: Pro Tip: Ask cool questions about Tetris to get upvotes.2012-06-06
  • 0
    I doubt this is the case, but does the teacher have a short closed-form answer for arbitrary $H, J, h_0, j_0$?2012-06-06
  • 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