Featured
Recursive Stochastic Counting: the Nesting Doll Method
Posted on 8 mins
Ok, I know I sound like a broken record, but I really really want to figure out a way to count the districtings of the 10 x 10 grid graph. And this problem feels within reach!
See here for context and a previous attempt at this.
Genealogy of this Idea.
The idea for this chain was partially inspired by section 14.4 of Levin & Peres [1], which itself attributes the original idea to Jerrum & Sinclair [2]. These publications gave a method to “approximately count” the number of proper \(q\)-colorings of a graph \(G\) of \(n\) vertices with maximal degree \(Δ\). They name \(𝒳\) the set of all proper \(q\)-colorings of \(G\), and they name the vertices of \(G\) as \( \lbrace v_1,…,v_n\rbrace\). Then, fixing a coloring \(x_0 \in 𝒳\), they define
Probabilistically Counting the Districtings of a Graph
Posted on 13 mins
Given a planar graph \(G = (V,E)\) and district sizes \(\lbrace k_i\rbrace_{i=1}^n\), a political districting of \(G = (V,E)\) is a partition \(\lbrace P_i\rbrace_{i=1}^n\) of \(G\) into (simply-)connected subgraphs (called districts) satisfying \(|P_i|=k_i\).
For the purposes of this project, I’ve usually taken \(G\) be an \(n\times n\) grid graph and \(k_i=n\) for all \(i\); but this was a choice made of convenience, not necessity. This project explores a method to stochastically estimate the number of districtings of \(G\) when enumerating them is not computationally viable.