The grasshopper problem

A grasshopper lands at a random point on a lawn of area one. It then jumps a fixed distance in a random direction. What shape should the lawn be to maximize the chance that the grasshopper remains on the lawn after jumping?

This easily stated yet hard to solve mathematical problem has intriguing connections to quantum information and statistical physics. A generalized version on the sphere can provide insight into a new class of Bell inequalities, stronger than those presently provable. A discrete version can be modeled by a spin system, representing a new class of statistical models with fixed-range interactions, where the range can be large. They exhibit an array of unusual properties, such as complex disconnected “ground state” spin configurations for certain values of the jump.

Together with Adrian Kent we studied the grasshopper problem analytically and numerically. We showed that, perhaps surprisingly, there is no value of the jump length for which a round lawn is optimal. We used simulated annealing and parallel tempering algorithms to search for optimal solutions of the discrete spin model and identified several classes of solutions with different symmetry properties.

Check out the video abstract for our paper on YouTube:

In a recent follow-up paper in collaboration with Dmitry Chistikov and Mike Paterson we presented analytical results for the grasshopper problem on the circle and the sphere, which are directly relevant to Bell experiments and related cryptographic tests.

Our most recent paper sheds light on the origin of the symmetry breaking in the 2d grasshopper model with emphasis on the importance of dimensionality. We also present new numerical results for the 3d grasshopper problem.

Our work on the grasshopper problem has received a lot of press coverage, including:

Click on the Altmetric badges for more press coverage:

This work is funded by the NSF grant “CQIS: The Grasshopper Problem”
NSF logo