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
1answer
25 views

Is there any differentiable function $f$ that approximates the “entropy” of a set of numbers $S$?

Where entropy is some measure of the degree of randomness/disorder in a given set of numbers: $S = \{a_1, a_2, ..., a_i\}$ For example, the set $S_{high} = \{4,0,2,5,8,3,7,2,5\}$ has a high degree of ...
2
votes
1answer
111 views

Coupon Collector Problem for Non-Uniform Coupons: On the number of missed Coupon

Suppose $\mathcal B=\{1,2,\ldots,b\}$ is the set of all possible coupons, with $\mathbf p = ( p_1,p_2,\ldots,p_b)$ assigning the probability of occurrence for all coupons in $\mathcal B$. The ...
2
votes
0answers
50 views

What is the variance of self-information (or surprisal)?

The self-information of an outcome $x_i$, or surprisal, is defined as: $$ I(x_i)=-\log P(x_i), $$ where $P$ means probability. This way, the Shannon entropy can be seen as the "average" or "expected" ...
0
votes
0answers
19 views

Statics maximization

I really need a help to compute the following maximization problem. $$\max _{p(x), E(x) \leq \alpha} \int_x \int_y \frac{p(x,y)^2}{p(x)p(y)} dx \,dy$$ Suppose that : $$p(y|x)=\frac{1}{\sqrt{2 \pi ...
1
vote
1answer
33 views

data processing inequality using non-deterministic functions

Generally data processing inequality says that the entropy cannot increase on applying a function f, or to be precise $H(f(X))\leq H(X)$ (also it is reversed if we know the function is k-to-1 so there ...
0
votes
1answer
34 views

How a Galois Field is used to construct a Hamming Parity Matrix

I'm trying to understand how Matlab is generating their Hamming parity matrix. The default according to the documentation is GF(2^m), where m=3. Hamming(7, 4) parity matrix from Matlab ...
0
votes
1answer
31 views

Largest positive eigenvalue of a matrix

I am dealing with the Capacity of constrained noiseless communication channels. It has been said that the channel capacity of such a channel is $\log{\lambda}$, which $\lambda$ is the largest positive ...
3
votes
1answer
47 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 ...
7
votes
1answer
73 views

Structure of equientropic transformations

Given a probability vector $v=(v_1,\ldots,v_n)$ with $1\geq v_i\geq 0$ and $\sum_{i=1}^n v_i=1$ its entropy can be defined as: $$ H(v):=-\sum_{i=1}^nv_i\log v_i $$ I wonder what is known about ...
0
votes
0answers
31 views

Identifying a Markov chain

This is a very basic question in the theory of Markov chains and I'm just not sure how to prove it mathematically. Say we have random variables $X, Y$ that are correlated and we have a possibly ...
0
votes
0answers
31 views

How to calculate the mutual information between two outputs of Rayleigh fading channels

We have the two channels: $$X_{a,i} = H_{i}s_{i} +N_{a,i} \\ X_{b,i} = H_{i}s_{i} +N_{b,i} $$ for $1 \leq i \leq n$, where $H_i$ denotes the i.i.d. channel coefficient and is a zero-mean complex ...
0
votes
1answer
15 views

Relative Entropy decomposition reference

may I ask for some reference pointers? My bad as I got a classic case of losing my reference and thus unsure what I wrote was right or wrong. I tried looking my old references and internet and didn't ...
0
votes
2answers
40 views

Proving certain aspects of Entropy

I am trying to prove three properties of entropy. $1)$ $H(X|Y,Z)\le H(X|Y)$ $2)$ $H(X|Y,Z)\le H(X,Y)$ $3)$ $H(X,Y,Z)+H(Y)\le H(X,Y)+H(Y,Z)$ I have proved the third one, but it is based on part 1. ...
0
votes
1answer
46 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
1answer
31 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
35 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
27 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
19 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
35 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
57 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
13 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
29 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
47 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
25 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 ...
1
vote
2answers
64 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
2answers
29 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 = ...
0
votes
1answer
47 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?
1
vote
1answer
33 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 ...
2
votes
1answer
22 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
51 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 ...
2
votes
0answers
29 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
1answer
58 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 ...
1
vote
2answers
61 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
32 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 ...
3
votes
0answers
54 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) + ...
0
votes
0answers
57 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|$, ...
9
votes
1answer
139 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
94 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 ...
1
vote
1answer
55 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: ...
0
votes
0answers
40 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 ...
0
votes
2answers
136 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
2answers
42 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 ...
0
votes
1answer
89 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 ...
1
vote
1answer
45 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
49 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
37 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)$ ...
11
votes
0answers
235 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
0answers
24 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
70 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
1answer
34 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 ...