Edit on GitHub

Markov Chains

The following methods are used to "run" the chain; i.e., initiate the process of sequentially generating and evaluating districting plans.

We highly recommend using the ReCom plan proposal method.

You can think of the chain as a loop that progresses like this:

(generate proposal for new plan that fits within constraints ➡ decide whether to accept the proposal ➡ update partition to reflect new districting plan ➡ record value of scores on the new plan) x num_steps.

ReCom Chain

Runs a Markov Chain for num_steps steps using ReCom. In summary, the ReCom proposal method works as follows: merge two districts in the plan, generate a minimum spanning tree for the precincts in the merged district, then "split" the merged district into two new districts by finding a population-balanced cut of the MST. This method could potentially be used to merge/split an arbitrary number of districts, but currently, our implementation only supports merging 2 districts and splitting into 2 new districts.

GerryChain.recom_chain — Function
recom_chain(graph::BaseGraph,
            partition::Partition,
            pop_constraint::PopulationConstraint,
            num_steps::Int,
            scores::Array{S, 1};
            num_tries::Int=3,
            acceptance_fn::F=always_accept,
            rng::AbstractRNG=Random.default_rng(),
            no_self_loops::Bool=false)::ChainScoreData where {F<:Function, S<:AbstractScore}

Runs a Markov Chain for num_steps steps using ReCom. Returns a ChainScoreData object which can be queried to retrieve the values of every score at each step of the chain.

Arguments:

  • graph: BaseGraph
  • partition: Partition with the plan information
  • pop_constraint: PopulationConstraint
  • num_steps: Number of steps to run the chain for
  • scores: Array of AbstractScores to capture at each step
  • num_tries: num times to try getting a balanced cut from a subgraph before giving up
  • acceptance_fn: A function generating a probability in [0, 1] representing the likelihood of accepting the proposal. Should accept a Partition as input.
  • rng: Random number generator. The user can pass in their own; otherwise, we use the default RNG from Random.
  • no_self_loops: If this is true, then a failure to accept a new state is not considered a self-loop; rather, the chain simply generates new proposals until the acceptance function is satisfied. BEWARE - this can create infinite loops if the acceptance function is never satisfied!
source

Flip chain

The flip_chain method is quite similar to the recom_chain method. The only difference is how new plans are generated at each step of the chain. Out of the set of cut edges in a given plan, where a cut edge is defined to be an edge in the dual graph that crosses from a node in one district to a node in a different district, one cut edge is randomly selected, and one of the two precincts is "flipped" to the district of the other precinct.

Runs a Markov Chain for num_steps steps using Flip proposals.

GerryChain.flip_chain — Function
flip_chain(graph::BaseGraph,
           partition::Partition,
           pop_constraint::PopulationConstraint,
           cont_constraint::ContiguityConstraint,
           num_steps::Int,
           scores::Array{S, 1};
           acceptance_fn::F=always_accept,
           no_self_loops::Bool=false)::ChainScoreData where {F<:Function, S<:AbstractScore}

Runs a Markov Chain for num_steps steps using Flip proposals. Returns a ChainScoreData object which can be queried to retrieve the values of every score at each step of the chain.

Arguments:

  • graph: BaseGraph
  • partition: Partition with the plan information
  • pop_constraint: PopulationConstraint
  • cont_constraint: ContiguityConstraint
  • num_steps: Number of steps to run the chain for
  • scores: Array of AbstractScores to capture at each step
  • acceptance_fn: A function generating a probability in [0, 1] representing the likelihood of accepting the proposal
  • no_self_loops: If this is true, then a failure to accept a new state is not considered a self-loop; rather, the chain simply generates new proposals until the acceptance function is satisfied. BEWARE - this can create infinite loops if the acceptance function is never satisfied!
source

API

GerryChain.update_partition! — Function
update_partition!(partition::Partition,
                  graph::BaseGraph,
                  proposal::RecomProposal,
                  copy_parent::Bool=false)

Updates the Partition with the RecomProposal.

source
GerryChain.update_partition! — Function
update_partition!(partition::Partition,
                  graph::BaseGraph,
                  proposal::FlipProposal,
                  copy_parent::Bool=false)

Updates the Partition with the FlipProposal.

source