Delirious ducks

This week’s Riddler Classic is about random walks on a lattice:

Two delirious ducks are having a difficult time finding each other in their pond. The pond happens to contain a 3×3 grid of rocks.

Every minute, each duck randomly swims, independently of the other duck, from one rock to a neighboring rock in the 3×3 grid — up, down, left or right, but not diagonally. So if a duck is at the middle rock, it will next swim to one of the four side rocks with probability 1/4. From a side rock, it will swim to one of the two adjacent corner rocks or back to the middle rock, each with probability 1/3. And from a corner rock, it will swim to one of the two adjacent side rocks with probability 1/2.

If the ducks both start at the middle rock, then on average, how long will it take until they’re at the same rock again? (Of course, there’s a 1/4 chance that they’ll swim in the same direction after the first minute, in which case it would only take one minute for them to be at the same rock again. But it could take much longer, if they happen to keep missing each other.)

Extra credit: What if there are three or more ducks? If they all start in the middle rock, on average, how long will it take until they are all at the same rock again?

Here is my solution:
[Show Solution]

4 thoughts on “Delirious ducks”

  1. Hi Laurent,
    Very nice. Your approach is much more elegant than what I did.
    I approached it a little differently, building a Fokker-Planck equation to evolve from a starting configuration through the probabilities of each successive configuration, removing cases where the ducks join up again, and I get the same answers.

    Regarding an approximate answer:
    For large numbers of ducks, you might imagine that, before a move, the ducks are “randomly” distributed between the points of a given parity, and then compute the chance that they all converge to the same spot.
    When the ducks are on the 4 edge-states (2,4,6,8 in your notation), each duck has a 1/3 chance to go to the middle (5) and a 1/6 chance each to go to a given corner (1,3,7,9). Therefore the chance that they all go to the middle is 1/3^N and the chance that they all go to the same corner is 4/6^N (4 for the 4 corners).
    When the ducks are on an odd state, each duck has a 1/4 chance to go to a given edge, so there is a 1/4^N chance that they all go to (2) and the same for each of (4,6,8) for a total of 4/4^N chance that they will converge on the next move.
    Averaging over these two cases, the chance of “finishing” on a given move is
    ( 1/3^N + 4/6^N + 4/4^N)/2
    and the average number of moves is
    2/( 1/3^N + 4/6^N + 4/4^N)
    which is:
    4.235 for N=2
    16.94 for N=3
    64.40 for N=4
    234.31 for N=5
    821.68 for N=6
    2794.56 for N=7
    etc (asymptotically, adding a duck lengthens the process by a factor of 3)
    Of course this is not exact: the location of each duck is correlated and not completely random. But for large N the correlation is very small, and the approximation gets better. I was surprised how well it already worked for N=2…

  2. I did exactly what you did, Guy. At side-to-non-side transitions, there’s always a 1/3^N chance of all ducks meeting in the center, so the expected first meeting of all ducks in the center is 2*3^N. For large N, all ducks meeting elsewhere becomes vanishingly improbable compared to meeting in the center, so that seems to be the limiting expectation, and it’s a good approximation already for N > 10. (See plot at link.)

  3. Glad to see some new postings — I almost thought I saw some Julia code in here 😉

    Also, good catch on the issues with periodic behavior. It’s a nuisance, and I’d be inclined to tweak the problem to be a lazy chain ($\delta \in (0,1)$ so $P’:= \delta I + (1-\delta)P$) or possibly look at an ensemble average. When I first read the problem I was hoping for a Kronecker product structure, but I thought it was too good to be true.

    A couple other things — this is a *reversible* markov chain and in this particular case the steady probability vector entry for a given state is proportional to the number of connections it has — which is $\{\frac{1}{12}, \frac{1}{8}, \frac{1}{6}\}$ for the single duck case.

    One final thing, since $\pi_i = \frac{1}{\bar{X_i}}$ i.e. the perron / steady state vector has probability given by the inverse of the expected time to return to state i given a start in state i, *and* the Kronecker product has nice properties with respect to eigenvalues and eigenvectors we can say that in the $n$ duck case, if they all start in the same location, the expected time until they all meet again at that same location is $\{12^n, 8^n, 6^n\}$. I suppose this gives a very crude upper bound on expected time until rendez-vous for the more general case being contemplated in this Riddler (i.e. meeting in some arbitrary box)

    1. This problem is conceptually nice when we use $P’:= \delta I + (1-\delta)P$ for any $\delta \in (0,1)$. But the original problem with $\delta := 0$ has quite a bit of odd behavior. Algebraically speaking the oddities come from having an eigenvalue of +1 and -1, so when we do a kron product we have maximal eigenvalues given by $1\cdot 1=1$ and $-1\cdot-1=1$ and when we kron prod 3 matrices we have $1\cdot 1 \cdot 1 =1$ but also $1 \cdot -1 \cdot -1 = 1$, as well as $-1 \cdot 1 \cdot -1 = 1$, and $-1 \cdot -1 \cdot 1 = 1$, and so on for higher degrees of kronecker products. Having $k$ copies of the eigenvalue 1 tells us there are k disjoint, recurrent, graphs in here (perron frobenius). Each disjoint graph has its own real non-negative eigenvector that is disjoint (orthogonal) to the other eigenvectors associated with other graphs/ recurrent classes. So when we make some state (say the ‘middle’ one) an absorbing state, this doesn’t ‘hit’ k-1 of the eigenvectors with eigenvalue 1. This problem also makes a very good illustration of how the pseudo inverse is not in general continuous, but the actual inverse (when $\delta \in (0,1)$) is continuous. The non-lazy chain (i.e. stated problem) really is pecuiliar due to what happens when we mix periodicity (more than one eigenvalue with modulus one for a communicating class) and kronecker products.

Leave a Reply

Your email address will not be published. Required fields are marked *