Gerrymandering - krojenje izbornih jedinica i Metropolis-Hastings algoritam

master's thesis

• Author: Nikolina Pleić
• Mentor: Matija Kazalicki (mentor)
• Committee member: Matija Kazalicki (predsjednik povjerenstva)
• Committee member: Marko Tadić (član povjerenstva)
• Committee member: Marcela Hanzer (član povjerenstva)
• Committee member: Vjekoslav Kovač (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2019-03-01, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

U prvom poglavlju definirali smo Markovljeve lance na općenitom skupu stanja. Definirali smo pojmove kao što su prijelazna jezgra Markovljevog lanca u Definiciji 1.0.1, invarijantna mjera u Definiciji 1.0.7 te detaljna ravnoteža. Pokazali smo da je uvjet detaljne ravnoteže dovoljan uvjet da bi Markovljev lanac imao invarijantnu mjeru. Nakon toga u drugom poglavlju primijenili smo tu teoriju na Markovljev lanac dobiven Metropolis-Hastings algoritmom. Naveli smo dovoljne uvjete kako bi dobiveni lanac imao stacionarnu distribuciju. U Teoremu 2.5.3 objedinili smo rezultate o egzistenciji stacionarne distribucije i konvergenciji lanca k stacionarnoj distribuciji. U trećem poglavlju promatrali smo politički problem gerrymanderinga te smo ga vizualizirali na primjeru američke države North Caroline. Uveli smo evaluacijsku funkciju J kako bismo svakom izbornom planu dodijelili vjerojatnost takvu da izborni planovi s manjom vrijednošću evaluacijske funkcije budu više vjerojatni. Pomoću evaluacijske funkcije definirali smo ciljanu vjerojatnosnu distribuciju. Konačno, predložili smo način stvaranja novih izbornih raspodjela koristeći Metropolis-Hastings algoritam.

Abstract (english)

In the first chapter we discussed the theory of Markov chains on a general state space. We defined terms such as transition kernel in Definition 1.0.1, invariant measure in 1.0.7 and detailed balance condition. We have shown that the detailed balance condition is sufficient for a Markov chain to have an invariant measure. After that, in the second chapter, we have applied that theory to a Markov chain produced by Metropolis-Hastings algorithm. We list the sufficient conditions for the produced Markov chain to have a stationary distribution. In Theorem 2.5.3 we combine results of existence of stationary distribution and the convergence of a chain to the stationary distribution. In third chapter, we examined the political problem of gerrymandering. We visualized it on an example of an US state of North Carolina. We introduced a score function J in order to assign a value to each redistricting so that redistrictings with lower scores are more likely to occur. Using this score function we have defined a target distribution. Finally, we proposed a way of creating new redistrictings using a standard Metropolis-Hastings algorithm.

• Keywords: Markovljev lanac; prijelazna jezgra; invarijantna mjera; detaljna ravnoteža; Metropolis-Hastings algoritam; gerrymandering
• Keywords (english): Markov chain; transition kernel; invariant measure; detailed balance condition; Metropolis-Hastings algorithm; gerrymandering
• Language: croatian
• URN:NBN: urn:nbn:hr:217:320271
• Study programme: Title: Mathematical Statistics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2019-09-03 12:06:23