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)

0
votes
0answers
6 views

How to prove $2d_H(\{XY\},\{X\}\{Y\})^2 \le I(X,Y)$?

Let $X$ and $Y$ be discrete random variables. Denote the joint distribution of $X$ and $Y$ by $\{XY\}$ and their marginal distributions by $\{X\}$ and $\{Y\}$. Let $\{X\}\{Y\}$ denote the product of ...
0
votes
0answers
11 views

Kullback-Leibler Divergence (KL) and Approximation Symmetry Property

The Kullback-Leibler Divergence doesn't satisfy the symmetric property. But, it can be approximated (bounded) to such a value. in this paper: Compressing Interactive Communication under product ...
0
votes
0answers
8 views

Checking if a code can be unambiguously decoded

The source of information is A = {a, b, c, d}. More info is given in the table below. I have to find the average length of the codes, compare it to the entropy of ...
3
votes
3answers
2k views

How is logistic loss and cross-entropy related?

I found that Kullback-Leibler loss, log-loss or cross-entropy is the same loss function. Is the logistic-loss function used in logistic regression equivalent to the cross-entropy function? If yes, can ...
2
votes
0answers
11 views

Reference request: Relationship between Entropy and Lyapunov Exponent

If $\lambda$ is the largest positive Lyapunov exponent of a piecewise linear dynamical chaotic discrete in time map, then is there a relationship between the entropy and its $\lambda$. I remember ...
5
votes
2answers
52 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 ...
1
vote
1answer
11 views

The relationship between AEP and compression

So i've been reading up on AEP, and trying to get a grasp on it (and to figure out why it is important). I understand the general definitions, and that the whole idea is the knowlegde of typical ...
1
vote
1answer
39 views

Rate distortion function with infinite distortion

I am working through the problems in Elements of Information Theory by Cover and Thomas and have come across the following problem I couldn't answer. The problem is to find the rate distortion ...
0
votes
0answers
23 views

Lower bound on binomial tail

In something I am reading, the following statement is mentioned in passing as something obvious: if $X_1,\ldots,X_n$ are i.i.d. Bernoulli with parameter $1/2 + \delta$, then $\mathbb{P}(\sum_{i=1}^n ...
1
vote
0answers
27 views

Information in Filtrations

Is the “information” kept track of by filtrations the same as information-theoretic “information”? If not, is there some way the two concepts can be reconciled?
1
vote
1answer
16 views

Relative entropy between discrete and continuous random variables

Is this possible to define relative entropy between discrete and continuous random variables? Say $P$ is a discrete pmf and $Q$ is a continuous pdf, what is $D(P||Q)$?
1
vote
3answers
36 views

Approximation of an indefinite integral

Consider this integral $$\frac{1}{2d}\int_{-d}^{d}f(x-t) \, \mathrm{d}t$$ When $d$ goes to zero, $$\lim _{d\to 0} \frac{1}{2d}\int_{-d}^{d}f(x-t) \, \mathrm{d}t = f(x)$$ but what is the second ...
0
votes
0answers
8 views

Monte-Carlo estimation of Mutual Information over AWGN channel

I'm trying to solve a problem I was tasked with. Basically I have to generate a 100k 16QAM inputs and transmit them over a AWGN channel. With this I have to use the Monte-Carlo estimation to figure ...
0
votes
1answer
38 views

Proof regarding size and dimension of linear codes

The problem is stated as follows: Let C be a binary linear code of length n, dimension k and distance d and assume that C contains at least one element of odd weight. Let C' be the subset of C ...
6
votes
1answer
115 views

How much life does it take to stack your deck? (Sorting problem)

There is a card in Magic the Gathering called Lim-Dul's Vault. While it is slightly more complicated than presented, the question I would like to consider is this: Pay 1 life. Look at the top 5 ...
5
votes
1answer
113 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 ...
2
votes
1answer
25 views

Maximizing sum of logarithms (Z-channel capacity)

In the context of information theory, I am trying to maximize the following function (mutual information of the Z-channel's input and output) with respect to $p$ in order to derive Z-channel's ...
13
votes
5answers
396 views

(Elegant) proof of an inequality: $h(x) \geq 1- (1-\frac{x}{1-x})^2$, where $h$ is the binary entropy function

I am looking for the most concise and elegant proof of the following inequality: $$ h(x) \geq 1- \left(1-\frac{x}{1-x}\right)^2, \qquad \forall x\in(0,1) $$ where $h(x) = x \log_2\frac{1}{x}+(1-x) ...
0
votes
1answer
30 views

Comparing entropies $H((f(X,Y), g(X,Y)))$ and $H ((f(X,Y),g(X,Z)))$

Let X,Y,Z be three independent uniform distributions on $\{0,1\}^n$; $f, g:\{0,1\}^n\times\{0,1\}^n\rightarrow\{0,1\}$ be two boolean functions. Is it true that $$H((f(X,Y), g(X,Y)))\leq H ...
0
votes
2answers
26 views

Relative entropy (KL divergence) of sum of random variables

Suppose we have two independent random variables, $X$ and $Y$, with different probability distributions. What is the relative entropy between pdf of $X$ and $X+Y$, i.e. $$D(P_X||P_{X+Y})$$ assume all ...
0
votes
2answers
36 views

Repetition code and binary symmetric channel, where error is near 1/2

I want to send one bit $x$ over a noisy channel, specifically, a binary symmetric channel with error probability $p$, where $p=(1-\epsilon)/2$ and $\epsilon$ is small. In other words, the error ...
0
votes
0answers
11 views

Entropy of a binary string obtained from dynamical system and length of the source code

H(S), the entropy of a source, gives you the average codeword length to encode a given source alphabet. i.e. it is the average number of bits per symbol required to encode the information in the ...
1
vote
1answer
19 views

For a Fisher Information, $\mathcal{I}(\theta)$, why does $\mathcal{I}(\theta) = n\mathcal{I}_1(\theta)$ not hold for multiple dimensions?

Suppose we have that $X_1, \ldots, X_n$ are iid from a distribution with ONE parameter, $\theta$. Then, under regulatory conditions, the Fisher Information may be written as: $$ \mathcal{I}(\theta) = ...
1
vote
3answers
88 views

Partition-based entropy of a sequence

The entropy $H$ of a discrete random variable $X$ is defined by $$H(X)=E[I(X)]=\sum_xP(x)I(x)=\sum_xP(x)\log P(x)^{-1}$$ where $x$ are the possible values of $X$, $P(x)$ is the probability of $x$, ...
2
votes
1answer
71 views

Amount of information a hidden state can convey (HMM)

In this paper (Products of Hidden Markov Models, http://www.cs.toronto.edu/~hinton/absps/aistats_2001.pdf), the authors say that: The hidden state of a single HMM can only convey log K bits of ...
4
votes
1answer
70 views

Why do we like sticking random variables into their own distributions?

Let $X$ be a random variable taking values in the set $S$. It has some distribution $f(s)$. Often in statistics, we are interested in the real valued random variable $f(X)$. Here are some examples: ...
1
vote
1answer
27 views

Quantum Asymptotic Equipartition

From Information Theory, we have the Asymptotic Equipartition Property, which can be proved by the Weak Law of Large Number: $\log P(x^n)=\log \prod\limits_{i=1}^{n} P(x_i)=\sum\limits_{i=1}^{n} \log ...
0
votes
1answer
66 views

Number of different cycles in cyclic codes with length n

I am studying Information theory, coding theory in particular at the moment, and I am having trouble determining how many different cycles are defined by a certain generator polinomial? Given a ...
2
votes
1answer
55 views

Does it pay to know what you know?

Let's play a game. I ask you question a yes/no question, and you answer. You don't answer with a yes or no though, you answer with a probability of it being yes ($P \in (0,1)$). For example, I might ...
0
votes
0answers
25 views

Change of bases for entropy

From Cover and Thomas, Elements of Information Theory: Why isn't it: $ \log_b(p) = \frac{\log_a(p)}{\log_a(b)} $, so that $ H_a(X) $ is multiplied with $ \frac{1}{\log_b a} $?
1
vote
0answers
21 views

Entropy of a 2-dimensional function versus 1-dimensionl function.

I am a novice in information theory so this is more of a question seeking pointers to ideas/references to think further on the thought. I want to make concrete the idea that a function of two ...
-1
votes
1answer
18 views

Does the Information Gain algorithm favor a high-entropy attribute or a low-entropy one?

This might not be mutual to mathematics but it does relate to Information-Theory. My question is: Does the InformationGain algorithm, in Decision-Tree machine-learning, favor a high-entropy ...
3
votes
2answers
93 views

Origin of the notation for statistical divergence

The unusual notation $D(P||Q)$ seems to be universally used for statistical divergences (e.g. KL divergence). What is the origin of this notation, and do the double bars (pipe symbols) have any ...
3
votes
5answers
259 views

A limit problem $0\log \cfrac{0}{0}=0$

How can we show that $$0\log \cfrac{0}{0}=0 ?$$ PS. Not homework. This is taken as a convention in the book Elements of Information Theory by Cover. And the books claims it's by continuity (Page 31). ...
3
votes
1answer
171 views

I need a textbook! Information theory and probability

I have posted some questions: Probability result - 3 discrete random variables Markov chain - a notation I don't understand Random variables identities - how to make a formal proof. These ...
0
votes
2answers
37 views

Doubt in Conditional Probability

I'm studying Information theory from the book Information Theory, Coding and Cryptography-Rajan Bose. I got confused at one pos where they have derived the equation ...
3
votes
3answers
316 views

Introduction to Information Theory

I'm studying bioengineering but in conversations and reading I've found that a great background in information theory as it applies to probability, statistics, random process, causation and inference ...
2
votes
0answers
81 views

How to Calculate Values from Incoming Messages? - Evidence Propagation in Bayesian Network

I'm currently trying to wrap my head around evidence propagation in bayesian network (simple tree propagation) but I'm having trouble finding information about the process. As an example, let's take ...
2
votes
1answer
538 views

How come that HSL can contain more information than RGB?

I have noticed weird thing when working with HSL - unlike RGB, it has some blind spots where certain value just does not matter. I'm sure we were taught about this when I had Linear algebra lectures ...
1
vote
2answers
740 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 ...
1
vote
0answers
20 views

$K(xy)\leq K(x)+K(y) +c$?

Could anyone show that for any $c$, some strings $x$ and $y$ exist, where $K(xy)>K(x)+K(y)+c$? Here $K(x)$ is the Kolmogorov complexity. I already know that $K(xy) \leq 2K(x) + K(y) +c$ and $K(xy) ...
0
votes
1answer
57 views

Conditional entropy under quantization

Let $X$ be a continuous random variable and $X^n$ its quantization that becomes finer with larger $n$. Let $Y$ be a deterministic function of $X$. Then we have that the conditional entropy $$H(Y|X) = ...
2
votes
1answer
88 views

proof of upper bound on differential entropy of f(X)

I asked a similar question yesterday, but I organized my question here a little and further asked my second question. Suppose $X$ is a continuous random variable with the pdf $f_x$, and $Y=g(X)$. If ...
1
vote
0answers
12 views

Channel capacity of sum of symmetric channels

I've got a channel matrix $P$ of the form $\begin{bmatrix} Q \\ R \end{bmatrix}$ where $Q,R$ are channel matrices of symmetric channels, so they now have different input alphabets but the ...
0
votes
1answer
24 views

Basic Entropy Inequality and Identity question

This is a solution to a problem I am working on: \begin{equation} \begin{aligned} H(X|Y) + H(Y|Z) &\ge^? H(X|Y, Z) + H(Y|Z) \\ &=^\text{?}H(X,Y |Z) \\ &= H(X|Z) + H(Y|X, Z)\\ &\ge ...
1
vote
0answers
12 views

Representation of the optimal filter measure as the measure of a diffusion process

In "Mitter SK, Newton NJ. A Variational Approach to Nonlinear Estimation. SIAM J Control Optim. 2003 Jan;42(5):1813–33", it is shown that the path estimation measure $P_{X|Y}(\cdot,y)$ for the ...
0
votes
0answers
37 views

How to calculate the Shannon Entropy for a block length of a word

I have a binary sequence of length N as $10110110111...$ I want to segment the above series into equal blocks of a window of length $L$. One way of determining the block length is using the ...
0
votes
1answer
16 views

Calculating Entropy and Information Gain of a Variable

I have the following values for two random variables. I need to compute the following values: a. H(Y) b. H(Y|X) c. and finally IG(Y|X) I will show what I have calculated so far. a. H(Y) = ...
1
vote
0answers
11 views

Removing the dimension factor in Fannes inequality

Given two distributions $x=(x_1,\ldots, x_n),y=(y_1,\ldots y_n)$ on $[n]$, it is known by Fannes inequality that $H(x)-H(y)\leq O(\|x-y\|_1\log n)$, where $H(\cdot)$ and $\|\cdot\|_1$ represent ...
0
votes
0answers
11 views

Closed form of Mutual Information, Continuous Random Variables

Is there any closed form for any non Gaussian Joint distribution ? For the Gaussian case $I(X,Y)=f( \varrho )$ where $\varrho $ is the correlation coefficient, and $f$ is an known increasing ...