Algorithms

This module contains algorithmic tools operating on Markov chains.

Reachability

markovpy.algorithms.reachability.can_step(chain, u, v)

Returns true if state u can transition to state v

Parameters:

• chain – Chain of states

• u – State to transition from

• v – State to transition to

Return type:

bool

Returns:

Boolean indicating if state u can transition to state v

markovpy.algorithms.reachability.reachable(chain, source)

Returns a list of reachable states from state source

Parameters:

• chain – Chain of states

• source – Source state

Return type:

list

Returns:

List of reachable states

markovpy.algorithms.reachability.communicates(chain, u, v)

Returns true if state u can transition to state v AND state v can transition to state u. :type chain: :param chain: Chain of states :type u: :param u: First State :type v: :param v: Second State :rtype: bool :return: Returns true if state u can transition to state v AND state v can transition to state u.

Return type:

bool

markovpy.algorithms.reachability.communication_classes(chain)

Returns a list of communicating classes of chain :type chain: :param chain: Chain of states :rtype: list :return: List of communicating classes

Return type:

list

markovpy.algorithms.reachability.is_closed(chain, cls)

Returns true if state cls is closed (Cannot reach any other state) :type chain: :param chain: Chain of states :type cls: :param cls: Communicating class to check :rtype: bool :return: True if state cls is closed

Return type:

bool

Simulation

markovpy.algorithms.simulation.next_state(chain, current)

Return a single next state from current according to the chain’s transition probabilities.

Parameters:

• chain (Chain) – The Markov chain object

• current (str) – The current state from which to transition.

Return type:

str

Returns:

The next state chosen randomly according to probabilities.

markovpy.algorithms.simulation.simulate(chain, start, steps)

Simulates a path of length ‘steps’ from ‘start’. :type chain: Chain :param chain: The Markov chain object :type start: str :param start: The starting state of the simulation :type steps: int :param steps: The number of transitions to simulate :rtype: List[str] :return: A list of visited states, including the starting state

Parameters:

• chain (Chain)

• start (str)

• steps (int)

Return type:

List[str]

markovpy.algorithms.simulation.simulate_until(chain, start, target)

Simulates a path of ‘steps’ from ‘start’ to a ‘target’. :type chain: Chain :param chain: The Markov chain object :type start: str :param start: The starting state of the simulation :type target: :param target: The target states of the simulation :rtype: List[str] :return: A list of visited states, including the starting state

Parameters:

• chain (Chain)

• start (str)

Return type:

List[str]

States

markovpy.algorithms.states.is_absorbing(chain, s, tol=1e-12)

Returns true if the state can only transition to itself (Absorbing) :type chain: :param chain: Chain of states :type s: :param s: State to check :type tol: :param tol: Optional tolerance for absorbing states :rtype: bool :return: True if the state can only transition to itself (Absorbing)

Return type:

bool

markovpy.algorithms.states.absorbing_states(chain)

Returns a set of absorbing states :type chain: :param chain: Chain of states :rtype: set :return: Set of absorbing states

Return type:

set

markovpy.algorithms.states.is_transient(chain, s)

Returns true if the state can transition to other states (Transient) :type chain: :param chain: Chain of states :type s: :param s: State to check :rtype: bool :return: True if the state can transition to other states (Transient)

Return type:

bool

markovpy.algorithms.states.outgoing_mass(chain, s)

Returns the sum of all probabilities leaving this state (Useful for diagnostics) :type chain: :param chain: Chain of states :type s: :param s: State to check :rtype: float :return: Sum of all probabilities leaving this state.

Return type:

float