First passage times into a target STATE SET, for Markov and semi-Markov chains. More...

#include <algorithm>
#include <cmath>
#include <complex>
#include <cstddef>
#include <functional>
#include <limits>
#include <vector>
#include "line/api/lti/laplace_invert.h"
#include "line/api/mc/ctmc_solve.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/expm.h"
#include "line/util/lu.h"
#include "line/util/matrix.h"

Include dependency graph for ctmc_passage.h:

Classes
struct	line::mc::PassagePh< T >
	The phase-type form of a first passage time. More...
struct	line::mc::PassageMoments< T >
	Per-source and pi0-weighted passage moments. More...
struct	line::mc::PassageCurve< T >
	A passage-time law on a grid. More...

Namespaces
namespace	line
namespace	line::mc

Functions
template<class T>
PassagePh< T >	line::mc::ctmc_passage_ph (const Matrix< T > &Q, const std::vector< T > &pi0, const std::vector< std::size_t > &target)
	Phase-type representation of the first passage time from pi0 into target.
template<class T>
std::vector< std::complex< double > >	line::mc::ctmc_passage_lst (const Matrix< T > &Q, const std::vector< T > &pi0, const std::vector< std::size_t > &target, const std::vector< std::complex< double > > &s)
	L(s) = alpha (sI-S)^{-1} s0 + atom at the (complex) points s.
template<class T>
PassageMoments< T >	line::mc::ctmc_passage_moments (const Matrix< T > &Q, const std::vector< T > &pi0, const std::vector< std::size_t > &target, std::size_t nmax=1)
	Moments of order 1..nmax of the first passage time into target.
template<class T>
std::vector< T >	line::mc::ctmc_hitting_time (const Matrix< T > &Q, const std::vector< std::size_t > &target)
	Mean time to reach any state in target from each state of a CTMC.
template<class T>
PassageCurve< T >	line::mc::ctmc_passage_time (const Matrix< T > &Q, const std::vector< T > &pi0, const std::vector< std::size_t > &target, const std::vector< double > &tset, const std::string &method="expm", const std::string &lti_method="euler")
	CDF and density of the first passage time on the grid tset: F(t) = 1 - alpha exp(St) 1 and f(t) = alpha exp(St) s0.
template<class T>
PassageMoments< T >	line::mc::smp_passage_moments (const Matrix< T > &P, const Matrix< T > &hmom, const std::vector< T > &pi0, const std::vector< std::size_t > &target, std::size_t nmax=1)
	Moments of the semi-Markov first passage time from the per-state holding moments m_i(r), Eq.
template<class T>
std::vector< std::complex< double > >	line::mc::smp_passage_lst (const Matrix< T > &P, const std::vector< std::function< std::complex< double >(std::complex< double >)> > &hlst, const std::vector< T > &pi0, const std::vector< std::size_t > &target, const std::vector< std::complex< double > > &s)
	L(s) of the semi-Markov first passage time, Eqs.
template<class T>
PassageCurve< T >	line::mc::smp_passage_time (const Matrix< T > &P, const std::vector< std::function< std::complex< double >(std::complex< double >)> > &hlst, const std::vector< T > &pi0, const std::vector< std::size_t > &target, const std::vector< double > &tset, const std::string &lti_method="euler")
	CDF and density of the semi-Markov first passage time, by inverting smp_passage_lst through api/lti.

Detailed Description

First passage times into a target STATE SET, for Markov and semi-Markov chains.

Port of matlab/src/api/mc/ctmc_passage_*.m and smp_passage_*.m, which are the reference. Source: P. G. Harrison and W. J. Knottenbelt, "Passage Time Distributions in Large Markov Chains", 2002 – Eqs. 1-3 for the Markov case, Eqs. 4-8 for the semi-Markov one.

THE IDENTITY THE WHOLE FAMILY RESTS ON. The first passage time from an initial law pi0 into a target set B is PHASE-TYPE. With A the complement,

S     = Q(A,A)        sub-generator: the passage has not completed
s0    = -S*1          exit vector, equal to Q(A,B)*1
alpha = pi0(A)        UNNORMALIZED, see below
atom  = sum pi0(B)

so L(s) = alpha (sI-S)^{-1} s0 + atom and F(t) = 1 - alpha exp(St) 1. The paper writes the same system as n scalar equations with L_i = 1 on B.

ALPHA IS DELIBERATELY NOT NORMALIZED. Its mass is 1 - atom; the missing mass is the ATOM AT ZERO carried by initial states already inside the target. A caller that normalizes alpha and forgets the atom reports F(0) = 0 for a passage that has already completed with probability atom.

THIS IS NOT THE SPLIT solver_ctmc_cdf.h USES. That one is by EVENT (the tagged job arriving at or departing from a station, through the filtration), this one is by STATE SET. The two are complementary and must not be merged.

ARITHMETIC: needs expm and transcendentals, so exact arithmetic is refused by name rather than silently producing a wrong type.

Definition in file ctmc_passage.h.

Classes

Namespaces

Functions

Detailed Description