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
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
685 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
0answers
287 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 ...
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 ...
11
votes
6answers
1k 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).$$ ...
10
votes
3answers
259 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
3answers
183 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 ...
8
votes
2answers
666 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 ...
11
votes
1answer
307 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
347 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 ...
6
votes
2answers
157 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
2answers
271 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
1answer
667 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
165 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
0answers
159 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
362 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
384 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
0answers
35 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
116 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 ...
0
votes
2answers
320 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
2answers
75 views

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

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 ...