Mathematical theorem finds gerrymandering in PA congressional district maps

February 28, 2017
The current congressional districting of the state of Pennsylvania. Credit: Carnegie Mellon University

Pennsylvania's congressional district maps are almost certainly the result of gerrymandering according to an analysis based on a new mathematical theorem on bias in Markov Chains developed by Carnegie Mellon University and University of Pittsburgh mathematicians. Their findings are published in the Feb. 28 online early edition of the Proceedings of the National Academy of Sciences (PNAS).

Markov chains are algorithms which can generate a random object by starting from a fixed object and evolving in a stepwise fashion, making small random changes at each step. Markov chains have numerous applications, and are used to model things like thermodynamic processes, chemical reactions, economic and financial phenomena, protein folding and DNA sequences.

To evaluate gerrymandering of congressional districts, a Markov Chain can, in principle, be used to compare the characteristics of the current districting map with a typical districting of the same state by generating truly random districtings as points of comparison.

However, one of the limitations of Markov chains is that there is often no way to determine how long the chains need to run in order to achieve a truly random sample. Without knowing the upper limit, researchers must assume that they've run the algorithm long enough for their resulting assumptions to be valid.

In the PNAS paper, University of Pittsburgh Assistant Professor of Computational and Systems Biology Maria Chikina and Carnegie Mellon Professor of Mathematical Sciences Alan Frieze and Assistant Professor of Mathematical Sciences Wesley Pegden prove a theorem that can use a Markov Chain to show that a sample is nonrandom, without generating random samples from the Markov Chain itself. This allows researchers to use the Markov chain to rigorously demonstrate bias in the congressional districting maps of the state of Pennsylvania without having to make unproven assumptions on the time required to generate samples from the Markov Chain.

Districting produced after 2^40 random steps of the Markov chain. Credit: Carnegie Mellon University

The researchers began with a current map of Pennsylvania's congressional districts, and applied a Markov chain that incorporated geometric constraints on districts that would be used to create random districting maps. Those factors included ensuring roughly equal populations in each district, border continuity, and constraining the ratio of perimeter to area.

The researchers ran the , which changed the map in random steps. Statistical properties of the map were found to change rapidly with small random changes to the initial map, which, according to their theorem, would be extremely unlikely to happen by chance.

"There is no way that this map could have been produced by an unbiased process," said Pegden.

While the new method doesn't provide a new tool for drawing congressional district maps, it does provide a rigorous test to detect that existing maps were created in a biased fashion, and researchers may find applications in the many other fields where Markov Chains are used.

Explore further: Mathematical model developed 100 years ago used to improve weather and climate models

More information: Assessing significance in a Markov chain without mixing, PNAS, , DOI: 10.1073/pnas.1617540114

Related Stories

The ABC's of animal speech: Not so random after all

August 20, 2014

The calls of many animals, from whales to wolves, might contain more language-like structure than previously thought, according to study that raises new questions about the evolutionary origins of human language.

Can math solve the congressional districting problem?

August 4, 2015

Lost amidst the frenzy of coverage of the Supreme Court's rulings about the Affordable Care Act and same-sex marriage was a case involving the constitutionality of an independent commission to draw congressional districts ...

Recommended for you

Metacognition training boosts gen chem exam scores

October 20, 2017

It's a lesson in scholastic humility: You waltz into an exam, confident that you've got a good enough grip on the class material to swing an 80 percent or so, maybe a 90 if some of the questions go your way.

Scientists see order in complex patterns of river deltas

October 19, 2017

River deltas, with their intricate networks of waterways, coastal barrier islands, wetlands and estuaries, often appear to have been formed by random processes, but scientists at the University of California, Irvine and other ...

Six degrees of separation: Why it is a small world after all

October 19, 2017

It's a small world after all - and now science has explained why. A study conducted by the University of Leicester and KU Leuven, Belgium, examined how small worlds emerge spontaneously in all kinds of networks, including ...

Ancient DNA offers new view on saber-toothed cats' past

October 19, 2017

Researchers who've analyzed the complete mitochondrial genomes from ancient samples representing two species of saber-toothed cats have a new take on the animals' history over the last 50,000 years. The data suggest that ...


Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.