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 π 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<π For values of d just greater than π 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:
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:
I bet you didn't see Bob and Alice making it into this story, let alone their ownership of lawns. Ah grasshopper.... ## More Information## Related 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, Google+ or Linkedin.
## Comments
or email your comment to: comments@i-programmer.info |
|||

Last Updated ( Thursday, 23 November 2017 ) |