Grid Unlock, Part 2

How does our original experiment respond when applied to an infinitely large grid?

The original “Grid Unlock” post looked at how the string of stoplights that pedestrians must confront between streets affects the logic of their route-taking. In particular, we came up with these two distributions that govern how long a walk through an 8x8 grid will take, using the conditions that it takes one minute to walk a block and one minute to wait for a red light (given 50% chance of occurring at each intersection):

On the left is the distribution of durations if you refuse to turn until you’ve reached the grid’s corner and have no other choice (the “L”-route methodology, also fondly referred to as “dumb walks”). On the right is the distribution if you’re willing to turn 90 degrees every time you hit a red light, assuming you’re not already on the grid’s boundary.

The average dumb walk in this scenario takes 24 minutes, as you might gather from the symmetric distribution to the left. The distribution on the right is a little thornier — we fled to an entirely new post to grind out the probability function’s derivation — but ultimately the routes averaged to 17.57 minutes.

Walking somewhere in 17.57 minutes instead of 24 is tantamount to being 26.8% more efficient, as a quick calculation will demonstrate. This particular figure is only applicable to our original 8-by-8 set-up though. One wonders what kind of efficiency you can achieve in grids of different sizes, non-squares included…

Below is a graph that shows the efficiency gains of the smart walk methodology over the dumb walk methodology for grids of every size from 1x1 to 50x50. Theoretical values could have been used, since we are aware of the types of probability functions in play, but in the spirit of simulation, a thousand trials were actually run for each grid. (At such volume, the two approaches should be almost identical anyway).

There are a couple of cool things to note here. First of all, since we’re making a graph of these grids on an actual grid, the size and shape of each area can be recreated simply by extending its point to the y- and x- axes.

More important, of course, is the size of those bubbles, which indicate how much efficiency is gained at each grid size by using the smart walk approach. Some of the trends are:

1. The visualization is symmetric across the diagonal y=x. This seems pretty intuitive, since the act of walking in, say, a 25x20 grid should be the same as walking in its reflection, a 20x25 grid.
2. The bubbles are larger as grids become more square. This too seems logical, since the more lopsided a grid is, the more likely a walker will end up on an edge and lose the ability to turn away from a stoplight.
3. The bubbles are larger as grids get bigger. This would follow from the idea that the ways to avoid the edge within the rectangle increases faster than the edge itself.
4. There seems to be a clear limit to how efficient a grid can become, as the bubbles reach a certain size pretty early and only grow imperceptibly after that: the efficiency of the final 50x50 grid doesn’t seem that much greater than that of the 25x25 grid.

The fourth point introduces an intriguing follow-up question. Obviously we did not expect our smart walks to eventually achieve absolute efficiency, since cutting off 100% of the dumb walk duration would be equivalent to teleporting from one corner to the other. But that doesn’t mean the level to which the efficiency will converge is obvious.

So let’s figure it out! Below is a graph of the efficiency achieved by square grids starting at 1x1 and doubling in side-length (quadrupling in area) all the way up to 16,384x16,384:

Between the unit-sized grid and 256x256, the efficiency more than doubles. From there though, it slowly creeps toward 33.3… %, demarcated by the dotted line.

Remember that our efficiency is defined as the time cut off from the average dumb walk to the average smart walk, or, using the greek letter mu as the standard symbol for mean:

If this term converges to one third, the second term in the above expression must be converging to two thirds as our side length, s, grows infinitely large:

Remember that the dumb walk can be modeled quite simply like flipping coins, or as a set of Bernoulli trials with probability 1/2. As a result, the histogram of dumb walks will grow wider as our square grid swells toward infinity, but will always be symmetric and centered over the mean. Check out the histogram for every size square from 4x4 to 50x50 to see this truth in action:

If your eyes can move fast enough, you’ll notice that the center and mean of the graph always sprouts from a value equal to three times the side length (the dumb walk mean of the original 8x8 grid was, accordingly, 24 minutes).

Why? Well first, we know that each trial’s duration must be at least twice the length of its grid’s side, since no matter what stop lights you hit, you must complete the vertical and horizontal distance of the square grid just to get to the opposite corner. With each block taking a minute, your minimum duration is 2s for a grid with side length s.

Then we must add the expected value of those stoplights (Bernoulli trials). The expected value of any binomial distribution is equal to the probability of success (50% in our case) multiplied by the number of trials. Since there’s one stoplight for each block, we will have 2s trials, or a mean of s successes once multiplied by that 50%.

So that’s where we get 3s: the requisite 2s that’s baked into the act of walking added to the expected delay of s from the stoplights. Therefore we can replace the dumb walk mean in our limit:

Thus this limit can only exist if the smart walk mean converges to 2s while the dumb one is converging to 3s. So we can conclude that as our grid grows to infinity, the smart walk will average out to 2s:

But wait! We established that 2s is any trial’s minimum duration, no matter how many turns you take, since you must walk the 2s blocks at a minute per block. So if their average becomes the un-delayed minimum of a walk across the grid, the smart walks are actually gradually becoming perfectly efficient.

Taking the same growth from a 4x4 to a 50x50 grid used above, we can see that the smart walk distribution gets squeezed toward the minimum of 2s:

Interestingly, the actual minimum duration will never be the most probable value in any single experiment — notice how the far left bar is always about half the height of its neighbor — but the clustering of probability toward the next closest values assures that the minimum will still be approached.

You can twist your mind around to confirm the theoretical truth in this finding: if delays only occur on the border, and there is no border in an infinite grid, then naturally a walk through it would be unimpeded by stoplights.

More useful is the general idea that adoption of the smart walk becomes more valuable as the grid gets larger and larger, trending toward an absolute circumvention of those oppressive stoplights in the first place. Of course, the larger the original parameters, the more likely you’ll forego a long walk in favor of an Uber ride in the first place. However, if you do find yourself strolling along the sidewalk of an infinite city, remember not to let a red light stop you.

Thanks for reading the extension of the original Grid Unlock post. The idea is hardly tapped, so if you have any ideas about further experiments, let us know!

As always, all data and scripts available at https://github.com/PerplexCity/Grid-Unlock-2.

If you enjoy this type of content, please consider liking our Facebook page, following the Medium publication, or signing up for the newsletter.

See you next Thursday!