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)

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 ...
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 ...
33
votes
8answers
9k 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).$$ ...
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 ...
6
votes
2answers
119 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 ...
7
votes
2answers
444 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
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 question....
5
votes
1answer
331 views

Non-zero Conditional Differential Entropy between a random variable and a function of it

Let two continuous random variables, where the one is a function of the other: $X\, $ and $\, Y=g\left(X\right)$. Their mutual information is defined as $$I\left(X,Y\right)\,=\,h\left(X\right)\,-\,h\...
5
votes
1answer
97 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)] ...
-8
votes
2answers
196 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 ...
4
votes
0answers
442 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 ...
2
votes
2answers
102 views

Differential Entropy

I'm a little temporarily confused about the concept of differential entropy. It says on wikipedia that the differential entropy of a Gaussian is $\log(\sigma\sqrt{2\pi e})$. However I was thinking as $...
1
vote
1answer
702 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 ...
1
vote
1answer
87 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 ...
1
vote
0answers
97 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$ ...
12
votes
3answers
738 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 ...
1
vote
3answers
2k views

Is it wrong to use Binary Vector data in Cosine Similarity?

I am doing Information Retrieval using Cosine Similarity. My data is binary vector. Since most of all reference I read is using non-binary vector (non-binary matrix) data, I am wondering if it is ...
12
votes
3answers
358 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 ...
8
votes
4answers
112 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
1answer
924 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)= \...
1
vote
2answers
813 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 p(x,y,z)\ln\frac{p(...
6
votes
1answer
266 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
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 ...
1
vote
1answer
76 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 ...
10
votes
3answers
669 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
894 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 ...
8
votes
2answers
771 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 ...
1
vote
1answer
52 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 ...
0
votes
1answer
90 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
2answers
684 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 ...
4
votes
1answer
1k 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
436 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 ...
3
votes
2answers
156 views

Convergence to normal distribution

Consider the probability distribution of the simple symmetric walk. That is the random variable $X_i$ equals $c$ or $-c$ with equal probability and all $X_i$ are independent and $c\geq1$. We are ...
3
votes
1answer
100 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 ...
2
votes
1answer
63 views

Tutorials on LDPC error correction codes

Please consider this as soft question. Recently, I have been studying channel coding and in particular error correction codes. I am looking for best tutorial (easy to understand) on LDPC error ...
1
vote
1answer
607 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
773 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. ...
1
vote
0answers
234 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 random ...
1
vote
1answer
57 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 ...
0
votes
1answer
157 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
0answers
47 views

differential entropy of f(X)

The differential entropy is translation invariant but not scaling invariant: $h(X+c) = h(x)$ for some constant $c$,and $h(aX) = h(X) + \ln (|a|)$ . I am interested in an extension of the scaling case,...
0
votes
1answer
259 views

concatenation of channels

Assuming I have 2 channels: BSC => Z Z=> BSC the first channel is a concatenation of the BSC channel and then the Z channel. the second channel is a concatenation of the Z channel and then the BSC ...
0
votes
0answers
41 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
1answer
65 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
0answers
37 views

Probability Distribution on the Simplex with support on the faces

I am looking for a parametrized distribution on the (probability) $K$-simplex with support on its $(K-1)$-faces. I.e. say $(x_1,...x_{K+1})$ are the coordinates of the simplex with $\sum_jx_j=1$, then ...
0
votes
1answer
60 views

What modification is this of the notion of Renyi divergence?

Given two probability distributions $P$ and $Q$ over the same outcome and event space (assume finite if needed) one defines their Renyi divergence as $D_\alpha (P \vert \vert Q) = \frac{1}{\alpha -1} \...