Sequential Monte Carlo for Sampling Balanced and Compact Redistricting Plans

Random sampling of graph partitions under constraints has become a popular tool for evaluating legislative redistricting plans. Analysts detect partisan gerrymandering by comparing a proposed redistricting plan with an ensemble of sampled alternative plans. For successful application, sampling methods must scale to large maps with many districts, incorporate realistic legal constraints, and accurately and efficiently sample from a selected target distribution. Unfortunately, most existing methods struggle in at least one of these three areas. We present a new Sequential Monte Carlo (SMC) algorithm that draws representative redistricting plans from a realistic target distribution of choice. Because it samples directly, the SMC algorithm can efficiently explore the relevant space of redistricting plans better than the existing Markov chain Monte Carlo algorithms that yield dependent samples. Our algorithm can simultaneously incorporate several constraints commonly imposed in real-world redistricting problems, including equal population, compactness, and preservation of administrative boundaries. We validate the accuracy of the proposed algorithm by using a small map where all redistricting plans can be enumerated. We then apply the SMC algorithm to evaluate the partisan implications of several maps submitted by relevant parties in a recent high-profile redistricting case in the state of Pennsylvania. We find that the proposed algorithm is roughly 40 times more efficient in sampling from the target distribution than a state-of-the-art MCMC algorithm. Open-source software is available for implementing the proposed methodology.

Markov-chain Monte-Carlo Sampling for Optimal Fidelity Determination in Dynamic Decision-Making

Decision making for dynamic systems is challenging due to the scale and dynamicity of such systems, and it is comprised of decisions at strategic, tactical, and operational levels. One of the most important aspects of decision making is incorporating real time information that reflects immediate status of the system. This type of decision making, which may apply to any dynamic system, needs to comply with the systems current capabilities and calls for a dynamic data driven planning framework. Performance of dynamic data driven planning frameworks relies on the decision making process which in return is relevant to the quality of the available data. This means that the planning framework should be able to set the level of decision making based on the current status of the system, which is learned through the continuous readings of sensory data. In this work, a Markov chain Monte Carlo sampling method is proposed to determine the optimal fidelity of decision making in a dynamic data driven framework. To evaluate the performance of the proposed method, an experiment is conducted, where the impact of workers performance on the production capacity and the fidelity level of decision making are studied.

Monte Carlo Renormalization of the 3-D Ising model: Analyticity and Convergence

We review the assumptions on which the Monte Carlo renormalization technique is based, in particular the analyticity of the block spin transformations. On this basis, we select an optimized Kadanoff blocking rule in combination with the simulation of a d=3 Ising model with reduced corrections to scaling. This is achieved by including interactions with second and third neighbors. As a consequence of the improved analyticity properties, this Monte Carlo renormalization method yields a fast convergence and a high accuracy. The results for the critical exponents are y_H=2.481(1) and y_T=1.585(3).

Greens Function Monte Carlo study of SU(3) lattice gauge theory in (3+1)D

A `forward walking Greens Function Monte Carlo algorithm is used to obtain expectation values for SU(3) lattice Yang-Mills theory in (3+1) dimensions. The ground state energy and Wilson loops are calculated, and the finite-size scaling behaviour is explored. Crude estimates of the string tension are derived, which agree with previous results at intermediate couplings; but more accurate results for larger loops will be required to establish scaling behaviour at weak coupling.