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.
Thanks in advance,
 A: 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.
A: 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.
