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)

1
vote
0answers
86 views

optimization problem gaussian maximizes entropy

Let $X_1, X_2, Z_1$ be random variables and define $$Y=aX_1+bX_2+Z_1$$ I have the following optimization problem of difference of entropies, $$f=\max_{p(x_1x_2)} h(Y) - h(Y|X_2)= \max_{p(x_1,x_2)} ...
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 ...
4
votes
1answer
1k 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 ...
1
vote
0answers
64 views

A probabilty of error calculation

Let's assume I have $N$ binary strings $\{T_1,T_2,\ldots,T_N\}$ of length $L$. All these strings satisfy a minimum hamming distance with respect to a reference binary string R with $\|R\|_1$ ones and ...
1
vote
1answer
328 views

confused about joint mutual information

I have a difficulty understanding 'joint mutual information' The expressions like $I(X,Y;B)$ are not understood. Is there an good example to understand joint mutual information? Actually, I want to ...
16
votes
3answers
7k 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 ...
6
votes
3answers
762 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 ...
7
votes
2answers
275 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) $$
8
votes
2answers
483 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 ...
4
votes
0answers
367 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 ...
1
vote
0answers
76 views

Vector distance of binary

Suppose $\overline{u},\overline{v},\overline{w},\overline{x}$ are four binary vectors, pairwise distance d apart. Show that d must be even, there's exactly one vector which is a distance $d\over 2$ ...
0
votes
1answer
44 views

mutual information of coupled variables

I have been looking for a method for evaluating the mutual information between a combination of source variables, $X_0, X_1$ and a target variable, $Y$. $$I(Y;X_0,X_1)$$ When I look on wikipedia's ...
17
votes
7answers
3k 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).$$ ...
11
votes
3answers
553 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
3answers
288 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 ...
5
votes
1answer
768 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)= ...
8
votes
2answers
702 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 ...
6
votes
1answer
250 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 ...
0
votes
1answer
61 views

Have Information Theoretic results been used in other branches of mathematics?

consider this a soft-question. Information Theory is fairly young branch of mathematics (60 years). I am interested in question, whether there have been any information theoretic results that had ...
13
votes
2answers
416 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 ...
10
votes
3answers
456 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 ...
5
votes
1answer
64 views

Prove that bitstrings with 1/0-ratio different from 50/50 are compressable

I'm looking for a proof, that $$ \sum_{i=0}^{\lambda n} \binom{n}{i} \le 2^{nH(\lambda)} $$ with $n>0$, $0 \le \lambda \le 1/2$ and $ H(\lambda)=-[\lambda log \lambda + (1-\lambda) log (1-\lambda)] ...
3
votes
2answers
90 views

Mutual information of discrete RVs which converge in distribution to a continuous RV

We have a sequence of pairs of discrete, real-valued RVs $X_n$ and $Y_n$. Each pair is characterized by a discrete probability measure on $\mathbf{R}^2$, which we will just denote $\mu_{X_n,Y_n},$ ...
1
vote
1answer
36 views

Justifying $\log{\frac{1}{P_{X}(x)}}$ as the measure of self information

I was reviewing self information and then came to realize that there is one idea that I have that I believe should be wrong but don't know why. Let self-information associated with a random variable ...
-6
votes
2answers
125 views

How is Goedel's 1st incompleteness theorem related to the Axioms of a theory [closed]

i am thinking of various connections and formulations of Goedel's 1st incompleteness theorem. Apart from connections to Turing's Halting Problem and Algorithmic Complexity Theory, i am looking for ...
5
votes
3answers
1k 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 ...
4
votes
1answer
864 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$ ...
3
votes
1answer
58 views

Constructor theory distinguishability

In David Deustch and Chiara Marletto's Constructor Theory of Information (section 5) a set of attributes $S$ is defined as distinguishable if the task of transforming each attribute $x$ of $S$ into an ...
3
votes
1answer
323 views

Solid Angle Calculation - Understanding a formula

I'm currently reading a paper and try to understand this one formula. The problem is: In an n dimensional space. A cone with half-angle $\theta$ is given (the top of the cone is in the origin). We are ...
1
vote
1answer
38 views

conditioning reduces mutual information

$I (X, Y |Z) >I (X,Y)$ can happen, for example $X$, $Y$ independent bits and $Z = X+Y$. How do you show this fact using Venn diagrams? Conditioning would mean removing the mass of conditioning ...
1
vote
0answers
196 views

Random variables identities - how to make a formal proof.

Let $X, Y, Z$ be three random discrete variables. Consider the below random variables: $A = X\vert Y\vert Z$ ,$B= X\vert Y,Z$ Question: Can I conclude that $A$ and $B$ are the same ...
1
vote
1answer
504 views

Variations of the Hamming code.

What types of basic variations of the Hamming code are there and what are their objectives? I was taught the following version: $$ L = n + k $$ $$ n \geq \log_2M $$ $$ k \ge \log_2(n+k+1) $$ where ...
1
vote
1answer
582 views

Weighing Pool Balls where the number of balls is odd

As many of you might have seen before, here is the description of the classic weighing balls problem: One of twelve pool balls is a bit lighter or heavier (you do not know) than the others. ...
0
votes
1answer
48 views

Simple information theory question: where is this equation coming from?

I am reading a simple example of a joint distribution that looks like this: ...
0
votes
2answers
139 views

what is the mutual information of three variables?

mutual information of tow variables is $\displaystyle\sum\sum p(x,y)\ln\frac{p(x,y)}{p(x)p(y)}$ what is the mutual information of three variables? is it $\displaystyle\sum\sum\sum ...
0
votes
1answer
82 views

Entropy of sum is sum of entropies

Having $X$ and $Y$ discrete random variables above finite set. Z is defined as $Z=X+Y$ when does the following happen: $$H(Z)=H(X)+H(Y)$$
0
votes
1answer
59 views

Connection between Boltzmann entropy and Kolmogorov entropy

what is the connectivity between Boltzmann's entropy expression and Shannon's entropy expression? mentions a realtionship between Shannon entropy and Bolltzmann entropy. Is there a ...
0
votes
0answers
38 views

How to define “compound entropy”

Entropy measures the "surprise" one experiences when uncovering a the actual value of a random variable as $$-\sum_i p_i \log_2 p_i$$ E.g., if we observe Red 8 ...
0
votes
2answers
487 views

How to define the entropy of a list of numbers?

Considering a list of numbers $\{a_1,a_2,...,a_n\}$, after sorting the $n$ numbers in increasing order, how much the entropy changes? Updated Or we can understand the problem by using the number of ...