dtmc_solve_reducible.h File Reference

Limiting distribution of a discrete-time Markov chain whose transition matrix may be reducible. More...

#include <cstddef>
#include <vector>
#include "line/api/mc/dtmc_makestochastic.h"
#include "line/api/mc/dtmc_solve.h"
#include "line/api/mc/stronglyconncomp.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/lu.h"
#include "line/util/matrix.h"

Include dependency graph for dtmc_solve_reducible.h:

Go to the source code of this file.

Classes
struct	line::mc::ReducibleResult< T >

Namespaces
namespace	line
namespace	line::mc

Functions
template<class T>
ReducibleResult< T >	line::mc::dtmc_solve_reducible (const Matrix< T > &P, const std::vector< T > &pin, double zeroColTol=1e-12)
	Limiting distribution of a discrete-time Markov chain whose transition matrix may be reducible.
template<class T>
ReducibleResult< T >	line::mc::dtmc_solve_reducible (const Matrix< T > &P, double zeroColTol=1e-12)
	Overload without an initial vector.

Detailed Description

Limiting distribution of a discrete-time Markov chain whose transition matrix may be reducible.

Templated port of matlab/src/api/mc/dtmc_solve_reducible.m and jar/src/main/java/jline/api/mc/Dtmc_solve_reducible.java. The states are partitioned into strongly connected components; the components are lumped into a chain Pl on which the recurrent ones are made absorbing; the limiting matrix of Pl distributes the initial mass over the recurrent components; and within each component the conditional limiting vector is the stationary vector of the restricted chain.

EXACT, DELIBERATELY, AND THIS IS WHERE THE PORT BEATS THE REFERENCE. MATLAB computes the limiting matrix of the lumped chain by spectral decomposition (spectd), with a power iteration capped at 1000 steps and tolerance 1e-10 as the fallback whenever the eigenvector matrix has condition number above 1e10 – which is exactly the situation a lumped chain with repeated unit eigenvalues produces, so the fallback is the common case rather than the rare one, and it converges only linearly in the subdominant eigenvalue. Here the same matrix is obtained in closed form: the recurrent lumped states are absorbing, so the limit is the absorption probability PI(t, r) = [(I - Pl_TT)^-1 Pl_TR](t, r), PI(r, r') = delta, with I - Pl_TT non-singular because every transient component reaches a recurrent one. That is one finite linear solve, no iteration and no tolerance, so the whole routine instantiates at Rational and returns the true limiting distribution of a rational chain.

The only tolerance left is the one MATLAB uses to decide that a state has no incoming mass (column sum below 1e-12) when no initial vector is supplied; it is a structural test on the input, not a convergence criterion, and it is exposed as a parameter.

Definition in file dtmc_solve_reducible.h.