Content deleted Content added
m Changing : in the math mode to \colon |
Rescuing 19 sources and tagging 0 as dead.) #IABot (v2.0.9.5 |
||
| (46 intermediate revisions by 31 users not shown) | |||
Line 2:
{{other uses|Entropy (disambiguation)}}
{{More citations needed|date=February 2019}}
{{Use dmy dates|date=
{{Information theory}}
In [[information theory]], the '''entropy''' of a [[random variable]] is the average level of "information", "surprise", or "uncertainty" inherent to the variable's possible outcomes. Given a discrete random variable <math>X</math>, which takes values in the
<math display="block">\Eta(X) := -\sum_{x \in \mathcal{X}} p(x) \log p(x)
where <math>\Sigma</math> denotes the sum over the variable's possible values. The choice of base for <math>\log</math>, the [[logarithm]], varies for different applications. Base 2 gives the unit of [[bit]]s (or "[[shannon (unit)|shannon]]s"), while base [[Euler's number|''e'']] gives "natural units" [[nat (unit)|nat]], and base 10 gives units of "dits", "bans", or "[[Hartley (unit)|hartleys]]". An equivalent definition of entropy is the [[expected value]] of the [[self-information]] of a variable.<ref name="pathriaBook">{{cite book|last1=Pathria|first1=R. K.|url=https://books.google.com/books?id=KdbJJAXQ-RsC|title=Statistical Mechanics|last2=Beale|first2=Paul|date=2011|publisher=Academic Press|isbn=978-0123821881|edition=Third|page=51}}</ref>
[[File:Entropy flip 2 coins.jpg|thumb|300px|Two bits of entropy: In the case of two fair coin tosses, the information entropy in bits is the base-2 logarithm of the number of possible outcomes
The concept of information entropy was introduced by [[Claude Shannon]] in his 1948 paper "[[A Mathematical Theory of Communication]]",<ref name="shannonPaper1">{{cite journal|last=Shannon|first=Claude E.|author-link=Claude Shannon|date=July 1948|title=A Mathematical Theory of Communication|journal=[[Bell System Technical Journal]]|volume=27|issue=3|pages=379–423|doi=10.1002/j.1538-7305.1948.tb01338.x|hdl-access=free|title-link=A Mathematical Theory of Communication|hdl=10338.dmlcz/101429}} ([https://web.archive.org/web/20120615000000*/https://www.alcatel-lucent.com/bstj/vol27-1948/articles/bstj27-3-379.pdf PDF], archived from [http://www.alcatel-lucent.com/bstj/vol27-1948/articles/bstj27-3-379.pdf here] {{Webarchive|url=https://web.archive.org/web/20140620153353/http://www3.alcatel-lucent.com/bstj/vol27-1948/articles/bstj27-3-379.pdf |date=20 June 2014 }})</ref><ref name="shannonPaper2">{{cite journal|last=Shannon|first=Claude E.|author-link=Claude Shannon|date=October 1948|title=A Mathematical Theory of Communication|journal=[[Bell System Technical Journal]]|volume=27|issue=4|pages=623–656|doi=10.1002/j.1538-7305.1948.tb00917.x|hdl-access=free|title-link=A Mathematical Theory of Communication|hdl=11858/00-001M-0000-002C-4317-B}} ([https://web.archive.org/web/20120615000000*/https://www.alcatel-lucent.com/bstj/vol27-1948/articles/bstj27-4-623.pdf PDF], archived from [http://www.alcatel-lucent.com/bstj/vol27-1948/articles/bstj27-4-623.pdf here] {{Webarchive|url=https://web.archive.org/web/20130510074504/http://www.alcatel-lucent.com/bstj/vol27-1948/articles/bstj27-4-623.pdf |date=10 May 2013 }})</ref> and is also referred to as '''Shannon entropy'''. Shannon's theory defines a [[data communication]] system composed of three elements: a source of data, a [[communication channel]], and a receiver. The "fundamental problem of communication" – as expressed by Shannon – is for the receiver to be able to identify what data was generated by the source, based on the signal it receives through the channel.<ref name="shannonPaper1" /><ref name="shannonPaper2" /> Shannon considered various ways to encode, compress, and transmit messages from a data source, and proved in his
Entropy in information theory is directly analogous to the [[Entropy (statistical thermodynamics)|entropy]] in [[statistical thermodynamics]]. The analogy results when the values of the random variable designate energies of microstates, so Gibbs's formula for the entropy is formally identical to Shannon's formula. Entropy has
==Introduction==
The core idea of information theory is that the "informational value" of a communicated message depends on the degree to which the content of the message is surprising. If a highly likely event occurs, the message carries very little information. On the other hand, if a highly unlikely event occurs, the message is much more informative. For instance, the knowledge that some particular number ''will not'' be the winning number of a lottery provides very little information, because any particular chosen number will almost certainly not win. However, knowledge that a particular number ''will'' win a lottery has high informational value because it communicates the
The ''[[information content]],'' also called the ''surprisal'' or ''self-information,'' of an event <math>E</math> is a function which increases as the probability <math>p(E)</math> of an event decreases. When <math>p(E)</math> is close to 1, the surprisal of the event is low, but if <math>p(E)</math> is close to 0, the surprisal of the event is high. This relationship is described by the function
<math display="block">\log\left(\frac{1}{p(E)}\right) ,</math>
where <math>\log</math> is the [[logarithm]], which gives 0 surprise when the probability of the event is 1.<ref>{{cite web |url = https://www.youtube.com/watch?v=YtebGVx-Fxw |title = Entropy (for data science) Clearly Explained!!! |via = [[YouTube]] |access-date = 5 October 2021 |archive-date = 5 October 2021 |archive-url = https://web.archive.org/web/20211005135139/https://www.youtube.com/watch?v=YtebGVx-Fxw |url-status = live }}</ref> In fact, {{math|log}} is the only function that satisfies а specific set of conditions defined in section ''{{slink|#Characterization}}''.
Hence, we can define the information, or surprisal, of an event <math>E</math> by
Line 28:
<math display="block">I(E) = \log_2\left(\frac{1}{p(E)}\right) .</math>
Entropy measures the expected (i.e., average) amount of information conveyed by identifying the outcome of a random trial.<ref name="mackay2003">{{cite book
Consider a coin with probability {{math|''p''}} of landing on heads and probability {{math|1 − ''p''}} of landing on tails. The maximum surprise is when {{math|''p'' {{=}} 1/2}}, for which one outcome is not expected over the other. In this case a coin flip has an entropy of one [[bit]]. (Similarly, one [[Ternary numeral system|trit]] with equiprobable values contains <math>\log_2 3</math> (about 1.58496) bits of information because it can have one of three values.) The minimum surprise is when {{math|''p'' {{=}} 0}} or {{math|''p'' {{=}} 1}}, when the event outcome is known ahead of time, and the entropy
=== Example ===
Information theory is useful to calculate the smallest amount of information required to convey a message, as in [[data compression]]. For example, consider the transmission of sequences comprising the 4 characters 'A', 'B', 'C', and 'D' over a binary channel. If all 4 letters are equally likely (25%), one
==Definition==
Named after [[H-theorem|Boltzmann's Η-theorem]], Shannon defined the entropy {{math|Η}} (Greek capital letter [[eta]]) of a [[discrete random variable]] <math display="inline">X</math>, which takes values in the
<math display="block">\Eta(X) = \mathbb{E}[\operatorname{I}(X)] = \mathbb{E}[-\log p(X)].</math>
Line 67 ⟶ 68:
<math display="block"> \Eta_\mu(M) = \sup_{P \subseteq M} \Eta_\mu(P) .</math>
Finally, the entropy of the probability space is <math>\Eta_\mu(\Sigma)</math>, that is, the entropy with respect to <math>\mu</math> of the sigma-algebra of ''all'' measurable subsets of <math>X</math>.
==Example==
Line 83 ⟶ 78:
\Eta(X) &= -\sum_{i=1}^n {p(x_i) \log_b p(x_i)}
\\ &= -\sum_{i=1}^2 {\frac{1}{2}\log_2{\frac{1}{2}}}
\\ &= -\sum_{i=1}^2 {\frac{1}{2} \cdot (-1)} = 1.
\end{align}</math>
Line 91 ⟶ 86:
\\ &= - 0.7 \log_2 (0.7) - 0.3 \log_2 (0.3)
\\ &\approx - 0.7 \cdot (-0.515) - 0.3 \cdot (-1.737)
\\ &= 0.8816 < 1.
\end{align}</math>
Uniform probability yields maximum uncertainty and therefore maximum entropy. Entropy, then, can only decrease from the value associated with uniform probability. The extreme case is that of a double-headed coin that never comes up tails, or a double-tailed coin that never results in a head. Then there is no uncertainty. The entropy is zero: each toss of the coin delivers no new information as the outcome of each coin toss is always certain.<ref name=cover1991/>{{rp|14–15}}
==Characterization==
To understand the meaning of {{math|−Σ ''p''<sub>''i''</sub> log(''p''<sub>''i''</sub>)}}, first define an information function {{math|I}} in terms of an event {{math|''i''}} with probability {{math|''p''<sub>''i''</sub>}}. The amount of information acquired due to the observation of event {{math|''i''}} follows from Shannon's solution of the fundamental properties of [[Information content|information]]:<ref>{{cite book |last=Carter |first=Tom |date=March 2014 |title=An introduction to information theory and entropy |url=
# {{math|I(''p'')}} is [[monotonically decreasing]] in {{math|''p''}}: an increase in the probability of an event decreases the information from an observed event, and vice versa.
# {{math|I(1) {{=}} 0}}: events that always occur do not communicate information.
Line 106 ⟶ 99:
Given two independent events, if the first event can yield one of {{math|''n''}} [[equiprobable]] outcomes and another has one of {{math|''m''}} equiprobable outcomes then there are {{math|''mn''}} equiprobable outcomes of the joint event. This means that if {{math|log<sub>2</sub>(''n'')}} bits are needed to encode the first value and {{math|log<sub>2</sub>(''m'')}} to encode the second, one needs {{math|log<sub>2</sub>(''mn'') {{=}} log<sub>2</sub>(''m'') + log<sub>2</sub>(''n'')}} to encode both.
Shannon discovered that a suitable choice of <math>\operatorname{I}</math> is given by:<ref>Chakrabarti, C. G., and Indranil Chakrabarty. "Shannon entropy: axiomatic characterization and application." ''International Journal of Mathematics and Mathematical Sciences'' 2005. 17 (2005): 2847-2854 [https://arxiv.org/pdf/quant-ph/0511171.pdf url] {{Webarchive|url=https://web.archive.org/web/20211005135940/https://arxiv.org/pdf/quant-ph/0511171.pdf |date=5 October 2021 }}</ref>
<math display="block">\operatorname{I}(p) = \log\left(\tfrac{1}{p}\right) = -\log(p).</math>
In fact, the only possible values of <math>\operatorname{I}</math> are <math>\operatorname{I}(u) = k \log u</math> for <math>k<0</math>. Additionally, choosing a value for {{math|''k''}} is equivalent to choosing a value <math>x>1</math> for <math>k = - 1/\log x</math>, so that {{math|''x''}} corresponds to the [[Base of a logarithm|base for the logarithm]]. Thus, entropy is [[characterization (mathematics)|characterized]] by the above four properties.
Line 138 ⟶ 131:
# Maximum: <math>\Eta_n</math> should be maximal if all the outcomes are equally likely i.e. <math>\Eta_n(p_1,\ldots,p_n) \le \Eta_n\left(\frac{1}{n}, \ldots, \frac{1}{n}\right)</math>.
# Increasing number of outcomes: for equiprobable events, the entropy should increase with the number of outcomes i.e. <math>\Eta_n\bigg(\underbrace{\frac{1}{n}, \ldots, \frac{1}{n}}_{n}\bigg) < \Eta_{n+1}\bigg(\underbrace{\frac{1}{n+1}, \ldots, \frac{1}{n+1}}_{n+1}\bigg).</math>
# Additivity: given an ensemble of {{math|''n''}} uniformly distributed elements that are
==== Discussion ====
The rule of additivity has the following consequences: for [[positive integers]] {{math|''b''<sub>''i''</sub>}} where {{math|''b''<sub>1</sub> + ... + ''b''<sub>''k''</sub> {{=}} ''n''}},
:<math>\Eta_n\left(\frac{1}{n}, \ldots, \frac{1}{n}\right) = \Eta_k\left(\frac{b_1}{n}, \ldots, \frac{b_k}{n}\right) + \sum_{i=1}^k \frac{b_i}{n} \, \Eta_{b_i}\left(\frac{1}{b_i}, \ldots, \frac{1}{b_i}\right).</math>
Choosing {{math|''k'' {{=}} ''n''}}, {{math|''b''<sub>1</sub> {{=}} ... {{=}} ''b''<sub>''n''</sub> {{=}} 1}} this implies that the entropy of a certain outcome is zero: {{math|Η<sub>1</sub>(1) {{=}} 0}}. This implies that the efficiency of a source
The characterization here imposes an additive property with respect to a [[partition of a set]]. Meanwhile, the [[conditional probability]] is defined in terms of a multiplicative property, <math>P(A\mid B)\cdot P(B)=P(A\cap B)</math>. Observe that a logarithm mediates between these two operations. The [[conditional entropy]] and related quantities inherit simple relation, in turn. The measure theoretic definition in the previous section defined the entropy as a sum over expected surprisals <math>\mu(A)\cdot \ln\mu(A)</math> for an extremal partition. Here the logarithm is ad hoc and the entropy is not a measure in itself. At least in the information theory of a binary string, <math>\log_2</math> lends itself to practical interpretations.
Motivated by such relations, a plethora of related and competing quantities have been defined. For example, [[David Ellerman]]'s analysis of a "logic of partitions" defines a competing measure in structures [[Duality (mathematics)|dual]] to that of subsets of a universal set.<ref>{{cite journal |last1=Ellerman |first1=David |title=Logical Information Theory: New Logical Foundations for Information Theory |journal=Logic Journal of the IGPL |date=October 2017 |volume=25 |issue=5 |pages=806–835 |doi=10.1093/jigpal/jzx022 |url=http://philsci-archive.pitt.edu/13213/1/Logic-to-information-theory3.pdf |access-date=2 November 2022 |archive-date=25 December 2022 |archive-url=https://web.archive.org/web/20221225080028/https://philsci-archive.pitt.edu/13213/1/Logic-to-information-theory3.pdf |url-status=live }}</ref> Information is quantified as "dits" (distinctions), a measure on partitions. "Dits" can be converted into [[Shannon (unit)|Shannon's bits]], to get the formulas for conditional entropy, and so on.
===Alternative characterization via additivity and subadditivity===
Another succinct axiomatic characterization of Shannon entropy was given by [[
# Subadditivity: <math>\Eta(X,Y) \le \Eta(X)+\Eta(Y)</math> for jointly distributed random variables <math>X,Y</math>.
Line 155 ⟶ 153:
# Small for small probabilities: <math>\lim_{q \to 0^+} \Eta_2(1-q, q) = 0</math>.
==== Discussion ====
It was shown that any function <math>\Eta</math> satisfying the above properties must be a constant multiple of Shannon entropy, with a non-negative constant.<ref name="aczelentropy"/> Compared to the previously mentioned characterizations of entropy, this characterization focuses on the properties of entropy as a function of random variables (subadditivity and additivity), rather than the properties of entropy as a function of the probability vector <math>p_1,\ldots ,p_n</math>.
Line 164 ⟶ 163:
* Adding or removing an event with probability zero does not contribute to the entropy:
::<math>\Eta_{n+1}(p_1,\ldots,p_n,0) = \Eta_n(p_1,\ldots,p_n)</math>.
::<math>\Eta(
▲:This maximal entropy of {{math|log<sub>''b''</sub>(''n'')}} is effectively attained by a source alphabet having a uniform probability distribution: uncertainty is maximal when all possible events are equiprobable.
* The entropy or the amount of information revealed by evaluating {{math|(''X'',''Y'')}} (that is, evaluating {{math|''X''}} and {{math|''Y''}} simultaneously) is equal to the information revealed by conducting two consecutive experiments: first evaluating the value of {{math|''Y''}}, then revealing the value of {{math|''X''}} given that you know the value of {{math|''Y''}}. This may be written as:<ref name=cover1991/>{{rp|16}}
::<math> \Eta(X,Y)=\Eta(X|Y)+\Eta(Y)=\Eta(Y|X)+\Eta(X).</math>
Line 188 ⟶ 186:
The inspiration for adopting the word ''entropy'' in information theory came from the close resemblance between Shannon's formula and very similar known formulae from [[statistical mechanics]].
In [[statistical thermodynamics]] the most general formula for the thermodynamic [[entropy]] {{math|''S''}} of a [[thermodynamic system]] is the [[Gibbs entropy]]
:<math>S = - k_\text{B} \sum p_i \ln p_i \,,</math>
where {{math|''k''<sub>B</sub>}} is the [[Boltzmann constant]], and {{math|''p''<sub>''i''</sub>}} is the probability of a [[Microstate (statistical mechanics)|microstate]]. The [[Entropy (statistical thermodynamics)|Gibbs entropy]] was defined by [[J. Willard Gibbs]] in 1878 after earlier work by [[Ludwig Boltzmann|Boltzmann]] (1872).<ref>Compare: Boltzmann, Ludwig (1896, 1898). Vorlesungen über Gastheorie : 2 Volumes – Leipzig 1895/98 UB: O 5262-6. English version: Lectures on gas theory. Translated by Stephen G. Brush (1964) Berkeley: University of California Press; (1995) New York: Dover {{isbn|0-486-68455-5}}</ref>
The Gibbs entropy translates over almost unchanged into the world of [[quantum physics]] to give the [[von Neumann entropy]]
:<math>S = - k_\text{B} \,{\rm Tr}(\rho \ln \rho) \,,</math>
where ρ is the [[density matrix]] of the quantum mechanical system and Tr is the [[Trace (linear algebra)|trace]].<ref>{{Cite book|last=Życzkowski|first=Karol|title=Geometry of Quantum States: An Introduction to Quantum Entanglement|publisher=Cambridge University Press|year=2006|pages=301}}</ref>
At an everyday practical level, the links between information entropy and thermodynamic entropy are not evident. Physicists and chemists are apt to be more interested in ''changes'' in entropy as a system spontaneously evolves away from its initial conditions, in accordance with the [[second law of thermodynamics]], rather than an unchanging probability distribution. As the minuteness of the [[Boltzmann constant]] {{math|''k''<sub>B</sub>}} indicates, the changes in {{math|''S'' / ''k''<sub>B</sub>}} for even tiny amounts of substances in chemical and physical processes represent amounts of entropy that are extremely large compared to anything in [[data compression]] or [[signal processing]]. In classical thermodynamics, entropy is defined in terms of macroscopic measurements and makes no reference to any probability distribution, which is central to the definition of information entropy.
The connection between thermodynamics and what is now known as information theory was first made by [[Ludwig Boltzmann]] and expressed by his [[Boltzmann's entropy formula|
:<math>S=k_\text{B} \ln W,</math>
where <math>S</math> is the thermodynamic entropy of a particular macrostate (defined by thermodynamic parameters such as temperature, volume, energy, etc.), {{math|''W''}} is the number of microstates (various combinations of particles in various energy states) that can yield the given macrostate, and {{math|''k''<sub>B</sub>}} is the [[Boltzmann constant]].<ref>{{Cite journal|last1=Sharp|first1=Kim|last2=Matschinsky|first2=Franz|date=2015|title=Translation of Ludwig Boltzmann's Paper "On the Relationship between the Second Fundamental Theorem of the Mechanical Theory of Heat and Probability Calculations Regarding the Conditions for Thermal Equilibrium"|journal=Entropy|volume=17|pages=1971–2009|doi=10.3390/e17041971|doi-access=free}}</ref> It is assumed that each microstate is equally likely, so that the probability of a given microstate is {{math|1=''p''<sub>''i''</sub> = 1/''W''}}. When these probabilities are substituted into the above expression for the Gibbs entropy (or equivalently {{math|''k''<sub>B</sub>}} times the Shannon entropy), Boltzmann's equation results. In information theoretic terms, the information entropy of a system is the amount of "missing" information needed to determine a microstate, given the macrostate.
In the view of [[Edwin Thompson Jaynes|Jaynes]] (1957),<ref>{{Cite journal|last=Jaynes|first=E. T.|date=1957-05-15|title=Information Theory and Statistical Mechanics|url=https://link.aps.org/doi/10.1103/PhysRev.106.620|journal=Physical Review|volume=106|issue=4|pages=620–630|doi=10.1103/PhysRev.106.620|bibcode=1957PhRv..106..620J|s2cid=17870175 }}</ref> thermodynamic entropy, as explained by [[statistical mechanics]], should be seen as an ''application'' of Shannon's information theory: the thermodynamic entropy is interpreted as being proportional to the amount of further Shannon information needed to define the detailed microscopic state of the system, that remains uncommunicated by a description solely in terms of the macroscopic variables of classical thermodynamics, with the constant of proportionality being just the [[Boltzmann constant]]. Adding heat to a system increases its thermodynamic entropy because it increases the number of possible microscopic states of the system that are consistent with the measurable values of its macroscopic variables, making any complete state description longer. (See article: ''[[maximum entropy thermodynamics]]''). [[Maxwell's demon]] can (hypothetically) reduce the thermodynamic entropy of a system by using information about the states of individual molecules; but, as [[Rolf Landauer|Landauer]] (from 1961) and co-workers<ref>{{Cite journal|last=Landauer|first=R.|date=July 1961|title=Irreversibility and Heat Generation in the Computing Process|url=https://ieeexplore.ieee.org/document/5392446|journal=IBM Journal of Research and Development|volume=5|issue=3|pages=183–191|doi=10.1147/rd.53.0183|issn=0018-8646|access-date=15 December 2021|archive-date=15 December 2021|archive-url=https://web.archive.org/web/20211215235046/https://ieeexplore.ieee.org/document/5392446|url-status=live}}</ref> have shown, to function the demon himself must increase thermodynamic entropy in the process, by at least the amount of Shannon information he proposes to first acquire and store; and so the total thermodynamic entropy does not decrease (which resolves the paradox). [[Landauer's principle]] imposes a lower bound on the amount of heat a computer must generate to process a given amount of information, though modern computers are far less efficient.
===Data compression===
Line 212 ⟶ 210:
If a [[Data compression|compression]] scheme is lossless – one in which you can always recover the entire original message by decompression – then a compressed message has the same quantity of information as the original but communicated in fewer characters. It has more information (higher entropy) per character. A compressed message has less [[redundancy (information theory)|redundancy]]. [[Shannon's source coding theorem]] states a lossless compression scheme cannot compress messages, on average, to have ''more'' than one bit of information per bit of message, but that any value ''less'' than one bit of information per bit of message can be attained by employing a suitable coding scheme. The entropy of a message per bit multiplied by the length of that message is a measure of how much total information the message contains. Shannon's theorem also implies that no lossless compression scheme can shorten ''all'' messages. If some messages come out shorter, at least one must come out longer due to the [[pigeonhole principle]]. In practical use, this is generally not a problem, because one is usually only interested in compressing certain types of messages, such as a document in English, as opposed to gibberish text, or digital photographs rather than noise, and it is unimportant if a compression algorithm makes some unlikely or uninteresting sequences larger.
A 2011 study in ''[[Science (journal)|Science]]'' estimates the world's technological capacity to store and communicate optimally compressed information normalized on the most effective compression algorithms available in the year 2007, therefore estimating the entropy of the technologically available sources.<ref name="HilbertLopez2011">[http://www.sciencemag.org/content/332/6025/60 "The World's Technological Capacity to Store, Communicate, and Compute Information"] {{Webarchive|url=https://web.archive.org/web/20130727161911/http://www.sciencemag.org/content/332/6025/60 |date=27 July 2013 }}, Martin Hilbert and Priscila López (2011), ''[[Science (journal)|Science]]'', 332(6025); free access to the article through here: martinhilbert.net/WorldInfoCapacity.html</ref>{{rp|60–65}}
{| class="wikitable"
|+
Line 229 ⟶ 227:
===Entropy as a measure of diversity===
{{Main|Diversity index}}
Entropy is one of several ways to measure biodiversity, and is applied in the form of the [[Diversity index|Shannon index]].<ref>{{Cite journal|last1=Spellerberg|first1=Ian F.|last2=Fedor|first2=Peter J.|date=2003|title=A tribute to Claude Shannon (1916–2001) and a plea for more rigorous use of species richness, species diversity and the 'Shannon–Wiener' Index
===
There are a number of entropy-related concepts that mathematically quantify information content
* the '''[[self-information]]''' of an individual message or symbol taken from a given probability distribution (message or sequence see as an individual event),
* the '''[[joint entropy]]''' of
* the '''[[entropy rate]]''' of a [[stochastic process]] (message or sequence is seen as a succession of events).
(The "rate of self-information" can also be defined for a particular sequence of messages or symbols generated by a given stochastic process: this will always be equal to the entropy rate in the case of a [[stationary process]].) Other [[quantities of information]] are also used to compare or relate different sources of information.
Line 245 ⟶ 243:
===Limitations of entropy in cryptography===
In [[cryptanalysis]], entropy is often roughly used as a measure of the unpredictability of a cryptographic key, though its real [[Uncertainty principle|uncertainty]] is unmeasurable. For example, a 128-bit key that is uniformly and randomly generated has 128 bits of entropy. It also takes (on average) <math>2^{127}</math> guesses to break by brute force. Entropy fails to capture the number of guesses required if the possible keys are not chosen uniformly.<ref>{{cite conference |first1=James |last1=Massey |year=1994 |title=Guessing and Entropy |book-title=Proc. IEEE International Symposium on Information Theory |url=http://www.isiweb.ee.ethz.ch/archive/massey_pub/pdf/BI633.pdf |access-date=31 December 2013 |archive-date=1 January 2014 |archive-url=https://web.archive.org/web/20140101065020/http://www.isiweb.ee.ethz.ch/archive/massey_pub/pdf/BI633.pdf |url-status=live }}</ref><ref>{{cite conference |first1=David |last1=Malone |first2=Wayne |last2=Sullivan |year=2005 |title=Guesswork is not a Substitute for Entropy |book-title=Proceedings of the Information Technology & Telecommunications Conference |url=http://www.maths.tcd.ie/~dwmalone/p/itt05.pdf |access-date=31 December 2013 |archive-date=15 April 2016 |archive-url=https://web.archive.org/web/20160415054357/http://www.maths.tcd.ie/~dwmalone/p/itt05.pdf |url-status=live }}</ref> Instead, a measure called ''guesswork'' can be used to measure the effort required for a brute force attack.<ref>{{cite conference |first1=John |last1=Pliam |title=Selected Areas in Cryptography |year=1999 |chapter=Guesswork and variation distance as measures of cipher security|series=Lecture Notes in Computer Science |volume=1758 |pages=62–77 |book-title=International Workshop on Selected Areas in Cryptography |doi=10.1007/3-540-46513-8_5 |isbn=978-3-540-67185-5 |doi-access=free }}</ref>
Other problems may arise from non-uniform distributions used in cryptography. For example, a 1,000,000-digit binary [[one-time pad]] using exclusive or. If the pad has 1,000,000 bits of entropy, it is perfect. If the pad has 999,999 bits of entropy, evenly distributed (each individual bit of the pad having 0.999999 bits of entropy) it may provide good security. But if the pad has 999,999 bits of entropy, where the first bit is fixed and the remaining 999,999 bits are perfectly random, the first bit of the ciphertext will not be encrypted at all.
Line 265 ⟶ 263:
==Efficiency (normalized entropy)==
A source
AR Wilcox - 1967 https://www.osti.gov/servlets/purl/4167340</ref>
:<math>\eta(X) = \frac{H}{H_{max}} = -\sum_{i=1}^n \frac{p(x_i) \log_b (p(x_i))}{\log_b (n)}.
</math>
Applying the basic properties of the logarithm, this quantity can also be expressed as:
:<math>\eta(X) = -\sum_{i=1}^n \frac{p(x_i) \log_b (p(x_i))}{\log_b (n)} = \sum_{i=1}^n \frac{\log_b(p(x_i)^{-p(x_i)})}{\log_b(n)} =
\sum_{i=1}^n \log_n(p(x_i)^{-p(x_i)}) =
\log_n (\prod_{i=1}^n p(x_i)^{-p(x_i)}).
</math>
Line 335 ⟶ 334:
==Use in number theory==
[[Terence Tao]] used entropy to make a useful connection trying to solve the [[Erdős discrepancy problem]].<ref>{{Cite journal |last=Tao |first=Terence |date=2016-02-28 |title=The Erdős discrepancy problem |url=https://discreteanalysisjournal.com/article/609 |journal=Discrete Analysis |language=en |arxiv=1509.05363v6 |doi=10.19086/da.609 |s2cid=59361755 |access-date=20 September 2023 |archive-date=25 September 2023 |archive-url=https://web.archive.org/web/20230925184904/https://discreteanalysisjournal.com/article/609 |url-status=live }}</ref>
Intuitively the idea behind the proof was if there is low information in terms of the Shannon entropy between consecutive random variables (here the random variable is defined using the [[Liouville function]] (which is
The proof is quite involved and it bought together breakthroughs not just in novel use of Shannon Entropy, but also its used the [[Liouville function]] along with [https://arxiv.org/pdf/1502.02374.pdf averages of modulated multiplicative functions] {{Webarchive|url=https://web.archive.org/web/20231028111132/https://arxiv.org/pdf/1502.02374.pdf |date=28 October 2023 }} in short intervals. Proving it also broke the [https://terrytao.wordpress.com/2007/06/05/open-question-the-parity-problem-in-sieve-theory/ "parity barrier"] {{Webarchive|url=https://web.archive.org/web/20230807211237/https://terrytao.wordpress.com/2007/06/05/open-question-the-parity-problem-in-sieve-theory/ |date=7 August 2023 }} for this specific problem.
While the use of Shannon Entropy in the proof is novel it is likely to open new research in this direction.
Line 379 ⟶ 378:
[[Machine learning]] techniques arise largely from statistics and also information theory. In general, entropy is a measure of uncertainty and the objective of machine learning is to minimize uncertainty.
[[Decision tree learning]] algorithms use relative entropy to determine the decision rules that govern the data at each node.<ref>{{Cite
[[Bayesian inference]] models often apply the [[
[[Classification in machine learning]] performed by [[logistic regression]] or [[artificial neural network]]s often employs a standard loss function, called [[cross-entropy]] loss, that minimizes the average cross entropy between ground truth and predicted distributions.<ref>{{Cite book|last1=Rubinstein|first1=Reuven Y.|url=https://books.google.com/books?id=8KgACAAAQBAJ&dq=machine+learning+cross+entropy+loss+introduction&pg=PA1|title=The Cross-Entropy Method: A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation and Machine Learning|last2=Kroese|first2=Dirk P.|date=2013-03-09|publisher=Springer Science & Business Media|isbn=978-1-4757-4321-0|language=en}}</ref> In general, cross entropy is a measure of the differences between two datasets similar to the KL divergence (also known as relative entropy).
Line 423 ⟶ 422:
===Textbooks on information theory===
* [[Thomas M. Cover|Cover, T.M.]], [[Joy A. Thomas|Thomas, J.A.]] (2006), ''Elements of Information Theory
* [[David J.C. MacKay|MacKay, D.J.C.]] (2003), ''Information Theory, Inference and Learning Algorithms''
* Arndt, C. (2004), ''Information Measures: Information and its Description in Science and Engineering'', Springer, {{isbn|978-3-540-40855-0}}
* Gray, R. M. (2011), ''Entropy and Information Theory'', Springer.
* {{cite book|author1=Martin, Nathaniel F.G. |author2=England, James W. |title=Mathematical Theory of Entropy|publisher=Cambridge University Press|year=2011|isbn=978-0-521-17738-2|url=https://books.google.com/books?id=_77lvx7y8joC}}
* [[Claude Shannon|Shannon, C.E.]], [[Warren Weaver|Weaver, W.]] (1949) ''The Mathematical Theory of Communication'', Univ of Illinois Press. {{isbn|0-252-72548-4}}
* Stone, J. V. (2014), Chapter 1 of [http://jim-stone.staff.shef.ac.uk/BookInfoTheory/InfoTheoryBookMain.html ''Information Theory: A Tutorial Introduction''] {{Webarchive|url=https://web.archive.org/web/20160603070027/http://jim-stone.staff.shef.ac.uk/BookInfoTheory/InfoTheoryBookMain.html |date=3 June 2016 }}, University of Sheffield, England. {{isbn|978-0956372857}}.
==External links==
Line 435 ⟶ 434:
{{Library resources box|onlinebooks=yes}}
* {{springer|title=Entropy|id=p/e035740}}
* [http://rosettacode.org/wiki/Entropy "Entropy"] {{Webarchive|url=https://web.archive.org/web/20160604053728/http://rosettacode.org/wiki/Entropy |date=4 June 2016 }} at [[Rosetta Code]]—repository of implementations of Shannon entropy in different programming languages.
* ''[http://www.mdpi.com/journal/entropy Entropy] {{Webarchive|url=https://web.archive.org/web/20160531032753/http://www.mdpi.com/journal/entropy |date=31 May 2016 }}'' an interdisciplinary journal on all aspects of the entropy concept. Open access.
{{Compression Methods}}
Line 444 ⟶ 443:
[[Category:Information theory]]
[[Category:Statistical randomness]]
[[Category:Complex systems theory]]
| |||