Usage

Installation

To use jMarkov, first install it using pip:

(.venv) $ pip install jmarkov

Markov chains

class jmarkov.markov_chain.markov_chain

Continuous-time Markov chains

class jmarkov.ctmc.ctmc(generator: array)

Implements a finite continuous-time Markov chain (CTMC)

The chain is defined by its number of states, states, and a generator matrix. The class provides methods to compute both stationary and transient metrics, as well as to check the chain properties (ergodicity).

__init__(generator: array)

Creates a continuous-time Markov chain from its generator matrix

steady_state() → ndarray

Computes the steady state distribution of the continuous-time Markov chain

Computes the steady state probability distribution by replacing one of the matrix equations with a normalizing equation that ensures the result is a probability distribution.

Returns the stationary probability distribution in array form

transient_probabilities(t: float, alpha: ndarray) → ndarray

Computes the transient distribution at time t with initial state alpha

Computes alpha*exp(Q*t)*ones to obtain the probability distribution at time t given the initial probability distribution alpha

first_passage_time(target: str)

Computes the expected first passage time to a target state from a start state.

This method calculates the expected number of steps required for the Markov chain to reach the specified target state from the start state by creating a sub-matrix of the generator matrix with the target removed.

Returns the expected steps to reach the target state from any start state (except target) in array form

occupation_time(T, Epsilon=1e-05)

Computes the expected occupation time in each state until time T.

This method computes the expected time the chain spends in each state, from time 0 until time T. To this end it uses the embedded matrix and the uniformization method.

Returns the expected time in each state from 0 to T

is_irreducible()

Checks if the given continous-time Markov Chain is irreducible.

This method determines if the continous-time Markov Chain is irreducible by checking if, starting in any state, it is possible to reach any other state in a sequence of transitions.

Returns a boolean

is_ergodic()

Checks if a given continous-time Markov Chain is ergodic.

Given that a finite continous-time Markov Chain is ergodic if it is irreducible, this method checks if it is irreducible to determine if the provided chain is ergodic or not.

Discrete-time Markov chains

class jmarkov.dtmc.dtmc(transition_matrix: array)

Implements a finite discrete-time Markov chain (CTMC)

The chain is defined by its number of states, states, and a transition matrix. The class provides methods to compute both stationary and transient metrics, as well as to check the chain properties (aperiodicity and ergodicity).

__init__(transition_matrix: array)

steady_state() → ndarray

Computes the steady state distribution of the discrete-time Markov chain

Computes the steady state probability distribution by replacing one of the matrix equations with a normalizing equation that ensures the result is a probability distribution.

Returns the stationary probability distribution in array form

transient_probabilities(n, alpha)

Computes the transient distribution at transition n with initial state alpha

Computes alpha*(P^n)*ones to obtain the probability distribution at time/transition n given the initial probability distribution alpha

period()

Computes the period of a discrete-time Markov Chain.

This method calculates the period of a discrete-time Markov Chain by iterating a total of N steps, where N represents the number of states that the chain has. In each k-th iteration, the chain is elevated to the k-th power to compute the transient probabilities in the k-th step. If one of the elementsin in the diagonal of the resulting matrix is greater than 0, the chain can potentially have a period k. The period of the matrix will be the Greatest Common Divisor (GCD) between the potential new period of the matrix in the k-th iteration and the current GCD before the k-th iteration.

Returns the period of the chain as an int

is_irreducible()

Checks if the given discrete-time Markov Chain is irreducible.

This method determines if the discrete-time Markov Chain is irreducible by checking if, starting in any state, it is possible to reach any other state in a sequence of transitions.

Returns a boolean

is_ergodic()

Checks if a given discrete-time Markov Chain is ergodic.

Given that a finite discrete-time Markov Chain is ergodic if it is aperiodic and irreducible, this method checks if both conditions are met to determine if the provided chain is ergodic or not.

Returns a boolean

Infinite Continuous-time Birth-death Markov chains

class jmarkov.ctbd.ctbd(birth_rates: array, death_rates: array)

Implements an infinite continuous-time birth-death (CTBD) Markov chain

The CTBD chain is defined by its birth and death rates, which themselves define the number of states, states, and the generator matrix. The representation in this class relies on the birth and death rates between states 0 to K, and it is assumed that from state K onwards the birth and death rates have the same values. The class provides methods to compute both stationary and transient metrics, as well as to check the chain properties (ergodicity).

__init__(birth_rates: array, death_rates: array)

Creates a continuous-time Birth-Death Markov chain from its birth and death rates

_check_birth_death_rates(birth_rates: ndarray, death_rates: ndarray)

Checks that all birth and death rates are positive

Checks that arrays of birth and death rates have the same nonzero size

steady_state(n: int = 0) → ndarray

Computes the steady state distribution of the continuous-time BD Markov chain

Computes the steady state probability distribution by solving the balance equations to first find pi0 and then the remaining entries of the distribution.

n is an optional parameter to specify the length of the steady state distribution vector. It should be at least as large as the size of the birth and death rate arrays. If not specified, the returned vector is equal to the length of the birth and death arrays.

Returns the stationary probability distribution in array form

is_irreducible()

Checks if the given continous-time BD Markov Chain is irreducible.

This method determines if the birth-death continous-time Markov Chain is irreducible by checking if, starting in any state, it is possible to reach any other state in a sequence of transitions.

Returns a boolean

is_ergodic()

Checks if the given continous-time BD Markov Chain is ergodic.

Given that this chain is infinite, we first check if is irreducible and next check if the last birth rate is smaller than the last death rate, a condition that ensures ergodicity.

Finite Continuous-time Birth-death Markov chains

class jmarkov.finite_ctbd.finite_ctbd(birth_rates: array, death_rates: array)

Implements a finite continuous-time birth-death (CTBD) Markov chain

The finite CTBD chain is defined by its birth and death rates, which themselves define the number of states, states, and the generator matrix. The representation in this class relies on the birth and death rates between states 0 to K. The class provides methods to compute stationary metrics, as well as to check the chain properties (ergodicity).

__init__(birth_rates: array, death_rates: array)

Creates a finite continuous-time Birth-Death Markov chain from its birth and death rates

_check_birth_death_rates(birth_rates: ndarray, death_rates: ndarray)

Checks that all birth and death rates are positive

Checks that arrays of birth and death rates have the same nonzero size

steady_state() → ndarray

Computes the steady state distribution of the continuous-time BD Markov chain

Computes the steady state probability distribution by solving the balance equations to first find pi0 and then the remaining entries of the distribution.

Returns the stationary probability distribution in array form

is_irreducible()

Checks if the given continous-time BD Markov Chain is irreducible.

This method determines if the birth-death continous-time Markov Chain is irreducible by checking if, starting in any state, it is possible to reach any other state in a sequence of transitions.

Returns a boolean

is_ergodic()

Checks if the given continous-time BD Markov Chain is ergodic.

Given that a finite continous-time Markov Chain is ergodic if it is irreducible, this method checks if it is irreducible to determine if the provided chain is ergodic or not.

Queueing systems

class jmarkov.queue.mmk.mmk(k: int, arr_rate: float64, ser_rate: float64)

Implements an M/M/k queue and computes steady state metrics

The M/M/k queue has exponential interarrival times, with rate arr_rate, exponential service times, with ser_rate, and k servers in parallel.

The class builds a birth-death chain that models this queue and uses the steady state probability distribution of the chain to compute measures of performance such as mean number of entities in the system, in queue, in service, and the mean time in the system, in queue, and in service.

__init__(k: int, arr_rate: float64, ser_rate: float64)

Creates an M/M/k queue with k servers, arr_rate arrival rate and ser_rate service rate

mean_number_entities() → float64

Computes the mean number of entities in the system in steady state

A birth-death chain is built and its stattionary probability distribution is used to compute the mean number of entities in the system in steady state

mean_number_entities_queue() → float64

Computes the mean number of entities in queue in steady state

A birth-death chain is built and its stattionary probability distribution is used to compute the mean number of entities in queue in steady state

mean_number_entities_service() → float64

Computes the mean number of entities in service in steady state

A birth-death chain is built and its stattionary probability distribution is used to compute the mean number of entities in the system in steady state

mean_time_system() → float64

Computes the mean time in the system in steady state

A birth-death chain is built and its stationary probability distribution is used to compute the mean number of entities in the system in steady state, which is then used with Little’s Law to obtain the mean time in the system in steady state

mean_time_queue() → float64

Computes the mean time in the queue in steady state

A birth-death chain is built and its stationary probability distribution is used to compute the mean number of entities in the queue in steady state, which is then used with Little’s Law to obtain the mean time in the system in steady state

mean_time_service() → float64

Computes the mean time in service

A simple relation is used to obtain the mean service time

is_stable() → bool

Returns True if the queue is stable, False otherwise

This queue is stable if the arrival rate is smaller than the maximum service rate

class jmarkov.queue.mmkn.mmkn(k: int, arr_rate: float64, ser_rate: float64, n: int)

Implements an M/M/k/n queue and computes steady state metrics

The M/M/k/n queue has exponential interarrival times, with rate arr_rate, exponential service times, with ser_rate, k servers in parallel, and n places in total (n-k for waiting).

The class builds a birth-death chain that models this queue and uses the steady state probability distribution of the chain to compute measures of performance such as mean number of entities in the system, in queue, in service, and the mean time in the system, in queue, and in service.

__init__(k: int, arr_rate: float64, ser_rate: float64, n: int)

Creates an M/M/k/n queue with k servers, arr_rate arrival rate, ser_rate service rate, and capacity n

mean_number_entities() → float64

Computes the mean number of entities in the system in steady state

A birth-death chain is built and its stationary probability distribution is used to compute the mean number of entities in the system in steady state

mean_number_entities_queue() → float64

Computes the mean number of entities in queue in steady state

A birth-death chain is built and its stattionary probability distribution is used to compute the mean number of entities in queue in steady state

mean_number_entities_service() → float64

Computes the mean number of entities in service in steady state

A birth-death chain is built and its stattionary probability distribution is used to compute the mean number of entities in the system in steady state

mean_time_system() → float64

Computes the mean time in the system in steady state

A birth-death chain is built and its stationary probability distribution is used to compute the mean number of entities in the system in steady state, which is then used with Little’s Law to obtain the mean time in the system in steady state

mean_time_queue() → float64

Computes the mean time in the queue in steady state

A birth-death chain is built and its stationary probability distribution is used to compute the mean number of entities in the queue in steady state, which is then used with Little’s Law to obtain the mean time in the system in steady state

mean_time_service() → float64

Computes the mean time in service

A birth-death chain is built and its stationary probability distribution is used to compute the mean number of entities in the queue in steady state, which is then used with Little’s Law to obtain the mean time in the system in steady state

Discrete-time Markov Decision Processes (MDPs)

class jmarkov.mdp.dtmdp.dtmdp(states: array, actions: array, transition_matrices: Dict, immediate_returns: array, discount_factor: int)

Implements a Markov decision process (MDP)

The process is defined by its number of states, states, number of actions, actions, the immediate returns of implementing each action and a transition matrix for each action. The class provides methods to solve MDPs and to compute the expected value of the optimal policy.

__init__(states: array, actions: array, transition_matrices: Dict, immediate_returns: array, discount_factor: int)

Creates a markov decision process from its transition matrices, immediate returns and discount factor

_check_transition_matrices(M: Dict)

Checks that all matrices are stochastic

Checks that all row sums are equal to one and all elements are non negative

_check_immediate_returns(R: array, M: Dict)

Checks that the immediate returns are valid and dimensionally-coherent

Checks that immediate return array has dimensions length of states x length of actions

_check_discount_factor(beta: int)

Checks that the discount factor is valid

Checks that discount factor is a number equal to or greater than 0 and less than 1

Discrete-time Stochastic Dynamic Programming (SDPs)

class jmarkov.sdp.dtsdp.dtsdp(periods: array, states: array, actions: array, transition_matrices: Dict, immediate_returns: array, discount_factor: int)

Implements an Stochastic Decision Process (SDP)

The process is defined by its time horizon, number of states, states, number of actions, actions, the immediate returns of implementing each action and a transition matrix for each action. The class provides methods to solve SDPs and to compute the expected value of the optimal policy.

__init__(periods: array, states: array, actions: array, transition_matrices: Dict, immediate_returns: array, discount_factor: int)

Creates a markov decision process from its transition matrices, immediate returns and discount factor

_check_transition_matrices(M: Dict)

Checks that all matrices are stochastic

Checks that all row sums are equal to one and all elements are non negative

_check_immediate_returns(R: array, states: array, periods: array, actions: array)

Checks that the immediate returns are valid and dimensionally-coherent

Checks that immediate return array has dimensions length of epochs x length of states x length of actions

_check_discount_factor(beta: int)

Checks that the discount factor is valid

Checks that discount factor is a number equal to or greater than 0 and less than 1

_check_time_period(periods: int)

” Checks that the time period is valid

Checks that the time period is a number greater than 0

solve(minimize=False)

Solves SDP’s with backward iteration

Returns the expected value of following the optimal policy at each state and the optimal policy for each state