Markov Chain Utilities

CTMC and DTMC analysis tools.

The mc module provides general tools for analyzing Markov chains, including steady-state and transient analysis for both continuous-time and discrete-time Markov chains.

Key function categories:

Steady-state analysis: ctmc_solve_reducible(), dtmc_solve_reducible(), ctmc_stochcomp()
Transient analysis: ctmc_transient(), ctmc_uniformization()
Simulation: ctmc_simulate(), ctmc_rand()
Aggregation methods: ctmc_courtois(), ctmc_takahashi(), ctmc_kms()
State-space generation: ctmc_ssg(), ctmc_ssg_reachability()
Generator matrices: ctmc_makeinfgen(), ctmc_multi()

Markov Chain Analysis (line_solver.api.mc)

Markov Chain analysis algorithms.

Native Python implementations for continuous-time and discrete-time Markov chain analysis.

Key algorithms:: ctmc_solve: CTMC steady-state distribution ctmc_transient: CTMC transient analysis ctmc_uniformization: Uniformization method for transient analysis ctmc_stochcomp: Stochastic complementation dtmc_solve: DTMC steady-state distribution

ctmc_solve(Q)[source]

Solve for steady-state probabilities of a CTMC.

Computes the stationary distribution π by solving πQ = 0 with normalization constraint Σπ = 1.

Handles reducible CTMCs by decomposing into strongly connected components and solving each separately.

Parameters:: Q (ndarray) – Infinitesimal generator matrix (row sums should be zero)
Returns:: Steady-state probability distribution (1D array)
Return type:: ndarray

ctmc_solve_reducible(Q)[source]

Solve reducible CTMCs by converting to DTMC via uniformization.

Parameters:: Q (ndarray) – Infinitesimal generator matrix (possibly reducible)
Returns:: Steady-state probability vector
Return type:: ndarray

ctmc_makeinfgen(Q)[source]

Convert a matrix into a valid infinitesimal generator for a CTMC.

An infinitesimal generator has: - Row sums equal to zero - Non-positive diagonal elements - Non-negative off-diagonal elements

Parameters:: Q (ndarray) – Candidate infinitesimal generator matrix
Returns:: Valid infinitesimal generator matrix with corrected diagonal
Return type:: ndarray

ctmc_transient(Q, initial_dist, time_points, method='expm')[source]

Compute transient probabilities of a CTMC.

Calculates time-dependent state probabilities π(t) for specified time points using matrix exponential methods.

Parameters:

Q (ndarray) – Infinitesimal generator matrix
initial_dist (ndarray) – Initial probability distribution π(0)
time_points (float | ndarray) – Array of time points to evaluate, or single time value
method (str) – ‘expm’ for matrix exponential, ‘ode’ for ODE solver

Returns:

Transient probabilities at each time point. Shape: (len(time_points), n) if multiple times, (n,) if single time

Return type:

ndarray

ctmc_uniformization(Q, lambda_rate=None)[source]

Uniformize CTMC generator matrix.

Converts CTMC to an equivalent uniformized discrete-time chain for numerical analysis and simulation purposes.

The uniformized DTMC has transition matrix P = I + Q/λ where λ is the uniformization rate (max exit rate).

Parameters:

Q (ndarray) – Infinitesimal generator matrix
lambda_rate (float | None) – Uniformization rate (optional, auto-computed if None)

Returns:

‘P’: Uniformized transition matrix
’lambda’: Uniformization rate

Return type:

dict containing

ctmc_randomization(Q, initial_dist, time_points, precision=1e-10)[source]

Compute CTMC transient probabilities using randomization.

Uses Jensen’s randomization method (uniformization) to compute transient probabilities by converting the CTMC to a uniformized DTMC.

This method is numerically stable and avoids matrix exponentials.

Parameters:

Q (ndarray) – Infinitesimal generator matrix
initial_dist (ndarray) – Initial probability distribution
time_points (ndarray) – Array of time points to evaluate
precision (float) – Numerical precision for truncation (Poisson tail)

Returns:

Transient probabilities at each time point

Return type:

ndarray

ctmc_stochcomp(Q, keep_states, eliminate_states=None)[source]

Compute stochastic complement of CTMC.

Reduces the CTMC by eliminating specified states while preserving the steady-state distribution restricted to the kept states.

Parameters:

Q (ndarray) – Infinitesimal generator matrix
keep_states (ndarray) – States to retain in reduced model (array of indices)
eliminate_states (ndarray | None) – States to eliminate (optional, inferred if None)

Returns:

‘S’: Stochastic complement (reduced generator)
’Q11’: Submatrix for kept states
’Q12’: Transitions from kept to eliminated
’Q21’: Transitions from eliminated to kept
’Q22’: Submatrix for eliminated states
’T’: Transient contribution matrix

Return type:

dict containing

ctmc_timereverse(Q, pi=None)[source]

Compute time-reversed CTMC generator.

The time-reversed generator Q* has elements: Q*_{ij} = π_j * Q_{ji} / π_i

Parameters:

Q (ndarray) – Original infinitesimal generator matrix
pi (ndarray | None) – Steady-state distribution (optional, computed if None)

Returns:

Time-reversed generator matrix

Return type:

ndarray

ctmc_rand(n, density=0.3, max_rate=10.0)[source]

Generate random CTMC generator matrix.

Parameters:

n (int) – Number of states
density (float) – Sparsity density (0 to 1, default 0.3)
max_rate (float) – Maximum transition rate (default 10.0)

Returns:

Random infinitesimal generator matrix

Return type:

ndarray

ctmc_simulate(Q, initial_state, max_time, max_events=10000, seed=None)[source]

Simulate CTMC sample path using Gillespie algorithm.

Generates a realization of the continuous-time Markov chain using the next-reaction method.

Parameters:

Q (ndarray) – Infinitesimal generator matrix
initial_state (int) – Starting state (integer index)
max_time (float) – Maximum simulation time
max_events (int) – Maximum number of transitions (default: 10000)
seed (int | None) – Random seed for reproducibility (optional)

Returns:

‘states’: Array of visited states
’times’: Array of transition times
’sojourn_times’: Time spent in each state

Return type:

dict with

ctmc_isfeasible(Q, tolerance=1e-10)[source]

Check if matrix is a valid CTMC infinitesimal generator.

Validates: - Off-diagonal elements are non-negative - Row sums are zero - Diagonal elements are non-positive

Parameters:

Q (ndarray) – Candidate generator matrix
tolerance (float) – Numerical tolerance (default: 1e-10)

Returns:

True if matrix is valid CTMC generator

Return type:

bool

ctmc_ssg(sn, options=None)[source]

Generate complete CTMC state space for a queueing network.

Creates all possible network states including those not reachable from the initial state. For open classes, a cutoff parameter limits the maximum population to keep state space finite.

The state space is aggregated to show per-station-class job counts.

Parameters:

sn (Any) – NetworkStruct object (from getStruct())
options (Dict | None) – Solver options dict with fields: - cutoff: Population cutoff for open classes (required if open) - config.hide_immediate: Hide immediate transitions (default True)

Returns:

state_space: Complete state space matrix (rows=states, cols=state components)
state_space_aggr: Aggregated state space (rows=states, cols=stations*classes)
state_space_hashed: Hashed state indices for lookup
node_state_space: Dictionary of per-node state spaces
sn: Updated network structure with space field populated

Return type:

CtmcSsgResult containing

References

MATLAB: matlab/src/api/mc/ctmc_ssg.m

ctmc_ssg_reachability(sn, options=None)[source]

Generate reachable CTMC state space for a queueing network.

Creates only the states reachable from the initial state through valid transitions. This is more efficient than ctmc_ssg for networks with constrained reachability.

Parameters:

sn (Any) – NetworkStruct object (from getStruct())
options (Dict | None) – Solver options dict with fields: - config.hide_immediate: Hide immediate transitions (default True)

Returns:

state_space: Reachable state space matrix
state_space_aggr: Aggregated state space (per station-class)
state_space_hashed: Hashed state indices
node_state_space: Dictionary of per-node state spaces
sn: Updated network structure

Return type:

CtmcSsgResult containing

References

MATLAB: matlab/src/api/mc/ctmc_ssg_reachability.m

class CtmcSsgResult(state_space, state_space_aggr, state_space_hashed, node_state_space, sn)[source]

Bases: object

Result from CTMC state space generation.

state_space: ndarray

state_space_aggr: ndarray

state_space_hashed: ndarray

node_state_space: Dict[int, ndarray]

sn: Any

dtmc_solve(P)[source]

Solve for steady-state probabilities of a DTMC.

Computes the stationary distribution π by solving π(P - I) = 0 with normalization constraint Σπ = 1.

This leverages the CTMC solver by treating (P - I) as an infinitesimal generator.

Parameters:: P (ndarray) – Transition probability matrix (row stochastic)
Returns:: Steady-state probability distribution (1D array)
Return type:: ndarray

dtmc_solve_reducible(P, pin=None)[source]

Solve reducible DTMCs with transient states.

Handles DTMCs with multiple recurrent classes and transient states by: 1. Decomposing into strongly connected components (SCCs) 2. Identifying recurrent vs transient SCCs 3. Computing limiting distribution considering absorption from transient states

For a reducible DTMC with a single transient SCC, this computes the limiting distribution when starting from the transient states (e.g., class switching networks where jobs start in a transient class).

Parameters:

P (ndarray) – Transition probability matrix (possibly reducible)
pin (ndarray) – Initial probability vector (optional)

Returns:

Steady-state probability vector

Return type:

ndarray

dtmc_makestochastic(A)[source]

Convert matrix to row-stochastic transition matrix.

Normalizes each row to sum to 1. Rows with zero sum are replaced with uniform distribution.

Parameters:: A (ndarray) – Input matrix to normalize
Returns:: Row-stochastic matrix
Return type:: ndarray

dtmc_isfeasible(P, tolerance=1e-10)[source]

Check if matrix is a valid DTMC transition matrix.

Validates: - All elements are non-negative - All row sums equal 1

Parameters:

P (ndarray) – Candidate transition matrix
tolerance (float) – Numerical tolerance (default: 1e-10)

Returns:

True if matrix is valid DTMC transition matrix

Return type:

bool

dtmc_simulate(P, initial_state, num_steps, seed=None)[source]

Simulate DTMC sample path.

Generates a realization of the discrete-time Markov chain for a specified number of steps.

Parameters:

P (ndarray) – Transition probability matrix
initial_state (int) – Starting state index
num_steps (int) – Number of simulation steps

Returns:

Array of visited states (length num_steps + 1)

Return type:

ndarray

dtmc_rand(n, density=0.5)[source]

Generate random DTMC transition matrix.

Parameters:

n (int) – Number of states
density (float) – Sparsity density (0 to 1, default 0.5)

Returns:

Random transition probability matrix

Return type:

ndarray

dtmc_timereverse(P, pi=None)[source]

Compute time-reversed DTMC transition matrix.

The time-reversed chain has transition probabilities: P*_{ij} = π_j * P_{ji} / π_i

Parameters:

P (ndarray) – Original transition matrix
pi (ndarray | None) – Steady-state distribution (optional, computed if None)

Returns:

Time-reversed transition matrix

Return type:

ndarray

dtmc_stochcomp(P, keep_states, eliminate_states=None)[source]

Compute stochastic complement of DTMC.

Reduces the DTMC by eliminating specified states while preserving the steady-state distribution restricted to the kept states.

Parameters:

P (ndarray) – Transition probability matrix
keep_states (ndarray) – States to retain in reduced model
eliminate_states (ndarray | None) – States to eliminate (optional, inferred if None)

Returns:

Reduced transition matrix (stochastic complement)

Return type:

ndarray

dtmc_transient(P, initial_dist, steps)[source]

Compute transient probabilities of a DTMC.

Calculates π(n) = π(0) * P^n for each step from 0 to steps.

Parameters:

P (ndarray) – Transition probability matrix
initial_dist (ndarray) – Initial probability distribution π(0)
steps (int) – Number of time steps

Returns:

Array of shape (steps+1, n) with transient probabilities

Return type:

ndarray

dtmc_hitting_time(P, target_states)[source]

Compute mean hitting times to target states.

Calculates the expected number of steps to reach any target state from each starting state.

Parameters:

P (ndarray) – Transition probability matrix
target_states (ndarray) – Array of target state indices

Returns:

Array of mean hitting times from each state

Return type:

ndarray

class CourtoisResult(p, Qperm, Qdec, eps, epsMAX, P, B, q)[source]

Bases: object

Result of Courtois decomposition.

p: ndarray

Qperm: ndarray

Qdec: ndarray

eps: float

epsMAX: float

P: ndarray

B: ndarray

q: float

class KMSResult(p, p_1, Qperm, eps, epsMAX, pcourt)[source]

Bases: object

Result of KMS aggregation-disaggregation.

p: ndarray

p_1: ndarray

Qperm: ndarray

eps: float

epsMAX: float

pcourt: ndarray

class TakahashiResult(p, p_1, pcourt, Qperm, eps, epsMAX)[source]

Bases: object

Result of Takahashi aggregation-disaggregation.

p: ndarray

p_1: ndarray

pcourt: ndarray

Qperm: ndarray

eps: float

epsMAX: float

ctmc_courtois(Q, MS, q=None)[source]

Courtois decomposition for near-completely decomposable CTMCs.

Decomposes a large CTMC into macrostates and computes approximate steady-state probabilities using hierarchical aggregation.

Parameters:

Q (ndarray) – Infinitesimal generator matrix
MS (List[List[int]]) – List where MS[i] is the list of state indices in macrostate i
q (float | None) – Randomization coefficient (optional)

Returns:

CourtoisResult with approximate solution and diagnostics

Return type:

CourtoisResult

References

Original MATLAB: matlab/src/api/mc/ctmc_courtois.m Courtois, “Decomposability: Queueing and Computer System Applications”, 1977

ctmc_kms(Q, MS, numSteps=10)[source]

Koury-McAllister-Stewart aggregation-disaggregation method.

Iteratively refines the Courtois decomposition solution using aggregation and disaggregation steps.

Parameters:

Q (ndarray) – Infinitesimal generator matrix
MS (List[List[int]]) – List where MS[i] is the list of state indices in macrostate i
numSteps (int) – Number of iterative steps (default: 10)

Returns:

KMSResult with refined solution

Return type:

KMSResult

References

Original MATLAB: matlab/src/api/mc/ctmc_kms.m Koury, McAllister, Stewart, “Iterative Methods for Computing Stationary Distributions of Nearly Completely Decomposable Markov Chains”, 1984

ctmc_takahashi(Q, MS, numSteps=10)[source]

Takahashi’s aggregation-disaggregation method.

Iteratively refines the Courtois decomposition solution using a different aggregation-disaggregation scheme.

Parameters:

Q (ndarray) – Infinitesimal generator matrix
MS (List[List[int]]) – List where MS[i] is the list of state indices in macrostate i
numSteps (int) – Number of iterative steps (default: 10)

Returns:

TakahashiResult with refined solution

Return type:

TakahashiResult

References

Original MATLAB: matlab/src/api/mc/ctmc_takahashi.m Takahashi, “A Lumping Method for Numerical Calculations of Stationary Distributions of Markov Chains”, 1975

ctmc_multi(Q, MS, MSS)[source]

Multigrid aggregation-disaggregation method.

Two-level hierarchical decomposition using nested macrostates.

Parameters:

Q (ndarray) – Infinitesimal generator matrix
MS (List[List[int]]) – List where MS[i] is the list of state indices in macrostate i
MSS (List[List[int]]) – List where MSS[i] is the list of macrostate indices in macro-macrostate i

Returns:

TakahashiResult with multigrid solution

Return type:

TakahashiResult

References

Original MATLAB: matlab/src/api/mc/ctmc_multi.m

Continuous-Time Markov Chains (line_solver.api.ctmc)

The ctmc module contains algorithms specifically for continuous-time Markov chains (CTMCs), including steady-state solvers and transient analysis.

Discrete-Time Markov Chains (line_solver.api.dtmc)

The dtmc module provides algorithms for discrete-time Markov chains (DTMCs), including steady-state and transient analysis.