In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a Markov information source, or simply, a Markov source, is an
information source whose underlying dynamics are given by a stationary finite
Markov chain
A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happe ...
.
Formal definition
An information source is a sequence of
random variable
A random variable (also called random quantity, aleatory variable, or stochastic variable) is a mathematical formalization of a quantity or object which depends on random events. It is a mapping or a function from possible outcomes (e.g., the po ...
s ranging over a finite alphabet Γ, having a
stationary distribution.
A Markov information source is then a (stationary) Markov chain ''M'', together with a function
:
that maps states ''S'' in the Markov chain to letters in the alphabet Γ.
A unifilar Markov source is a Markov source for which the values
are distinct whenever each of the states
are reachable, in one step, from a common prior state. Unifilar sources are notable in that many of their properties are far more easily analyzed, as compared to the general case.
00
Applications
Markov sources are commonly used in
communication theory
Communication theory is a proposed description of communication phenomena, the relationships among them, a storyline describing these relationships, and an argument for these three elements. Communication theory provides a way of talking about a ...
, as a model of a
transmitter
In electronics and telecommunications, a radio transmitter or just transmitter is an electronic device which produces radio waves with an antenna (radio), antenna. The transmitter itself generates a radio frequency alternating current, which i ...
. Markov sources also occur in
natural language processing
Natural language processing (NLP) is an interdisciplinary subfield of linguistics, computer science, and artificial intelligence concerned with the interactions between computers and human language, in particular how to program computers to pro ...
, where they are used to represent hidden meaning in a text. Given the output of a Markov source, whose underlying Markov chain is unknown, the task of solving for the underlying chain is undertaken by the techniques of
hidden Markov model
A hidden Markov model (HMM) is a statistical Markov model in which the system being modeled is assumed to be a Markov process — call it X — with unobservable ("''hidden''") states. As part of the definition, HMM requires that there be an ob ...
s, such as the
Viterbi algorithm.
See also
*
Entropy rate
References
*Robert B. Ash, ''Information Theory'', (1965) Dover Publications.
Markov processes
Statistical natural language processing
{{probability-stub