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 functions.

This module provides unified access to both continuous-time (CTMC) and discrete-time (DTMC) Markov chain analysis functions. It serves as a consolidated interface for Markov chain computations used throughout LINE.

Functions include both CTMC and DTMC methods: - ctmc_makeinfgen: Construct infinitesimal generator - ctmc_solve: Steady-state CTMC analysis - dtmc_solve: Steady-state DTMC analysis - Transient analysis methods - Simulation functions - Time-reversal and other transformations

This module aggregates functions from both ctmc and dtmc modules.

ctmc_makeinfgen(birth_rates, death_rates, max_states=None)

Construct infinitesimal generator for birth-death process.

Creates a tridiagonal generator matrix for a birth-death CTMC with specified birth and death rates.

Parameters:

• birth_rates – Array of birth rates (transitions i -> i+1).

• death_rates – Array of death rates (transitions i -> i-1).

• max_states – Maximum number of states (optional).

Returns:

Infinitesimal generator matrix Q.

Return type:

numpy.ndarray

ctmc_solve(Q)

Solve for steady-state probabilities of a CTMC.

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

Parameters:

Q – Infinitesimal generator matrix.

Returns:

Steady-state probability distribution.

Return type:

numpy.ndarray

ctmc_transient(Q, initial_dist, time_points)

Compute transient probabilities of a CTMC.

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

Parameters:

• Q – Infinitesimal generator matrix.

• initial_dist – Initial probability distribution π(0).

• time_points – Array of time points to evaluate.

Returns:

Transient probabilities at each time point.

Return type:

numpy.ndarray

ctmc_simulate(Q, initial_state, max_time, max_events=10000)

Simulate CTMC sample path.

Generates a realization of the continuous-time Markov chain using the Gillespie algorithm or similar Monte Carlo method.

Parameters:

• Q – Infinitesimal generator matrix.

• initial_state – Starting state (integer index).

• max_time – Maximum simulation time.

• max_events – Maximum number of transitions (default: 10000).

Returns:

Simulation results with ‘states’, ‘times’, and ‘sojourn_times’.

Return type:

dict

ctmc_randomization(Q, initial_dist, time_points, precision=1e-10)

Compute CTMC transient probabilities using randomization.

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

Parameters:

• Q – Infinitesimal generator matrix.

• initial_dist – Initial probability distribution.

• time_points – Array of time points to evaluate.

• precision – Numerical precision for truncation (default: 1e-10).

Returns:

Transient probabilities via randomization.

Return type:

numpy.ndarray

ctmc_uniformization(Q, lambda_rate=None)

Uniformize CTMC generator matrix.

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

Parameters:

• Q – Infinitesimal generator matrix.

• lambda_rate – Uniformization rate (optional, auto-computed if None).

Returns:

Contains uniformized transition matrix ‘P’ and rate ‘lambda’.

Return type:

dict

ctmc_stochcomp(Q, keep_states, eliminate_states)

Compute stochastic complement of CTMC.

Parameters:

• Q – Infinitesimal generator matrix.

• keep_states – States to retain in reduced model.

• eliminate_states – States to eliminate from model.

Returns:

Reduced generator matrix.

Return type:

numpy.ndarray

ctmc_timereverse(Q, pi=None)

Compute time-reversed CTMC generator.

Parameters:

• Q – Original infinitesimal generator matrix.

• pi – Steady-state distribution (optional, computed if None).

Returns:

Time-reversed generator matrix.

Return type:

numpy.ndarray

ctmc_rand(n, density=0.3, max_rate=10.0)

Generate random CTMC generator matrix.

Parameters:

• n – Number of states.

• density – Sparsity density (default: 0.3).

• max_rate – Maximum transition rate (default: 10.0).

Returns:

Random infinitesimal generator matrix.

Return type:

numpy.ndarray

dtmc_solve(P)

Solve for steady-state probabilities of DTMC.

Parameters:

P – Transition probability matrix.

Returns:

Steady-state probability distribution.

Return type:

numpy.ndarray

dtmc_makestochastic(A)

Convert matrix to stochastic transition matrix.

Parameters:

A – Input matrix to normalize.

Returns:

Row-stochastic matrix.

Return type:

numpy.ndarray

dtmc_isfeasible(P, tolerance=1e-10)

Check if matrix is a valid DTMC transition matrix.

Parameters:

• P – Candidate transition matrix.

• tolerance – Numerical tolerance (default: 1e-10).

Returns:

True if matrix is valid DTMC.

Return type:

bool

dtmc_simulate(P, initial_state, num_steps)

Simulate DTMC sample path.

Parameters:

• P – Transition probability matrix.

• initial_state – Starting state index.

• num_steps – Number of simulation steps.

Returns:

Sequence of visited states.

Return type:

numpy.ndarray

dtmc_rand(n, density=0.5)

Generate random DTMC transition matrix.

Parameters:

• n – Number of states.

• density – Sparsity density (default: 0.5).

Returns:

Random transition probability matrix.

Return type:

numpy.ndarray

dtmc_stochcomp(P, keep_states, eliminate_states)

Compute stochastic complement of DTMC.

Parameters:

• P – Transition probability matrix.

• keep_states – States to retain in reduced model.

• eliminate_states – States to eliminate from model.

Returns:

Reduced transition matrix.

Return type:

numpy.ndarray

dtmc_timereverse(P, pi=None)

Compute time-reversed DTMC transition matrix.

Parameters:

• P – Original transition matrix.

• pi – Steady-state distribution (optional, computed if None).

Returns:

Time-reversed transition matrix.

Return type:

numpy.ndarray

ctmc_courtois(Q, epsilon=1e-6)

Courtois decomposition for nearly completely decomposable CTMCs.

Parameters:

• Q – Infinitesimal generator matrix

• epsilon – Decomposition threshold (default: 1e-6)

Returns:

Decomposition results with aggregated chain and coupling matrices

Return type:

dict

ctmc_kms(Q, blocks)

Koury-McAllister-Stewart aggregation-disaggregation method for CTMCs.

Parameters:

• Q – Infinitesimal generator matrix

• blocks – Block structure specification

Returns:

Steady-state probability vector

Return type:

numpy.ndarray

ctmc_multi(Q, levels)

Multi-level aggregation method for CTMCs.

Parameters:

• Q – Infinitesimal generator matrix

• levels – Number of aggregation levels

Returns:

Multi-level aggregation results

Return type:

dict

ctmc_pseudostochcomp(Q, partition)

Pseudo-stochastic complementation for CTMCs.

Parameters:

• Q – Infinitesimal generator matrix

• partition – State partition specification

Returns:

Reduced generator matrix

Return type:

numpy.ndarray

ctmc_relsolve(Q, ref_states)

Equilibrium distribution of a continuous-time Markov chain re-normalized with respect to reference states.

Parameters:

• Q – Infinitesimal generator matrix

• ref_states – Reference state indices

Returns:

Re-normalized steady-state probabilities

Return type:

numpy.ndarray

ctmc_solve_reducible(Q)

Solve reducible CTMCs by converting to DTMC via randomization.

Parameters:

Q – Infinitesimal generator matrix (possibly reducible)

Returns:

Steady-state probability vector

Return type:

numpy.ndarray

ctmc_stmonotone(Q)

Computes the stochastically monotone upper bound for a CTMC.

Parameters:

Q – Infinitesimal generator matrix

Returns:

Stochastically monotone upper bound generator

Return type:

numpy.ndarray

ctmc_takahashi(Q, epsilon=1e-8)

Takahashi’s aggregation-disaggregation method for CTMCs.

Parameters:

• Q – Infinitesimal generator matrix

• epsilon – Convergence threshold (default: 1e-8)

Returns:

Steady-state probability vector

Return type:

numpy.ndarray

ctmc_testpf_kolmogorov(Q)

Test if a CTMC has product form using Kolmogorov’s criteria.

Parameters:

Q – Infinitesimal generator matrix

Returns:

True if the CTMC has product form

Return type:

bool

dtmc_solve_reducible(P)

Solve reducible DTMCs.

Parameters:

P – Transition probability matrix (possibly reducible)

Returns:

Steady-state probability vector

Return type:

numpy.ndarray

dtmc_uniformization(P, steps)

DTMC uniformization analysis.

Parameters:

• P – Transition probability matrix

• steps – Number of uniformization steps

Returns:

Uniformization results with probability vector and iterations

Return type:

dict

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.

Continuous-Time Markov Chain (CTMC) analysis algorithms.

This module provides low-level functions for analyzing continuous-time Markov chains, including transient and steady-state analysis, uniformization, simulation, and various computational methods.

These functions support the CTMC solver and other analytical methods.

ctmc_uniformization(pi0, Q, t)

Compute transient probabilities using uniformization method.

Parameters:

• pi0 – Initial probability distribution.

• Q – Infinitesimal generator matrix.

• t – Time points for transient analysis.

Returns:

Transient probability distributions.

Return type:

numpy.ndarray

ctmc_timereverse(matrix)

Compute time-reversed CTMC.

Constructs the time-reversed continuous-time Markov chain using the detailed balance equations and steady-state probabilities.

Parameters:

matrix – Original infinitesimal generator matrix.

Returns:

Time-reversed generator matrix.

Return type:

numpy.ndarray

ctmc_makeinfgen(matrix)

Construct infinitesimal generator matrix.

Converts a rate matrix to a proper infinitesimal generator by setting diagonal elements to negative row sums.

Parameters:

matrix – Rate matrix with non-negative off-diagonal elements.

Returns:

Infinitesimal generator matrix.

Return type:

numpy.ndarray

ctmc_solve(matrix)

Solve for steady-state probabilities of a CTMC.

Computes the stationary distribution of a continuous-time Markov chain by solving the system πQ = 0 with the normalization constraint.

Parameters:

matrix – Infinitesimal generator matrix Q.

Returns:

Steady-state probability distribution π.

Return type:

numpy.ndarray

ctmc_transient(Q, pi0=None, t0=None, t1=None)

Compute transient probabilities of a CTMC.

Parameters:

• Q – Infinitesimal generator matrix.

• pi0 – Initial probability distribution (optional).

• t0 – Start time (optional).

• t1 – End time (required).

Returns:

(times, probabilities) arrays.

Return type:

tuple

ctmc_simulate(Q, pi0=None, n=1000)

Simulate a CTMC using Monte Carlo methods.

Parameters:

• Q – Infinitesimal generator matrix.

• pi0 – Initial distribution (optional).

• n – Number of simulation steps (default: 1000).

Returns:

(states, sojourn_times) arrays.

Return type:

tuple

ctmc_rand(length)

Generate random CTMC generator matrix.

Creates a random infinitesimal generator matrix suitable for use as a continuous-time Markov chain generator.

Parameters:

length – Size of the square matrix (number of states).

Returns:

Random infinitesimal generator matrix.

Return type:

numpy.ndarray

ctmc_ssg(sn, options)

Generate state space for CTMC from service network.

Parameters:

• sn – Service network model.

• options – Generation options.

Returns:

State space information including matrices and mappings.

Return type:

dict

ctmc_stochcomp(Q, I_list=None)

Compute stochastic complementarity decomposition of CTMC.

Parameters:

• Q – Infinitesimal generator matrix.

• I_list – Index list for decomposition (optional).

Returns:

Decomposed matrices (S, Q11, Q12, Q21, Q22, T).

Return type:

dict

ctmc_ssg_reachability(sn, options=None)

Generate reachable state space for CTMC from service network.

Parameters:

• sn – Service network model.

• options – Reachability analysis options (optional).

Returns:

Reachable state space information.

Return type:

dict

ctmc_randomization(Q, q=None)

Apply randomization (uniformization) to CTMC.

Parameters:

• Q – Infinitesimal generator matrix.

• q – Randomization rate (optional, auto-computed if None).

Returns:

(P_matrix, q_rate) - transition matrix and rate.

Return type:

tuple

ctmc_krylov(Q, pi0, t, options=None)

Compute CTMC transient probabilities using Krylov subspace methods.

Parameters:

• Q – Infinitesimal generator matrix.

• pi0 – Initial probability distribution.

• t – Time point.

• options – Krylov method options (optional).

Returns:

Transient probability distribution at time t.

Return type:

numpy.ndarray

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.

Discrete-Time Markov Chain (DTMC) analysis algorithms.

This module provides functions for analyzing discrete-time Markov chains, including steady-state analysis, stochastic complement operations, time-reversal, and simulation methods.

These functions are used by various solvers and analysis methods.

dtmc_solve(matrix)

Solve for steady-state probabilities of a DTMC.

Parameters:

matrix – Transition probability matrix.

Returns:

Steady-state probability distribution.

Return type:

numpy.ndarray

dtmc_stochcomp(matrix, indexes)

Compute stochastic complement of a DTMC.

Performs state space reduction by computing the stochastic complement, eliminating specified states while preserving transition probabilities.

Parameters:

• matrix – Transition probability matrix.

• indexes – List of state indexes to eliminate.

Returns:

Reduced transition matrix (stochastic complement).

Return type:

numpy.ndarray

dtmc_timereverse(matrix)

Compute time-reversed DTMC.

Constructs the time-reversed discrete-time Markov chain using the detailed balance equations and steady-state probabilities.

Parameters:

matrix – Original transition probability matrix.

Returns:

Time-reversed transition probability matrix.

Return type:

numpy.ndarray

dtmc_makestochastic(matrix)

Normalize matrix to be row-stochastic.

Converts a non-negative matrix to a proper stochastic matrix by normalizing rows to sum to 1.

Parameters:

matrix – Non-negative matrix to normalize.

Returns:

Row-stochastic matrix.

Return type:

numpy.ndarray

dtmc_rand(length)

Generate random DTMC transition matrix.

Creates a random row-stochastic matrix suitable for use as a discrete-time Markov chain transition matrix.

Parameters:

length – Size of the square matrix (number of states).

Returns:

Random stochastic transition matrix.

Return type:

numpy.ndarray

dtmc_simulate(P, pi0, n)

Simulate DTMC state trajectory.

Generates a sample path of the discrete-time Markov chain starting from an initial distribution.

Parameters:

• P – Transition probability matrix.

• pi0 – Initial state distribution.

• n – Number of time steps to simulate.

Returns:

Sequence of visited states.

Return type:

numpy.ndarray

dtmc_isfeasible(P)

Check if matrix is a valid DTMC transition matrix.

Verifies that the matrix satisfies the requirements for a discrete-time Markov chain: non-negative entries and row sums equal to 1.

Parameters:

P – Matrix to check.

Returns:

True if matrix is a valid DTMC transition matrix.

Return type:

bool