  After every U.S. national census, a state legislature is required to redraw
the boundaries of congressional districts in order to account for changes in
population. At the moment this is done in a highly partisan way, with
districting done in order to maximize the benefits to the party in power. This
is a threat to U.S's democracy. There have been proposals to take the
re-districting out of the hands of political parties and give to an
"independent" commission. Independence is hard to come by and in this thesis we
want to explore the possibility of computer generated districts that as far as
possible to avoid partisan "gerrymandering". The idea we have is to treat every
possible redistricting as a state in a Markov Chain: every state is obtained by
its former state in random way. With some technical conditions, we will get a
near uniform member of the states after running sufficiently long time (the
mixing time). Then we can say the uniform member is an impartial distribution.
Based on the geographical and statistical data of Pennsylvania, I have achieved
the Markov Chain algorithm with several constraints, done optimization
experiments and a web interface is going to be made to show the results.
