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

Entropy Calculation and derivation of logarithm

I have probabilities as $$p_1 = 0.4,\ p_2 = 0.3,\ p_3=0.2,\ p_4=0.1$$ hence entropy is given by: $$H(x) = -\big(0.4\cdot \log_2(0.4) + 0.3\cdot \log_2(0.3) + 0.2\cdot \log_2(0.2) + 0.1\cdot ...
0
votes
0answers
13 views

How to prove equality $K(x, K(x)) = K(x) + O(1) $?

It is needed to prove that $K(x, K(x))=K(x) + O(1)$ where $K$ means Kolmogorov complexity. I think the equality is true because when we find Kolmogorov complexity of $x$ we already knows $K(x)$ and ...
0
votes
0answers
19 views

Is there a perfect secret sharing scheme for any structure of access with three participants?

It is needed to check that: 1)for any structure of access with three participants there is always a perfect secret sharing scheme 2)for any structure of access with four participants there is always ...
0
votes
0answers
19 views

Why do we need ϵ>0 for typical set in Asymptotic Equipartition Property (AEP)?

In following text, author has used ϵ>0 for a typical set in AEP but it don't matter if we don't take it. Why is ϵ needed as I am seeing it a lot in information theory specially in AEPs. Can someone ...
2
votes
0answers
18 views

Confidence Interval of Information Entropy?

Information entropy, $IE$, is defined as: $$IE = \sum_{i} p_i log\frac{1}{p_i}$$ Where $p_i$ is the probability of event $i$ (and we are summing over all possible events). Let's say I have data ...
0
votes
1answer
21 views

Summation notation conversion to multiplication in attached equation.. How? Please explain.

Can any one please tell me how summation sign has been changed to multiplication in 2nd and 3rd equation and inequality also changed to equal sign.
0
votes
0answers
13 views

Finding optimal output alphabets

Let's say I have am given an input distribution, and I want to find the optimal output distribution. By "optimal" I mean that the mean squared error between output and input distribution is minimized, ...
0
votes
1answer
20 views

Question about conditional entropy.

Jointly distributed random variables (a) and (b) are distributed on the n-element set. Let $\varepsilon = Prob(a \ne b)$ It is needed to prove that $H(a|b) \le 1 + \varepsilon log(n-1)$. I tried ...
2
votes
0answers
12 views

Help me construct a bijection $g: \left(1..n\right)^m \to \left(1..n\right)^m$, with influence of each component of $x$ in each component of $g(x)$

Let $x \in \left(0..n-1\right)^m$. I want to construct a bijection $g$ : $\left(0..n-1\right)^m \to \left(0..n-1\right)^m$ such that if we know $m'$ components of $g(x)$ and $m-m'$ components of $x$, ...
0
votes
1answer
14 views

Mutual Information of Coupled channels

I am trying to determine the what the expression for the mutual information of following system would be; $Y_1$ = ($X_1$ + $\eta_1$) + A($X_2$ + $\eta_2$) $Y_2$ = B($X_1$ + $\eta_1$) + ($X_2$ + ...
0
votes
0answers
31 views

Is there an alternative encoding scheme to binary where similarity of pattern correlates with size of number?

If I compare binary for 7 111 and binary for 8 1000 there is no correlation between these two patterns that suggests that ...
0
votes
1answer
21 views

Proof of an inequality with entropy and mutual information.

Entropy of a random variable (a) is (h) : $H(a) = h$. Mutual information of (a) and (b) is (3h/4) : $I(a;b) = 3h/4$. Mutual information of (a) and (c) is (3h/4) : $I(a;c) = 3h/4$. It is needed to ...
1
vote
1answer
37 views

Linearity of codes

Assuming $C$ is a binary linear code and let $a$ $\notin $ $C$ be any vector. Show that $C$ $\cup (a + C) $ is also linear. I know that for any $C_1,C_2 \in C $ then $\alpha C_1 + \beta C_2 \in C$ ...
1
vote
0answers
66 views

Vector distance of binary

Suppose $\overline{u},\overline{v},\overline{w},\overline{x}$ are four binary vectors, pairwise distance d apart. Show that d must be even, there's exactly one vector which is a distance $d\over 2$ ...
0
votes
0answers
22 views

What are some techniques of specifying a molecules structure using the least amount of information?

For instance say I have a water molecule I can describe it's structure by two bond lengths and a bond angle. Are there any neat math tricks or representations of objects that I could use to describe ...
1
vote
0answers
25 views

Constructor Theory: Why does $y\subset z$ imply $y \not \bot z$?

In the paper Constructor Theory of Information, page 11. We are told that a set $X$ of attributes are distinguishable if the following is a possible task: $$\{ x\rightarrow \Psi_x | x\in X \}$$ where ...
0
votes
2answers
27 views

Mutual information expressed as Kullback-Leibler divergence

My lecturer defines the mutual information: $$ I(X;Y\mid Z) = D_{KL}\big(p(X,Y\mid Z)\parallel p(X\mid Z)\;p(Y\mid Z)\big)$$ Is this correct? I feel like it doesn't really make sense to say that; ...
1
vote
0answers
20 views

Proof that the inequality with mutual information and conditional mutual information is not true always.

It is needed to prove that inequality $I(a:b) \le I(a:b|x) + I(a:b|y) + I(x:y)$ (where I(a:b) is mutual information and I(a:b|x) is conditional mutual information) is true not for all sets of random ...
2
votes
1answer
89 views

Using Markov Chains to simplify mutual information expressions

I read a paper in Information Theory which claims that the following sum of three mutual information expressions $$ I(Y_1;X_1,X_2,X_3)+I(Y_2;X_2,X_3\mid Y_1,X_1)+I(Y_3;X_3\mid Y_1,Y_2,X_1,X_2)\tag1$$ ...
1
vote
0answers
19 views

Task about Hartley information(logarithm from cardinality of the set) of a number of paths in a graph and about limit linked with this information.

Let $L_n$ be the number of all paths of length n in a directed graph(below). It is needed to find $lim_{n \to \infty}\chi(L_n)/n$ where $\chi(L_n)$ is Hartley information in $L_n$ set. (If I am not ...
0
votes
1answer
27 views

Existing of a distribution of three random variables that have conditional mutual information with defined properties.

I have two similar questions: 1)Does exist a distribution of three random variables such that: $I(a:b) = 0$ and $I(a:b|c)>0$ (where $I(a:b)$ is a mutual information and $I(a:b|c)$ is a ...
6
votes
1answer
108 views

Guessing number in set 1-100 with weighted questions.

It is needed to guess number from 1 to 100. I can ask questions and get answers:"yes" or "no". For the "yes"-answer I must pay one dollar, for the "no"-answer - two dollars. How many dollars should I ...
1
vote
1answer
22 views

Why does the information content of a less probable event yield more bits than a more probable one?

I gather for a series of four coin flips, if we get $H,H,H,H$, this has a probability of $\tfrac{1}{16}$, so we have information content $$\log_2 \frac{1}{\frac{1}{16}}$$ But for the rest of the ...
1
vote
0answers
44 views

Proof of an inequality about set in four-dimensional space

It is needed to prove that for set $A \subset N^4$ $3\log|A|\le \log|\pi_{1,2,3}(A)|+\log|\pi_{1,2,4}(A)|+\log|\pi_{1,3,4}(A)|+\log|\pi_{2,3,4}(A)|$ where $\pi_{i,j,k}(A)$ is a projection of $A$ on ...
0
votes
0answers
36 views

The mutual information rate spectrum

Definition: $\mathbf{X}$ denotes the random vector $({X_1},{X_2},...,{X_n})$. The mutual information between $X$ and $Y$, $I(X;Y)$, is determined by the joint law of $p(X,Y)$, Given two random ...
0
votes
1answer
28 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
39 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
19 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
12 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) + ...
2
votes
0answers
19 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
13 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
25 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
37 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
24 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
22 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
30 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
36 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
27 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
25 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
37 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
22 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
22 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
43 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
30 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
29 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{} \ ...