Entropy rate
Encyclopedia
In the mathematical theory of probability
, the entropy rate or source information rate of a stochastic process
is, informally, the time density of the average information in a stochastic process. For stochastic processes with a countable index, the entropy rate H(X) is the limit of the joint entropy of n members of the process Xk divided by n, as n tends to
infinity
:
when the limit exists. An alternative, related quantity is:
For strongly stationary stochastic processes,
.
that is irreducible and aperiodic has a stationary distribution
, the entropy rate is independent of the initial distribution.
For example, for such a Markov chain Yk defined on a countable number of states, given the transition matrix Pij, H(Y) is given by:
where μi is the stationary distribution
of the chain.
A simple consequence of this definition is that the entropy rate of an i.i.d. stochastic process
has an entropy rate that is the same as the entropy
of any individual member of the process.
, for chromosome 1, which consists of 247 Mbp, there is an entropy rate of 1.82 bits per base pair.
Probability
Probability is ordinarily used to describe an attitude of mind towards some proposition of whose truth we arenot certain. The proposition of interest is usually of the form "Will a specific event occur?" The attitude of mind is of the form "How certain are we that the event will occur?" The...
, the entropy rate or source information rate of a stochastic process
Stochastic process
In probability theory, a stochastic process , or sometimes random process, is the counterpart to a deterministic process...
is, informally, the time density of the average information in a stochastic process. For stochastic processes with a countable index, the entropy rate H(X) is the limit of the joint entropy of n members of the process Xk divided by n, as n tends to
Limit (mathematics)
In mathematics, the concept of a "limit" is used to describe the value that a function or sequence "approaches" as the input or index approaches some value. The concept of limit allows mathematicians to define a new point from a Cauchy sequence of previously defined points within a complete metric...
infinity
Infinity
Infinity is a concept in many fields, most predominantly mathematics and physics, that refers to a quantity without bound or end. People have developed various ideas throughout history about the nature of infinity...
:
when the limit exists. An alternative, related quantity is:
For strongly stationary stochastic processes,
.Entropy rates for Markov chains
Since a stochastic process defined by a Markov chainMarkov chain
A Markov chain, named after Andrey Markov, is a mathematical system that undergoes transitions from one state to another, between a finite or countable number of possible states. It is a random process characterized as memoryless: the next state depends only on the current state and not on the...
that is irreducible and aperiodic has a stationary distribution
Stationary distribution
Stationary distribution may refer to:* The limiting distribution in a Markov chain* The marginal distribution of a stationary process or stationary time series* The set of joint probability distributions of a stationary process or stationary time series...
, the entropy rate is independent of the initial distribution.
For example, for such a Markov chain Yk defined on a countable number of states, given the transition matrix Pij, H(Y) is given by:
where μi is the stationary distribution
Stationary distribution
Stationary distribution may refer to:* The limiting distribution in a Markov chain* The marginal distribution of a stationary process or stationary time series* The set of joint probability distributions of a stationary process or stationary time series...
of the chain.
A simple consequence of this definition is that the entropy rate of an i.i.d. stochastic process
Stochastic process
In probability theory, a stochastic process , or sometimes random process, is the counterpart to a deterministic process...
has an entropy rate that is the same as the entropy
Entropy
Entropy is a thermodynamic property that can be used to determine the energy available for useful work in a thermodynamic process, such as in energy conversion devices, engines, or machines. Such devices can only be driven by convertible energy, and have a theoretical maximum efficiency when...
of any individual member of the process.
Example
In the Human genomeHuman genome
The human genome is the genome of Homo sapiens, which is stored on 23 chromosome pairs plus the small mitochondrial DNA. 22 of the 23 chromosomes are autosomal chromosome pairs, while the remaining pair is sex-determining...
, for chromosome 1, which consists of 247 Mbp, there is an entropy rate of 1.82 bits per base pair.
External links
- Systems Analysis, Modelling and Prediction (SAMP), University of Oxford MATLABMATLABMATLAB is a numerical computing environment and fourth-generation programming language. Developed by MathWorks, MATLAB allows matrix manipulations, plotting of functions and data, implementation of algorithms, creation of user interfaces, and interfacing with programs written in other languages,...
code for estimating information-theoretic quantities for stochastic processes.