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
votes
0answers
9 views

Weak continuity of K-L divergence function

If $P_n$ and $Q_n$ are two pmf's of a discrete set (say $A$) with common support and $P_n \to P$ and $Q_n \to Q$ where the convergence is pointwise here (even weak would be fine here I guess), then $$ ...
0
votes
1answer
24 views

Mutual Information: How these two equations are equal?

I'm a biologist trying to apply the Mutual Information (MI) to some RNA secondary structure. I know that there exists two MI equation that, mathematically, are equal: $I(X,Y) = \sum_{x,y} p(x,y) ...
2
votes
1answer
29 views

Puzzle: Determining the structure of a bipartite graph

Consider the bipartite graph $G = (X, Y, E)$, with $|X| = |Y| = n$. We can think of $X$ and $Y$ as clusters of $n$ switches on either end of a long hallway. Each switch on one end of the hallway has ...
0
votes
1answer
33 views

Derivation of equation for self information

I am trying to understand how the formula I(x) = -log(p(x)) for self information was derived. From what I have read, 2 constraints were imposed on the properties ...
1
vote
1answer
43 views

Help with “Elements of Information Theory”

I was following the textbook by Cover & Thomas (2006): Elements of Information Theory. (hyperlink is not owned by me) I have one question that has been irking me for some time. It is regarding ...
0
votes
0answers
13 views

Network Coding multicast r symbols simultaneously. Physically How?

I understand how network coding works but physically how r symbols can be multicast to all destinations from one source? For example in following butterfly network, there are two symbols which can be ...
-1
votes
1answer
22 views

Plug mutual information in PCA

What happens if I plugin mutual information instead of usual cor/cov in the PCA algh?Tnks(ps: I am not interested in I-PCA)
1
vote
2answers
39 views

How much information does learning this interval give you?

Let's say you have a number $x$, and a priori, you know that $x \in [0, 1)$ (each value from 0 to 1 is equally likely.) Then a wizard comes and tells you that $x \in [a, b) \subseteq [0, 1)$. How much ...
0
votes
1answer
62 views

mutual information adds along path

Is it true that $I(X;Y)+I(Y;Z)=I(X;Z)$ for $X \to Y \to Z$? $I(X;Z) = H(X)+H(Z)-H(X,Z)$ and $I(X;Y)+I(Y;Z) = H(X)+H(Z)-H(Z|Y)-H(X|Y)$ Hence, we would require $-H(X,Z)=-H(Z|Y)-H(X|Y)$ -- is it true? ...
0
votes
1answer
57 views

Constructing a new Markov chain from another Markov chain

I have a very simple problem, but it seems I have difficulty to prove it rigorously. Suppose random variables $X, Y$ and $Z$ form the following Markov chain: $X\leftrightarrow Y\leftrightarrow Z$. My ...
-1
votes
1answer
20 views

Proof: difference in codeword length is less than 2 (Huffman coding of uniform distribution)

Assume an alphabet in which all letters have the same probability. These letters are coded using a binary Huffman code. Proof that the difference in codeword length is less than 2. It seems ...
3
votes
2answers
93 views

Mutual information of discrete RVs which converge in distribution to a continuous RV

We have a sequence of pairs of discrete, real-valued RVs $X_n$ and $Y_n$. Each pair is characterized by a discrete probability measure on $\mathbf{R}^2$, which we will just denote $\mu_{X_n,Y_n},$ ...
0
votes
0answers
22 views

Kac Lemma for staionary ergodic processes

Simple question. I have a stationary ergodic process $U$ on a finite alphaet and I want to prove the Kac's Lemma (see Cover and Thomas - Elements of Information Theory (second ed.) page 445). In the ...
0
votes
0answers
11 views

Channel capacity of matrix with two identical rows

If a channel matrix $M$ has two identical rows $r_1,r_2$, and $M'$ is the channel matrix $M$ with $r_1$ removed, how would you show the channels with matrices $M$ and $M'$ have the same capacities?
1
vote
2answers
64 views

Calculation of Shannon entropy given the mutual information of Binary strings

Suppose $A$ and $B$ two different binary strings of length $l$. Suppose the Mutual Information (https://en.wikipedia.org/wiki/Mutual_information) of $A$ and $B$ is known to be $I$. Now suppose ...
0
votes
0answers
9 views

Precise statement of Gersho's conjecture

Here is the Gersho's conjecture from his paper "Asymptotically optiaml block qunatization" "For $N$ sufficiently large the optimal(distortion-minimizing) quantizer for a random vector uniformly ...
0
votes
1answer
36 views

For $A,B,C$ independent and normal, what is $I(A+B;\ A+C)$?

Say $A,B,C$ are mutually independent and normally distributed with zero mean but possibly different variances $\sigma_1,\sigma_2,\sigma_3$. What is the mutual information between $A+B$ and $A+C$? All ...
0
votes
1answer
51 views

Given a biased coin $P(X=0)=.75$, can someone show me a compression scheme that beats 1 bit

Given a biased coin $P(X=0)=.75$, I've been unable to find a coding scheme which beats the identity code of $0\to0$ and $1\to1$, which of course is an efficiency of 1 bit per transmission. The ...
-1
votes
1answer
47 views

How can AC be listed as a single voltage [closed]

How can AC be listed as a single voltage (e.g 240V AC) when it constantly varies and what does this have to do with RMS Voltage.
1
vote
1answer
30 views

Inequality in differential entropy

In the book on "Network Information Theory" by El Gamal, there is a question to choose the correct relation ($\geq,\leq,=$) for the following: Let $X$ be a continuous random variable. Let $Y\sim ...
1
vote
1answer
39 views

Shannon entropy and inequality of expectations

Consider two distinct probability distributions $P(X)$ and $Q(Y)$---defined on the same domain---with (Shannon) entropy of $H(X)$ and $H(Y)$. I am interested to prove (or disprove) that $$ H(X) \leq ...
1
vote
0answers
64 views

Why covariance constraint subsumes the average power constraint?

I am studying an optimization problem in the form of \begin{equation} \begin{aligned} &\underset{p(x)}{\text{maximize}} & & W\\ & \text{subject to} & & 0 \preceq K_{X} ...
1
vote
0answers
27 views

Construct PDA that accepts the language $ L = \{ w \in \{ a,b,c\}^*; |w|_c=|w|_a + |w|_b \} $

Problem Construct PDA that accepts the language $ L = \{ w \in \{ a,b,c\}^*; |w|_c=|w|_a + |w|_b \} $ My first idea was this: There can be an "a","b" or a "c" at the beginning of a word Then we ...
0
votes
2answers
37 views

What delimits the mathematical framework within which information compression limits (from entropy) are valid.

Lets suppose for absurd that I eliminate one number from the naturals. If I were supersticious I would eliminate number 13. Now imagine that to keep normal mathematics possible within such system ...
0
votes
1answer
39 views

Where can I find a proof of this result?

Does anyone know where I can find a proof of the underlined statement? Newman states it without a proof, and I could see how he gets $\dfrac {\sigma}{n} + O\left(\dfrac{1}{n^{3/2}}\right)$. Any ...
2
votes
0answers
52 views

Is Gaussian $(X_1, X_2)$ optimal for $h(a_1X_1+ a_2X_2+Z_1) - \mu \, h( b_1X_1+b_2X_2+ Z_2)$?

Let \begin{align} W &= h(X_1+Z_1) - \mu \, h( X_2+ Z_2) \quad (1) \end{align} where $h(\cdot)$ is the differential entropy function, $\mu\ge 1 $ is a scalar, and $Z_1$ and $Z_2$ are ...
0
votes
0answers
17 views

Rent's Rule and Modularity?

Rent's Rule http://en.wikipedia.org/wiki/Rent%27s_rule plays a very important role in the engineering of computer circuits, as well as in models of processing (be it of information, be it of brain ...
0
votes
0answers
26 views

Information Theory - Uniquely Decipherable code problem

Hi I'm having trouble with parts bii) and c) of the following problem. For bii) I feel I might need to apply Markov's inequality but I'm really not sure. Edit: Think I've sorted out bii) it was not ...
0
votes
1answer
45 views

Shannon's definition of ergodicity

In A Mathematical Theory of Communication (1948) Shannon gives a definition of ergodicity for a Markov process. In order to be ergodic the directed graph of the process must have the following ...
2
votes
2answers
36 views

Expected time to pick up n things when I can drop them each round?

Why Can't I Hold All These Limes? Suppose I wanted to hold $n$ limes. Each time step, I pick up a lime. But limes are hard to hold, so I also have a probability $p$ to drop a lime on each step which ...
1
vote
1answer
32 views

Tutorials on LDPC error correction codes

Please consider this as soft question. Recently, I have been studying channel coding and in particular error correction codes. I am looking for best tutorial (easy to understand) on LDPC error ...
2
votes
2answers
44 views

Why is an entropy of $\text{log}(n)$ only compatible with the uniform distribution

I have a random variable $X$ and want to show that having an entropy $$ H(X) = - \sum_{i=1}^n p_i \text{log}(p_i) = \text{log}(n)$$ is equivalent to the distribution of $X$ being uniform. Starting ...
2
votes
0answers
54 views

Quantum Teleportation - how to prove the general case?

I've taken a course of quantum information theory and although I can compute a quantum teleportation in an explicit case where I'm given a quantum entanglement shared by Alice and Bob (normally ...
0
votes
1answer
23 views

Shannon's Noisy Coding Theorem

I'm confused by what it means when it says rate. At the bottom of page 15 and page 16 here http://www0.maths.ox.ac.uk/system/files/coursematerial/2014/3093/6/Lecture_notes.pdf it seems to be saying ...
1
vote
0answers
23 views

Interpreting the expression for the “typical” probability of a distribution (Information Theory)

When thinking about typical sets, I've been coming across the notion of the 'typical probability': (1) $p_{typical, X} = 2^{-H(X)}$ (2) $H(X) = -\Sigma p_{i}log(p_{i})$ = $-\Sigma ...
0
votes
2answers
37 views

Entropy Formula $\sum_i p_i log(\frac{1}{p_i})$

In my algorithms course I have been introduced to the concept of entropy and data compression, mainly using huffman encoding. I am trying to understand the formula for entropy $$\sum_i p_i ...
6
votes
1answer
67 views

Distance between theorems

In automated proving one can define the best proof of a theorem as the one which minimizes the length of the proof. Given a set of known statements one could define the difficulty of a theorem as the ...
1
vote
1answer
24 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
20 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
27 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
26 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
28 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
1answer
32 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
37 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
35 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
40 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
76 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$ ...
1
vote
0answers
28 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 ...