Uniformization (probability theory): Difference between revisions

Revision as of 02:19, 29 October 2020

Revision as of 00:06, 15 December 2020

Line 1:

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 |url=https://archive.org/details/markovprocessesf00ibeo |url-access=limited |last=Ibe |first=Oliver C. |year=2009 |publisher=[[Academic Press]] |isbn=0-12-374451-2 |page=[https://archive.org/details/markovprocessesf00ibeo/page/n112 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. 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 Winfried Grassmann in 1977.<ref>{{Cite journal | last1 = Gross | first1 = D. | last2 = Miller | first2 = D. R. | title = The Randomization Technique as a Modeling Tool and Solution Procedure for Transient Markov Processes | journal = Operations Research | volume = 32 | issue = 2 | pages = 343–361 | doi = 10.1287/opre.32.2.343 | year = 1984 | pmid = | pmc = }}</ref><ref>{{Cite journal | last1 = Grassmann | first1 = W. K. | doi = 10.1016/0305-0548(77)90007-7 | title = Transient solutions in markovian queueing systems | journal = Computers & Operations Research | volume = 4 | pages = 47–00 | year = 1977 | pmid = | pmc = }}</ref><ref>{{Cite journal | last1 = Grassmann | first1 = W. K.| title = Transient solutions in Markovian queues | doi = 10.1016/0377-2217(77)90049-2 | journal = European Journal of Operational Research | volume = 1 | issue = 6 | pages = 396–402| year = 1977 | pmid = | pmc = }}</ref>

==Method description==

Line 25:

==Implementation==

[[Pseudocode]] for the algorithm is included in Appendix A of Reibman and Trivedi's 1988 paper.<ref name="reibman">{{Cite journal | last1 = Reibman | first1 = A. | last2 = Trivedi | first2 = K. | doi = 10.1016/0305-0548(88)90026-3 | title = Numerical transient analysis of markov models | journal = Computers & Operations Research | volume = 15 | pages = 19 | year = 1988 | pmid = | pmc = | url = http://people.ee.duke.edu/~kst/markovpapers/numerical.pdf}}</ref> Using a [[parallel algorithm|parallel]] version of the algorithm, chains with state spaces of larger than 10⁷ have been analysed.<ref>{{Cite journal | last1 = Dingle | first1 = N. | last2 = Harrison |first2 = P. G. | authorlink2author-link2 = Peter G. Harrison| last3 = Knottenbelt | first3= W. J.| title = Uniformization and hypergraph partitioning for the distributed computation of response time densities in very large Markov models | doi = 10.1016/j.jpdc.2004.03.017 | url = http://aesop.doc.ic.ac.uk/pubs/markov-uniformization-jpdc/| journal = Journal of Parallel and Distributed Computing | volume = 64 | issue = 8 | pages = 908–920 | year = 2004 | pmid = | pmc = | hdl = 10044/1/5771 | hdl-access = free }}</ref>

==Limitations==