LINE Solver (C++)
Templated C++ port of the LINE queueing solver
Loading...
Searching...
No Matches
markov_chain.h File Reference
Model classes

The MarkovProcess / MarkovChain object surface. More...

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <map>
#include <random>
#include <string>
#include <vector>
#include "line/api/mc/ctmc_courtois.h"
#include "line/api/mc/ctmc_foxglynn.h"
#include "line/api/mc/ctmc_isfeasible.h"
#include "line/api/mc/ctmc_kms.h"
#include "line/api/mc/ctmc_multi.h"
#include "line/api/mc/ctmc_passage.h"
#include "line/api/mc/ctmc_rand.h"
#include "line/api/mc/ctmc_relsolve.h"
#include "line/api/mc/ctmc_sens.h"
#include "line/api/mc/ctmc_simulate.h"
#include "line/api/mc/ctmc_solve.h"
#include "line/api/mc/ctmc_solve_reducible.h"
#include "line/api/mc/ctmc_takahashi.h"
#include "line/api/mc/ctmc_timereverse.h"
#include "line/api/mc/ctmc_uniformization.h"
#include "line/api/mc/dtmc_makestochastic.h"
#include "line/api/mc/dtmc_rand.h"
#include "line/api/mc/dtmc_solve.h"
#include "line/api/mc/dtmc_solve_reducible.h"
#include "line/api/mc/dtmc_stochcomp.h"
#include "line/api/mc/dtmc_transient.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 markov_chain.h:

Go to the source code of this file.

Classes

struct  line::lang::processes::MarkovChainModel< T >
 A user-supplied chain: a MarkovProcess when discrete is false, else a MarkovChain. More...
struct  line::lang::processes::ProbStateResult< T >
 What getProbState returns: the probability and the two determinants behind it. More...
struct  line::lang::processes::TransientAtResult< T >
 What the CTMC transient returns: the law at t and the truncation it used. More...
struct  line::lang::processes::TimeAverageOut< T >
 What timeAverage returns. More...
struct  line::lang::processes::AggregateResult< T >
 What aggregate returns: the approximate law and the two NCD indices. More...
struct  line::lang::processes::StochCompOut< T >
 What stochCompFull returns for a CTMC; a DTMC fills the same blocks from P. More...
struct  line::lang::processes::ChainPath< T >
 A sampled path: the states visited, with their holding times for a CTMC. More...

Namespaces

namespace  line
namespace  line::lang
namespace  line::lang::processes

Functions

template<class T>
MarkovChainModel< T > line::lang::processes::to_markov_process (const MarkovChainModel< T > &m)
 MarkovChain.toMarkovProcess / toCTMC: read the DTMC as a CTMC with unit exit rates, Q = P - I.
template<class T>
T line::lang::processes::default_uniformization_rate (const Matrix< T > &Q)
 The uniformization rate this port uses when the caller names none.
template<class T>
MarkovChainModel< T > line::lang::processes::to_markov_chain (const MarkovChainModel< T > &m, const T &q)
 MarkovProcess.toMarkovChain / toDTMC: the UNIFORMIZED chain, P = Q/q + I.
template<class T>
MarkovChainModel< T > line::lang::processes::to_markov_chain (const MarkovChainModel< T > &m)
template<class T>
MarkovChainModel< T > line::lang::processes::to_dtmc (const MarkovChainModel< T > &m)
 toDTMC, the backwards-compatible alias of toMarkovChain.
template<class T>
MarkovChainModel< T > line::lang::processes::to_dtmc (const MarkovChainModel< T > &m, const T &q)
template<class T>
MarkovChainModel< T > line::lang::processes::to_embedded (const MarkovChainModel< T > &m)
 MarkovProcess.toEmbedded: the JUMP CHAIN, the DTMC of the states visited at transition epochs.
template<class T>
MarkovChainModel< T > line::lang::processes::to_time_reversed (const MarkovChainModel< T > &m)
 toTimeReversed for either kind: the chain run backwards in time.
template<class T>
std::vector< T > line::lang::processes::chain_solve (const MarkovChainModel< T > &m)
 MarkovProcess.solve / MarkovChain.solve.
template<class T>
std::vector< T > line::lang::processes::solve_relative (const MarkovChainModel< T > &m, std::size_t refstate=0)
 MarkovProcess.solveRelative: the equilibrium vector normalized so that refstate carries one, which exists even where the normalizing constant does not.
template<class T>
ProbStateResult< T > line::lang::processes::get_prob_state (const MarkovChainModel< T > &m, std::size_t i)
 MarkovProcess.getProbState: the probability of ONE state by Cramer's rule.
template<class T>
std::size_t line::lang::processes::match_state (const MarkovChainModel< T > &m, const std::vector< T > &state)
 Row index of state in the chain's state space, or n when it carries none.
template<class T>
ProbStateResult< T > line::lang::processes::get_prob_state (const MarkovChainModel< T > &m, const std::vector< T > &state)
 getProbState addressed by the state itself rather than by its index.
template<class T>
bool line::lang::processes::is_feasible (const MarkovChainModel< T > &m)
 isFeasible: a valid generator, or a stochastic transition matrix.
template<class T>
TransientAtResult< T > line::lang::processes::chain_transient_at (const MarkovChainModel< T > &m, const std::vector< T > &pi0in, const T &t, const std::string &method="unif")
 MarkovProcess.transient: the law at ONE time t, by uniformization.
template<class T>
Matrix< T > line::lang::processes::chain_transient_steps (const MarkovChainModel< T > &m, const std::vector< T > &pi0in, std::size_t steps=1)
 MarkovChain.transient: the law at every step 0..steps, one row per step.
template<class T>
TransientAtResult< T > line::lang::processes::chain_transient_unif (const MarkovChainModel< T > &m, const std::vector< T > &pi0in, const T &t)
 MarkovChain.transientUnif: the DTMC read as the randomized image of a CTMC, so t is CONTINUOUS here where chain_transient_steps counts steps.
template<class T>
TimeAverageOut< T > line::lang::processes::time_average (const MarkovChainModel< T > &m, const std::vector< T > &pi0in, const T &t)
 MarkovProcess.timeAverage: the law averaged over [0,t], and its endpoint.
template<class T>
std::vector< T > line::lang::processes::chain_sens (const MarkovChainModel< T > &m, const Matrix< T > &dQ)
 MarkovProcess.sens: the derivative of the stationary law with respect to a scalar parameter, given the derivative dQ of the generator.
template<class T>
AggregateResult< T > line::lang::processes::aggregate (const MarkovChainModel< T > &m, const std::vector< std::vector< std::size_t > > &MS, const std::string &method="courtois", const T *param=nullptr)
 MarkovProcess.aggregate: aggregation-disaggregation over a macrostate partition.
template<class T>
AggregateResult< T > line::lang::processes::aggregate_multi (const MarkovChainModel< T > &m, const std::vector< std::vector< std::size_t > > &MS, const std::vector< std::vector< std::size_t > > &MSS)
 The "multi" arm of aggregate, separated because its parameter is a PARTITION OF THE PARTITION and not a scalar.
template<class T>
StochCompOut< T > line::lang::processes::stoch_comp_full (const MarkovChainModel< T > &m, const std::vector< std::size_t > &I=std::vector< std::size_t >())
 stochComp / stochCompFull for either kind.
template<class T>
Matrix< T > line::lang::processes::stoch_comp (const MarkovChainModel< T > &m, const std::vector< std::size_t > &I=std::vector< std::size_t >())
 stochComp: the complement alone.
template<class T>
std::vector< T > line::lang::processes::hitting_time (const MarkovChainModel< T > &m, const std::vector< std::size_t > &target)
 hittingTime: the mean time (CTMC) or step count (DTMC) to reach any state in target, zero on the target set itself and infinite from a state that cannot reach it.
template<class T, class Gen>
ChainPath< T > line::lang::processes::chain_sample (const MarkovChainModel< T > &m, const std::vector< T > &pi0in, std::size_t n, Gen &gen)
 sample: simulate n steps.
template<class T, class Gen>
MarkovChainModel< T > line::lang::processes::rand_process (std::size_t n, Gen &gen)
 MarkovProcess.rand: a random generator of the given order.
template<class T, class Gen>
MarkovChainModel< T > line::lang::processes::rand_chain (std::size_t n, Gen &gen)
 MarkovChain.rand: a random transition matrix of the given order.
template<class T>
MarkovChainModel< T > line::lang::processes::from_sample_sys_aggr (const Matrix< T > &sample_state)
 MarkovChain.fromSampleSysAggr: estimate a DTMC from an observed trajectory.

Detailed Description

The MarkovProcess / MarkovChain object surface.

Port of matlab/src/lang/processes/MarkovProcess.m (a CTMC, carrying a generator) and MarkovChain.m (a DTMC, carrying a transition matrix). Both are thin objects over api/mc: the algorithms already lived there before this header did, and what was missing was the surface that names them and fixes which one each method calls. That distinction is the whole content of the two classes and it is not cosmetic – solve and transient each pick a DIFFERENT primitive for the two chain kinds, and toDTMC and toEmbedded both turn a CTMC into a DTMC while disagreeing about what the result means.

ONE MODEL TYPE FOR BOTH KINDS. MarkovChainModel<T>::discrete says which class the object would be in MATLAB. The reference dispatches on the class, so every function here dispatches on that flag, and the constructors' normalization (ctmc_makeinfgen / dtmc_makestochastic) is applied by the factories exactly as the two constructors apply it. This type was previously declared inside solvers/ctmc/solver_ctmc_chain.h, which aliases it now.

WHAT IS DELIBERATELY ABSENT:

  • plot and plot3. They call graphViz4Matlab and MATLAB's digraph, a rendering layer this tree has no counterpart for. A caller wanting the graph has mat and state_space and can emit whatever format it wants.
  • getGenerator / getTransMat / setStateSpace, which are field access: mat and state_space are public members.
  • isfinite. It is a flag the reference stores and never reads.

TWO PLACES WHERE THE REFERENCE IS NOT REPRODUCIBLE, and how this port stands:

  • toMarkovChain with no argument picks q = max|Q| + rand, so the SAME chain uniformizes to a different P on every call. Any q > max|Q| is a valid uniformization rate and all of them carry the same stationary law, but the returned matrix is not the same object, so a golden recorded against it would be noise. The default here is deterministic, q = max|Q| * (1 + 1/16), and the rate is an explicit parameter for a caller that wants the reference's own draw.
  • MarkovChain.sample draws its own uniform initial law before simulating. Here the initial law is a parameter, empty meaning that same random draw, so the caller can make the path reproducible without a fork of the primitive.

Definition in file markov_chain.h.