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)

2
votes
0answers
18 views

Departure from uniformity in a continuous (time) distribution

I know how to quantify the departure from uniformity ( or a uniform distribution) for discrete distributions. Assume you have a distribution set of P: ...
1
vote
0answers
16 views

Sequential information discovery in minimum number of steps when some items have information about other items

There are N items, say three: call them A B and C. For each item, there is an associated bit (0 or 1) and there is a prior probability that the bit is 1, call them p(A), p(B) and p(C). There is some ...
0
votes
0answers
30 views

Mutual Information: Are these two equations equal?

I'm working with Multivariate Mutual Information (MMI), specifically with three variables $(X,Y,Z)$, applied to RNA sequences. The MMI equation that I use for three variables is based on entropy ...
0
votes
1answer
27 views

Partition-based entropy of a sequence

The entropy $H$ of a discrete random variable $X$ is defined by $$H(X)=E[I(X)]=\sum_xP(x)I(x)=\sum_xP(x)\log P(x)^{-1}$$ where $x$ are the possible values of $X$, $P(x)$ is the probability of $x$, ...
0
votes
1answer
22 views

How to calculate entropy from a set of samples?

entropy (information content) is defined as: $$ H(X) = \sum_{i} {\mathrm{P}(x_i)\,\mathrm{I}(x_i)} = -\sum_{i} {\mathrm{P}(x_i) \log_b \mathrm{P}(x_i)} $$ This allows to calculate the entropy of a ...
1
vote
0answers
35 views

Derivative of the Kullback Leibler Divergence

If: $$ H (\pi(t)|\mu(t+1)) = \sum^n_{i=1}\pi_i(t) \log \frac{\pi_i(t)}{\mu_i(t+1)} $$ How do I interpret: $\nabla H(\pi(t) | \mu(t+1) )$? Would it be the vector: $$ \left ( \frac{\partial ...
0
votes
1answer
41 views

Noiseless Channel Capacity

Nyquist theorem proves that a signal of $B$ bandwidth, in order to be sampled correctly thus avoid aliasing, has to be sampled with a $f_c > = 2B$. When it comes to calculating the capacity of a ...
1
vote
1answer
42 views

Is conditional entropy ever taken to be a random variable?

In probability theory, the conditional expectation $E(X|Y)$ and variance $V(X|Y)$ er usually taken to be random variables, st. the value of $E(X|Y)$ depends on what value $Y$ ends up taking. I've ...
1
vote
1answer
22 views

Finding C from $\Delta C$

Define: $\Delta A(t) = A(t+1)-A(t)$ and let $$ \Delta C = \sum^{T-1}_{t=0} [~~H(\pi(t+1)~|~\mu(t+1))~~ - ~~H(\pi(t)~|~\mu(t+1))~~] $$ Where $H (\pi(t+1)|\mu(t+1)) = \sum^n_{i=1}\pi_i(t) \log ...
1
vote
0answers
56 views

Trellis Diagram - Viterbi decoding

I have the trellis diagram below which is used as Viterbi decoder. The coded message is the sequence of bits at the bottom of the picture. My question is this. t=0:The decoder starts from state 00 ...
1
vote
0answers
25 views

Vector Differential in specific form

for the operator: $\Delta A(t) = A(t+1)-A(t)$, let : $$ \Delta C = \sum^{T-1}_{t=0} [~~H(\pi(t+1)~|~\mu(t+1))~~ - ~~H(\pi(t)~|~\mu(t+1))~~] $$ Where $H (\pi(t+1)|\mu(t+1)) = \sum^n_{i=1}\pi_i(t) \log ...
0
votes
1answer
17 views

Shannon-Hartley theorem for other bases

The Shannon-Hartley theorem is given with terms referring to a binary signal. What if a channel does not transmit via binary, but instead in another system, such as ternary or base-4?
0
votes
2answers
17 views

Information limit for digital signal

Wikipedia give the Shannon-Hartley theorem as: $$ C = B \log_2 \left(1+ \frac{S}{N}\right) $$ Where $S/N$ is the signal to noise ratio, with each quantity measured in watts. What if the channel is ...
0
votes
1answer
35 views

Kullback - Leibler Divergence and the Triangle Inequality

The KL Divergence, or relative entropy for two probability distributions $p,q$ on $\Omega$ is defined as: $$ H(p|q) = \int_{\Omega} p(\omega) \log \frac{p(\omega)}{q(\omega)} d\omega $$ This is a ...
0
votes
1answer
22 views

A doubt regarding KL-divergence for estimating a distribution

Suppose given a probability distribution $q$. I'm trying to estimate it by $p$ such that the KL-divergence between $p$ and $q$ is minimized. Now which one of the two: $KL(p||q)$, $KL(q||p)$ should be ...
1
vote
0answers
25 views

Mutual information as a fraction of entropy?

Suppose I have two (discrete) random variables $(X,Y)$ with some joint distribution $P$. The mutual information $I(X;Y)$ is informally defined as the reduction is the remaining entropy in $X$ once the ...
1
vote
0answers
18 views

Function of Determinant convexity via information theoretic methods

In Cover and Thomas, "Elements of Information Theory", second edition, I encountered this question: Let $K$ and $K_0$ be symmetric positive definite matrices of same size (s.p.d.m). Then show that ...
1
vote
3answers
59 views

Combining Markov chains

If the following Markov chain relations hold: $$X \rightarrow Y \rightarrow Z,$$ $$Z \rightarrow W \rightarrow Y,$$ can we combine them to have $$X \rightarrow Y \rightarrow Z \rightarrow W ...
0
votes
1answer
52 views

Campbell's Source coding

In the usual Shannon's source coding problem one chooses code words that minimize $E[L]:=\sum_i p_il_i$ over all $L=(l_1,l_2, \dots), l_i\ge 0$ such that $\sum_i e^{-l_i}\le 1$ (Kraft inequality), ...
0
votes
1answer
45 views

What modification is this of the notion of Renyi divergence?

Given two probability distributions $P$ and $Q$ over the same outcome and event space (assume finite if needed) one defines their Renyi divergence as $D_\alpha (P \vert \vert Q) = \frac{1}{\alpha -1} ...
3
votes
1answer
47 views

Fano's Inequality Proof

For an information theory class, I am studying the proof for Fano's inequality, i.e.: $H(P_e) + P_elog(|X|) \geq H(X|\hat{X}) \geq H(X|Y)$ Where $H(X)$ is the entropy of the random variable X ...
1
vote
1answer
22 views

Four Variable Data Processing Inequality

While Solving problems in "Elements of Information Theory" by Cover and Thomas, I found this problem in the last chapter. Let $X \to Y \to (Z,W)$ be a Markov chain i.e. $p(x,y,z,w)= ...
0
votes
0answers
16 views

Optimal decision for sampling a distribution.

I was wondering which probability distribution is best sampled with $\pm\alpha^n, n\in\{1,2,\cdots\}$ for various values of alpha. Sampling means to pick the one which is closest, store the sign and ...
1
vote
0answers
40 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
28 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
42 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
36 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
52 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 ...
-1
votes
1answer
23 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
40 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? ...
-1
votes
1answer
70 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
22 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
100 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
29 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
68 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
10 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
41 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
49 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
32 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
42 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
66 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
32 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
38 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
40 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
19 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
27 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 ...