Piecewise-deterministic Markov process

Last updated

In probability theory, a piecewise-deterministic Markov process (PDMP) is a process whose behaviour is governed by random jumps at points in time, but whose evolution is deterministically governed by an ordinary differential equation between those times. The class of models is "wide enough to include as special cases virtually all the non-diffusion models of applied probability." [1] The process is defined by three quantities: the flow, the jump rate, and the transition measure. [2]

Contents

The model was first introduced in a paper by Mark H. A. Davis in 1984. [1]

Examples

Piecewise linear models such as Markov chains, continuous-time Markov chains, the M/G/1 queue, the GI/G/1 queue and the fluid queue can be encapsulated as PDMPs with simple differential equations. [1]

Applications

PDMPs have been shown useful in ruin theory, [3] queueing theory, [4] [5] for modelling biochemical processes such as DNA replication in eukaryotes and subtilin production by the organism B. subtilis, [6] and for modelling earthquakes. [7] Moreover, this class of processes has been shown to be appropriate for biophysical neuron models with stochastic ion channels. [8]

Properties

Löpker and Palmowski have shown conditions under which a time reversed PDMP is a PDMP. [9] General conditions are known for PDMPs to be stable. [10]

Galtier et al. [11] studied the law of the trajectories of PDMP and provided a reference measure in order to express a density of a trajectory of the PDMP. Their work opens the way to any application using densities of trajectory. (For instance, they used the density of a trajectories to perform importance sampling, this work was further developed by Chennetier and Al. [12] to estimate the reliability of industrial systems.)

See also

Related Research Articles

<span class="mw-page-title-main">Queueing theory</span> Mathematical study of waiting lines, or queues

Queueing theory is the mathematical study of waiting lines, or queues. A queueing model is constructed so that queue lengths and waiting time can be predicted. Queueing theory is generally considered a branch of operations research because the results are often used when making business decisions about the resources needed to provide a service.

In statistics, Markov chain Monte Carlo (MCMC) is a class of algorithms used to draw samples from a probability distribution. Given a probability distribution, one can construct a Markov chain whose elements' distribution approximates it – that is, the Markov chain's equilibrium distribution matches the target distribution. The more steps that are included, the more closely the distribution of the sample matches the actual desired distribution.

A hybrid system is a dynamical system that exhibits both continuous and discrete dynamic behavior – a system that can both flow and jump. Often, the term "hybrid dynamical system" is used, to distinguish over hybrid systems such as those that combine neural nets and fuzzy logic, or electrical and mechanical drivelines. A hybrid system has the benefit of encompassing a larger class of systems within its structure, allowing for more flexibility in modeling dynamic phenomena.

A mathematical or physical process is time-reversible if the dynamics of the process remain well-defined when the sequence of time-states is reversed.

In queueing models, a discipline within the mathematical theory of probability, the quasi-birth–death process describes a generalisation of the birth–death process. As with the birth-death process it moves up and down between levels one at a time, but the time between these transitions can have a more complicated distribution encoded in the blocks.

Jump diffusion is a stochastic process that involves jumps and diffusion. It has important applications in magnetic reconnection, coronal mass ejections, condensed matter physics, option pricing, and pattern theory and computational vision.

In queueing theory, a discipline within the mathematical theory of probability, Burke's theorem is a theorem asserting that, for the M/M/1 queue, M/M/c queue or M/M/∞ queue in the steady state with arrivals is a Poisson process with rate parameter λ:

  1. The departure process is a Poisson process with rate parameter λ.
  2. At time t the number of customers in the queue is independent of the departure process prior to time t.

In probability theory, a product-form solution is a particularly efficient form of solution for determining some metric of a system with distinct sub-components, where the metric for the collection of components can be written as a product of the metric across the different components. Using capital Pi notation a product-form solution has algebraic form

<span class="mw-page-title-main">Fork–join queue</span> Type of queue

In queueing theory, a discipline within the mathematical theory of probability, a fork–join queue is a queue where incoming jobs are split on arrival for service by numerous servers and joined before departure. The model is often used for parallel computations or systems where products need to be obtained simultaneously from different suppliers. The key quantity of interest in this model is usually the time taken to service a complete job. The model has been described as a "key model for the performance analysis of parallel and distributed systems." Few analytical results exist for fork–join queues, but various approximations are known.

<span class="mw-page-title-main">Two-state trajectory</span>

A two-state trajectory is a dynamical signal that fluctuates between two distinct values: ON and OFF, open and closed, , etc. Mathematically, the signal has, for every either the value or .

In queueing theory, a discipline within the mathematical theory of probability, a fluid queue is a mathematical model used to describe the fluid level in a reservoir subject to randomly determined periods of filling and emptying. The term dam theory was used in earlier literature for these models. The model has been used to approximate discrete models, model the spread of wildfires, in ruin theory and to model high speed data networks. The model applies the leaky bucket algorithm to a stochastic source.

Mark Herbert Ainsworth Davis was Professor of Mathematics at Imperial College London. He made fundamental contributions to the theory of stochastic processes, stochastic control and mathematical finance.

In queueing theory, a discipline within the mathematical theory of probability, an M/G/k queue is a queue model where arrivals are Markovian, service times have a General distribution and there are k servers. The model name is written in Kendall's notation, and is an extension of the M/M/c queue, where service times must be exponentially distributed and of the M/G/1 queue with a single server. Most performance metrics for this queueing system are not known and remain an open problem.

In probability theory, reflected Brownian motion is a Wiener process in a space with reflecting boundaries. In the physical literature, this process describes diffusion in a confined space and it is often called confined Brownian motion. For example it can describe the motion of hard spheres in water confined between two walls.

In queueing theory, a discipline within the mathematical theory of probability, a fluid limit, fluid approximation or fluid analysis of a stochastic model is a deterministic real-valued process which approximates the evolution of a given stochastic process, usually subject to some scaling or limiting criteria.

Mean-field particle methods are a broad class of interacting type Monte Carlo algorithms for simulating from a sequence of probability distributions satisfying a nonlinear evolution equation. These flows of probability measures can always be interpreted as the distributions of the random states of a Markov process whose transition probabilities depends on the distributions of the current random states. A natural way to simulate these sophisticated nonlinear Markov processes is to sample a large number of copies of the process, replacing in the evolution equation the unknown distributions of the random states by the sampled empirical measures. In contrast with traditional Monte Carlo and Markov chain Monte Carlo methods these mean-field particle techniques rely on sequential interacting samples. The terminology mean-field reflects the fact that each of the samples interacts with the empirical measures of the process. When the size of the system tends to infinity, these random empirical measures converge to the deterministic distribution of the random states of the nonlinear Markov chain, so that the statistical interaction between particles vanishes. In other words, starting with a chaotic configuration based on independent copies of initial state of the nonlinear Markov chain model, the chaos propagates at any time horizon as the size the system tends to infinity; that is, finite blocks of particles reduces to independent copies of the nonlinear Markov process. This result is called the propagation of chaos property. The terminology "propagation of chaos" originated with the work of Mark Kac in 1976 on a colliding mean-field kinetic gas model.

<span class="mw-page-title-main">Richard H. Stockbridge</span>

Richard H. Stockbridge is a Distinguished Professor of Mathematics at the University of Wisconsin-Milwaukee. His contributions to research primarily involve stochastic control theory, optimal stopping and mathematical finance. Most notably, alongside Professors Thomas G. Kurtz, Kurt Helmes, and Chao Zhu, he developed the methodology of using linear programming to solve stochastic control problems.

<span class="mw-page-title-main">Damir Filipović</span> Swiss mathematician

Damir Filipović is a Swiss mathematician specializing in quantitative finance. He holds the Swissquote Chair in Quantitative Finance and is the director of the Swiss Finance Institute at EPFL.

Amber Lynn Puha is an American mathematician and educator at California State University San Marcos. Her research concerns probability theory and stochastic processes.

<span class="mw-page-title-main">Eugene A. Feinberg</span> American applied mathematician

Eugene A. Feinberg is an American mathematician and distinguished professor of applied mathematics and statistics at Stony Brook University. He is noted for his work in probability theory, real analysis, and Markov decision processes.

References

  1. 1 2 3 Davis, M. H. A. (1984). "Piecewise-Deterministic Markov Processes: A General Class of Non-Diffusion Stochastic Models". Journal of the Royal Statistical Society. Series B (Methodological). 46 (3): 353–388. doi:10.1111/j.2517-6161.1984.tb01308.x. JSTOR   2345677.
  2. ↑ Costa, O. L. V.; Dufour, F. (2010). "Average Continuous Control of Piecewise Deterministic Markov Processes". SIAM Journal on Control and Optimization. 48 (7): 4262. arXiv: 0809.0477 . doi:10.1137/080718541. S2CID   14257280.
  3. ↑ Embrechts, P.; Schmidli, H. (1994). "Ruin Estimation for a General Insurance Risk Model". Advances in Applied Probability. 26 (2): 404–422. doi:10.2307/1427443. JSTOR   1427443. S2CID   124108500.
  4. ↑ Browne, Sid; Sigman, Karl (1992). "Work-Modulated Queues with Applications to Storage Processes". Journal of Applied Probability. 29 (3): 699–712. doi:10.2307/3214906. JSTOR   3214906. S2CID   122273001.
  5. ↑ Boxma, O.; Kaspi, H.; Kella, O.; Perry, D. (2005). "On/off Storage Systems with State-Dependent Input, Output, and Switching Rates". Probability in the Engineering and Informational Sciences. 19: 1–14. CiteSeerX   10.1.1.556.6718 . doi:10.1017/S0269964805050011. S2CID   24065678.
  6. ↑ Cassandras, Christos G.; Lygeros, John (2007). "Chapter 9. Stochastic Hybrid Modeling of Biochemical Processes" (PDF). Stochastic Hybrid Systems. CRC Press. ISBN   9780849390838.
  7. ↑ Ogata, Y.; Vere-Jones, D. (1984). "Inference for earthquake models: A self-correcting model". Stochastic Processes and Their Applications. 17 (2): 337. doi: 10.1016/0304-4149(84)90009-7 .
  8. ↑ Pakdaman, K.; Thieullen, M.; Wainrib, G. (September 2010). "Fluid limit theorems for stochastic hybrid systems with application to neuron models". Advances in Applied Probability. 42 (3): 761–794. arXiv: 1001.2474 . doi:10.1239/aap/1282924062. S2CID   18894661.
  9. ↑ Löpker, A.; Palmowski, Z. (2013). "On time reversal of piecewise deterministic Markov processes". Electronic Journal of Probability. 18. arXiv: 1110.3813 . doi:10.1214/EJP.v18-1958. S2CID   1453859.
  10. ↑ Costa, O. L. V.; Dufour, F. (2008). "Stability and Ergodicity of Piecewise Deterministic Markov Processes" (PDF). SIAM Journal on Control and Optimization. 47 (2): 1053. doi:10.1137/060670109.
  11. ↑ Galtier, T. (2019). "On the optimal importance process for piecewise deterministic Markov process". Esaim: Ps. 23: 893–921. doi: 10.1051/ps/2019015 . S2CID   198467101.
  12. ↑ Chennetier, G. (2022). "Adaptive importance sampling based on fault tree analysis for piecewise deterministic Markov process". arXiv: 2210.16185 [stat.CO].
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.