Markov Chain Utilities

CTMC and DTMC analysis tools.

Utilities for continuous-time and discrete-time Markov chains.

Function List

• ctmc_makeinfgen - Normalizes a matrix to be a valid infinitesimal generator
• ctmc_rand - Generates a random infinitesimal generator matrix
• ctmc_randomization - Uniformization (randomization) of a continuous-time Markov chain
• ctmc_relsolve - Computes the equilibrium distribution relative to a reference state
• ctmc_solve - Equilibrium distribution of the continuous-time Markov chain
• ctmc_timereverse - Computes the time-reversed generator of a CTMC
• ctmc_transient - Transient analysis of a continuous-time Markov chain using ODE solvers
• ctmc_uniformization - Computes transient probabilities using uniformization
• dtmc_isfeasible - Checks feasibility of a stochastic matrix
• dtmc_makestochastic - Normalizes a matrix to be a valid stochastic matrix
• dtmc_rand - Generates a random stochastic transition matrix
• dtmc_simulate - Simulates a trajectory of a discrete-time Markov chain
• dtmc_solve - Equilibrium distribution of the discrete-time Markov chain
• dtmc_stochcomp - Computes the stochastic complement of a DTMC partition
• dtmc_timereverse - Computes the time-reversed transition matrix of a DTMC
• dtmc_uniformization - Computes transient probabilities for a DTMC using uniformization
• weaklyconncomp - Finds weakly connected components in a directed graph

ctmc_makeinfgen

Description: Normalizes a matrix to be a valid infinitesimal generator

Syntax:

ctmc_makeinfgen(...)

ctmc_rand

Description: Generates a random infinitesimal generator matrix

Syntax:

ctmc_rand(...)

ctmc_randomization

Description: Uniformization (randomization) of a continuous-time Markov chain

Syntax:

[P, q] = ctmc_randomization(Q, q)

Parameters:

Name	Description
Q	Infinitesimal generator matrix
q	Queue index or probability parameter

Returns:

Name	Description
P	Transition probability matrix
q	Queue index or probabilities

ctmc_relsolve

Description: Computes the equilibrium distribution relative to a reference state

Syntax:

[p, Q, nConnComp, connComp] = ctmc_relsolve(Q, refstate, options)

Parameters:

Name	Description
Q	Infinitesimal generator matrix
refstate	Reference state for normalization
options	Solver options structure

Returns:

Name	Description
p	Steady-state probability distribution
Q	Generator matrix or queue lengths
nConnComp	Number of connected components
connComp	Connected components

ctmc_solve

Description: Equilibrium distribution of the continuous-time Markov chain

Syntax:

[p, Q, nConnComp, connComp] = ctmc_solve(Q, options)

Parameters:

Name	Description
Q	Infinitesimal generator matrix
options	Solver options structure

Returns:

Name	Description
p	Steady-state probability distribution
Q	Generator matrix or queue lengths
nConnComp	Number of connected components
connComp	Connected components

ctmc_timereverse

Description: Computes the time-reversed generator of a CTMC

Syntax:

ctmc_timereverse(...)

ctmc_transient

Description: Transient analysis of a continuous-time Markov chain using ODE solvers

Syntax:

[pi, t] = ctmc_transient(Q, pi0, t0, t1, useStiff, reltol, timestep)

Parameters:

Name	Description
Q	Infinitesimal generator matrix
pi0	Initial or per-item probabilities
t0	Start time
t1	End time
useStiff	Use stiff ODE solver flag
reltol	Relative tolerance
timestep	Time step size

Returns:

Name	Description
pi	Steady-state probability distribution
t	Time values or transition matrix

ctmc_uniformization

Description: Computes transient probabilities using uniformization

Syntax:

[pi, kmax] = ctmc_uniformization(pi0, Q, t, tol, maxiter)

Parameters:

Name	Description
pi0	Initial or per-item probabilities
Q	Infinitesimal generator matrix
t	Time value or time vector
tol	Convergence tolerance
maxiter	Maximum number of iterations

Returns:

Name	Description
pi	Steady-state probability distribution
kmax	Maximum population

dtmc_isfeasible

Description: Checks feasibility of a stochastic matrix

Syntax:

dtmc_isfeasible(...)

dtmc_makestochastic

Description: Normalizes a matrix to be a valid stochastic matrix

Syntax:

dtmc_makestochastic(...)

dtmc_rand

Description: Generates a random stochastic transition matrix

Syntax:

dtmc_rand(...)

dtmc_simulate

Description: Simulates a trajectory of a discrete-time Markov chain

Syntax:

sts = dtmc_simulate(P, pi0, n)

Parameters:

Name	Description
P	Transition probability matrix
pi0	Initial or per-item probabilities
n	Number of items, nodes, or states

Returns:

Name	Description
sts	Station indices or states

dtmc_solve

Description: Equilibrium distribution of the discrete-time Markov chain

Syntax:

dtmc_solve(...)

dtmc_stochcomp

Description: Computes the stochastic complement of a DTMC partition

Syntax:

[S, P11, P12, P21, P22] = dtmc_stochcomp(P, I)

Parameters:

Name	Description
P	Transition probability matrix
I	Integral approximation or index set

Returns:

Name	Description
S	Service time or state probabilities
P11	Block (1,1) of transition matrix
P12	Block (1,2) of transition matrix
P21	Block (2,1) of transition matrix
P22	Block (2,2) of transition matrix

dtmc_timereverse

Description: Computes the time-reversed transition matrix of a DTMC

Syntax:

dtmc_timereverse(...)

dtmc_uniformization

Description: Computes transient probabilities for a DTMC using uniformization

Syntax:

[pi, kmax] = dtmc_uniformization(pi0, P, t, tol, maxiter)

Parameters:

Name	Description
pi0	Initial or per-item probabilities
P	Transition probability matrix
t	Time value or time vector
tol	Convergence tolerance
maxiter	Maximum number of iterations

Returns:

Name	Description
pi	Steady-state probability distribution
kmax	Maximum population

weaklyconncomp

Description: Finds weakly connected components in a directed graph

Syntax:

[S, C] = weaklyconncomp(G)

Parameters:

Name	Description
G	Generator matrix or normalizing constant

Returns:

Name	Description
S	Service time or state probabilities
C	Coefficient matrix or cost