최근까지 게리맨더링된 지역은 뒤틀린 덩굴손으로 식별할 수 있는 튀어나오는 경향이 있었습니다. 더 이상 그렇지 않습니다. "현대 기술을 사용하면 모양을 매우 이상하게 만들지 않고도 꽤 효과적으로 게리맨더를 할 수 있습니다."라고 말했습니다. 베스 말름스코그, 콜로라도 대학의 수학자. 이로 인해 지도가 부당하게 조작되었는지 여부를 파악하기가 훨씬 더 어려워집니다.

명백히 기형적인 구역이라는 숨길 수 없는 신호가 없으면 수학자들은 게리맨더를 찾기 위해 점점 더 강력한 통계적 방법을 개발해 왔습니다. 이들은 지도를 수천 또는 수백만 개의 가능한 지도의 앙상블과 비교하여 작동합니다. 지도 결과가 평균 지도에서 예상되는 것보다 민주당원 또는 공화당원의 의석이 눈에 띄게 더 많다면 수상한 일이 발생했을 수 있다는 신호입니다.

그러나 그러한 앙상블을 만드는 것은 생각보다 까다롭습니다. 가능한 모든 맵을 고려하는 것이 실현 가능하지 않기 때문입니다. 슈퍼컴퓨터가 셀 수 있는 조합이 너무 많습니다. 최근의 많은 수학적 발전은 가능한 시뮬레이션의 엄청나게 큰 공간을 탐색하는 방법을 제안하여 수학자에게 공정과 불공평을 구별할 수 있는 신뢰할 수 있는 방법을 제공합니다.

선거구 재조정과 관련된 많은 일과 마찬가지로 그들의 작업은 법정에서 끝납니다. 지난 XNUMX년 동안 시뮬레이션은 미주리, 노스캐롤라이나, 오하이오 및 미시간에서 재판구를 재조정하는 증거로 받아들여졌습니다. 그리고 그들은 토론의 중심 대상입니다. 앨런 대 밀리건, 중요한 사건 대법원에 계류 중 흑인 유권자들은 앨라배마 주가 그들에게 불이익을 주기 위해 의회 선거구 지도를 그렸다고 비난합니다. 이 경우에도 다른 많은 경우와 마찬가지로 원고와 피고가 소송을 변론하기 위해 시뮬레이션을 사용하고 있습니다. 법원은 결정을 내릴 것으로 예상 XNUMX월이나 XNUMX월에.

그러나 원고의 변호사 중 한 명이 XNUMX월 구두 변론에서 Samuel Alito 판사에게 말했듯이 "시뮬레이션은 실제로 대답하는 것보다 더 많은 질문을 생성합니다."

조합 폭발

앙상블 생성의 수학적 어려움을 이해하려면 비현실적으로 단순한 맵을 생각하는 것부터 시작하십시오. 예를 들어 4x4 그리드를 상상해 보십시오. 이 117개의 사각형을 구역당 16개의 사각형이 있는 6개의 인접한 구역으로 세분하는 6가지 방법이 있습니다. 거기에서 조합 폭발로 알려진 가능성이 매우 빠르게 커집니다. 각각 451,206개의 정사각형으로 구성된 9개의 연속 구역이 있는 9x700 그리드에는 10개의 가능성이 있습니다. 각각 10개의 정사각형으로 구성된 100개의 구역이 있는 10xXNUMX 그리드? XNUMX조 개가 넘는 옵션. XNUMX개의 정사각형이 있는 XNUMX x XNUMX 그리드의 경우 가능한 XNUMX개 구역 구성이 몇 개인지 아무도 모릅니다.

물론, 일반적인 주에는 100개 이상의 다양한 관할 구역이 있으며, 이를 구역으로 그룹화할 수 있습니다. 분석가는 종종 투표 구역에서 가능한 구역을 만듭니다. 예를 들어 노스캐롤라이나에는 2,500개 이상의 선거구가 있는 반면 펜실베이니아에는 9,159개가 있습니다. 공식 구역 계획은 일반적으로 훨씬 더 세분화된 인구 조사 블록을 기반으로 합니다. 앨라배마에는 185,976개의 블록이 있습니다.

모든 주에는 선거구를 그리는 데 서로 다른 규칙이 있지만 일반적으로 선거구는 연속적이고 "밀집"되어야 하며 전통적인 지리적 및 정치적 경계를 보존하고 인구가 거의 같아야 하며 소위 이익 공동체를 분리하지 않아야 합니다. 투표권법(Voting Rights Act)은 또한 모든 인종 그룹의 유권자가 "자신이 선택한 대표를 선출"할 수 있는 동등한 기회를 보장하는 방식으로 선거구를 구성할 것을 요구합니다. 이러한 모든 요구 사항을 조정하는 것은 수학적으로 어려운 일입니다. 재구획에 대한 요구 사항이 많을수록 "수학적 문제가 더 복잡해진다"고 Malmskog는 말했습니다.

지난 20년 동안 가능한 많은 지도를 생성하는 지배적인 기술은 "무작위 시드 및 성장(random seed and grow)"이라는 기술이었습니다. 이것은 들리는 방식대로 작동합니다. 수천 개의 개별 투표 구역을 예를 들어 각각 약 10명의 사람들을 포함해야 하는 760,000개의 의회 구역으로 결합하려고 한다고 가정해 보겠습니다. 특정 구역을 "시드"할 구역을 무작위로 선택하여 시작합니다. 그런 다음 구역의 인구가 760,000명에 가까워질 때까지 이 시드에 인접한 구역을 추가합니다. 그런 다음 나머지 구역이 나올 때까지 다른 구역에서 시작하여 다른 구역에서 시작하는 과정을 반복합니다.

비교적 간단한 조정을 통해 구역이 콤팩트한지 확인하면 이 방법을 사용하여 합리적으로 보이는 많은 지도를 만들 수 있습니다. 그러나 가능한 지도의 수가 폭발적으로 증가하기 때문에 무작위 시드 앤 성장 기법으로 만든 수백만 개의 지도도 가능한 모든 지도의 극히 일부에 불과합니다. 그리고 이 분수가 전체적으로 유효한 지도 집합을 대표한다는 수학적 증거가 없습니다. 즉, 비교 기준으로 사용하면 잘못된 결론을 내릴 수 있습니다.

그렇기 때문에 지난 XNUMX년 동안 이마이 코스케, 하버드 대학교 정부 및 통계학 교수, 조나단 매팅리Duke University의 수학과 통계학 교수인 은 지도를 만들기 위해 Markov chain Monte Carlo(MCMC)라는 기술을 적용하기 시작했습니다.

MCMC는 먼저 기존 구역 지도를 선 또는 가장자리로 연결된 노드 또는 점으로 구성된 수학적 구조인 그래프로 변환하여 작동합니다. 각 구역은 노드가 됩니다. 구역이 실생활에서 경계를 공유하는 경우 그래프에서 가장자리로 연결됩니다. 초기 MCMC 방법은 Imai와 동료들이 설명한 "플립 기반" 방법과 같습니다. 2014 논문, 수학적으로 특정한 방식으로 경계 구역 사이의 선거구를 교환하여 작업했습니다.

지도를 그래프로 생각함으로써 연구원들은 Perron-Frobenius 정리라고 하는 그래프 이론의 도구를 사용하여 알고리즘이 충분히 오랫동안 실행되도록 허용되면(수학자들이 혼합 시간이라고 부르는 간격) 제대로 작동하는지 보여줄 수 있습니다. 가능한 모든 유효한 지도의 분포에서 표본을 추출합니다. 이것은 개선 사항이지만 혼합 시간이 정확히 얼마나 걸리는지 엄격하게 증명하는 것은 여전히 ​​일반적으로 불가능합니다. Mattingly는 “우리가 샘플링을 잘 했다는 것을 모든 사람에게 증명”하는 최선의 방법에 대한 질문이 아직 해결되지 않은 상태로 남아 있다고 말했습니다. 그래서 수학자들은 믹싱 시간에 대한 한계를 더 잘 설정하고 더 빨리 도달하기 위해 MCMC를 조정하는 작업을 하고 있습니다.

2019년에 연구원 그룹이 버지니아 하원의원을 위한 새로운 지구 지도를 그리는 더 나은 방법을 연구하면서 한 가지 진전이 있었습니다. 작년에 연방 법원은 버지니아 지도에 있는 11개 구역이 투표권을 약화시키는 방식으로 흑인 거주자를 집중시켰기 때문에 위헌이라고 판결했습니다. 더욱이 버지니아는 선거구 재조정 과정에서 비정상적으로 엄격한 제약이 있습니다. 선거구는 인구에서 1%만 벗어날 수 있습니다. 100개의 주 하원 선거구가 있다는 점을 감안할 때 "그것은 상당히 빡빡한 경계"라고 말했습니다. 대릴 디포드, 버지니아 지도의 공정성을 분석한 워싱턴 주립 대학의 수학자. 그것은 그룹이 선거구 수준에서 일할 수 없다는 것을 의미했습니다. DeFord는 "일부 선거구는 기본적으로 너무 커서 유효한 계획을 세울 수 없었습니다."라고 말했습니다. 지도를 더 작은 인구 조사 블록 단위로 분할하는 것도 작동하지 않았습니다. 약 10만 단계 후에 표준 플립 기반 MCMC 알고리즘은 "전체 공간에서 대표 샘플을 갖는 데 근접하지 않았습니다"라고 그는 말했습니다.

그래서 DeFord와 그의 동료들은 공간을 더 빨리 이동할 수 있는 방법을 생각해 냈습니다. 가능한 지도의 전체 공간에서 샘플을 신속하게 얻기 위해, 그들은 구역의 인접성을 유지하는 방식으로 한 번에 많은 구역에 대한 구역 할당을 변경해야 했습니다. 이로 인해 Markov 체인의 각 단계는 계산 비용이 더 많이 들지만 각 단계가 혼합 시간에 훨씬 더 가까워진다는 의미이기도 합니다.

그들은 인접한 두 구역을 무작위로 선택하고 병합하여 단일 유닛을 생성하는 방식으로 작동하는 ReCom이라는 알고리즘을 고안했습니다. 이 단위는 각 지구가 가지고 있던 그래프 구조를 계승합니다. 그러나 인접한 선거구를 교체하는 대신 ReCom은 두 개의 결합된 지구(각각 선거구를 나타냄)의 노드를 서로 연결하는 스패닝 트리라는 새 그래프를 임의로 생성합니다. 이 그래프는 루프를 포함하지 않지만 모든 노드가 연결됩니다. 고리가 없기 때문에 한쪽 가장자리를 자르면 결합된 두 구역이 다시 두 부분으로 나뉩니다(나무의 가지를 자르면 정확히 두 부분으로 자르는 것과 같습니다).

일반적으로 각 결과 구성 요소에 거의 동일한 수의 노드를 남기는 에지를 쉽게 찾을 수 있습니다. ReCom은 이러한 에지를 무작위로 선택합니다. (찾을 수 없는 경우 스패닝 트리를 다시 그립니다.) 스패닝 트리의 통계 때문에 이 또한 조밀한 구역을 생성하는 자연스러운 경향이 있습니다. ReCom은 각 단계에서 수백 가지 변경 사항을 적용하기 때문에 발명가는 한 번에 더 적은 구역을 변경하는 플립 기반 방법보다 혼합 시간에 더 빨리 도달한다고 생각합니다.

현실 세계의 도전

버지니아의 빡빡한 인구 제한은 이 과정에서 가능한 유일한 왜곡이 아닙니다. 콜로라도는 인접성 및 소형화라는 일반적인 제약 조건을 넘어서는 특이한 요구 사항을 가지고 있습니다. 콜로라도 법은 또한 학군이 "경쟁적"이어야 한다고 요구합니다.

이 법은 경쟁력을 모호하게 정의할 뿐이므로 콜로라도 주의 입법 구역 지도를 그리는 독립 위원회는 과거 데이터를 사용하여 경쟁 구역을 정의하기로 결정했습니다. 가상의 선거구가 "경쟁적"이 되려면 이전 세 번의 선거에서 민주당원과 공화당원 모두 선택한 인종의 총 득표율이 46%에서 54% 사이여야 했습니다.

그런 다음 위원회는 DeFord, Malmskog 및 잔느 클렐랜드, 콜로라도 칼리지의 Malmskog의 동료인 Flavia Sancier-Barbosa와 함께 볼더에 있는 콜로라도 대학의 수학자. XNUMX명의 연구원은 ReCom 알고리즘을 사용하여 주의 재구획 기준을 따르는 수백만 개의 지도 앙상블을 생성했습니다. 그런 다음 해당 앙상블을 사용하여 "경쟁 범위에 속할 것으로 예상되는 지구 수에 대한 값 범위"를 파악했다고 Clelland는 말했습니다. 그런 다음 위원회가 새로운 계획을 세웠을 때 수학자들은 그들이 통계 분석 내에서 어디에 속하는지 결정했습니다. 결국 입법 재조정 위원회는 수학자들이 앙상블에서 본 평균보다 더 많은 경쟁 구역이 있는 지도를 선택했다고 Clelland는 말했습니다.

Cleland는 경쟁 선거구가 공정하게 들릴 수 있지만 실제로는 각 정당의 대표자 수가 주 전체에서 해당 정당의 유권자 수와 일치해야 한다는 목표인 비례성과 충돌할 수 있다고 언급했습니다. "결과가 50%에 가까운 선거구가 많다면 득표율의 아주 작은 변화가 의석 점유율에 큰 변화를 가져올 수 있습니다."

Imai는 어떤 경우에는 초기 계획에서 시작하여 조정하는 ReCom과 같은 MCMC 방법이 "공간을 탐색하는 데 어려움을 겪는다"고 우려했습니다. 가능한 유효한 맵의 공간은 매우 다양하기 때문에(서로 매우 다른 여러 좋은 솔루션이 있을 수 있음을 의미) 이러한 알고리즘은 초기 조건에 너무 가깝게 머무를 위험이 있습니다. 그렇기 때문에 Imai는 대학원생인 Cory McCartan과 함께 "Sequential Monte Carlo" 또는 SMC라는 새로운 방법을 도입했습니다. 프리 프린트 에 게재가 승인된 것입니다. 응용통계연보. SMC는 또한 맵을 그래프로 변환하고 ReCom과 마찬가지로 이러한 그래프의 스패닝 트리를 생성합니다.

SMC는 모든 구역에 대한 노드를 포함하는 단일 스패닝 트리를 생성합니다. 그런 다음 그래프의 나머지 부분에서 한 구역만 분리하려고 시도합니다. Imai와 McCartan이 지정한 기준에 따라 절단할 가장 유망한 가장자리를 식별한 다음 이러한 가장자리 중 하나를 무작위로 선택합니다. 그런 다음 그래프의 나머지 부분에서 프로세스를 반복하여 필요한 수의 구역이 생성될 때까지 한 번에 하나의 새 구역을 분할합니다. 이 프로세스를 수백만 번 반복함으로써 SMC는 수백만 개의 실행 가능한 맵을 생성합니다.

수학적 인수

전산 재구획은 단일 맵이 공정한지 여부에 대한 비교적 간단한 질문을 훨씬 더 복잡해 보이는 수백만 개의 맵이 공정한지 여부와 같은 질문으로 효과적으로 대체합니다. 이것은 단순한 문제가 훨씬 더 복잡한 문제와 같다는 것을 보여준 다음 더 복잡한 문제를 해결하는 수학적 전통에 정확히 배치됩니다.

2022년 XNUMX월 Imai의 팀은 방대한 컬렉션을 출시했습니다. 의회 선거구 재조정 맵 시뮬레이션 50년 인구 조사 데이터를 기반으로 2020개 주 전체에 대해 조정할 매개 변수가 많기 때문에 대답하려는 질문에 따라 도구가 앙상블 분석을 대중에게 제공할 수 있기를 바랍니다.

Imai는 계류 중인 대법원 사건의 원고 측 전문가 증인입니다. 원고는 그가 생성한 앙상블을 사용하여 앨라배마의 지역구가 흑인 유권자의 권리를 박탈함으로써 투표권법을 위반한다고 주장하고 있습니다. 그러나 소송을 당하고 있는 앨라배마 주는 그의 앙상블을 이용해 지도가 공정하게 그려졌다고 주장하고 있다. 법원이 어떤 결정을 내리든 그것은 선거와 관련하여 수학이 항상 정치와 싸워야 한다는 것을 보여줍니다.