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)

27
votes
2answers
297 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 ...
14
votes
3answers
1k 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 ...
13
votes
3answers
995 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 ...
11
votes
3answers
408 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 ...
10
votes
3answers
254 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 ...
10
votes
1answer
283 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 ...
9
votes
3answers
321 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
2answers
549 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 ...
9
votes
2answers
532 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 ...
8
votes
2answers
642 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
2answers
613 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". ...
7
votes
2answers
252 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 ...
7
votes
1answer
234 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
3answers
176 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
0answers
173 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 ...
6
votes
5answers
660 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 it's entropy is: $H(X) = -\displaystyle\sum_{x} p(x)\log\;p(x)$ Why ...
6
votes
3answers
278 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
4answers
185 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 ...
6
votes
2answers
1k 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
209 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
283 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
131 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) $$
6
votes
1answer
300 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 ...
6
votes
1answer
222 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 ...
5
votes
4answers
280 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
576 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
3answers
130 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 ...
5
votes
2answers
268 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 ...
5
votes
1answer
114 views

Card drawing algorithm

I want to know whether there is an algorithm for randomly and securely drawing cards from a deck. I was thinking about a way to play deck-based games online with no trusted party and no way to cheat. ...
5
votes
1answer
871 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 ...
5
votes
1answer
218 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 ...
5
votes
1answer
173 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)$ ...
4
votes
3answers
156 views

simulating a fair random process with an unfair one.

Let's say I have a stochastic process that outputs $1$ or $0$ with probability $p$ or $1-p$ respectively, $p\neq 1/2$. Let's assume this is a repeatable iid process. So I can generate $X_1,X_2\dots$ ...
4
votes
3answers
125 views

Does any error correction code still work in such situation?

I'm looking for a kind of error correction code or solution that can correct my codeword in this case: My message holds k bits, and 2*k bits codeword (rate is 1/2) is produced by the generator ...
4
votes
1answer
496 views

Upper bound for variance of an (arbitrary) zero-mean random variable $X$ given distance between it and a known random variable $Y$

I have a zero-mean Gaussian random variable $Y\sim\mathcal{N}(0,\sigma^2_X)$ with known variance $\sigma_X^2$. I also have a zero-mean random variable $X$, which may be dependent on $Y$ (though, I ...
4
votes
1answer
534 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)= ...
4
votes
2answers
178 views

Are there simple examples of capacity-achieving block codes for discrete memoryless channels?

The title pretty much says it all, but I am particularly interested in the case where the number of input and output symbols are equal and the transition matrix defining the DMC is nondegenerate. I am ...
4
votes
1answer
620 views

What is the relationship of $\mathcal{L}_1$ (total variation) distance to hypothesis testing?

Kullback-Leibler divergence (a.k.a. relative entropy) has a nice property in hypothesis testing: given some observed measurement $m\in \mathcal{Q}$, and two probability distributions $P_0$ and $P_1$ ...
4
votes
1answer
628 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 ...
4
votes
2answers
731 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 ...
4
votes
1answer
47 views

Joint Probability from Marginal Probabilities

$X, Y_1, Y_2$ are random variables with (possibly) different finite alphabets. For given conditional probability mass functions $\mathbb{P}(Y_1|X)$ and $\mathbb{P}(Y_2|X)$, is it always possible to ...
4
votes
1answer
193 views

What is the general context for entropy (information theory)?

From Wikipedia: Let $X$ be a random variable with a probability density function $f$ whose support is a set $\mathbb{X}$. The differential entropy $h(f)$ is defined as $$ h(f) = ...
4
votes
0answers
37 views

Looking for a a measure-theoretic treatment of “differential entropy”

If $X$ is a discrete random variable, its entropy $H(X)$ is usually defined as something along the lines of $-\sum \def\P{\mathbb{P}}\P(x) \log_2( \P(x))$, where the sum ranges over all the possible ...
4
votes
0answers
71 views

Dividing a deck of cards using only imagination

The idea came up from a discussion I had with my friends. Suppose we want to play a game using a deck of cards, and we can't use any physical materials. If we are intelligent enough, we can remember ...
4
votes
0answers
96 views

A tight lower bound for the entropy of the XOR of two random variables

Let $U$ be the uniform random variable over $n$-bit binary strings, and let $X$ be another random variable that is dependent on $U$ and ranges over $n$-bit binary strings. Assuming $I(X;U) \le ...
4
votes
0answers
249 views

Universal Correlation measure — ranking correlations

I have time series data of experimental observations for two related processes. I want to measure correlation for use in further analysis. Correlation of the series changes over time and across ...
4
votes
0answers
282 views

Inequalities involving the probability density function and variance

I am wondering whether anyone knows of any any inequalities involving the probability density function of an unknown distribution (as opposed to the cumulative distribution function) and its known ...
3
votes
1answer
246 views

Entropy of $X =\{1,2,\ldots,\infty\}$ with the probability of $\{1/2^1,1/2^2,\ldots,1/2^\infty\}$?

I'm studing for an information theory exam, maybe some of you can help me here with an exercise. What's the entropy of $X$ as $\{1,2,\ldots,n\}$ ($n$=infinity) where the probabilities are $P \{1/2^1, ...
3
votes
1answer
257 views

Entropy of generatable(?) structures

In many places I see the entropy definition as: $H(X) = \sum_{i=1}^n {p(x_i)\,I(x_i)} = -\sum_{i=1}^n {p(x_i) \log_b p(x_i)}$ In Wikipedia I saw: $H(X) = \operatorname{E}(I(X))$ where E is ...