  Finding outlying elements in probability distributions can be a hard problem.
Taking a real example from Voting Rights Act enforcement, we consider the
problem of maximizing the number of simultaneous majority-minority districts in
a political districting plan. An unbiased random walk on districting plans is
unlikely to find plans that approach this maximum. A common search approach is
to use a biased random walk: preferentially select districting plans with more
majority-minority districts. Here, we present a third option, called short
bursts, in which an unbiased random walk is performed for a small number of
steps (called the burst length), then re-started from the most extreme plan
that was encountered in the last burst. We give empirical evidence that
short-burst runs outperform biased random walks for the problem of maximizing
the number of majority-minority districts, and that there are many values of
burst length for which we see this improvement. Abstracting from our use case,
we also consider short bursts where the underlying state space is a line with
various probability distributions, and then explore some features of more
complicated state spaces and how these impact the effectiveness of short
bursts.
