ctmc_ssd.h File Reference

Stochastically stable distribution of a perturbed Markov chain (Wicks 2009). More...

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <limits>
#include <string>
#include <vector>
#include "line/api/mc/ctmc_gth.h"
#include "line/api/mc/stronglyconncomp.h"
#include "line/util/error.h"
#include "line/util/lu.h"
#include "line/util/matrix.h"

Include dependency graph for ctmc_ssd.h:

Go to the source code of this file.

Namespaces
namespace	line
	Conservation laws of a layered queueing network, enumerated from its structure.
namespace	line::mc

Functions
std::vector< double >	line::mc::ctmc_ssd (const Matrix< double > &Cin, const Matrix< double > &Rin)
	Stochastically stable distribution, rates C(i,j) eps^R(i,j) (Wicks 2009).
std::vector< double >	line::mc::dtmc_ssd (const Matrix< double > &C, const Matrix< double > &R)
	SSD of a perturbed transition matrix P_eps(i,j) ~ C(i,j) eps^R(i,j); equals ctmc_ssd.

Detailed Description

Stochastically stable distribution of a perturbed Markov chain (Wicks 2009).

Port of matlab/src/api/mc/ctmc_ssd.m and dtmc_ssd.m; JAR twin jline.api.mc.Ctmc_ssd, Python twin line_solver.api.mc.gth.ctmc_ssd. The off-diagonal rates behave as Q_eps(i,j) ~ C(i,j) eps^R(i,j) as eps -> 0+ (rows are sources; a zero rate is R = Inf or C = 0), and the result is the exact limit of the stationary vector, no eps ever substituted. Q_eps must be irreducible for eps > 0. The recursion (see ctmc_ssd.m for the full account):

1. shift R to minimum 0 and take G0, the zero-resistance graph;
2. one closed class in G0: GTH on the constant chain over G0;
3. else a class of G0 with two or more states: drop its positive-resistance internal edges (Lemma 7.22) and censor all its states but one, with the constant N0 = (-Q0_ss)^{-1} (Theorem 7.31), in (C,R) arithmetic;
4. else divide the rates out of the closed singletons by eps^smin (Lemma 7.16) and keep the scaled solution on those states. (C,R) arithmetic: a sum keeps the least resistance and adds the tied costs, a product adds resistances and multiplies costs. Resistances are compared with a relative tolerance 1e-10, so the computation is double-valued. (J. R. Wicks, PhD thesis, Brown University, 2009, Ch. 7.)

Definition in file ctmc_ssd.h.