Tot voor kort hadden gerrymandered districten de neiging om uit te steken, herkenbaar aan hun verwrongen ranken. Dit is niet langer het geval. "Met moderne technologie kun je behoorlijk effectief gerrymanderen zonder je vormen heel raar te maken," zei Bet Malmskog, een wiskundige aan het Colorado College. Dit maakt het veel moeilijker om erachter te komen of een kaart oneerlijk is gemanipuleerd.

Zonder het veelbetekenende teken van een duidelijk misvormde wijk om voorbij te gaan, hebben wiskundigen steeds krachtigere statistische methoden ontwikkeld om gerrymanders te vinden. Deze werken door een kaart te vergelijken met een ensemble van duizenden of miljoenen mogelijke kaarten. Als de kaart resulteert in merkbaar meer zetels voor Democraten of Republikeinen dan zou worden verwacht van een gemiddelde kaart, is dit een teken dat er iets vreemds heeft plaatsgevonden.

Maar het maken van dergelijke ensembles is lastiger dan het klinkt, omdat het niet haalbaar is om alle mogelijke kaarten te overwegen - er zijn simpelweg te veel combinaties voor een supercomputer om te tellen. Een aantal recente wiskundige vorderingen suggereren manieren om door deze onmogelijk grote ruimte van mogelijke simulaties te navigeren, waardoor wiskundigen een betrouwbare manier krijgen om eerlijk van oneerlijk te onderscheiden.

Zoals zoveel dingen die verband houden met redistricting, eindigt hun werk voor de rechtbank. In de afgelopen vijf jaar zijn simulaties geaccepteerd als bewijsmateriaal in rechtszaken in Missouri, North Carolina, Ohio en Michigan. En zij zijn de centrale onderwerpen van debat in Allen tegen Milligan, een cruciaal geval hangende bij de Hoge Raad waarin zwarte kiezers de staat Alabama beschuldigen van het tekenen van de congresdistrictkaart om hen te benadelen. In dit geval, zoals in vele andere, worden simulaties gebruikt door zowel de aanklagers als de beklaagden om hun zaak te bepleiten. Het Hof is verwacht een besluit te nemen in juni of juli.

Maar, zoals een van de advocaten van de aanklagers tegen rechter Samuel Alito zei tijdens pleidooien in oktober, "de simulaties roepen eigenlijk meer vragen op dan ze beantwoorden."

Combinatorische explosie

Om de wiskundige moeilijkheid bij het genereren van een ensemble te begrijpen, begint u met het bedenken van onrealistisch eenvoudige kaarten. Stel je bijvoorbeeld een raster van 4 bij 4 voor. Er zijn 117 verschillende manieren om deze 16 pleinen op te delen in vier aaneengesloten wijken met vier pleinen per wijk. Van daaruit groeien de mogelijkheden heel snel in wat bekend staat als een combinatorische explosie. Een raster van 6 bij 6 met zes aaneengesloten districten van elk zes vierkanten heeft 451,206 mogelijkheden. Een raster van 9 bij 9 met negen districten van elk negen vierkanten? Meer dan 700 biljoen opties. Voor een raster van 10 bij 10, met 100 vierkanten, weet niemand hoeveel mogelijke configuraties van 10 districten er zijn.

Natuurlijk heeft een typische staat veel meer dan 100 verschillende jurisdicties die kunnen worden gegroepeerd in districten. Analisten bouwen vaak mogelijke districten uit kiesdistricten. North Carolina heeft bijvoorbeeld meer dan 2,500 districten, terwijl Pennsylvania er 9,159 heeft. Officiële districtsplannen zijn over het algemeen gebaseerd op nog gedetailleerdere censusblokken: Alabama heeft 185,976 van dergelijke blokken.

Elke staat heeft andere regels voor het tekenen van districten, maar over het algemeen moeten ze aaneengesloten en "compact" zijn, traditionele geografische en politieke grenzen behouden, bijna gelijk zijn in bevolking en voorkomen dat zogenaamde belangengemeenschappen uiteenvallen. De Voting Rights Act vereist ook dat districten zo worden getrokken dat ervoor wordt gezorgd dat kiezers van alle raciale groepen een gelijke kans krijgen om "vertegenwoordigers van hun keuze te kiezen". Het verzoenen van al deze vereisten is wiskundig een uitdaging. Hoe meer eisen er worden gesteld aan herverdeling, zei Malmskog, "hoe ingewikkelder het wiskundige probleem wordt."

De afgelopen 20 jaar is de dominante techniek voor het genereren van veel mogelijke kaarten een techniek geweest die 'willekeurig zaaien en groeien' wordt genoemd. Dit werkt ongeveer zoals het klinkt. Stel dat u duizenden individuele stemdistricten wilt combineren tot bijvoorbeeld 10 congresdistricten, die elk ongeveer 760,000 mensen moeten bevatten. Je begint met het willekeurig kiezen van een district om een ​​bepaald district te 'zaaien'. Vervolgens voeg je aangrenzend gebied toe aan dit zaad totdat je bijna 760,000 mensen in het district krijgt. Vervolgens herhaal je het proces - begin met een ander district om een ​​ander district te zaaien - totdat je de rest van je districten bedenkt.

Met enkele relatief eenvoudige aanpassingen om ervoor te zorgen dat de districten compact zijn, is het mogelijk om deze methode te gebruiken om veel redelijk ogende kaarten te maken. Maar vanwege de combinatorische explosie van het aantal mogelijke kaarten, vertegenwoordigen zelfs miljoenen kaarten gemaakt door de random-seed-and-grow-techniek slechts een klein deel van alle mogelijke kaarten. En er is geen wiskundig bewijs dat deze fractie representatief is voor de verzameling geldige kaarten als geheel, wat betekent dat het gebruik ervan als vergelijkingsbasis kan leiden tot misleidende conclusies.

Dat is de reden waarom, in het midden van het afgelopen decennium, onder meer onderzoekers Kosuke Imai, hoogleraar overheid en statistiek aan de universiteit van Harvard, en Jonathan mattend, een professor in wiskunde en statistiek aan de Duke University, begon een techniek genaamd Markov chain Monte Carlo of MCMC toe te passen om kaarten te maken.

MCMC werkt door eerst de bestaande districtskaart om te zetten in een grafiek - een wiskundige structuur die bestaat uit knooppunten of punten, verbonden door lijnen of randen. Elk district wordt een knooppunt; als districten in het echte leven een grens delen, worden ze verbonden door een rand in de grafiek. Vroege MCMC-methoden, zoals de "flip-based" methode beschreven door Imai en collega's in een 2014-papier, werkte door districten tussen aangrenzende districten op een wiskundig specifieke manier te verwisselen.

Door hun kaart als een grafiek te beschouwen, kunnen onderzoekers een hulpmiddel uit de grafentheorie, de stelling van Perron-Frobenius, gebruiken om aan te tonen dat, als het algoritme lang genoeg wordt uitgevoerd - een interval dat wiskundigen de mengtijd noemen - het goed zal werken. steekproef uit de distributie van alle mogelijke geldige kaarten. Dit is een verbetering, maar het is meestal nog steeds onmogelijk om rigoureus te bewijzen hoe lang de mengtijd precies is. Mattingly zei dat de vraag hoe we het beste "aan iedereen kunnen bewijzen dat we goed werk hebben geleverd" onopgelost blijft. Wiskundigen werken dus aan tweaks voor MCMC om beter grenzen te stellen aan de mengtijd - en om deze sneller te bereiken.

Een stap vooruit kwam in 2019, toen een groep onderzoekers werkte aan een betere manier om een ​​nieuwe districtskaart te tekenen voor het Virginia House of Delegates. Het voorgaande jaar had een federale rechtbank geoordeeld dat 11 districten op de kaart van Virginia ongrondwettelijk waren omdat ze zwarte inwoners op een zodanige manier concentreerden dat hun stemkracht afzwakte. Bovendien heeft Virginia een ongewoon strikte beperking in het herdistrictingsproces: districten kunnen slechts 1% afwijken in bevolking. Gezien het feit dat er 100 staatshuisdistricten zijn, "is dat een behoorlijk krappe grens", zei Daryl DeFord, een wiskundige aan de Washington State University die de eerlijkheid van de kaart van Virginia analyseerde. Het betekende dat de groep niet op wijkniveau kon werken. "Sommige gebieden waren eigenlijk te groot om een ​​geldig plan te maken," zei DeFord. Het opdelen van de kaart in kleinere censusblokeenheden werkte ook niet. Na ongeveer 10 miljoen stappen waren standaard flip-gebaseerde MCMC-algoritmen "bij lange na niet in de buurt van representatieve samples uit de hele ruimte", zei hij.

Dus bedachten DeFord en zijn collega's een manier om sneller door de ruimte te bewegen. Om snel voorbeelden te krijgen van de hele ruimte van mogelijke kaarten, moesten ze de districtstoewijzing voor veel districten tegelijk wijzigen op een manier die de aaneengeslotenheid van de districten behield. Dit maakte elke stap in de Markov-keten rekenkundig duurder, maar het betekende ook dat elke stap hen veel dichter bij de mengtijd bracht.

Ze bedachten een algoritme genaamd ReCom dat werkt door willekeurig twee aangrenzende districten te selecteren en ze samen te voegen tot een enkele eenheid. Deze eenheid erft de grafiekstructuur die elk district had. Maar in plaats van aangrenzende districten te verwisselen, maakt ReCom willekeurig een nieuwe grafiek, een spanning tree genaamd, die de knooppunten in de twee gecombineerde districten (die elk een district vertegenwoordigen) met elkaar verbindt op een manier die geen lussen bevat, maar ervoor zorgt dat alle de knooppunten zijn verbonden. Omdat er geen lussen zijn, zou het doorsnijden van een rand de twee gecombineerde districten weer in twee delen splitsen (net zoals het afzagen van een tak van een boom deze in precies twee delen zou snijden).

Het is meestal gemakkelijk om randen te vinden die een bijna gelijk aantal knooppunten achterlaten in elk van de resulterende componenten — ReCom kiest willekeurig zo'n rand. (Als het er geen kan vinden, wordt de opspannende boom opnieuw getekend.) Vanwege de statistieken van opspannende bomen heeft dit ook de natuurlijke neiging om compacte districten te produceren. Omdat ReCom bij elke stap honderden wijzigingen oplegt, geloven de uitvinders dat het de mengtijd sneller bereikt dan op flip gebaseerde methoden die minder wijken tegelijk veranderen.

Uitdagingen in de echte wereld

De krappe bevolkingsbeperking van Virginia is niet de enige mogelijke wending in het proces. Colorado heeft een ongebruikelijke vereiste die verder gaat dan de typische beperkingen van contiguïteit en compactheid: de wet van Colorado vereist ook dat districten 'competitief' zijn.

De wet definieert het concurrentievermogen slechts vaag, dus besloot de onafhankelijke commissie die verantwoordelijk was voor het opstellen van de wetgevende districtskaart van de staat Colorado om een ​​concurrerend district te definiëren met behulp van historische gegevens. Om een ​​hypothetisch district 'competitief' te laten zijn, moest het aantal stemmen voor geselecteerde rassen tijdens de vorige drie verkiezingen, voor zowel democraten als republikeinen, tussen 46% en 54% liggen.

De commissie wendde zich vervolgens tot DeFord, Malmskog en Jeanne Cleland, een wiskundige aan de Universiteit van Colorado, Boulder, samen met Flavia Sancier-Barbosa, een collega van Malmskog aan het Colorado College. De vier onderzoekers gebruikten het ReCom-algoritme om ensembles van miljoenen kaarten te genereren die de herverdelingscriteria van de staat volgden; vervolgens gebruikten ze die ensembles om een ​​"bereik van waarden te bepalen voor hoeveel districten je zou verwachten binnen dat competitieve bereik te vallen", zei Clelland. Toen de commissie nieuwe plannen maakte, bepaalden de wiskundigen waar ze binnen de statistische analyse vielen. Uiteindelijk selecteerde de wetgevende herverdelingscommissie een kaart met meer competitieve districten dan het gemiddelde dat de wiskundigen in hun ensembles zagen, zei Clelland.

Clelland merkte op dat hoewel competitieve districten misschien eerlijk klinken, ze in de praktijk in strijd kunnen zijn met evenredigheid, het doel dat het aantal vertegenwoordigers van een van beide partijen moet overeenkomen met het aantal kiezers in die partij over de gehele staat. "Als je heel veel districten hebt waar het resultaat echt dicht bij de 50% ligt, dan kan een heel kleine verandering in de fractie van het stemaandeel een heel grote verandering teweegbrengen in de fractie van het zetelaandeel."

Imai zei dat hij zich zorgen maakt dat in bepaalde gevallen MCMC-methoden zoals ReCom die uitgaan van een initieel plan en het aanpassen "het moeilijk hebben om de ruimte te verkennen". Omdat de ruimte van mogelijke geldige kaarten erg multimodaal is, zei hij (wat betekent dat er meerdere goede oplossingen kunnen zijn die sterk van elkaar verschillen), lopen dergelijke algoritmen het risico te dicht bij hun oorspronkelijke voorwaarden te blijven. Daarom introduceerde Imai samen met zijn afgestudeerde student Cory McCartan een nieuwe methode genaamd 'sequentiële Monte Carlo' of SMC, in een preprint die is geaccepteerd voor publicatie in de Annalen van toegepaste statistiek. SMC vertaalt ook kaarten in grafieken en maakt, net als ReCom, spanning trees van deze grafieken.

SMC maakt een enkele spanning tree met een knooppunt voor elk district. Vervolgens probeert het slechts één district af te splitsen van de rest van de grafiek. Het identificeert de meest veelbelovende snijkanten op basis van criteria die Imai en McCartan specificeren, en kiest vervolgens willekeurig een van deze randen. Het herhaalt vervolgens het proces op het resterende deel van de grafiek, waarbij één nieuw district per keer wordt afgesplitst totdat het vereiste aantal districten is gemaakt. Door dit proces miljoenen keren te herhalen, creëert SMC miljoenen mogelijk levensvatbare kaarten.

Wiskundige Argumenten

Computationele herverdeling vervangt in feite de relatief eenvoudige vraag of een enkele kaart eerlijk is door de schijnbaar veel gecompliceerdere vraag of miljoenen kaarten eerlijk zijn. Dit plaatst het volledig in de wiskundige traditie om te laten zien dat een eenvoudig probleem gelijk is aan een veel gecompliceerder probleem, en vervolgens het meer gecompliceerde probleem op te lossen.

In november 2022 bracht het team van Imai een enorme verzameling van herverdelingskaartsimulaties van het congres voor alle 50 staten op basis van gegevens van de volkstelling van 2020. Omdat er veel parameters zijn om aan te passen, afhankelijk van de vraag die je probeert te beantwoorden, hopen ze dat hun tool ensemble-analyse beschikbaar zal maken voor de massa.

Imai is getuige-deskundige voor de eisers in de hangende zaak van het Hooggerechtshof. De aanklagers beweren, gebruikmakend van de ensembles die hij heeft gegenereerd, dat de districten van Alabama de Voting Rights Act schenden door zwarte kiezers het kiesrecht te ontnemen. Maar de staat Alabama, die wordt aangeklaagd, gebruikt zijn ensembles om te beweren dat de kaart redelijk getekend is. Wat de rechtbank ook beslist, het laat zien dat wiskunde altijd de strijd aan moet gaan met politiek als het om verkiezingen gaat.