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
43 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
734 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
178 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
292 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
292 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
0answers
22 views

Relaxation of optimization problem [duplicate]

Can I solve the following optimization problem, $$f= \max \{h(Y) - h(Y|U)\}$$ by solving an easier upperbound on $f$ for example $g > f$ where $g= \max\{h(Y)-h(Z)\}$. My aim is to prove that ...
15
votes
3answers
2k 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
7answers
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
266 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
249 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
676 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 ...
5
votes
1answer
613 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)= ...
11
votes
1answer
327 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
358 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 ...
4
votes
1answer
687 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
178 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
168 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
386 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
417 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
45 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
35 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
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
138 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
337 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 ...