Building N Birds With 1 Store: Parallel Simulations of Stochastic Evolutionary Processes

Abstract

Stochastic processes are used to study the dynamics of evolution in finite, structured populations. Simulations of such processes provide a useful tool for their study, but are currently limited by computational speed and memory bottlenecks, even when naively parallelized. This thesis proposes two novel parallelization methods for simulating a particular class of evolutionary processes known as "games on graphs." The theoretical speed-up and scalability of these methods is analyzed across various parameters. A novel approximate parallel method is also proposed, which allows for further speed-up at the expense of some accuracy. Discussion of implementation considerations follows, and a resulting implementation in Python is used to provide empirical performance results which match closely with theoretical ones. Applications are suggested for a variety of open problems in biology, behavioral economics, political science, and linguistics.