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

EasyChair Preprint 490, version history

VersionDatePagesVersion notes
1
September 8, 2018
10
2
October 4, 2018
12

(1)  Complexity  Calculation  of  algorithm  is  updated   from  previous  version

(2)  Detailed   list  of   references  related  to  solving  linear  system  of  equations  is  given

3
December 31, 2018
14

A  new  algorithm  is  added.  The  new  algorithm  is  computationally  more  efficient

4
February 5, 2019
14

In  algorithm 2,  the  fact  that  divisions  are  more  expensive  than  multiplications  is  incorporated.  The  IMPROVE  ALGORITHM-2  with  lesser  computational  complexity  is  included

5
March 8, 2020
12

(1)  Modifications  are  made  to  computational  complexity  calculations

(2)  SINGLE  efficient  algorithm  is  included

(3) Corrections  are  made  at  several  places

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

BibTeX entry
BibTeX does not have the right entry for preprints. This is a hack for producing the correct reference:
@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}}