In
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, a Markov information source, or simply, a Markov source, is an
information source whose underlying dynamics are given by a stationary finite
Markov chain
In probability theory and statistics, a Markov chain or Markov process is a stochastic process describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally ...
.
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 Mathematics, mathematical formalization of a quantity or object which depends on randomness, random events. The term 'random variable' in its mathema ...
s ranging over a finite alphabet
, having a
stationary distribution Stationary distribution may refer to:
* and , a special distribution for a Markov chain such that if the chain starts with its stationary distribution, the marginal distribution of all states at any time will always be the stationary distribution. ...
.
A Markov information source is then a (stationary) Markov chain
, together with a
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-orie ...
:
that maps states
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.
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 (often abbreviated as XMTR or TX in technical documents) is an electronic device which produces radio waves with an antenna (radio), antenna with the purpose of sig ...
. Markov sources also occur in
natural language processing
Natural language processing (NLP) is a subfield of computer science and especially artificial intelligence. It is primarily concerned with providing computers with the ability to process data encoded in natural language and is thus closely related ...
, 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 Markov model in which the observations are dependent on a latent (or ''hidden'') Markov process (referred to as X). An HMM requires that there be an observable process Y whose outcomes depend on the outcomes of X ...
s, such as the
Viterbi algorithm
The Viterbi algorithm is a dynamic programming algorithm for obtaining the maximum a posteriori probability estimate of the most likely sequence of hidden states—called the Viterbi path—that results in a sequence of observed events. This i ...
.
See also
*
Entropy rate
In the mathematical theory of probability, the entropy rate or source information rate is a function assigning an entropy to a stochastic process.
For a strongly stationary process, the conditional entropy for latest random variable eventually ...
References
*Robert B. Ash, ''Information Theory'', (1965) Dover Publications.
Markov processes
Statistical natural language processing
{{probability-stub