| 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.
For values of d just greater than π-1/2 the shape changes from a cog to something disconnected and complicated:
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:
For d>0.87 the shape changes to a fan:
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 InformationRelated ArticlesLZ Compression And The One-Bit Catastrophe Best Laid Plans of Lions and Men How Not To Shuffle - The Knuth Fisher-Yates Algorithm What's a Sample of Size One Worth?
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, Facebook or Linkedin.
Comments
or email your comment to: comments@i-programmer.info |
|||
| Last Updated ( Thursday, 23 November 2017 ) |
