Skip to content

Pure Python 2.7 implementation of solving Absorbing Markov Chains (no dependencies)

Notifications You must be signed in to change notification settings

devrohityadav/absorbing-markov-chains

 
 

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

10 Commits
 
 
 
 
 
 
 
 

Repository files navigation

Build Status

Absorbing Markov Chains

Pure Python 2.7 implementation of solving Absorbing Markov Chains (no dependencies)

Motivation

Matrix operations in pure Python are nothing complex but boring. I saw a lot of code snippets in gists and stackexchange questions but I believe that absence of a solid package is a shame.

I guess you're looking for implementation to run in Python 2.7 sandbox. In this case this set of utility functions might save you several hours of coding and bugfixing.

This set of functions can do:

  • Identity matrix generation
  • Matrix subtraction
  • Matrix multiplications
  • Matrix inverse
  • Matrix reordering (to swap states to bring matrix to canonical form)
  • Check if the matrix is zero-matrix
  • Decompose Markov matrix on Q and R components

These are basically what you need to calculate some properties like absorbing probabilities.

Canonical form

Let an absorbing Markov chain with transition matrix P have t transient states and r absorbing states. Then

    [ Q R ]
P = [ 0 I ]

where Q is square t-by-t matrix, P is t-by-r matrix, 0 is zero-matrix and I is identity matrix.

Absorbing probabilities

If you linearly transform P such as Q becomes a zero-matrix then what will appear in place of R are final absorbing probabilities. In other words absorbing probabilities B could be calculated as B = (I - Q)^-1 * R.

Notes

  • These set of utility functions assume that I is a zero-matrix

About

Pure Python 2.7 implementation of solving Absorbing Markov Chains (no dependencies)

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • Python 100.0%