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
28 views

Schur complement for Square root information matrix

Consider a joint information matrix I over X and Y (both vectors). Now, I would like to get the marginal information matrix for X: $I_x$. This can be of course performed via Schur complement. Now ...
0
votes
0answers
24 views

quantization of a discrete probability source

The alphabet of a memory less source is $A=\{-5,-3, -1, 0, 1, 3, 5\}$ with corresponding probabilities $\{0.05, 0.1, 0.1, 0.15, 0.05, 0.25, 0.3\}$. If I know that the source can be quantized ...
1
vote
1answer
19 views

Best possible approximation of P(X,Y)

I want to show that $\min_Q D(P_{Y|X} || Q | P_x) = I(X;Y)$ and I've arrived at a question. Here $D$ is the KL divergence or relative entropy and $I$ is of course the mutual information. ...
3
votes
1answer
53 views

What is an intuitive explanation for Birkhoff's ergodic theorem?

If I'm not familiar with measure theory, what is a good way to understand the idea behind the definitions involved, the interpretation of the theorem, and the proofs thereof? Particularly, it's not ...
0
votes
3answers
37 views

Is there a means of calculating the entropy of a series of bits that takes correlation into account?

A common expression for calculating the entropy of a series of bits appears to be: $$-\sum_{i}{P\left (x_i\right )log_b\left (P \left (x_i\right )\right )}$$ This seems to fail (or my intuition of ...
0
votes
1answer
47 views

Conditional typicality (information theory) intuition

Reading Network Information Theory, Gamal. It's a bit terse at times and I'm trying to get an intuition for conditional typicality. The conditional typicality lemma states Let $(X,Y) \ \tilde{} \ ...
1
vote
0answers
19 views

Fisher Expected Information for a Gaussian Process model

Suppose I have a two dimensional Gaussian process model (GP), defined by a squared exponential correlation function s.t: $$R(x_{i},x_{j}) = \exp\left(-\frac{|x_{i} - x_{j}|^2}{2}\right).$$ I am ...
0
votes
0answers
15 views

Prove the identity $nH(X_1,…,X_n)=…$ for any $n \geq 2$

How can I prove that the identity $$nH(X_1,...,X_n)= \sum_{1\leq i_1 < i_2<...<i_n\leq n+1} H(X_{i_1},...,X_{i_n})+\sum_{i=1}^{n} H(X_i|X_j,j\neq i)$$ stands for any $n \geq 2$ For n=2 we ...
3
votes
1answer
45 views

sufficient and necessary condition for equality between conditional mutual information and unconditional one.

Suppose $X, Y, Z$ are three discrete random variables. Is there a good sufficient and necessary condition for $I(X;Y|Z) = I(X;Y)$? Usually the LHS can be bigger or smaller than the RHS, but if Z is ...
1
vote
1answer
28 views

Min/Max number of inequalities needed to determine the order of $n$ numbers

We are given an ordered $n$-tuple of positive real numbers $R=(r_1,..r_n)$. A $k$-inequality is an inequality of the form $x_1<x_2<...<x_k$ where $x_1,..,x_k$ are in $R$. For example, for ...
2
votes
1answer
36 views

Blackwell's informativeness criterion

Let $a=(a_1,\dots,a_i,\dots,a_n)$ be a probability vector, i.e. $\forall i: a_i\ge0$ and $\sum_i a_i=1$. Suppose $b$ is another $n$-dimensional probability vector. Is it true that there always ...
0
votes
1answer
45 views

Ratio between forward and reverse conditional probability

I have a probability distribution $p(Z | X)$ from which I can easily sample and compute the probability at every value for $Z$ and $X$. The inverse distribution $p(X | Z)$ however can be very complex ...
2
votes
2answers
94 views

How to prove H(X,Y) $\ge$ H(Z)?

I'm solving a problem from elements of information theory, 2nd. I got stuck by question(c) and actually, I've checked the answer, here it is: How to prove the inequality from the answer that is ...
0
votes
1answer
41 views

Calculating the information per symbol of a markov chain source

I have a 4-state 2nd order markov chain source with symbols 0 and 1. I have all the transition probabilities and have worked out the probabilities of each state. How do I go about finding the amount ...
0
votes
1answer
29 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
122 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
58 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
21 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
47 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
54 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
38 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
69 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
32 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
43 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
19 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
42 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
49 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
39 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
63 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
39 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
23 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
44 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
64 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
31 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
37 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
65 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
31 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
90 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
35 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
53 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
35 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
28 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
58 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
31 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
64 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
34 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
59 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
64 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|$, ...