The Grasshopper Problem
The Grasshopper Problem
Written by Mike James   
Wednesday, 22 November 2017

I am always amazed by the subtlety of probability. You can cite the Monty Hall problem or The Fisher Yates Shuffle, but what about the Grasshopper problem? Easy to state, but very difficult to solve and slightly unbelievable.

A new paper from Olga Goulko of the  University of Massachusetts and Adrian Kent of the University of Cambridge produces some surprising results from a very simple problem.

The problem is linked to questions of quantum mechanics, specifically Bell's inequalities, but a slightly simplified version is easy to state and just as suprising:

"You are given a bag of grass seed from which you can grow a lawn of any shape (not necessarily connected) with unit area on a planar surface. A grasshopper lands at a random point on your lawn, then jumps a given distance d in a random direction. What lawn shape should you choose to maximise the probability that the grasshopper remains on your lawn after jumping?" 
 

Jumping in a random direction - surely that means all directions are the same and so the solution must be just a disk? However, the first proof in the paper dismisses this intuition:

The disc of area 1 (radius π-1/2) is not optimal for any d>π-1/2.

So, if the jump distance is greater than the radius a disk, is not the answer to the question. The reason seems to be the possiblity that the lawn isn't simply connected. The proof relies on showing that removing a small disk from the center of the unit disk increases the probability that the grasshopper will land on the lawn. Thus there is at least one hole in the lawn shape that is better than the disk.

Note this proof doesn't tell us what that better shape is. It just provides an area that we can move to improve the probability - it doesn't say where the area should be deployed.

The result is later generalized to all values of d > 0 - so your intuition is completely wrong. 

The suggestion is that "knobbly" shapes are would do better, but the problem is to hard to solve exactly. Instead the researchers recast the problem as a spin model, a discrete approximation to the continuous grasshopper problem - a discrete grasshopper problem?

Spin models are often studied in physics using simulation and this is what happened next. The solution to the original problem corresponds to the ground state, i.e. the lowest energy state, of the spin system. This can be found using simulated annealing, which models the system at a given "temperature". The temperature controls how much random movement there is in the system and running the simulation for a long time lets it settle to equilibrium at that temperature. Slowly lowering the temperature lets the system settle into the lowest energy state with a high probability. This is, of course a simulation of what happens when you allow something hot to cool down - hence simulated annealing.

You can see the simulation in action in the following video:

 

For d<π-1/2 the best configurations were simply connected "cogwheels". As d decreases the number of cogs decreases.

cogs

For values of d just greater than π-1/2 the shape changes from a cog to  something disconnected and complicated:

critical

This seems to be a critical or phase change region for the problem.

For values of 0.65<d<0.87 the shape changes to another fairly stable three fan shape:

grassfan

For d>0.87 the shape changes to a fan:

grassstripe

So all fascinating and counter intuitive, but are there any applications?

The paper suggests quite a few, but the one that attracted my attention is:

Our numerical solutions strikingly illustrate the emergence of structures with discrete symmetries from an isotropic problem with continuous rotational symmetry. They also bear at least a passing resemblance to patterns seen elsewhere in nature, including the contours of flowers, the patterns seen on some seashells and the stripes on some animals.

Turing’s well-known theory of morphogenesis hypothesises that many such natural patterns arise as solutions to reaction-diffusion equations. This possibility has been demonstrated experimentally. Our results suggest that a rich variety of pattern formation can also a rise in systems with effectively fixed-range interactions, including interactions associated with the sort of catalytic reaction described above. It may be worth looking for explanations of this type in any context where highly regular patterns naturally arise and are not otherwise easily explained.

At the end of the paper the subject returns to quantum mechanics and Bell's inequalities, but I cannot stop without quoting the delightful final paragraph:

For projective measurements on pairs of qubits, such algorithms can be thought of as generalised grasshopper models, in which Alice has a single lawn, Bob has a set of available lawns, and Alice chooses which of Bob’s lawns is used in each given run.

I bet you didn't see Bob and Alice making it into this story, let alone their ownership of lawns.

Ah grasshopper....

More Information

The grasshopper problem

Related Articles

LZ Compression And The One-Bit Catastrophe

Best Laid Plans of Lions and Men

Irrational Guards

Cannibal Animal Games

How Not To Shuffle - The Knuth Fisher-Yates Algorithm

The Monty Hall Problem

What's a Sample of Size One Worth?       

The Monte Carlo Method        

Inside Random Numbers       

 

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on, Twitter, FacebookGoogle+ or Linkedin.

 

 

Banner


GitHub Adds Security Alerts
23/11/2017

Using its new dependency graph feature, GitHub is now able to warn you of potential security vulnerabilities in code that a project relies on and to suggest known fixes.



DeepMind's AlphaZero Triumphs At Chess
07/12/2017

DeepMind's latest program, AlphaZero, has used reinforcement learning from playing against itself to master the game of chess. Given the important role that chess has occupied in computer science, thi [ ... ]


More News

 

 
 

 

blog comments powered by Disqus

Last Updated ( Thursday, 23 November 2017 )
 
 

   
Banner
RSS feed of news items only
I Programmer News
Copyright © 2017 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.