Variance-reduced simulation of lattice Markov chains

Maginnis, Peter A.

Permalink

https://hdl.handle.net/2142/101032 Copy

Description

Title

Variance-reduced simulation of lattice Markov chains

Author(s)

Maginnis, Peter A.

Issue Date

2018-04-20

Director of Research (if dissertation) or Advisor (if thesis)

• West, Matthew
• Dullerud, Geir E.

Doctoral Committee Chair(s)

• West, Matthew
• Dullerud, Geir E.

Committee Member(s)

• Srikant, Rayadurgam
• Anderson, David F.
• Aluru, Narayana

Department of Study

Mechanical Sci & Engineering

Discipline

Mechanical Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Markov chains
• variance-reduction
• antithetic simulation
• Monte Carlo

Abstract

The focus of this dissertation is on reducing the cost of Monte Carlo estimation for lattice-valued Markov chains. We achieve this goal by manipulating the random inputs to stochastic processes (Poisson random variables in the discrete-time setting and Poisson processes in continuous-time) such that they become negatively correlated with some of their cohort while their individual marginal distributions are completely unaltered. In this way, we preserve the convergence properties of the Law of Large Numbers, but mean estimates, say, constructed from these sample paths exhibit dramatically reduced variance. The work is comprised of three main parts. First, we introduce algorithms to reduce the simulation costs for discrete-time Markov chains. We describe how to modify the simulation of sample trajectories that introduces negative correlation while introducing no additional computational cost and that are compatible with existing codes. We support this algorithm with theoretical results, including guarantee that such mean estimators will be unbiased and consistent with respect to the discrete-time distribution. Further, we prove a recursive relation that characterizes the evolution of mutual negative covariance over time in the general case as well as prove a sufficient condition in the case of linear rate functions. Lastly, we present several numerical experiments that demonstrate multiple orders-of-magnitude reduction in mean-square error (MSE) for both linear and nonlinear reaction rate systems. In the next part, we show how insights gained from the discrete-time case can be used to inform a related approach in continuous-time. In these cases, we rely on a formulation of these lattice Markov chains called the random-time change representation. This allows us to translate the general problem of simulating anticorrelated trajectories of a given lattice Markov chain into the simpler problem of simulating anticorrelated pairs of unit-rate Poisson processes, which are the fundamental source of randomness that are input into random time-change representations. We systematically construct and analyze algorithms to produce negatively correlated, identically distributed Poisson processes. We prove closed form expressions for the MSE evolution of one of these systems, as well as present asymptotic performance lower bounds. We then show how to use these anticorrelated Poisson processes to simulate exact, identically distributed stochastic processes which are now significantly negatively correlated, and are thus suitable for variance-reduced Monte Carlo. Numerical experiments on both linear and nonlinear systems demonstrate order-of-magnitude cost reduction. We also introduce error vs cost comparisons with existing standard methods. Finally, we present extensions and refinements of the above algorithms. First is an approach to discrete- time simulation (specifically for tau-leaping systems) that leverages insights gained from the continuous-time approach in order to further strengthen the performance of the original algorithm in its weakest regime. This algorithm inherits several desirable properties from the antithetic discrete-time simulation case. In addition, we present numerical studies that show where this refinement outperforms the original algorithm. Finally, we present extensions of the anticorrelated simulation algorithms into both model predictive control and particle filtering.

Graduation Semester

2018-05

Type of Resource

text

Permalink

http://hdl.handle.net/2142/101032

Copyright and License Information

Copyright 2018 Peter Maginnis

Owning Collections