Twisty lattice paths, all alike

I haven’t posted a puzzle in quite a while, so…

Every morning, I drive from my home at 1st and A to my work at 9th and J (8 blocks east and 9 blocks north), always heading either east or north so as not to backtrack… but I choose a random route each time, with all routes being equally likely.  How many turns should I expect to make?

And a follow-up: on busy city streets, left turns are typically much more time-consuming than right turns.  On average, how many left turns should I expect to make?

The first problem is presented in Zucker’s paper referenced below, and solved using induction on a couple of recurrence relations.  But it seems to me there is a much simpler solution, that more directly addresses the follow-up as well.

Reference:

  • Zucker, M., Lattice Paths and Harmonic Means, The College Mathematics Journal, 47(2) March 2016, p. 121-124 [JSTOR]

 

This entry was posted in Uncategorized. Bookmark the permalink.

2 Responses to Twisty lattice paths, all alike

  1. I didn’t look at the paper yet (behind a paywall), but I did try my usual, dumb Monte Carlo approach to estimate the answer. However, while I was writing the program and thinking about how to optimize it as a lookup table, a non-closed form, exact answer occurred to me. It’s the same sort of thing that happens in optimizing the Monte Carlo method for the Monte Hall problem. The problem falls apart and the solution becomes obvious without needing to estimate.

    Every route is a series of 17 binary decisions: north or east. A random route is generated by producing a random 17-bit integer. However, if the route runs to the “edge” of the map, the remaining bits are all effectively cleared or set depending on which edge it hit. I figured I could speed up the computation, and even do a parallel lookup in SIMD, by pre-computing the number of turns for each of the 2^17 integers as a table. I also realized I could do a little better and trim it to a tidy 16 bits since the last turn is never actually a decision.

    Then it hit me: if all I’m doing it sampling uniformly from this table, I don’t need Monte Carlo at all. I can just compute the exact expected value directly from the table. I was briefly concerned I was oversampling for certain routes. For example, if a zero indicates east, all integers beginning with 8 zeroes are the exact same route, but will appear many times in the table. Shouldn’t that only count as one? No, and I think this is the tricky part. Take an extreme example, where work is 1 east and 100 north. One of the possible paths is 1 east, followed by 100 north. It’s only 1 route of a possible 101 routes, but that single path is taken 50% of the time due to that very first decision, so it covers 50% of the table.

    That gives me 480429/65536 (~7.33) expected turns and 26333/8192 (~3.21) expected left turns.

    • (Yeah, I try to link to arXiv or other author pre-prints when I can, but I couldn’t find one in this case.) This is great; I love how there is almost always more buried in a problem, even one that at first glance might seem relatively straightforward.

      You have described another equally interesting interpretation of this problem– different from the one I intended :). That is, we can imagine (at least) a couple of reasonable models for picking a random route from (0,0) to (a,b)=(8,9). One is as you describe, and in hindsight is arguably more “realistic” (but slightly more complex to tackle): flipping a coin at each intersection, going east for heads, north for tails… but ignoring the coin if “following” it would increase the overall length of the route.

      As you point out, we can compute the corresponding expected values exactly by enumerating the 2^(a+b) possible sequences of coin flips. In fact, we can improve on this– see this gist for an example calculating the expected number of left turns– but as you can see from the code, it’s slightly tricky to do so, because of the edge cases of “walking off the map.”

      (Aside: I don’t get quite the same answers as you, and am not sure where the discrepancy lies. For the expected number of left turns, I get 486864/131072=30429/8192, or about 3.71448, and am unable to tweak assumptions to get your numbers. Maybe a smaller case will help us resolve? For example, for (a=1,b), I get an expected number of left turns equal to 1-1/2^b.)

      Another random model, and the one intended for this problem, is that “all routes are equally likely.” That is, before even getting in the car, we select our entire route from all distinct possibilities. In the context of the integer/bit-vector representation that you describe, we are selecting uniformly at random from only those integers with exactly b bits set to 1. Much of the subsequent analysis approach still applies… but the answer(s) are much “nicer.”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s