Path Weight Sampling: Exact Monte Carlo Computation of the Mutual Information between Stochastic Trajectories

Abstract

Most natural and engineered information-processing systems transmit information via signals that vary in time. Computing the information transmission rate or the information encoded in the temporal characteristics of these signals, requires the mutual information between the input and output signals as a function of time, i.e. between the input and output trajectories. Yet, this is notoriously difficult because of the high-dimensional nature of the trajectory space, and all existing techniques require approximations. We present an exact Monte Carlo technique called Path Weight Sampling (PWS) that, for the first time, makes it possible to compute the mutual information between input and output trajectories for any stochastic system that is described by a master equation. The principal idea is to use the master equation to evaluate the exact conditional probability of an individual output trajectory for a given input trajectory, and average this via Monte Carlo sampling in trajectory space to obtain the mutual information. We present three variants of PWS, which all generate the trajectories using the standard stochastic simulation algorithm. While Direct PWS is a brute-force method, Rosenbluth-Rosenbluth PWS exploits the analogy between signal trajectory sampling and polymer sampling, and Thermodynamic Integration PWS is based on a reversible work calculation in trajectory space. PWS also makes it possible to compute the mutual information between input and output trajectories for systems with hidden internal states as well as systems with feedback from output to input. Applying PWS to the bacterial chemotaxis system, consisting of 182 coupled chemical reactions, demonstrates not only that the scheme is highly efficient, but also that the number of receptor clusters is much smaller than hitherto believed, while their size is much larger.

arXiv comment19 pages (+ 14 pages appendix), 9 figures

References in corpus (29)

• Measuring Information Transfer
• Statistical physics of social dynamics
• Estimating Mutual Information
• Traffic and Related Self-Driven Many-Particle Systems
• Path ensembles averages in systems driven far-from-equilibrium
• A Novel Path Sampling Method for the Calculation of Rate Constants
• Simulating rare events in equilibrium or non-equilibrium stochastic systems
• Information flow and optimization in transcriptional control
• Effective Sample Size for Importance Sampling based on discrepancy measures
• Mutual information between in- and output trajectories of biochemical networks
• Information transmission in genetic regulatory networks: a review
• Mutual Information Rate-Based Networks in Financial Markets
• Growth dynamics and the evolution of cooperation in microbial populations
• E. coli chemotaxis is information-limited
• Master equations and the theory of stochastic path integrals
• Fast MCMC sampling for Markov jump processes and extensions
• Estimating the entropy of binary time series: Methodology, some theory and a simulation study
• Mutual information in time-varying biochemical systems
• Simulation from endpoint-conditioned, continuous-time Markov chains on a finite state space, with applications to molecular evolution
• Capacity of a Simple Intercellular Signal Transduction Channel
• A stochastic spectral analysis of transcriptional regulatory cascades
• The free energy cost of reducing noise while maintaining a high sensitivity
• Dynamics of cooperativity in chemical sensing among cell-surface receptors
• Stochastic actions for diffusive dynamics: Reweighting, sampling, and minimization
• Quasispecies theory for finite populations
• Non-Stationary Forward Flux Sampling
• Bayesian estimation of discretely observed multi-dimensional diffusion processes using guided proposals
• Estimating information in time-varying signals
• The behaviour of information flow near criticality

Cited by in corpus (6)

• Tuning transduction from hidden observables to optimize information harvesting
• Stochastic Distinguishability of Markovian Trajectories
• Weak transcription factor clustering at binding sites can facilitate information transfer from molecular signals
• Characterizing the non-monotonic behavior of mutual information along biochemical reaction cascades
• Optimizing information transmission in optogenetic Wnt signaling
• Unravelling the Flow of Information in a Nonequilibrium Process in the Presence of Hydrodynamic Interactions