 |
| illustration of grasshopper. [image: awesomedude.com] |
It’s a sunny afternoon in July and a grasshopper lands on your lawn. The lawn has an area of a square meter. The grasshopper lands at a random place and then jumps 30 centimeters. Which shape must the lawn have so that the grasshopper is most likely to land on the lawn again after jumping?
I know, sounds like one of these contrived but irrelevant math problems that no one cares about unless you can get famous solving it. But the answer to this question is more interesting than it seems. And it’s more about physics than it is about math or grasshoppers.
It turns out the optimal shape of the lawn greatly depends on how far the grasshopper jumps compared to the square root of the area. In my opening example this ratio would have been 0.3, in which case the optimal lawn-shape looks like an inkblot
 |
| From Figure 3 of arXiv:1705.07621 |
No, it’s not round! I learned this from a paper by Olga Goulko and Adrian Kent, which was published in the Proceedings of the Royal Society (arXiv version here). You can of course rotate the lawn around its center without changing the probability of the grasshopper landing on it again. So, the space of all solutions has the symmetry of a disk. But the individual solutions don’t – the symmetry is broken.
You might know Adrian Kent from his work on quantum foundations, so how come his sudden interest in landscaping? The reason is that problems similar to this appear in certain types of Bell-inequalities. These inequalities, which are commonly employed to identify truly quantum behavior, often end up being combinatorial problems on the unit sphere. I can just imagine the authors sitting in front of this inequality, thinking, damn, there must be a way to calculate this.
As so often, the problem isn’t mathematically difficult to state but dang hard to solve. Indeed, they haven’t been able to derive a solution. In their paper, the authors offer estimates and bounds, but no full solution. Instead what they did (you will love this) is to map the problem back to a physical system. This physical system they configure so that it will settle on the optimal solution (ie optimal lawn-shape) at zero temperature. Then they simulate this system on the computer.
Concretely, the simulate the lawn of fixed area by randomly scattering squares over a template space that is much larger than the lawn. They allow a certain interaction between the little pieces of lawn, and then they calculate the probability for the pieces to move, depending on whether or not such a move will improve the grasshopper’s chance to stay on the green. The lawn is allowed to temporarily go into a less optimal configuration so that it will not get stuck in a local minimum. In the computer simulation, the temperature is then gradually decreased, which means that the lawn freezes and thereby approaches its most optimal configuration.
In the video below you see examples for different values of d, which is the above mentioned ratio between the distance the grasshopper jumps and the square root of the lawn-area:
For very small d, the optimal lawn is almost a disc (not shown in the video). For increasingly larger d, it becomes a cogwheel, where the number of cogs depends on d. If d increases above approximately 0.56 (the inverse square root of π), the lawn starts falling apart into disconnected pieces. There is a transition range in which the lawn doesn’t seem to settle on any particular shape. Beyond 0.65, there comes a shape which they refer to as a “three-bladed fan”, and after that come stripes of varying lengths.
This is summarized in the figure below, where the red line is the probability of the grasshopper to stay on the lawn for the optimal shape:
 |
| Figure 12 of arXiv:1705.07621 |
The authors did a number of checks to make sure the results aren’t numerical artifacts. For example, they checked that the lawn’s shape doesn’t depend on using a square grid for the simulation. But, no, a hexagonal grid gives the same results. They told me by email they are looking into the question whether the limited resolution might hide that the lawn shapes are actually fractal, but there doesn’t seem to be any indication for that.
I find this a super-cute example for how much surprises seemingly dull and simple math problems can harbor!
As a bonus, you can get a brief explanation of the paper from the authors themselves in this brief video.
This is super neat.
ReplyDeleteThis is a great example of spontaneous symmetry breaking and how simple-sounding problems can give rise to complex structures! One could also look at this problem in different dimensions, for extra fun. Is the 1-dimensional case easy?
ReplyDeletePhysics embraces isotropy (re angular momentum conservation). Identical random direction events here lack it. There may be critical opalescence regimes wherein minima are only symmetric to themselves, suggesting (aargh!) second order phase transition. Fascinating.
ReplyDeleteJohn,
ReplyDeleteGreat question. I don't know, but maybe I can manage zero dimensions ;) Best,
B.
John again,
ReplyDeleteA friend suggests by email that for d=1 the optimal case would probably be a stretch of points with equal distance d, so that wherever you start you'll land on another point. It has some normalization problem of course, but I guess with a suitable epsilon-delta prescription one could fix that.
The paper has a section "Generalisations to other dimensions" on page 13 of the arXiv version. They write, "The problem generalises to R^n for any positive integer n. The case n = 1 is easy to solve. Consider the lawn defined by the segments [0,1/N], [d, d+1/N], ..., [(N−1)d, (N−1)d+1/N]. This has total length 1 and gives a probability (N−1)/N of the grasshopper remaining on the lawn. The sequence of such lawns for positive integer N thus gives us the supremum value 1 for the probability. This class of solutions, whose members are periodic over increasingly large ranges and have success probabilities increasingly close to 1, appears to have no analogy in higher dimensions, where the problem seems much harder. Intuitively, this appears to be because of a mismatch between the dimensionality of the jump and the space in which it takes place."
ReplyDelete... for d=1 the optimal case would probably be a stretch of points with equal distance d, so that wherever you start you'll land on another point
ReplyDeleteThe d=1 case won't depend on how the curve is embedded in space, as long as the convention is to measure lengths of the grasshopper jump along the curve.
How about the d=2 case? e.g., what happens on a sphere?
...the above mentioned ratio between the distance the grasshopper jumps and the square of the lawn-area... Square or square root? ...For very small d, the optimal lawn is almost spherical... Spherical or circular?
ReplyDeleteOn first blush, it seems obvious that controlling where the grasshopper lands is every bit as important as predicting it's subsequent jump.
ReplyDeleteSimple logic can narrow down the pattern almost as neatly as math.
It can also notice the loophole in the problem as literally stated.
That leads to the obvious solution of a cylinder.
The grasshopper "lands on a lawn" doesn't state where this grasshopper appears or how.
"Jumps 30cm" is really the only constraining factor here, so the surface must allow for a 30cm leap.
There is no mention of how "vertical/(lateral)" this "leap" must be.
Perhaps more importantly, there is no mention at all of the direction the grasshopper jumps. Not specified, even as random.
Therefore: Even eschewing some sort of dimensional warp or other silly factor being introduced, a simple 60cm long cylinder can easily also be 1 sq meter. This precludes ANY possibility of the grasshopper landing outside the declared surface (not including quantum tunneling).
Yes, that's cheating, but when it's well-considered I'm a fan.
~YiS
Amos,
ReplyDeleteI changed that to disk. Sorry, in my head a disk is a lower-dimensional sphere, hence the conflation.
Fun problem.
ReplyDeleteMy intuition suggests that for very large d, the solution should consist of very many small stripes, almost dots. In statphys problems there are generically no ordered phases in 1D, so the solution in 1D - many disconnected points - is the disordered phase. So when the disorder parameter grows large in higher dimensions, the solution should be similar to the 1D case.
Or perhaps the dots form some other 2D lattice with spacing d, not necessarily a linear one.
...the above mentioned ratio between the distance the grasshopper jumps and the square of the lawn-area... Square -> square root?
ReplyDeleteAmos,
ReplyDeleteThanks for pointing out, I've fixed that.
I tried to look at the problem using variational calculus with a contraint. Symbols are as in the paper unless I say here otherwise (some abbreviations due to the limitations of Unicode).
ReplyDeleteWe have the constraint
∫dx μ(x) = 1
(all my integrals are over ℝ², i.e. x, y, z are vectors) and want to maximize
p(μ)=∫dx ∫dy μ(x) μ(y) D(x-y)
where D is the ring-shaped delta function for the jump (or something more complicated, but I'll use D(x)=D(-x) later).
Thus the variation of S must vanish, with being a constant (the Lagrange multiplier) and
S=∫dx μ(x) { -λ + ∫dy [μ(y) D(x-y)]}
I get (unless i miscalculated)
0 = -λ + 2 ∫dx [μ(x) D(x-z)]
which essentially means that for all points z in the garden, the lawn-covered part of the circumference of the circle around z with radius d should have the same (i.e. independent of z) length. Since this contradicts the results of the paper (and can't be true for any reasonable lawn with compact support), some of my assumptions must be wrong, but I'd be interested to learn which one(s).
Hmm, if the jump is d = 30 centimeters and area is 1 sq meter, then a disk is the best lawn shape.
ReplyDeleteThe paper you cite shows Lemma 3.1:
The disc of area 1 (radius π−1/2) is not optimal for any d>π−1/2 ...where d is the distance jumped. That means the disk turns into a cog only for d > 56.4 cm
Ralf,
ReplyDeleteYou should think about the boundary conditions of your integrals.
Did they take the shape of the grasshopper into account or approximate it as a point mass? ;-)
ReplyDeleteNonlin: No, Sabine is right. You should also look at the results after lemma 3.1.
ReplyDeleteVincent: Results for non-pointlike grasshoppers are left for future work :-)