Markov Chains

Markov chains connect an initial partition, proposal, constraints, acceptance rule, and updaters.

class gerrychain.MarkovChain(proposal_fn: ~gerrychain.proposals.proposals.ProposalFn | None = None, constraints: ~collections.abc.Iterable[~collections.abc.Callable[[~gerrychain.partition.partition.Partition], bool]] | ~collections.abc.Callable[[~gerrychain.partition.partition.Partition], bool] = (), acceptance_fn: ~gerrychain.accept.AcceptanceFn = <function always_accept>, initial_partition: ~gerrychain.partition.partition.Partition | None = None, total_steps: int | None = None, *, rng: ~random.Random | int | None = None)

MarkovChain is a class that creates an iterator for iterating over the states of a Markov chain run in a gerrymandering analysis context.

It allows for the generation of a sequence of partitions (states) of a political districting plan, where each partition represents a possible state in the Markov chain.

Example usage:

chain = MarkovChain(proposal_fn, constraints, acceptance_fn, initial_partition, total_steps)
for state in chain:
    # Do whatever you want - print output, compute scores, ...

The chain may also be configured incrementally. Any parameter omitted from the constructor can be assigned afterward, and the configuration is checked when iteration begins (or explicitly, via check_valid()):

chain = MarkovChain(total_steps=1000)
chain.initial_partition = Partition(graph, assignment, updaters)
chain.proposal_fn = ReCom.cut_edges_mst(pop_col="TOTPOP", pop_target=ideal, epsilon=0.01)
chain.constraints = [contiguous]
for state in chain:
    ...

Constraints and updaters can also be added one at a time, in any order relative to the other configuration, with add_constraint() and add_updater().

acceptance_fn defaults to always_accept() and constraints defaults to no constraints; proposal_fn, initial_partition, and total_steps must be set before iterating. While a run is in progress the configuration is locked: assigning any of these attributes (or rng) raises AttributeError. The lock is released when the run ends, whether by exhausting the steps, an error in a step, or leaving the loop early with break.

Initialize a MarkovChain instance.

All configuration parameters are optional here; whatever is omitted can be assigned later as an attribute. The full configuration is checked by check_valid() when iteration begins.

Parameters:

• proposal_fn (ProposalFn | None, optional) – Function called as proposal_fn(state, rng=chain.rng) to propose the next state. The chain’s RNG takes precedence over an rng bound into a functools.partial proposal.

• constraints (Iterable[ConstraintFn] | ConstraintFn, optional) – One or more functions with signature Partition -> bool determining whether a proposed next state is valid. Bundled into a single Validator; passing a Validator directly also works. Defaults to no constraints.

• acceptance_fn (AcceptanceFn, optional) – Function called as acceptance_fn(proposed_state, rng=chain.rng) to accept or reject the proposed state. Defaults to always_accept().

• initial_partition (Partition | None, optional) – Initial Partition class.

• total_steps (int | None, optional) – Number of steps to run.

• rng (random.Random | int | None, optional) – Source of randomness for the run. An integer creates a reproducible random.Random; a supplied instance is kept by identity; None creates an independent RNG from system entropy.

Raises:

ValueError – If an initial_partition is given and is not valid according to the given constraints.

add_constraint(constraint: Callable[[Partition], bool]) → None

Add a constraint to the chain’s existing constraints.

If an initial partition is set, it is checked against the new constraint immediately; otherwise the check is deferred to check_valid().

Parameters:

constraint (ConstraintFn) – A new constraint to add to the Markov chain.

Raises:

• AttributeError – If a run is in progress.

• ValueError – If the initial partition fails the new constraint.

add_constraints(constraints: Iterable[Callable[[Partition], bool]]) → None

Add multiple constraints to the chain’s existing constraints.

If an initial partition is set, it is checked against the new constraints immediately; otherwise the check is deferred to check_valid().

Parameters:

constraints (Iterable[ConstraintFn]) – New constraints to add to the Markov chain.

Raises:

• AttributeError – If a run is in progress.

• ValueError – If the initial partition fails any of the new constraints.

add_updater(name: str, updater: Callable[[Partition], Any]) → None

Add a named updater to the chain’s partitions.

The updater is added to the initial partition (immediately if one is set, otherwise as soon as one is assigned) and is inherited by every partition the chain generates. Its value is accessed as partition[name].

Parameters:

• name (str) – Name under which the updater’s value is accessed.

• updater (Callable[[Partition], Any]) – The updater function.

Raises:

AttributeError – If a run is in progress.

add_updaters(updaters: dict[str, Callable[[Partition], Any]]) → None

Add multiple named updaters to the chain’s partitions.

The updaters are added to the initial partition (immediately if one is set, otherwise as soon as one is assigned) and are inherited by every partition the chain generates. Their values are accessed as partition[name].

Parameters:

updaters (dict[str, Callable[[Partition], Any]]) – A dictionary of updater functions, where keys are the names under which the updater’s values are accessed.

check_valid() → None

Check that the chain is fully and consistently configured.

This is called automatically when iteration begins, but can be called directly to fail fast after incremental configuration.

Raises:

ValueError – If proposal_fn, initial_partition, or total_steps is unset, or if the initial partition does not satisfy the constraints.

property constraints: Validator

The chain’s constraints, bundled into a single Validator callable.

Returns:

The constraints of the Markov chain.

Return type:

Validator

with_progress_bar() → Iterable[Partition]

Wraps the Markov chain in a tqdm progress bar.

Useful for long-running Markov chains where you want to keep track of the progress. Requires the tqdm package to be installed.

Returns:

A progress-reporting iterable over the chain.

Return type:

Iterable[Partition]