The science of compressing and communicating information. It is a branch of applied mathematics and electrical engineering. Though originally the focus was on digital communications and computing, it now finds wide use in biology, physics and other sciences.

learn more… | top users | synonyms (1)

32
votes
8answers
8k views

Intuitive explanation of entropy?

I have bumped many times into entropy, but it has never been clear for me why we use this formula: If $X$ is random variable then its entropy is: $$H(X) = -\displaystyle\sum_{x} p(x)\log p(x).$$ ...
28
votes
2answers
348 views

Information-theoretic aspects of mathematical systems?

It occured to me that when you perform division in some algebraic system, such as $\frac a b = c$ in $\mathbb R$, the division itself represents a relation of sorts between $a$ and $b$, and once you ...
22
votes
2answers
1k views

An information theory inequality which relates to Shannon Entropy

For $a_1,...,a_n,b_1,...,b_n>0,\quad$ define $a:=\sum a_i,\ b:=\sum b_i,\ s:=\sum \sqrt{a_ib_i}$. Is the following inequality true?: $${\frac{\Bigl(\prod a_i^{a_i}\Bigr)^\frac1a}a \cdot ...
17
votes
3answers
8k views

Expanding and understanding the poison pills riddle

You might have heard of the riddle that asks you to identify one fake pill (poisoned) among 12 pills of identical appearance, with the fake pill being either lighter or heavier than the others. You ...
15
votes
3answers
1k views

How to tell if a code is lossless

Consider the following code mapping: $$a \mapsto 010, \quad b\mapsto 001, \quad c\mapsto 01$$ It's easy to see that the code isn't lossless by observing the code $01001$, which can be translated to ...
14
votes
2answers
2k views

Why is “h” used for entropy?

Why is the letter "h" (or "H") used to denote entropy in information theory, ergodic theory, and physics (and possibly other places)? Edit: I'm looking for an explanation of the original use of "H". ...
14
votes
0answers
342 views

Determining information in minimum trials (combinatorics problem)

A student has to pass a exam, with $k2^{k-1}$ questions to be answered by yes or no, on a subject he knows nothing about. The student is allowed to pass mock exams who have the same questions as the ...
13
votes
5answers
399 views

(Elegant) proof of an inequality: $h(x) \geq 1- (1-\frac{x}{1-x})^2$, where $h$ is the binary entropy function

I am looking for the most concise and elegant proof of the following inequality: $$ h(x) \geq 1- \left(1-\frac{x}{1-x}\right)^2, \qquad \forall x\in(0,1) $$ where $h(x) = x \log_2\frac{1}{x}+(1-x) ...
13
votes
2answers
493 views

metric in the Wasserstein space of gaussian measures

I am reading the paper "Wasserstein Geometry of Gaussian measures" by Asuka Takatsu (section 3 is of interest to me) and I have difficulties understanding how the metric is used. In particular, I am ...
13
votes
2answers
121 views

can't swing the proof for this inequality

Let $p+p'=1$ and $q+q'=1$. If $\log(p/q)>\log(q'/p')$ then $(p+q)\log(p/q)>(p'+q')\log(q'/p')$. This looks deceptively simple to prove, but it's not. I couldn't crack it using Jensen's ...
12
votes
3answers
357 views

What is necessary to exchange messages between aliens? [closed]

Lets assume that two extreme intelligent species in the universe can exchange morse code messages for the first time. A can send messages to B and B to A, both have unlimited time, but they can not ...
12
votes
3answers
726 views

Has error correction been “solved”?

I recently came across Dan Piponi's blog post An End to Coding Theory and it left me very confused. The relevant portion is: But in the sixties Robert Gallager looked at generating random sparse ...
11
votes
2answers
1k views

What is the relationship between the Boltzmann distribution and information theory?

I'm reading a paper on Boltzmann machines (a type of neural network in Machine Learning), and it mentions that "The Boltzmann distribution has some beautiful mathematical properties and it is ...
10
votes
3answers
645 views

What is the least amount of questions to find out the number that a person is thinking between 1 to 1000 when they are allowed to lie at most once

A person is thinking of a number between 1 and 1000. What is the least number of yes/no questions that we can ask and know what that person's number is given that the person is allowed to lie on at ...
9
votes
3answers
2k views

What does the -log[P(X)] mean in the calculation of entropy?

The entropy (self information) of a discrete random variable X is calculated as: $$ H(x)=E(-log[P(X)]) $$ What does the -log[P(X)] mean? It seems to be something like ""the self information of each ...
9
votes
2answers
876 views

Can the entropy of a random variable with countably many outcomes be infinite?

Consider a random variable $X$ taking values over $\mathbb{N}$. Let $\mathbb{P}(X = i) = p_i$ for $i \in \mathbb{N}$. The entropy of $X$ is defined by $$H(X) = \sum_i -p_i \log p_i.$$ Is it possible ...
9
votes
3answers
1k views

In what sense is the Jeffreys prior invariant?

I've been trying to understand the motivation for the use of the Jeffreys prior in Bayesian statistics. Most texts I've read online make some comment to the effect that the Jeffreys prior is ...
9
votes
1answer
180 views

Is Entropy = Information circular or trivial?

I have seen several "maximum entropy distributions" used in the mathematical and statistical literature, often with the justification that they are "minimally informed" beyond the assumptions and data ...
9
votes
1answer
331 views

Error correction code handling deletions and insertions

I have data which is expressed in form of fixed-length sequence of decimal digits, typically 10 digits in length. I'm looking for error correction code that would allow me to append one or more ...
8
votes
2answers
768 views

How to make the encoding of symbols needs only 1.58496 bits/symbol as carried out in theory?

I'm reading the tutorial of Information Gain, and I see the following page: I know in the example above, I can encode this way: A 0 B 10 C 11 and then this ...
8
votes
3answers
221 views

Measure of how much information is lost in an implication

In an implication like $p \implies q$, is there some measure of how much information is lost in the implication? For example, consider the following implications, where $x \in \{0,1,\ldots,9\}$: ...
7
votes
4answers
264 views

Why do lower probability messages contain more information?

This question comes from here. Suppose messages $m_1, m_2, \ldots$ can be sent (through a channel) to a receiver with probabilities $p_1, p_2, \ldots$. The amount of information transferred when a ...
7
votes
3answers
258 views

Using decimals of $\pi$ to store data

I read recently about an idea to, instead of storing actual data, converting the data to a string of digits and then store the index of where this pattern occurs in some number, for example $\pi$. The ...
7
votes
2answers
2k views

Proof of Pinsker's inequality.

How to prove the following known (Pinsker's) inequality? For two strictly positive sequences $(p_i)^n_{i=l}$ and $(q_i)^n_{i=l}$ with $\sum_{i=1}^np_i=\sum_{i=1}^nq_i=1$ one has ...
7
votes
2answers
431 views

What is the connectivity between Boltzmann's entropy expression and Shannon's entropy expression?

What is the connection between Boltzmann's entropy expression and Shannon's entropy expression? Shannon's entropy expression: $$ S= -K\sum_{i=1}^np_i\log (p_i) $$
7
votes
1answer
342 views

Does “50/50 chance of.. . ” convey information?

I distinctly remember the professor in the undergrad introductory systems & control course saying that "when weather forecasters say there's a 50% chance of precipitation, they are conveying no ...
7
votes
1answer
222 views

Lemma in Petersen's *Ergodic Theory*

I'm trying to understand the proof of Lemma 6.2.1 (p.260-261) in Petersen's Ergodic Theory. Specifically, I don't understand why $B_{n}^{A} \in \mathscr{B}(T^{-1}\alpha \vee \dots \vee T^{-n}\alpha)$ ...
7
votes
1answer
77 views

Structure of equientropic transformations

Given a probability vector $v=(v_1,\ldots,v_n)$ with $1\geq v_i\geq 0$ and $\sum_{i=1}^n v_i=1$ its entropy can be defined as: $$ H(v):=-\sum_{i=1}^nv_i\log v_i $$ I wonder what is known about ...
7
votes
1answer
444 views

Lower bound on binomial coefficient

I encountered the following claim $$\frac{1}{n+1}2^{nH_2(k/n)} \le \binom{n}{k} \le 2^{nH_2(k/n)}$$ where $H_2$ is the binary entropy function. The upper bound is rather well known but how does one ...
7
votes
1answer
724 views

Empirical distribution vs. the true one: How fast $KL( \hat{P}_n || Q)$ converges to $KL( P || Q)$?

Let $X_1,X_2,\dots$ be i.i.d. samples drawn from a discrete space $\mathcal{X}$ according to probability distribution $P$, and denote the resulting empirical distribution based on n samples by ...
7
votes
0answers
248 views

Relation between Shannon Entropy and Total Variation distance

Let $p_1(\cdot), p_2(\cdot)$ be two discrete distributions on $\mathbb{Z}.$ Total variation distance is defined as $d_{TV}(p_1,p_2)= \frac{1}{2} \displaystyle \sum_{k \in \mathbb{Z}}|p_1(k)-p_2(k)|$ ...
6
votes
3answers
483 views

Another Information Theory Riddle

The following nice riddle is a quote from the excellent, free-to-download book: Information Theory, Inference, and Learning Algorithms, written by David J.C. MacKay. In a magic trick, there are ...
6
votes
2answers
2k views

What is the trellis diagram for a linear block code?

For the convolutional codes there is so-called trellis diagram, for which the definition is rather clear for me, however in mathematical sense is not. I have heard that it can be defined for linear ...
6
votes
3answers
883 views

What is information theoretic entropy and its physical significance?

I have learned entropy in my information theory classes. The definition I got from text books was the average information content in a message sequence etc. But in one of the MIT videos related to ...
6
votes
4answers
324 views

Is probability objective?

As we know, probability is a measure of events. However, is it an objectively attribute of events, or just an illusion in ones' mind? For example, suppose that there is an empty black box with an ...
6
votes
2answers
371 views

Theoretical basis for overfitting

There are many examples in which making more "precise" predictions gives worse performance (e.g. Runge's phenomenon). My professor implied that there was a sound basis for choosing "simple" functions ...
6
votes
2answers
400 views

Applications of information theory in economics?

What are some direct applications of information theory in economics theory and/or finance? Any relevant articles, surveys, or book references are appreciated (especially if they are targeted to ...
6
votes
1answer
262 views

measure of information

We know that $l_i=\log \frac{1}{p_i}$ is the solution to the Shannon's source compression problem: $\arg \min_{\{l_i\}} \sum p_i l_i$ where the minimization is over all possible code length ...
6
votes
1answer
2k views

Understanding the relationship of the $L^1$ norm to the total variation distance of probability measures, and the variance bound on it

I am trying to find a bound for variance of an arbitrary distribution $f_Y$ given a bound of a Kullback-Leiber divergence from a zero-mean Gaussian to $f_Y$, as I've explained in this related ...
6
votes
2answers
2k views

Can I normalize KL-divergence to be $\leq 1$?

The Kullback-Leibler divergence has a strong relationship with mutual information, and mutual information has a number of normalized variants. Is there some similar, entropy-like value that I can use ...
6
votes
1answer
79 views

Distance between theorems

In automated proving one can define the best proof of a theorem as the one which minimizes the length of the proof. Given a set of known statements one could define the difficulty of a theorem as the ...
6
votes
1answer
115 views

How much life does it take to stack your deck? (Sorting problem)

There is a card in Magic the Gathering called Lim-Dul's Vault. While it is slightly more complicated than presented, the question I would like to consider is this: Pay 1 life. Look at the top 5 ...
6
votes
2answers
116 views

Sum of uniform random variables on simplex

Let $X,X'$ be two independent uniform random variables on $n$-dimensional simplex $\Delta_n= \{(x_1,\ldots,x_n):x_i \geq 0, \sum x_i \leq 1\}$. I am trying to find the probability distribution of ...
6
votes
1answer
239 views

Guessing number in set 1-100 with weighted questions.

It is needed to guess number from 1 to 100. I can ask questions and get answers:"yes" or "no". For the "yes"-answer I must pay one dollar, for the "no"-answer - two dollars. How many dollars should I ...
6
votes
3answers
87 views

Guess the number despite false answer

This is the Guess-The-Number game with a twist! Variant 1 Take any positive integer $n$. The game-master chooses an $n$-bit integer $x$. The player makes queries one by one, each of the ...
5
votes
2answers
3k views

What is the motivation of the Kullback-Leibler Divergence?

The Kullback-Leibler Divergence is defined as $$K(f:g) = \int \left(\log \frac{f(x)}{g(x)} \right) \ dF(x)$$ It measures the distance between two distributions $f$ and $g$. Why would this be better ...
5
votes
3answers
2k views

Inverse of binary entropy function for $0 \le x \le \frac{1}{2}$

I'm trying to find the inverse of $H_2(x) = -x \log_2 x - (1-x) \log_2 (1-x)$[1] subject to $0 \le x \le \frac{1}{2}$. This is for a computation, so an approximation is good enough. My approach was ...
5
votes
4answers
725 views

Increasing the number of repetitions decreases the error probability

In coding theory when we encode 101 with 111000111 we have certain error probability. how can one prove that increasing the number of repetitions decreases the error probability. Let the probability ...
5
votes
2answers
282 views

Determinant of Fisher information

In information geometry, the determinant of the Fisher information matrix is a natural volume form on a statistical manifold, so it has a nice geometrical interpretation. But what is it in ...
5
votes
1answer
916 views

Kullback-Leibler divergence based kernel

I'm looking to paper "A Kullback-Leibler Divergence Based Kernel for SVM Classification in Multimedia Applications". Author suggest to use kernel function for two distributions $p$ and $q$: $k(p,q)= ...