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
2answers
52 views

Convexity of mutual information $I(X;Y)$ in conditional $p(y \mid x)$

I'm trying to understand the proof that $I(X;Y)$ is convex in conditional distribution $p(y \mid x)$ - from Elements of Information Theory by Cover & Thomas, theorem 2.7.4. In the proof we fix ...
0
votes
1answer
34 views

Relation between Genetic Algorithm and Information theory

Can anyone suggest me some references (papers, books, lecture notes) on the relation between GA and Information theory?
0
votes
1answer
23 views

Markov chain and mutual information

If $X\rightarrow Y\rightarrow Z$ follow a Markov chain, then we have the following properties$$I(X;Z)\leq I(X;Y)$$ where $I$ is the mutual information expression. Intuitvely I agree. I want to ...
0
votes
1answer
20 views

Comparing two mutual information expressions

Given the following Data Processing Inequality $$X\rightarrow Y\rightarrow Z$$ one can say that $$I(X;Y) \geq I(X;Y|Z)$$ Intuition tells me this is not correct since conditioning reduces entropy and ...
0
votes
1answer
12 views

Entropy is upper bounded by cardinality of the random variable

How can one prove that the entropy of random variable $X$ is upper bounded by $\log|X|$? I tried the following $$H(x) = - \sum_x p(x)\log p(x)$$ $$ \leq - \sum_x p(x)\sum_x\log p(x)$$ $$= - ...
0
votes
0answers
14 views

Kullback-Leiber divergence for two simple probability vectors

For any probability vectors $ p= (p_1,...,p_K) $ and $ q=(q_1,...,q_K) $ representing monotonically increasing functions $ x-1 $ and $ ln(x) $ respectively what is the KL divergence? $$ KL(p||q) = ...
0
votes
0answers
16 views

Upper bound for conditional entropy? (for information theorists)

Assume we have $X$ and $Y$, zero mean and independent from one another. Assume that the variance $$\text{Var}(X)= P$$ $$\text{Var}(Y)= Z$$ I need to show that $$h(X|X+Y) \leq \frac{1}{2}\log ...
0
votes
1answer
7 views

Explanation of Information double summation within Normalized Mutual Information

The Normalized Mutual Information NMI calculation is described in deflation-PIC paper with the applicable formula copied to the screenshot shown below. My question is specifically about the double ...
0
votes
1answer
49 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 ...
0
votes
1answer
23 views

Binomial coefficients bounded by entropy exponential

So I'm trying to prove that for $\frac{1}{2}< x \leq 1$ we have $$\sum_{\lceil nx \rceil}^{n}{n \choose k} \leq 2^{nh(x)}$$ I've managed to prove that $$\sum_{0}^{\lfloor nx \rfloor}{ n\choose ...
0
votes
1answer
30 views

Capacity of Z Channel

Calculating the capacity of the Z channel (binary asymmetric channel) here, the entropy $ H(Y)$ isn't supposed to be $ H(Y)=H(a+(1-a)p,(1-a)(1-p))$ ? What's the reason for having $H(Y)=H((1-a)(1-p))$ ...
0
votes
0answers
17 views

Metric Entropy Upper Bounds

In the paper Information-Theoretic Determination of Minimax Rates of Convergence the authors present Theorem 3 as follows: If $M_2(\epsilon)$ is the $\ell_2$ packing entropy of a density class ...
0
votes
2answers
14 views

Question regarding the Entropy of a probability mass function

I assume that the entropy, $E$, of a probability mass function (pmf), $p(X)$, of a discrete random variable, $X$, is computed as: $$\begin{align}\mathbb{E}(p(X)) &= -p(X = x_1)\log[p(X = ...
1
vote
1answer
32 views

Convexity of $I(X;Y)$: why $H(Y)$ convex in $p(y)$ $\Rightarrow$ $H(Y)$ convex in $p(x)$

I would like to understand the proof that mutual information $I(X;Y)$ is concave in $p(x)$ - as presented in Elements of Information Theory by Cover & Thomas, theorem 2.7.4. Here's the proof from ...
6
votes
2answers
1k views

Proof of Pinsker's inequality.

How to prove the following known (Pinsker's) inequality? For two strictly positive sequences $(p_i)^n_{i=l}$ and $(q_i)^n_{i=l}$ with $\sum_{i=1}^np_i=\sum_{i=1}^nq_i=1$ one has ...
1
vote
2answers
46 views

Probability of inequality, Markov inequality application

A bit of context: working on a problem about channel coding. Through a channel we are sending a random variable $X_n$, a code, and at the other side we see $Y$ (both discrete). Then we perform an ...
1
vote
1answer
56 views

Standard deviation of a baised $d$-sided coin

I know that that standard deviation of a noisy bit (a biased coin with probability distribution $\{ p, 1-p \}$ ) is given by $$ \sigma = \sqrt{p(1-p)} $$ What is then a measure of the standard ...
2
votes
1answer
18 views

conditional entropies for identical distributions

Let me say I have two distributions $X$ and $Y$ which are identical, but they are not independent. Now if were to calculate the conditional entropies $H(X|Y)$ and $H(Y|X)$. Is calculating one joint ...
1
vote
2answers
744 views

Fano's inequality explained intuitively?

I am now reading through a book to understand Fano's inequality, but I remember my professor explaining it in a certain way that made it seem so logical. I will go office hours as soon as possible, ...
2
votes
0answers
23 views

Doubt in derivation of a proof in Information Theory

In my class we were trying to derive Shanon's Source Theorem, first by proving the equivalent form in a weaker version. The question is -Consider a biased coin with probability of heads $p \geq ...
1
vote
2answers
60 views

Strategy to find out how wires are connected

There is a tube with $100$ electrical wires that are not labeled. At side $A$ of the tube, the terminal ends of the $100$ electrical wires can be connected. It is possible to connect more than $2$ ...
0
votes
0answers
29 views

What is the relationship between the Fourier spectrum and the information content?

Suppose you look at the Fourier transform of some data (say, a blurred image). The amount of high frequency signal tells you how much texture there is in the data (e.g., a blurrier image has a more ...
0
votes
0answers
50 views

Absolute value of difference between entropies (of two distributions)

I have the following inequality for the $L_1$ distance between two distributions $Q$, $Q^n$ on a finite set $B$: $$\|Q-Q^n|| < \frac{2|B|}{n}\leq \frac{C}{n} \leq \frac12 $$ Assuming $C\geq2|B|$, ...
3
votes
0answers
39 views

Proving or disproving concavity of a function

I want to prove that the following function is concave (as a part of another proof). $$f(p) = \max_{\begin{matrix}x,y\\0\le x \le 1\\0\le y \le 1 \\ x * y = p\end{matrix}} \lambda h(x) + ...
9
votes
1answer
131 views

Is Entropy = Information circular or trivial?

I have seen several "maximum entropy distributions" used in the mathematical and statistical literature, often with the justification that they are "minimally informed" beyond the assumptions and data ...
2
votes
2answers
75 views

Is Information Theory Mathematics?

When I read about Information Theory, for example on Wikipedia, I can never find statements that say if Information Theory is "real" Mathematics with underlying axioms, a notion of "proof beyond ...
0
votes
0answers
33 views

Do Redundancy and Shannon's Entropy correlate?

I wonder can anyone answer whether the Entropy and the Redundancy correlate. I am interested in cases where the distribution is over discrete categories (i.e., cases), but I think it should apply for ...
1
vote
0answers
25 views

What does “to first order in exponent” mean?

I am studying information theory on "Elements of Invormation theory" (Cover Thomas). I cannot understand the meaning of "to first order in exponent" in the following theorem: ...
11
votes
0answers
210 views

Determining information in minimum trials (combinatorics problem)

A student has to pass a exam, with $k2^{k-1}$ questions to be answered by yes or no, on a subject he knows nothing about. The student is allowed to pass mock exams who have the same questions as the ...
0
votes
1answer
41 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 ...
0
votes
1answer
81 views

From Orthogonal vectors to Useful Bivector

If we have set of orthogonal vectors (X) can we form a set of orthogonal bivectors from that set? I am trying to find if there is a way to get 'more information' from an orthogonal matrix by some ...
2
votes
2answers
35 views

Channel code for multiple bit errors

I've been exploring information theory out of personal interest and have a cursory understanding of Hamming Codes. From what I can tell, they're designed to exclusively detect the location of a single ...
1
vote
1answer
34 views

Understanding an application of Entropy

I'm struggling with the following exercise on entropy. Suppose that your friend Alice chooses a number $X$ uniformly at random from $[1,n]$, which she writes down using $\log n$ bits; you can assume ...
0
votes
0answers
45 views

Random Codebook Generation

I do generate a random codebook $\mathcal{C}$ by generating $2^{NC}$ codewords $X^N=[X_1\;X_2\;\cdots\;X_N]$ randomly and independently, each according to some distribution $p_{X^n}(x^n)=\Pi_{i=1}^n ...
0
votes
1answer
35 views

Relation between independence number and channel capacity

Suppose $P_{Y|X}$ is a discrete memoryless channel with confusability graph $G$ and capacity $C = max_{P_X}I(X; Y )$. I want to prove the following relation: $\log{\alpha(G)}\le C$ where $\alpha(G)$ ...
1
vote
1answer
23 views

Fewest number of questions to find subinterval

I need some help with the following question: Let $S=${$x_1$,... $x_n$} be a set of $n$ real numbers listed in ascending order: $x_1<x_2<...<x_n$. Given a real number $r$ that exists in ...
0
votes
0answers
22 views

Description length in model coding

In class, our professor posted the following: We will discretize $\theta$ (some model) into $1/\sqrt{n}$ distinct values. Intuitive argument: with N data points, our estimation error for $\hat ...
0
votes
0answers
64 views

Can we use the distance to nearest prime to approximate large integers?

Let's say we have two oracles, NearestPrime and IndexOfPrime, defined as follows: Given some integer x, NearestPrime yields the prime number nearest to x that is not greater than x. ...
0
votes
3answers
83 views

Isn't this the most compact binary representation of all numbers?

Here is the transformation: $$\begin{align*} &1\to(0)\\ &2\to(1)\\ &3\to(10)\\ &4\to((1))\\ &5\to(100)\\ &6\to(11)\\ &7\to(1000)\\ &8\to((10))\\ &9\to((1)0)\\ ...
0
votes
1answer
26 views

Is this formula a KL divergence?

As everyone knows KL divergence's formula is $KL(p||q) = \sum_{i=1}^{n}p(i)\log (p(i)/q(i))$. In the image, formula(9) is really calculate KL(X||($(UZ^TA^T)$)) , however i have no idea why there is ...
1
vote
0answers
33 views

Generalized Form of Fano's Inequality

The Wikipedia article on Fano's Inequality presents a generalization as follows: Let $\mathbf{F}$ be a class of probability densities with a subclass of $r+1$ densities denoted $f_{\theta^{(i)}}$ ...
2
votes
0answers
22 views

Error correcting codes for asymmetric channels

Most work in error correction coding theory (Hamming, Cyclic, BCH, Reed-Solomon, Turbo Codes, LDPC...) deals with linear codes. Now, a linear code binary code is a good fit (only?) for a symmetric ...
4
votes
1answer
140 views

Source coding theorem - optimum number of bits?

The source coding theorem says that information transfer with variable length code uses less bits and is equal to the entropy of the distribution. It also says that there is no code that uses lesser ...
2
votes
1answer
27 views

Capacity of a Binary Deletion Channel

It is well known that a communication channel with a randomly induced 50% bit error rate has zero capacity but determining the capacity of a binary deletion channel is still an open problem. Why ...
0
votes
1answer
40 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 ...
0
votes
1answer
40 views

What is the exact meaning of $I(X;Y|Z)$ in Information Theory?

I am wondering: is the notation $I(X;Y|Z)$ used to denote the mutual information between probabilities of $X$ and $Y|Z$ or between $X|Z$ and $Y|Z$?
1
vote
0answers
33 views

Kolmogorov complexity of a computer?

Warning: Vague, unclear question ahead. Proceed at your own risk. The Shannon entropy and Kolmogorov complexity give you in broad informal terms how unpredictable a string is and to what degree the ...
7
votes
2answers
378 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 ...
7
votes
3answers
152 views

Using decimals of $\pi$ to store data

I read recently about an idea to, instead of storing actual data, converting the data to a string of digits and then store the index of where this pattern occurs in some number, for example $\pi$. The ...
0
votes
1answer
38 views

Which one is bigger $D(P\Vert Q)$ or $D(Q \Vert P)$?

In general the Kullback-Leibler divergence is asymmetric. If $P$ and $Q$ are two distributions $D(P\Vert Q) \ne D(Q\Vert P)$. However, I was wondering if there are situations where we can say which ...