Mathematical theorem finds gerrymandering in PA congressional district maps

February 28, 2017, Carnegie Mellon University
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

T. Rex couldn't stick out its tongue, new research shows

June 20, 2018

Dinosaurs are often depicted as fierce creatures, baring their teeth, with tongues wildly stretching from their mouths like giant, deranged lizards. But new research reveals a major problem with this classic image: Dinosaurs ...


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.