en>Monkbot: Fix CS1 deprecated date parameter errors

2014-01-28T13:09:48Z

Fix CS1 deprecated date parameter errors

New page

In [[probability theory]], '''uniformization''' method, (also known as '''Jensen's method'''<ref name="stewart" /> or the '''randomization method'''<ref name="ibe">{{cite book |title=Markov processes for stochastic modeling |last=Ibe |first=Oliver C. |year=2009 |publisher=[[Academic Press]] |isbn=0-12-374451-2 |page=98}}</ref>) is a method to compute transient solutions of finite state [[continuous-time Markov chain]]s, by approximating the process by a [[discrete time Markov chain]].<ref name="ibe" /> The original chain is scaled by the fastest transition rate ''γ'', so that transitions occur at the same rate in every state, hence the name ''uniform''isation. The method is simple to program and efficiently calculates an approximation to the transient distribution at a single point in time (near zero).<ref name="stewart" /> The method was first introduced by Grassman in 1977.<ref>{{cite jstor|172104}}</ref><ref>{{cite doi|10.1016/0305-0548(77)90007-7}}</ref><ref>{{cite doi|10.1016/0377-2217(77)90049-2}}</ref>

==Method description==

For a continuous time Markov chain with [[transition rate matrix]] ''Q'', the uniformized discrete time Markov chain has probability transition matrix <math>P:=(p_{ij})_{i,j}</math>, which is defined by<ref name="stewart">{{cite book |title=Probability, Markov chains, queues, and simulation: the mathematical basis of performance modeling|last=Stewart |first=William J. |year=2009 |publisher=[[Princeton University Press]] |isbn=0-691-14062-6 |page=361}}</ref><ref name="cass">{{cite book |title=Introduction to discrete event systems|last=Cassandras |first=Christos G. |last2=Lafortune| first2=Stéphane|year=2008 |publisher=Springer |isbn=0-387-33332-0}}</ref><ref name="ross">{{cite book |title=Introduction to probability models|last=Ross |first=Sheldon M. |year=2007 |publisher=Academic Press |isbn=0-12-598062-0}}</ref>

::<math>p_{ij} = \begin{cases} q_{ij}/\gamma &\text{ if } i \neq j \\ 1 - \sum_{j \neq i} q_{ij}/\gamma &\text{ if } i=j \end{cases}</math>

with ''γ'', the uniform rate parameter, chosen such that

::<math>\gamma \geq \max_i |q_{ii}|.</math>

In matrix notation:

::<math>P=Id+\frac{1}{\gamma}Q.</math>

For a starting distribution π(0), the distribution at time ''t'', π(''t'') is computed by<ref name="stewart" />

::<math>\pi(t) = \sum_{n=0}^\infty \pi(0) P^n \frac{(\gamma t)^n}{n!}e^{-\gamma t}.</math>

This representation shows, that a continuous time Markov Chain can be described by a discrete Markov Chain with transition matrix ''P'' as defined above where jumps occur according to a Poisson Process with intensity γt.

In practice this [[series (mathematics)|series]] is terminated after finitely many terms.

==Implementation==

[[Pseudocode]] for the algorithm is included in Appendix A of Reibman and Trivedi's 1988 paper.<ref name="reibman">{{cite doi|10.1016/0305-0548(88)90026-3}}</ref> Using a [[parallel algorithm|parallel]] version of the algorithm, chains with state spaces of larger than 10<sup>7</sup> have been analysed.<ref>{{cite doi|10.1016/j.jpdc.2004.03.017}}</ref>

==Limitations==

Reibman and Trivedi state that "uniformization is the method of choice for typical problems," though they note that for [[stiff equation|stiff]] problems some tailored algorithms are likely to perform better.<ref name="reibman" />

==External links==
*[http://www.sis.pitt.edu/~dtipper/2130/unifm.m Matlab implementation]

==Notes==

{{Reflist}}

[[Category:Queueing theory]]
[[Category:Stochastic processes]]
[[Category:Markov processes]]

Phone hacking - Revision history

en>Monkbot: Fix CS1 deprecated date parameter errors