Skip to content

Markov Chains & Probabilistic Computation

← Back to Domain-Specific Families

Abstractions about stochastic state-transition models and their computational uses — structured Markov chain variants (nearly completely decomposable Markov chain, telescoping Markov chain, trellis), sampling algorithms such as the Metropolis algorithm, and probabilistic verification or reversible-computing models (probabilistic CTL, billiard-ball computer).

6 abstractions in this family — domain-specific abstractions that sit near one another in structural-signature space (k-means over structural-signature embeddings). Each is shown with its short description.

  • Billiard-Ball Computer — A billiard-ball computer, a type of conservative logic circuit, is an idealized model of a reversible mechanical computer based on Newtonian dynamics, proposed in 1982 by Edward Fredkin and Tommaso Toffoli.
  • Metropolis Algorithm — In statistics and statistical physics, the Metropolis–Hastings algorithm is a Markov chain Monte Carlo (MCMC) method for obtaining a sequence of random samples from a probability distribution from which direct sampling is difficult.
  • Nearly completely decomposable Markov chain — In probability theory, a nearly completely decomposable (NCD) Markov chain is a Markov chain where the state space can be partitioned in such a way that movement within a partition occurs much more frequently than movement between partitions.
  • Probabilistic CTL — Probabilistic Computation Tree Logic (PCTL) is an extension of computation tree logic (CTL) that allows for probabilistic quantification of described properties.
  • Telescoping Markov chain — In probability theory, a telescoping Markov chain (TMC) is a vector-valued stochastic process that satisfies a Markov property and admits a hierarchical format through a network of transition matrices with cascading dependence.
  • Trellis (graph) — A trellis is a graph whose nodes are ordered into vertical slices (time) with every node at almost every time connected to at least one node at an earlier and at least one node at a later time.