Markov chain

A Markov chain (named for Andrey Markov) is a sequence of random variable taking values in the state space of the chain, with the property that the probability of moving to the next state depends only upon the current state:

Pr(X n+1=x|X 1=x 1,X 2=x 2,...,X n=x n)=Pr(X n+1=x|X n=x n). Pr(X_{n + 1} = x | X_1 = x_1, X_2 = x_2,..., X_n = x_n) = Pr(X_{n + 1} = x | X_n = x_n).

A Markov chain can also be described as a coalgebra for the endofunctor on Set which maps a set XX to the set of probability distributions on XX.

Ian Durham: I assume that a Markov chain can be represented as a directed graph in some way and thus can be used to generate a free category of some sort. Is this a correct assumption?

Eric: I’m pretty sure that is the case for finite Markov chains.

Ian Durham: Hmmm. I’ll have to think about that.



Baez and his students recently defined a generalization, open Markov chains:

  • John C. Baez, Brendan Fong, Blake S. Pollard, A compositional framework for Markov processes, arxiv/1508.06448

category: probability

Last revised on January 12, 2016 at 16:59:53. See the history of this page for a list of all contributions to it.