0
# Markov Chain Analysis
1
2
Core MCMC functionality for generating ensembles of districting plans. The MarkovChain class orchestrates the entire analysis workflow by iterating through proposed partitions, validating constraints, and making acceptance decisions.
3
4
## Capabilities
5
6
### MarkovChain Creation
7
8
Create and configure Markov chains with proposal functions, constraints, acceptance criteria, and initial states.
9
10
```python { .api }
11
class MarkovChain:
12
def __init__(
13
self,
14
proposal: ProposalFunction,
15
constraints: Union[ConstraintFunction, List[ConstraintFunction], Validator],
16
accept: AcceptanceFunction,
17
initial_state: Partition,
18
total_steps: int
19
) -> None:
20
"""
21
Create a Markov chain for redistricting analysis.
22
23
Parameters:
24
- proposal (ProposalFunction): Function that proposes new partitions
25
- constraints (Union[ConstraintFunction, List[ConstraintFunction], Validator]):
26
Validation functions or Validator instance
27
- accept (AcceptanceFunction): Function that accepts/rejects proposals
28
- initial_state (Partition): Starting partition for the chain
29
- total_steps (int): Number of steps to run
30
31
Returns:
32
None
33
34
Raises:
35
ValueError: If initial_state fails constraint validation
36
"""
37
```
38
39
Usage example:
40
```python
41
from gerrychain import MarkovChain, GeographicPartition
42
from gerrychain.constraints import contiguous, within_percent_of_ideal_population
43
from gerrychain.proposals import recom
44
from gerrychain.accept import always_accept
45
46
# Set up initial partition
47
partition = GeographicPartition(graph, assignment="district", updaters=updaters)
48
49
# Create Markov chain
50
chain = MarkovChain(
51
proposal=recom,
52
constraints=[
53
contiguous,
54
within_percent_of_ideal_population(partition, 0.05)
55
],
56
accept=always_accept,
57
initial_state=partition,
58
total_steps=1000
59
)
60
```
61
62
### Chain Properties and Configuration
63
64
Access and modify chain properties including constraints, state, and step counting.
65
66
```python { .api }
67
@property
68
def constraints(self) -> Validator:
69
"""
70
Read-only access to the constraints validator.
71
72
Returns:
73
Validator: The constraints validator instance
74
"""
75
76
@constraints.setter
77
def constraints(
78
self,
79
constraints: Union[ConstraintFunction, List[ConstraintFunction], Validator]
80
) -> None:
81
"""
82
Update chain constraints and validate initial state against new constraints.
83
84
Parameters:
85
- constraints: New constraint functions or Validator instance
86
87
Returns:
88
None
89
90
Raises:
91
ValueError: If initial_state fails new constraint validation
92
"""
93
```
94
95
### Chain Iteration
96
97
Execute the Markov chain using Python's iterator protocol for seamless integration with loops and analysis workflows.
98
99
```python { .api }
100
def __iter__(self) -> "MarkovChain":
101
"""
102
Initialize chain iteration, resetting counter and state.
103
104
Returns:
105
MarkovChain: Self as iterator
106
"""
107
108
def __next__(self) -> Partition:
109
"""
110
Advance to next valid, accepted partition in the chain.
111
112
Returns:
113
Partition: Next partition state
114
115
Raises:
116
StopIteration: When total_steps is reached
117
"""
118
119
def __len__(self) -> int:
120
"""
121
Get total number of steps in the chain.
122
123
Returns:
124
int: Total steps configured for this chain
125
"""
126
```
127
128
### Progress Tracking
129
130
Add visual progress tracking for long-running chains using tqdm progress bars.
131
132
```python { .api }
133
def with_progress_bar(self):
134
"""
135
Wrap the Markov chain with a tqdm progress bar for visual feedback.
136
137
Returns:
138
tqdm-wrapped MarkovChain iterator
139
140
Requires:
141
tqdm package must be installed
142
"""
143
```
144
145
Usage example:
146
```python
147
# Run chain with progress bar
148
for partition in chain.with_progress_bar():
149
# Analyze partition
150
score = compute_score(partition)
151
scores.append(score)
152
153
# Log every 100 steps
154
if len(scores) % 100 == 0:
155
print(f"Step {len(scores)}: Score = {score:.3f}")
156
```
157
158
### Complete Analysis Workflow
159
160
Example of a complete Markov chain analysis workflow:
161
162
```python
163
from gerrychain import MarkovChain, Graph, GeographicPartition
164
from gerrychain.constraints import contiguous, within_percent_of_ideal_population
165
from gerrychain.proposals import recom
166
from gerrychain.accept import always_accept
167
from gerrychain.updaters import Tally, cut_edges
168
from gerrychain.metrics import mean_median, efficiency_gap
169
170
# 1. Create graph and initial partition
171
graph = Graph.from_file("precincts.shp")
172
partition = GeographicPartition(
173
graph,
174
assignment="district",
175
updaters={
176
"population": Tally("population"),
177
"cut_edges": cut_edges,
178
"SEN18": Election("SEN18", ["SEN18D", "SEN18R"])
179
}
180
)
181
182
# 2. Set up constraints
183
constraints = [
184
contiguous,
185
within_percent_of_ideal_population(partition, 0.05)
186
]
187
188
# 3. Create and run chain
189
chain = MarkovChain(
190
proposal=recom,
191
constraints=constraints,
192
accept=always_accept,
193
initial_state=partition,
194
total_steps=10000
195
)
196
197
# 4. Collect metrics
198
mean_medians = []
199
efficiency_gaps = []
200
201
for state in chain.with_progress_bar():
202
# Compute partisan metrics
203
mm = mean_median(state["SEN18"])
204
eg = efficiency_gap(state["SEN18"])
205
206
mean_medians.append(mm)
207
efficiency_gaps.append(eg)
208
209
# 5. Analyze results
210
import numpy as np
211
print(f"Mean-Median: {np.mean(mean_medians):.3f} ± {np.std(mean_medians):.3f}")
212
print(f"Efficiency Gap: {np.mean(efficiency_gaps):.3f} ± {np.std(efficiency_gaps):.3f}")
213
```
214
215
## Types
216
217
```python { .api }
218
ProposalFunction = Callable[[Partition], Partition]
219
ConstraintFunction = Callable[[Partition], bool]
220
AcceptanceFunction = Callable[[Partition], bool]
221
UpdaterFunction = Callable[[Partition], Any]
222
```