Efficient Algorithms for Computation of Equilibrium/Transient Probability Distribution of Finite Markov Chains: Potential Lower Bound on Computational Complexity

EasyChair Preprint 490, version 2

Abstract

In this  research  paper,  efficient  algorithms  for  computation  of  equilibrium as  well  as  transient  probability  distribution  of  arbitrary  finite  state  space  Continuous  Time  Markov  Chain  are  proposed. The  effective  idea  is  to  solve  a  structured  systems  of  linear  equations  efficiently.  The  algorithms  potentially  achieve  lower  bound  on  the  computational  complexity ( of  solving  structured  system   of  linear  equations  arising  in  the  equilibrium/transient  analysis  of  Continuous  Time  Markov  Chains ).

Keyphrases: Lower Bound on Complexity, Markov chains, Transient distribution, efficient algorithms, equilibrium distribution

@booklet{EasyChair:490,
  author    = {Rama Murthy Garimella},
  title     = {Efficient  Algorithms  for  Computation  of  Equilibrium/Transient  Probability Distribution  of  Finite  Markov  Chains: Potential  Lower  Bound  on  Computational  Complexity},
  howpublished = {EasyChair Preprint 490},
  year      = {EasyChair, 2018}}