Discrete-time Markov chain: Difference between revisions

Revision as of 03:00, 28 August 2020

Revision as of 01:50, 31 December 2020

Line 134:

:<math>\pi_i p_{ij} = \pi_j p_{ji}\,.</math><ref name="PRS"/>

The single time-step from ''n'' to ''n''&nbsp;+&nbsp;1 can be thought of as each person ''i'' having {{pi}}_''i'' dollars initially and paying each person ''j'' a fraction ''p_ij'' of it. The detailed balance condition states that upon each payment, the other person pays exactly the same amount of money back.<ref name="Durrett2012">{{cite book|url=https://books.google.com/books?id=i_Ovy6OvI54C&pg=PA37|title=Essentials of Stochastic Processes|author=Richard Durrett|date=19 May 2012|publisher=Springer Science & Business Media|isbn=978-1-4614-3615-7|page=37|archiveurlarchive-url=https://web.archive.org/web/20170206031627/https://books.google.com/books?id=i_Ovy6OvI54C&pg=PA37|archivedatearchive-date=6 February 2017|url-status=live}}</ref> Clearly the total amount of money '''{{pi}}''' each person has remains the same after the time-step, since every dollar spent is balanced by a corresponding dollar received. This can be shown more formally by the equality

:<math>\sum_i \pi_i p_{ij} = \sum_i \pi_j p_{ji} = \pi_j \sum_i p_{ji} = \pi_j\,,</math>

Line 170:

|journal= Probability and Its Applications

|url-status= live

|archiveurlarchive-url= https://web.archive.org/web/20150319050311/https://books.google.com/books?id=JBBRiuxTN0QC&pg=PA35

|archivedatearchive-date= 2015-03-19

}}</ref> in which case the unique such distribution is given by <math>\pi_i=\frac{1}{M_i}</math> where <math>M_i=\mathbb{E}(T_i)</math> is the mean recurrence time of ''i''.<ref name="PRS"/>

Line 196:

===Expected hitting times===

For a subset of states ''A''&nbsp;⊆&nbsp;''S'', the vector ''k''^''A'' of hitting times (where element <math> k_i^A </math> represents the [[expected value]], starting in state ''i'' that the chain enters one of the states in the set ''A'') is the minimal non-negative solution to<ref name="norris2">{{cite book|title=Markov Chains|year=1997|isbn=9780511810633|pages=108–127|chapter=Continuous-time Markov chains II|doi=10.1017/CBO9780511810633.005|pmc=|pmid=|last1=Norris|first1=J. R.|authorlink1author-link1=James R. Norris}}</ref>

:<math>\begin{align}

Line 217:

* [[J. L. Doob]] (1953) ''Stochastic Processes''. New York: John Wiley and Sons {{ISBN|0-471-52369-0}}.

* S. P. Meyn and R. L. Tweedie (1993) ''Markov Chains and Stochastic Stability''. London: Springer-Verlag {{ISBN|0-387-19832-6}}. online: [https://web.archive.org/web/20100619010320/https://netfiles.uiuc.edu/meyn/www/spm_files/book.html MCSS] . Second edition to appear, Cambridge University Press, 2009.

* {{cite book |title=Finite Mathematical Structures |url=https://archive.org/details/finitemathematic0000keme_h5g0 |url-access=registration |last=Kemeny |first=John G. |publisher=Prentice-Hall, Inc. |year=1959 |isbn= |edition=1st |___location=Englewood Cliffs, NJ |pages = |id = Library of Congress Card Catalog Number 59-12841 |author2=Hazleton Mirkil |author3=J. Laurie Snell |author4=Gerald L. Thompson }} Classical text. cf Chapter 6 ''Finite Markov Chains'' pp.&nbsp;384ff.

* [[John G. Kemeny]] & [[J. Laurie Snell]] (1960) ''Finite Markov Chains'', D. van Nostrand Company {{ISBN|0-442-04328-7}}

* E. Nummelin. "General irreducible Markov chains and non-negative operators". Cambridge University Press, 1984, 2004. {{ISBN|0-521-60494-X}}