Over the past two weeks, I have worked towards formalizing my project goals. The idea I had initially for my project fell through when the data was not easily accessible. With the help of Dr. Dunbar and BMVP, I was able to pivot to another topic. In addition to formalizing a project, I have spent time learning about recombination Markov chains. I have also been working on this website. I did not know any HTML coming into this, so I have learned a lot about this too!

The first step in my project was to gather data on Wisconsin Wards, which will be needed to create adjacency graphs to build maps. I have also been looking at the Wisconsin Elections Commission site to see what voter data is available at the ward level. This will shape how a user may eventually interact with the results. I have also been considering how I might store my data to best suit the end product.

This week has been a bit slow for me, but I did begin working on understanding the algorithms on smaller examples. Using square grids, the adjacency lists are much easier to create, so I have been working on looking at graph decomposition for those examples. Dr. Dunbar has created a few more examples, split into color districts, for me to begin working on creating random walks for. These will also help me work on the map visualization.

I have a graph! This week felt like the first time the mathematics of my project really became tangible. Up to this point, I had been reading about recombination Markov chains and working through small graph examples somewhat abstractly. Now, I am actually implementing the algorithm step by step: merging adjacent districts, constructing a spanning tree of the combined region, and cutting random edges to create new connected districts. Watching this process unfold on a 5x5 and 50x50 grid has made the theory feel much more concrete. From a mathematical standpoint, the spanning tree construction has been especially interesting to me. Enforcing contiguity in a redistricting algorithm is powerful. When randomly cutting one edge of the tree, the structure immediately decomposes into connected components. On a more personal level, this week involved a lot of debugging and restructuring. I had to carefully think about how adjacency lists, district labels, and JSON files interact. Getting the algorithm to update district assignments correctly and then render them visually forced me to be precise about how data flows through my program. Once this works consistently on grid examples, I will feel much more confident scaling the algorithm to Wisconsin ward data.

This week, I have discovered a massive flaw in my algorithm. This did not occur to me until I tested enough cases on my 50x50 grid below. The initial districting for the examples below was equal columns of 5 colors. I was finding that my 50x50 grid district maps were very consistently red. I had some trouble rationalizing this because red was the leftmost initial column, meaning it had fewer adjacencies than the center columns. This was happening because I was using a BFS spanning tree to make a random cut into two components. This has a very high probability of cutting very unevenly sized districts. I have not yet introduced a population component to ensure equally sized districts; however, that would have likely failed anyway. Not all trees are guaranteed to have a cut edge that would produce equal subgraphs. I have a few other options for how I can accomplish this task.

Another set of options I am considering involves moving away from cutting spanning trees altogether and instead redefining the transition step of the Markov chain. One possibility is to implement a flip-based method, where border vertices are swapped between adjacent districts. I would need to enforce connectivity and approximate population balance at each step. Although flips are more local and may mix more slowly than large recombination moves, they are well understood and avoid the structural imbalance issues inherent in random tree cuts. A second alternative would be a growth-based approach. I could start from a boundary node and grow a district outward until a target population is reached. Finally, there may be a hybrid strategy that selectively searches for more interior edges in a spanning tree. By walking inward from terminal vertices, cuts are more likely to produce balanced components. I am trying to figure out which option will be the most feasible for this project

I like trees again! This week I began looking into Wilson's algorithm as a way to generate better spanning trees. In my earlier approach, I was using a BFS tree, which introduced a lot of structure and bias. Wilson's algorithm instead produces a uniform spanning tree, meaning every possible spanning tree of the graph is equally likely. It works by performing random walks. Starting from an arbitrary root vertex, a random walk begins from another randomly selected vertex and continues until it hits the existing tree. If the walk forms a loop, the loop is erased. The resulting path is then added to the tree, and this process repeats until all vertices are included. While this fixes the bias in the tree generation, it does not solve the problem of uneven cuts. Even with a perfectly random spanning tree, most edges separate very small subtrees from the rest of the graph. To address this, I am experimenting with selecting only edges that produce near-equal components when cut. This should help ensure that recombination steps actually generate districts of comparable size, rather than repeatedly creating very uneven partitions. I will likely need to find a more efficient way to do this.