ctmc_stmonotone.h File Reference

Stochastically monotone upper bound of a Markov chain. More...

#include <cstddef>
#include "line/api/mc/ctmc_randomization.h"
#include "line/api/mc/ctmc_solve.h"
#include "line/api/mc/dtmc_makestochastic.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for ctmc_stmonotone.h:

Go to the source code of this file.

Namespaces
namespace	line
namespace	line::mc

Functions
template<class T>
Matrix< T >	line::mc::dtmc_stmonotone (const Matrix< T > &P)
template<class T>
Matrix< T >	line::mc::ctmc_stmonotone (const Matrix< T > &Q)
	Stochastically monotone upper bound of a Markov chain.

Detailed Description

Stochastically monotone upper bound of a Markov chain.

Templated port of jar/src/main/java/jline/api/mc/Ctmc_stmonotone.java, which has no MATLAB twin. Given a row-stochastic P the algorithm of Abu-Kamel and Stewart builds the smallest st-monotone Q that dominates P in the strong stochastic order, by filling the tail sums from the last column backwards: Q(0,l..n-1) = P(0,l..n-1), Q(i,l..n-1) = max( Q(i-1,l..n-1), P(i,l..n-1) ), and recovering Q(i,l) as that tail sum minus the tail already assigned. Every row tail of Q then dominates the corresponding row tail of P and is nondecreasing in i, which is exactly st-monotonicity.

The CTMC entry uniformizes Q at max|Q| (the rate the reference uses), repairs the rounding through dtmc_makestochastic, bounds the embedded chain and maps the bound back to a generator with ctmc_makeinfgen. Uniformization is a bijection between the two, so the bound is preserved.

ARITHMETIC: field plus comparisons. Exact under Rational.

Definition in file ctmc_stmonotone.h.