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

Decomposability of Inf. Entropy applied to corpus statistics

Can you help me understand the additivity property of IE? I think I may have found a violation but it may be that I'm just misunderstanding the maths. I'm attempting to achieve a meaningful ...
0
votes
1answer
32 views

How to understand the product of two conditional probabilities?

I am struggling a little bit with making sense of the distribution of bigrams in an artificial language I randomly generated from english. Every word occurs with an equal probability but the ...
1
vote
1answer
22 views

Confused By Information Diagram

I'm working on information theory and I get confused by the information(venn) diagram. Is there any one help me with the following confusion? As defined, mutual information $I(X;Y)$(Figure a) is ...
1
vote
1answer
19 views

Understanding Conditional Mutual Information

Recently I'm working on conditional mutual information and I'm trying to prove the following property: I(X;Y|Z,W)<=I(X;Y|Z) The property seems obvious to me: ...
0
votes
1answer
18 views

Finding error control capability of Hamming distance

I have known how to calculate the Hamming distance between two message codes. But I don't know how to get the error control capability. In one case I have hamming distance of: $$ d = 8 $$ Errors ...
0
votes
1answer
20 views

Mutual Information Gaussian

Suppose $x$ has a multivariate Gaussian distribution given by $\mathcal{N}(\mu , \Sigma)$. How do you express the mutual information between two coordinates that is $\mathrm{I}(x_i;x_j)$ , as a ...
1
vote
0answers
9 views

Proof of inequality about mutual information

There is some joint distribution of random variables $(a, b, c, x, y)$. It is known that $I(a;b|c) = I(a;c|b) = I(b;c|a) = 0$ It is needed to prove this inequality: $I(a;b) \leq I(a;b|x) + I(a;b|y) + ...
1
vote
0answers
12 views

Kolmorogov complexity equality [closed]

Prove, that KS (x, KS(x)) = KS (x) + O(1). Please tell me in which direction to think.
2
votes
0answers
15 views

Kolmogorov complexity inequality

Prove, that KP (x) ≤ KS (x) + log KS(x) + 2 log log KS (x) + O(1). Please tell me in which direction to think.
1
vote
0answers
10 views

Optimal Kolmogorov complexity

Let computable function U is the best way to describe to Kolmogorov complexity. Prove that the mapping V, determined crucial for any word p as V (p) = U (U (p)), is also optimal way to describe the. ...
1
vote
0answers
20 views

Proof of a fact about mutual information and entropy

It is needed to prove that for distribution (a, b, c) such that $I(a;b|c) = I(a;c|b) = I(b;c|a) = 0$ exists a random variable $d$ such that $H(d) = I(a, b, c)$ and $a,b,c$ are independent with ...
1
vote
1answer
27 views

Proof of inequality with entropy

I can not prove this inequality $2H(a,b,c) \leq H(a,b) + H(a,c) + H(b,c|a),\ H-entropy $. I tried do it by using chain rule and this inequality $H(X|Y) \leq H(X;Y)$ but without any success. Please ...
0
votes
1answer
20 views

Questions Regarding Mutual Information

I've been conducting a small experiment to test a few of my interpretations about mutual information, and I'm running into some difficulties. I've created some MATLAB code that basically makes two ...
0
votes
0answers
15 views

Capacity of uniform noise channel

I'm pretty sure I've made some error in reasoning in this exercise because it gets a little bit too easy. Let $X$ be independent from $N$ where $N$ is uniformly distributed over $[-1,1]$. Suppose ...
0
votes
1answer
29 views

a question about entropy of run length coding

I'm doing an exercise from chapter two of $\textit {elements of information theory}$. Here is the problem and its solution, . I'm not very clear about the equation 2.36 or say why does the equation ...
1
vote
2answers
30 views

Entropy for three random variables [duplicate]

I'm just working through some information theory and entropy, and I've come into a bit of a problem. In many texts, it's easy to find the "chain rule" for entropy in two variables, and the ...
1
vote
1answer
23 views

conditioning reduces mutual information

$I (X, Y |Z) >I (X,Y)$ can happen, for example $X$, $Y$ independent bits and $Z = X+Y$. How do you show this fact using Venn diagrams? Conditioning would mean removing the mass of conditioning ...
0
votes
0answers
24 views

Sum of Coding rates of encoders accessible by decoder must be at least “h”, in order for “r” to be admissible. How?

Let we have one source with information rate "h" and 4 encoders with information rate r1, r2, r3 and r3 and r=[r1...r4]. Following conditions are necessary for r to be admissible. How? r1+r2 >= h ...
0
votes
2answers
35 views

Required bits to communicate a partial order?

Suppose that you have a ranking (i.e. a strict complete partial order) over $n$ different objects, so that the objects can be ordered as $a>b>\cdots>n$. You want to communicate the exact ...
0
votes
1answer
21 views

the counterexample of the pinsker inequality.

if P and Q are probability measures over a set X, and P is absolutely continuous with respect to Q,then set $$ D_{\mathrm{KL}}(P\|Q) = \int_X \ln\frac{{\rm d}P}{{\rm d}Q} \, {\rm d}P, $$ set ...
0
votes
0answers
20 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
21 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
17 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
42 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
28 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
24 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
16 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 ...
2
votes
0answers
26 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
25 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
16 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
37 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
60 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
30 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
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
105 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
49 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
32 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
31 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 ...
2
votes
0answers
30 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
28 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
28 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
33 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 ...