0
# Acceptance Functions
1
2
Control which proposed partitions are accepted in the Markov chain. Acceptance functions implement the probabilistic acceptance rules that determine whether to move to a proposed state or remain in the current state.
3
4
## Capabilities
5
6
### Basic Acceptance Functions
7
8
Simple acceptance rules for standard Markov chain analysis.
9
10
```python { .api }
11
def always_accept(partition: Partition) -> bool:
12
"""
13
Always accept any proposed partition that passes constraints.
14
15
Most common acceptance function for basic redistricting analysis.
16
Creates a uniform sampling of the space of valid partitions.
17
18
Parameters:
19
- partition (Partition): Proposed partition (not used in decision)
20
21
Returns:
22
bool: Always returns True
23
"""
24
```
25
26
Usage example:
27
```python
28
from gerrychain.accept import always_accept
29
30
# Standard usage in Markov chain
31
chain = MarkovChain(
32
proposal=recom,
33
constraints=constraints,
34
accept=always_accept, # Accept all valid proposals
35
initial_state=partition,
36
total_steps=10000
37
)
38
```
39
40
### Metropolis-Hastings Acceptance
41
42
Probabilistic acceptance based on proposal quality, enabling biased sampling toward better plans.
43
44
```python { .api }
45
def cut_edge_accept(partition: Partition) -> bool:
46
"""
47
Metropolis-Hastings acceptance based on number of cut edges.
48
49
Always accepts if cut edges increase (more fragmented districts).
50
Uses Metropolis criterion otherwise: accepts with probability
51
proportional to cut_edges_parent / cut_edges_current.
52
53
This tends to sample partitions with more cut edges, which can
54
be useful for exploring more varied district shapes.
55
56
Parameters:
57
- partition (Partition): Proposed partition with parent reference
58
59
Returns:
60
bool: True to accept, False to reject
61
"""
62
```
63
64
Usage example:
65
```python
66
from gerrychain.accept import cut_edge_accept
67
from gerrychain.updaters import cut_edges
68
69
# Set up partition to track cut edges
70
partition = GeographicPartition(
71
graph,
72
assignment="district",
73
updaters={"cut_edges": cut_edges}
74
)
75
76
# Use Metropolis acceptance
77
chain = MarkovChain(
78
proposal=recom,
79
constraints=constraints,
80
accept=cut_edge_accept, # Biased toward more cut edges
81
initial_state=partition,
82
total_steps=10000
83
)
84
```
85
86
### Custom Acceptance Functions
87
88
Examples of creating custom acceptance functions for specialized analysis:
89
90
```python
91
import random
92
import math
93
from gerrychain.metrics import efficiency_gap, mean_median
94
95
def fairness_biased_accept(partition, temperature=1.0):
96
"""
97
Accept based on partisan fairness with simulated annealing.
98
99
Biases sampling toward more fair partitions using efficiency gap.
100
Temperature parameter controls exploration vs exploitation.
101
"""
102
if partition.parent is None:
103
return True
104
105
# Calculate fairness scores
106
current_eg = abs(efficiency_gap(partition["election"]))
107
parent_eg = abs(efficiency_gap(partition.parent["election"]))
108
109
# Always accept if fairness improves
110
if current_eg <= parent_eg:
111
return True
112
113
# Metropolis criterion for worse fairness
114
delta = current_eg - parent_eg
115
probability = math.exp(-delta / temperature)
116
return random.random() < probability
117
118
def compactness_threshold_accept(partition, min_compactness=0.3):
119
"""
120
Accept only if average compactness exceeds threshold.
121
"""
122
from gerrychain.metrics import polsby_popper
123
import numpy as np
124
125
pp_scores = polsby_popper(partition)
126
avg_compactness = np.mean(list(pp_scores.values()))
127
128
return avg_compactness >= min_compactness
129
130
def diversity_accept(partition, diversity_factor=0.1):
131
"""
132
Probabilistically accept to maintain chain diversity.
133
134
Accepts with higher probability if partition is different
135
from recent states (requires tracking recent states).
136
"""
137
# This is a simplified example - real implementation would
138
# need to track recent states for comparison
139
base_probability = 0.8
140
141
# Add randomness to prevent chains from getting stuck
142
diversity_bonus = random.random() * diversity_factor
143
accept_probability = min(1.0, base_probability + diversity_bonus)
144
145
return random.random() < accept_probability
146
147
def multi_metric_accept(partition, weights=None):
148
"""
149
Accept based on weighted combination of multiple metrics.
150
"""
151
if weights is None:
152
weights = {"fairness": 0.4, "compactness": 0.4, "stability": 0.2}
153
154
if partition.parent is None:
155
return True
156
157
# Calculate metrics (simplified)
158
fairness_score = 1.0 - abs(efficiency_gap(partition["election"]))
159
160
from gerrychain.metrics import polsby_popper
161
import numpy as np
162
compactness_score = np.mean(list(polsby_popper(partition).values()))
163
164
# Stability = inverse of changes made
165
stability_score = 1.0 - (len(partition.flips) / len(partition.graph.nodes)
166
if hasattr(partition, 'flips') else 0.1)
167
168
# Combined score
169
combined_score = (weights["fairness"] * fairness_score +
170
weights["compactness"] * compactness_score +
171
weights["stability"] * stability_score)
172
173
# Accept if score improves or with probability based on score
174
if partition.parent:
175
parent_fairness = 1.0 - abs(efficiency_gap(partition.parent["election"]))
176
parent_compactness = np.mean(list(polsby_popper(partition.parent).values()))
177
parent_stability = 1.0 - 0.1 # Simplified
178
179
parent_score = (weights["fairness"] * parent_fairness +
180
weights["compactness"] * parent_compactness +
181
weights["stability"] * parent_stability)
182
183
if combined_score >= parent_score:
184
return True
185
else:
186
# Probabilistic acceptance
187
return random.random() < combined_score
188
189
return True
190
191
# Usage examples with custom acceptance functions
192
193
# Fairness-biased chain with cooling schedule
194
def run_fairness_optimization(initial_partition, steps=10000):
195
current_temp = 1.0
196
cooling_rate = 0.95
197
198
chain_results = []
199
partition = initial_partition
200
201
for step in range(steps):
202
# Create acceptance function with current temperature
203
def temp_accept(p):
204
return fairness_biased_accept(p, temperature=current_temp)
205
206
# Run short chain segment
207
chain = MarkovChain(
208
proposal=recom,
209
constraints=constraints,
210
accept=temp_accept,
211
initial_state=partition,
212
total_steps=100
213
)
214
215
# Get final state and cool temperature
216
for state in chain:
217
partition = state
218
219
chain_results.append(partition)
220
current_temp *= cooling_rate
221
222
if step % 1000 == 0:
223
eg = efficiency_gap(partition["election"])
224
print(f"Step {step}: EG = {eg:.4f}, Temp = {current_temp:.3f}")
225
226
return chain_results
227
228
# Quality threshold chain
229
def run_quality_filtered_chain(initial_partition):
230
"""Run chain that only accepts high-quality partitions."""
231
232
def quality_accept(p):
233
# Combine multiple quality criteria
234
return (compactness_threshold_accept(p, min_compactness=0.4) and
235
abs(efficiency_gap(p["election"])) < 0.05) # Low partisan bias
236
237
chain = MarkovChain(
238
proposal=recom,
239
constraints=constraints,
240
accept=quality_accept,
241
initial_state=initial_partition,
242
total_steps=5000
243
)
244
245
high_quality_plans = []
246
for state in chain:
247
high_quality_plans.append(state)
248
249
return high_quality_plans
250
```
251
252
### Advanced Acceptance Patterns
253
254
Examples of sophisticated acceptance strategies for research applications:
255
256
```python
257
# Adaptive acceptance based on chain performance
258
class AdaptiveAcceptance:
259
def __init__(self, base_acceptance=always_accept, adaptation_rate=0.01):
260
self.base_acceptance = base_acceptance
261
self.adaptation_rate = adaptation_rate
262
self.recent_scores = []
263
self.acceptance_rate = 1.0
264
265
def __call__(self, partition):
266
# Track performance
267
if hasattr(partition, 'parent') and partition.parent:
268
score = self.calculate_quality(partition)
269
self.recent_scores.append(score)
270
271
# Keep only recent history
272
if len(self.recent_scores) > 100:
273
self.recent_scores.pop(0)
274
275
# Adapt acceptance rate based on improvement
276
if len(self.recent_scores) > 10:
277
recent_trend = (self.recent_scores[-1] - self.recent_scores[-10])
278
if recent_trend > 0: # Improving
279
self.acceptance_rate = min(1.0, self.acceptance_rate + self.adaptation_rate)
280
else: # Not improving
281
self.acceptance_rate = max(0.1, self.acceptance_rate - self.adaptation_rate)
282
283
# Apply adaptive acceptance
284
if random.random() > self.acceptance_rate:
285
return False
286
287
return self.base_acceptance(partition)
288
289
def calculate_quality(self, partition):
290
# Define quality metric (example)
291
fairness = 1.0 - abs(efficiency_gap(partition["election"]))
292
return fairness
293
294
# Ensemble acceptance for robust sampling
295
def ensemble_accept(partition, acceptance_functions, weights=None):
296
"""
297
Combine multiple acceptance functions with voting.
298
"""
299
if weights is None:
300
weights = [1.0] * len(acceptance_functions)
301
302
votes = []
303
for accept_func, weight in zip(acceptance_functions, weights):
304
vote = accept_func(partition)
305
votes.append(weight if vote else 0)
306
307
# Accept if weighted average exceeds threshold
308
total_weight = sum(weights)
309
weighted_score = sum(votes) / total_weight
310
311
return weighted_score > 0.5 # Majority rule
312
```
313
314
## Types
315
316
```python { .api }
317
AcceptanceFunction = Callable[[Partition], bool]
318
Temperature = float # For simulated annealing
319
Probability = float # Between 0 and 1
320
```