(data structure)
Definition: A finite state machine with probabilities for each transition, that is, a probability that the next state is sj given that the current state is si.
See also hidden Markov model.
Note: Equivalently, a weighted, directed graph in which the weights correspond to the probability of that transition. In other words, the weights are nonnegative and the total weight of outgoing edges is positive. If the weights are normalized, the total weight, including self-loops, is 1. After [Leda98].
Author: PEB
Named after Andrei Andreyevich Markov (1856 - 1922), who studied poetry and other texts as stochastic sequences of characters.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 23 January 2006.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Paul E. Black, "Markov chain", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 23 January 2006. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/markovchain.html
