Content
     1. Numerical solution for equilibrium equations of Markov chain: 
       •  Exact methods: Gaussian elimination, and GTH 
       •  Approximation (iterative) methods: Power method, Gauss-
          Seidel variant
     2. Transient analysis of Markov process, uniformization, and 
        occupancy time
     3. M/M/1-type models: Quasi Birth Death processes and Matrix 
        geometric solution
     4. G/M/1 and M/G/1-type models: Free-skip processes in one 
        direction 
     5. Finite Quasi Birth Death processes
    Lecture 1: Algo. Methods for discrete time MC                      2
                            Lecture 1
       Algorithmic methods for finding the equilibrium 
              distribution of finite Markov chains
               Exact methods: Gaussian elimination, and GTH
          Approximation (iterative) methods: Power method, Gauss-
                                 Seidel variant
    Lecture 1: Algo. Methods for discrete time MC                  3
                             Introduction 
       Let  denote a discrete time stochastic process with finite states 
       
        space 
       Markov property: 
       If the process  satisfies the Markov property, it is then called a 
        discrete time Markov chain
       A Markov chain is stationary if   is independent of , i.e., . In this 
        case is called the one-step transition probability from state i to j 
               
       The matrix ,  is transition probability matrix of , , where  is column 
        vector of ones. The element  of , matrix  to power n, represents 
        the transition probability to go from i to j in  steps
    Lecture 1: Algo. Methods for discrete time MC                             4
                             Introduction
        A stationary Markov chain can be represented by a 
      
         transition states diagram  
        In a transition states diagram, two states can 
         communicate if there is a route that joins them
        A Markov chain is irreducible if all its states can  
         communicate between each other, i.e.,  an integer  
         such that  >0)
                        1                                0.5
                1              2                   1              2
                       0.3                               0.3
        0.5                          0.7                                0.7
                        3                    0.5          3
                          0.5                                1
             Three states irreducible MC       Three states absorbing MC: state 3 
                                               is absorbing, {1,2} are transient
    Lecture 1: Algo. Methods for discrete time MC                           5
                        Introduction
     Let  denotes the set of transient states and  the 
     
       set of absorbing states. For absorbing Markov 
       chains the transition probability matrix can be 
       written as,  identity matrix,             0.5
                                             1         2
                                                 0.3
                                        1                   0.7
                                                  3
                                                     1
       Let , , denote expected number of visits to  before 
       absorption given that the chain starts in  at the 
       time 0. 
     The matrix M gives 
                                  
                                                             6
   Lecture 1: Algo. Methods for discrete time MC