Stochastic simulation | EPFL Graph Search

A stochastic simulation is a simulation of a system that has variables that can change stochastically (randomly) with individual probabilities. Realizations of these random variables are generated and inserted into a model of the system. Outputs of the model are recorded, and then the process is repeated with a new set of random values. These steps are repeated until a sufficient amount of data is gathered. In the end, the distribution of the outputs shows the most probable estimates as well as a frame of expectations regarding what ranges of values the variables are more or less likely to fall in. Often random variables inserted into the model are created on a computer with a random number generator (RNG). The U(0,1) uniform distribution outputs of the random number generator are then transformed into random variables with probability distributions that are used in the system model. Etymology Stochastic originally meant "pertaining to conjecture";

Minimizing Generalized Buchi Automata

Sudeep Juvekar

We consider the problem of minimization of generalized Buchi automata. We show how to extend fair simulation and delayed simulation to the case where the Buchi automaton has multiple acceptance conditions. For fair simulation, we show how to efficiently compute the fair-simulation relation while maintaining the structure of the automaton. We then use the fair-simulation relation to merge states and remove transitions. Our fair-simulation algorithm works in time

O(mn^2k^2)

where

m

is the number of transitions,

n

is the number of states, and

k

is the number of acceptance sets. For delayed simulation, we extend the existing definition to the case of multiple acceptance condition. We show that our definition can indeed be used for minimization and give an algorithm that computes the delayed-simulation relation. Our delayed-simulation algorithm works in time

O(mn^2k)

. We implemented the two algorithms and report on experimental results.

2005

Treatment of long-range interactions arising in the Enskog-Vlasov description of dense fluids

Mohammadhossein Gorji

The kinetic theory of rarefied gases and numerical schemes based on the Boltzmann equation, have evolved to the cornerstone of non-equilibrium gas dynamics. However, their counterparts in the dense regime remain rather exotic for practical non-continuum scenarios. This problem is partly due to the fact that long-range interactions arising from the attractive tail of molecular potentials, lead to a computationally demanding Vlasov integral. This study focuses on numerical remedies for efficient stochastic particle simulations based on the Enskog–Vlasov kinetic equation. In particular, we devise a Poisson type elliptic equation which governs the underlying long-range interactions. The idea comes through fitting a Green function to the molecular potential, and hence deriving an elliptic equation for the associated fundamental solution. Through this transformation of the Vlasov integral, efficient Poisson type solvers can be readily employed in order to compute the mean field forces. Besides the technical aspects of different numerical schemes for treatment of the Vlasov integral, simulation results for evaporation of a liquid slab into the vacuum are presented. It is shown that the proposed formulation leads to accurate predictions with a reasonable computational cost.

2018

Fast Adaptive Uniformization for the Chemical Master Equation

Maria-Emanuela-Canini Mateescu, Verena Wolf

Within systems biology there is an increasing interest in the stochastic behavior of biochemical reaction networks. An appropriate stochastic description is provided by the chemical master equation, which represents a continuous-time Markov chain (CTMC). Standard Uniformization (SU) is an efficient method for the transient analysis of CTMCs. For systems with very different time scales, such as biochemical reaction networks, SU is computationally expensive. In these cases, a variant of SU, called adaptive uniformization (AU), is known to reduce the large number of iterations needed by SU. The additional difficulty of AU is that it requires the solution of a birth process. In this paper we present an on-the-fly variant of AU, where we improve the original algorithm for AU at the cost of a small approximation error. By means of several examples, we show that our approach is particularly well-suited for biochemical reaction networks.

Ieee Computer Soc Press, Customer Service Center, Po Box 3014, 10662 Los Vaqueros Circle, Los Alamitos, Ca 90720-1264 Usa2009