Markov Chains

The random walk discussed in the previous chapter is a special case of a more general Markov process ¹ . Suppose that a random process passes through a discrete sequence of steps or trials numbered n = 0 , 1 , 2 , … $ n=0,1,2,\ldots $ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315156576/49190045-e11a-4825-88bf-d327626f56ef/content/inline-math4_1.tif"/> , where the outcome of the n-th trial is the random variable X n $ X_{n} $ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315156576/49190045-e11a-4825-88bf-d327626f56ef/content/inline-math4_2.tif"/> ; X 0 $ X_{0} $ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315156576/49190045-e11a-4825-88bf-d327626f56ef/content/inline-math4_3.tif"/> is the initial position of the process. This discrete random variable can take one of the values i = 1 , 2 , … m $ i=1, 2, \ldots m $ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315156576/49190045-e11a-4825-88bf-d327626f56ef/content/inline-math4_4.tif"/> . The actual outcomes are called the states of the system, and are denoted by E i $ E_{i} $ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315156576/49190045-e11a-4825-88bf-d327626f56ef/content/inline-math4_5.tif"/> ( i = 1 , 2 , … m $ i=1,2,\ldots m $ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315156576/49190045-e11a-4825-88bf-d327626f56ef/content/inline-math4_6.tif"/> ) (states can be any consecutive sequence of integers, say starting with i = 0 $ i=0 $ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315156576/49190045-e11a-4825-88bf-d327626f56ef/content/inline-math4_7.tif"/> or some other integer, but they can be renumbered to start with i = 1 $ i=1 $ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315156576/49190045-e11a-4825-88bf-d327626f56ef/content/inline-math4_8.tif"/> ). In most but not quite all cases in this text, we shall investigate systems with a finite number, m, of states E 1 , E 2 , … E m $ E_{1},E_{2},\ldots E_{m} $ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315156576/49190045-e11a-4825-88bf-d327626f56ef/content/inline-math4_9.tif"/> , which are independent and exhaustive.