dtmc

Type-safe discrete-time Markov chains for Haskell.

dtmc supports both finite chains and locally finite kernels over countable state spaces. It validates probability data at construction, keeps finite models tied to their state type, and provides finite-time, structural, and long-run analysis alongside simulation.

Features

• Dense transition matrices indexed by domain-specific finite state types.
• Sparse transition kernels for finite or potentially infinite state spaces.
• Validated dense and sparse probability distributions.
• Distribution evolution, transition probabilities, timed events, and conditional probabilities.
• Hitting times, first-return times, and finite or total visit counts.
• Communicating classes, recurrence, periodicity, and absorbing states.
• Canonical decomposition, fundamental matrices, and absorption analysis.
• Stationary distributions, ordinary limits, and cyclic subsequential limits.
• Random sampling and trajectory simulation through either representation.
• No hmatrix types in the public API.

Installation

Add the package to your Cabal file:

build-depends: dtmc ^>=0.2.0.0

The package requires GHC 9.6 or newer and a BLAS/LAPACK implementation for its internal use of hmatrix. On Ubuntu or Debian:

sudo apt-get install libblas-dev liblapack-dev

On macOS, hmatrix can use Apple Accelerate.

Quick start

This complete example defines a two-state weather chain and asks three different probability questions:

{-# LANGUAGE DeriveAnyClass #-}
{-# LANGUAGE DeriveGeneric #-}

module Main (main) where

import Dtmc.Analysis.Event (DiscreteEvent (..))
import Dtmc.Analysis.FiniteTime qualified as FiniteTime
import Dtmc.Analysis.HittingTime qualified as HittingTime
import Dtmc.Distribution.Vector (DistributionVector)
import Dtmc.Distribution.Vector qualified as Vector
import Dtmc.State (FiniteState)
import Dtmc.Transition.Matrix (TransitionMatrix)
import Dtmc.Transition.Matrix qualified as Matrix
import GHC.Generics (Generic)

data Weather = Dry | Wet
  deriving (Eq, Ord, Show, Generic, FiniteState)

weather :: TransitionMatrix Weather
weather =
  checked $
    Matrix.fromRows
      [ [0.9, 0.1]
      , [0.4, 0.6]
      ]

initial :: DistributionVector Weather
initial = checked (Vector.fromList [1, 0])

checked :: Show problem => Either problem value -> value
checked = either (error . show) id

main :: IO ()
main = do
  -- P(X_2 = Wet | X_0 = Dry)
  print (FiniteTime.nStepProbability 2 weather Dry Wet)

  -- P(H_Wet <= 2) under the initial distribution
  print (HittingTime.probability (AtMost 2) weather (== Wet) initial)

  -- P(H_Wet < infinity) under the initial distribution
  print (HittingTime.eventualProbability weather [Wet] initial)

Constructor order is the canonical state order. The rows and columns above therefore represent Dry followed by Wet; Vector.fromList uses the same order. Invalid dimensions, weights, or row sums are returned as typed errors.

The two hitting queries take their target differently, and the difference is not cosmetic. A bounded query walks forward a fixed number of steps, so it works through any Transition — including a kernel over an infinite state space — and takes a predicate. An eventual query solves a linear system over the whole state space, so it requires a finite TransitionMatrix, takes an explicit target list, and returns Either LinearSystemError.

Analysis modules intentionally use concise, overlapping names such as probability and expectation. Import them qualified, as in the example. The top-level Dtmc module is an orientation and module map rather than a facade of re-exports.

Choosing a representation

A TransitionKernel does not enumerate its state space. It only requires each one-step transition law to have finite support, so the same finite-horizon algorithms work without global truncation. Analyses that need the complete state space require a finite TransitionMatrix.

Finite states

For a named enumeration, derive Generic and FiniteState:

data Queue = Empty | Busy | Full
  deriving (Eq, Ord, Show, Generic, FiniteState)

Constructors must have no fields. Their declaration order determines the canonical order used by vectors, matrices, and whole-state results. Use Finite n when names are unnecessary. Instances are also provided for (), Bool, and Ordering.

Locally finite kernels

A kernel is a function from a state to a validated sparse distribution:

import Dtmc.Distribution (DistributionError)
import Dtmc.Distribution.Map qualified as Distribution
import Dtmc.Transition.Kernel (TransitionKernel)
import Dtmc.Transition.Kernel qualified as Kernel

countUp :: TransitionKernel Integer
countUp = Kernel.fromLaws (Distribution.pointMass . (+ 1))

randomWalk :: Either DistributionError (TransitionKernel Integer)
randomWalk = do
  stepLaw <- Distribution.fromList [(-1, 0.5), (1, 0.5)]
  pure $
    Kernel.fromLaws $ \position ->
      Distribution.mapStates (+ position) stepLaw

The random walk has an infinite reachable state space, while every individual transition law remains finite.

Construction guide

Transition matrices can be combined with compose, identity, and power. Both matrix and vector values are abstract and nominally associated with their state type, preventing accidental use with a different finite model.

Analysis guide

Functions ending in GivenInitialState condition on a particular starting state. Their shorter counterparts accept any compatible Distribution.

Discrete events

Hitting, return, and visit-count queries use DiscreteEvent:

For a quantity that may be infinite, GreaterThan and AtLeast include its mass at infinity. Eventual hitting, eventual return, and infinitely many visits remain explicit operations because they require finite-state analysis.

Validation and numerical behavior

Distribution constructors reject non-finite values and repair coordinate or total-mass error only within 1e-9. Tolerated coordinate error is clamped to [0, 1], then the repaired weights are normalized. Transition-matrix rows follow the same policy.

Structural analysis is combinatorial: a stored matrix entry is an edge exactly when it is greater than zero, with no floating-point tolerance. Numerical analyses use checked Double linear algebra and return Either LinearSystemError result on failure. Computed results are not silently clamped or renormalized, and mathematically infinite expectations are reported as InfiniteExpectation rather than floating-point infinity.

See each module's Haddock documentation for edge cases and complexity bounds.

Building from source

git clone https://github.com/kholmetskii/dtmc.git
cd dtmc
cabal update
cabal build all --enable-tests
cabal test all --test-show-details=direct

Generate local API documentation with:

cabal haddock all --haddock-hyperlink-source

The package is tested with GHC 9.6.7, 9.8.4, 9.10.3, 9.12.4, and 9.14.1.

Documentation and support

• Browse the Haddock API documentation.
• Report bugs or request features in the issue tracker.
• See the changelog for release notes.

License

dtmc is distributed under the BSD 3-Clause License; see the LICENSE file in the source distribution.