Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [information-theory]

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.

1
vote
0answers
18 views

Multivariate Conditional Entropy as a test of correlation between random variables

I use the word columns to mean the data from which a random variable can be estimated. It is a sample of a random variable. I am working with $N$ columns of weakly correlated data. Furthermore, I ...
0
votes
0answers
20 views

Mutual information with 4 variables [on hold]

I am given the following formula which I understand: I(z,c) = I(z,x)- I(z,x|c) + I(z,c|x). However, now I would like to get an expression for I(z,c) given an extra variable y, so something like: I(z,...
2
votes
2answers
56 views

Information theory riddle about finding a gift in one of 16 boxes

There are $16$ boxes, one of which contains the gift. We have $7$ persons, who can help us by answering on any yes/no question, but one of the persons is a liar, he may not tell us the truth. We have ...
3
votes
1answer
39 views

Optimal code for simple game

Setup: Alice and Bob are playing a cooperative game. Alice chooses a number $y \in \{1, 2, 3, 4\}$ uniformly at random. Bob doesn't observe $y$; his goal is to guess $y$. Alice can send Bob a message $...
-2
votes
0answers
17 views

Proof Markov Chain [closed]

Can you help me write the proof, please ? Thanks
1
vote
0answers
17 views

Proof $I(X;Y|Z) = H(Y|Z) - H(Y|X,Z)$

$I(X;Y|Z) = H(Y|Z) - H(Y|X,Z)$ $= \sum_{x,y,z}p(x,y,z) \log \frac{p(x,y|z)}{p(x|z) p(y|z)}$ $= \sum_{x,y,z} p(x,y,z) \log p(x,y|z) - \sum_{x,y,z} p(x,y,z) \log p(x|z) - \sum_{x,y,z} p(x,y,z) \log p(y|...
0
votes
1answer
17 views

Proof $I(X;X|Z)= H(X|Z)$

$I(X;X|Z)= H(X|Z)$ Proof $I(X;X|Z) = \sum_{x,z}p(x,z) \log \frac{p(x,x|z)}{p(x|z)p(x|z)}$ since $p(x,x|z)= p(x|z)$ Then $I(X;X|Z) = \sum_{x,z} p(x,z) \log \frac{1}{p(x|z)}$ $= - \sum_{x,z} p(x,z)...
0
votes
1answer
12 views

Proof $ I(X;Y) = H(X) - H(X|Y) $

$I(X;Y) = H(X) - H(X|Y)$ proof $ I(X;Y)=\sum_{x,y}p(x,y) \log \frac{p(x,y)}{p(x)p(y)} $ $=\sum_{x,y}p(x,y) \log \frac{p(x|y)}{p(x)}$ $= \sum_{x,y}p(x,y) \log p(x|y) + \sum_{x,y}p(x,y) \log p(x) $ ...
1
vote
1answer
29 views

The motivation of continuous random variable mutual information by $k$'th nearest neighbour

I am reading this paper Kraskov et al, 2004, Estimating Mutual Information on estimating the mutual information of two continuous random variables based on entropy estimates from $k$-nearest neighbour ...
1
vote
1answer
27 views

Prove an inequality concerning Kullback-Leibler Divergence

For any distribution $P$ and $Q$ on $\mathcal{X}$ and any function $f:\mathcal{X} \rightarrow \mathbb{R}$, prove the following inequality: $$\mathbb{E}_{x\sim Q}[f(x)]\le \ln \mathbb{E}_{x\sim P}[\exp(...
0
votes
0answers
82 views

Why is the (undirected) remaining degree distribution symmetric in its indices?

I am trying to calculate the remaining degree distribution of an undirected graph. Let $q_{j,k}$ be defined as the joint probability distribution of the remaining degrees of the two nodes at either ...
0
votes
1answer
30 views

A mutual information equality

$x$ and $y$ are two random variables and $I(u;v)$ is the mutual information between random variables $u$ and $v$. Does the following equality hold? $$\text{argmax}_a I(y;ax)=\text{argmin}_a I(y;y-ax).$...
0
votes
0answers
30 views

Bound on KL-divergence-like quantity (with squared logarithms)

Given two discrete probability distributions over $n$ events, with $p_i$ and $q_i$ denoting the probability that the ith event occurs respectively, I am looking for an upper bound of the following ...
0
votes
0answers
27 views

How close is the expected length of Huffman coding and entropy?

If I want to use entropy as an approximation for the expected length of Huffman coding, how good is the approximation? I know the following identity: $H(X)\leq L(X)< H(X)+1\ $ where expected ...
0
votes
1answer
20 views

Multivariate conditional entropy

I would like to take data columns and compute the multivariate conditional entropy. For instance, suppose I have columns $A, B, C D, E$ and I want to compute the conditional entropy $H(E | A,B,C,D)$. ...
1
vote
1answer
30 views

Simple Expression Related to Mutual Information

One way to define the mutual information is $I(X;Y) = H(X) - H(X|Y)$ I have found it useful to look the related quantity $?(X;Y=y) = H(X) - H(X|Y=y)$ That is, we look at how much the entropy of $X$...
0
votes
2answers
36 views

Finding a binary prefix code provided lengths

Firstly, I am relatively new to this particular forum, and I usually use Stack exchange (maths). I do not know if this is the right place to post so please be aware in case, I should ask this question ...
1
vote
2answers
49 views

Entropy of continuous and discrete random variables

If N is a continuous random variable and X a discrete random variable. How can I calculate H(X|Y) if Y=X+N? N is a triangular distribution between -1 and 1 X can take the values ​​+-0.5 with equal ...
1
vote
0answers
27 views

How can I prove the asymptotic equipartition property (AEP) for an identically distributed markov chain?

$ $ Hi, everyone. I am recently reading the lecture note of EE376a : Information Theory course from Stanford University. This note introduces that we can prove the Asymptotic Equipartition Property (...
2
votes
0answers
18 views

Restricting an MDS code to a subset of coordinates

If we have an $(n,k)$ MDS code and we take a subset of coordinates in a set say $J$, where $|J| > k$. If $c$ is a codeword in the original MDS code let $c_J$ denote its projection on the set $J$. ...
0
votes
0answers
17 views

build convolutional encoder using generator matrix

can I build convolutional encoder using given generator matrix or generator polynomials? If it's possible, is there any algorithm for that?
6
votes
4answers
108 views

Entropy Lower Bound in Terms of $\ell_2$ norm

Define $$ \begin{align} H(p_1, \dots, p_n) &= \sum_{i=1}^n p_i\log1/p_i\\ &=\log n+\sum_{i=1}^n\sum_{k=2}^\infty (-1)^{k + 1} n^{k - 1} \frac{(p_i - 1/n)^k}{k (k - 1)}, \end{align} $$ where $...
0
votes
1answer
35 views

Is Kullback-Leibler Divergennce not equal to Relative Entropy?

In many books, Kullback-Leibler Divergence is equal to Relative Entropy. $$ D_{kl}(u,v) = \sum_{i=1}^n(u_ilog(u_i/v_i). $$ However, I find in the book, Convex Optimization (Stephen Boyd) page 90, ...
1
vote
0answers
21 views

How do we know $X$ and $Z$ are independent in Gaussian Channel

$H(Y|X) = H(X+Z|X) = H(Z|X) = H(Z)$ I am wondering why $X$ and $Z$ are independent. $X$ is input and $Z$ is noise. How do I prove it??
2
votes
2answers
30 views

Should conditional entropy always be negative?

Recently I am studying basic of information theory and I found an awkward inequality while I am postulating following equalities using definitions of the entropy and Kullbeck-Leibler divergence. ...
0
votes
0answers
23 views

Information theory - Intuition of the formula of code rate

I'm reading Elements of Information Theory - 2nd edition (2006). In the book, at page 195, they give the formula: The rate $R$ of an $(M, n)$ code is $\hspace{5.0cm} R = \frac{\log M}{n}$ bits ...
1
vote
0answers
43 views

Mutual information: Proving $I(X;Y)=\underset{r(x),s(y)}{\min}D_{KL}[p(x,y)\mid\mid r(x)\cdot s(y)]$

I was asked to show that for two discrete RVs $X,Y$ with joint distribution $p\left(x,y\right)$ and marginal distributions $p\left(x\right)$ and $p\left(y\right)$, it holds that for any two ...
0
votes
0answers
26 views

Signal Processing and the Fourier Transform

I'm working on this problem where I need to find the Fourier Transform of $$ f(t)\approx f_P=\sum_{k\epsilon\ \mathbb{Z}}[\sum_{n=-N}^{N}\widehat {(f_{k})}[n]e^{2\pi int/T}]X_{[kT,(k+1)T]}(t) $$ ...
0
votes
0answers
22 views

Idempotents of binary cyclic codes

Let $e(x)$ be an idempotent in $R_n = \mathbb{F}_{2}[x]/\langle x^n - 1 \rangle$, where $n$ is odd. Let $\alpha$ be a primitive $n^{th}$ root ofunity in some extension of $\mathbb{F}_2$. I'm trying to ...
0
votes
1answer
22 views

Two-look Gaussian channel

I'm reading through a solution from Elements of Information Theory by Thomas A. Cover. This is the two-look Gaussian channel, where the input to the channel is $X$ and the output is $(Y_1, Y_2)$. $...
0
votes
0answers
26 views

Derivation of Sanov's theorem for continuous variables

Where can I find a derivation of Sanov's theorem for continuous variables? I am familiar with the derivation for discrete variables. I am looking hopefully for something similarly intuitive.
0
votes
1answer
24 views

$(2)-$ cyclotomic cosets modulo a prime

Let $p$ be an odd prime. Assume $2$ is a quadratic residue modulo $p$. Is it true that the $(2)-$ cyclotomic cosets modulo $p$ are ${\{0}\}, {\{Q}\}, {\{N}\}$, where $Q$ are the quadratic residues ...
1
vote
1answer
32 views

Bound on code: $A(n,d) \leq 2A(n-1,d)$

Note: We are talking about binary codes. Definition 1: For integers $1 ≤ d ≤ n$, a code $C$ is an $(n, d)$-code if it has length $n$ and minimum distance $d_H (C) ≥ d$. An $(n, M, d)$-code is an $(n,...
2
votes
1answer
34 views

Why PCA is a suboptimal of maximization of mutual information

"A common theme in linear compression and feature extraction is to map a high dimensional vector $x$ to a lower dimensional vector $y=Wx$ such that the information in the vector $x$ is maximally ...
6
votes
2answers
79 views

How to calculate mutual information

I study about Mutual Information but I confuse about that. I study in this paper that mutual information is:$$I(x,y)=\iint p(x,y)\log\frac{p(x,y)}{p(x)p(y)}\,\mathrm dx\mathrm dy,$$ where $x, y$ are ...
0
votes
1answer
42 views

Showing that if the KL divergence between two multivariate Normal distributions is zero then their covariances and means are equal

We have two, k-dimensional multivariate normal distributions $\mathcal{N}_0(\mu_0,\Sigma_0)$ and $\mathcal{N}_1(\mu_1,\Sigma_1)$ with means $\mu_0$ and $\mu_1$ and covariances $\Sigma_0$ and $\Sigma_1$...
1
vote
1answer
49 views

Confused by Kullback-Leibler on conditional probability distributions

I understand the Kullback-Leibler divergence well enough when it comes to a probability distribution over a single variable. However, I'm currently trying to teach myself variational methods and the ...
1
vote
1answer
25 views

Constructing the binary Golay code

I'm reading up about the binary Golay code of length $23$. I know it's a cyclic code and I also know it's a quadratic residue code. I've read that we can consider the linear code over $\mathbb{F}_2$ ...
0
votes
1answer
35 views

In Information Theory, what is the lower bound that minimizes the value of $2^{l_x}$

Here is the question from my notes: Suppose we wish to find a decipherable code that minimizes the expected value of $2^{l_x}$ for a probability distribution $p(x)$. Establish the lower bound $$E\big(...
0
votes
0answers
31 views

Entropy of intervening variable in Markov Chain

Let's assume we are given discrete random variables $X$, $Z$, with some nonzero mutual information $I[X,Z] > 0$. I would like to understand the minimum entropy of variables $Y$ such that $X \...
1
vote
2answers
41 views

Hamming code of length $8$ self dual

I'm reading a paper by N.J.A Sloane on self dual codes, and he introduces the binary Hamming code of length $8$ with generator matrix $$ G = \begin{bmatrix} 1&1&1&1&1&1&1&...
3
votes
1answer
69 views

Characterisation of the rate distortion function: issue with functional derivative

In Elements of Information Theory, I can't figure out how the functional derivative $ \frac{\delta J}{\delta q(\hat{x}|x)} $ for $ J(q) = \sum_x \sum_{\hat{x}} p(x)q(\hat{x}|x)\log{\frac{q(\hat{x}|x)}{...
0
votes
1answer
20 views

Smallest set (typical set)

Given the following table of sequences, I'm trying to find the smallest set with probability $p = 0.9$. \ The smallest set consists of some sequences from the table, which probability (column 3) ...
1
vote
1answer
39 views

Number of bits in 0

I have found a few sources which have said that the number of bits in a binary number is equal to $floor(log_2(n))+1$. But this doesn't seem to work for binary values less than 1. I would expect ...
0
votes
2answers
38 views

Proof that $H(X) \leq \log(|A|)$ (Shannon entropy)

The full question states: "Show that $$H(X) \leq \log(|A|)$$ with equality if and only if $P_X$ is uniform. Hint: use the Gibbs or log-sum inequality " I used "$A$" as the alphabet in here. My ...
0
votes
0answers
53 views

Is there a way to reverse the Chinese Remainder Theorem? What extra information do we need?

Dear math stackexchange community, Given a list of numbers < N, after generating the Chinese Remainder, is there a way to get back to the same list of numbers? Example: N = 100 List of numbers =...
0
votes
0answers
44 views

Comparison of two Huffman codes:

A set of eight messages with probabilities of $0.2$, $0.15$, $0.15$, $0.1$, $0.1$, $0.1$, $0.1$, and $0.1$ are encoded into a ternary Huffman code. One set of Huffman codewords are {$2, 01, 02, 10, ...
0
votes
2answers
45 views

Entropy of an infinite sequence?

Does an infinite sequence always have finite entropy? For example, doesn't $a_n=n$, the sequence of non-negative integers, have very low entropy? It feels like all "well-defined" sequences ought to ...
0
votes
0answers
54 views

Information theory - Intuition of channel capacity

Question As stated in Elements of Information theory, given $p(y|x)$, the Information channel capacity formula is $C = \max_{p(x)} I(X; Y)$ where $X, Y$ are input and output symbols, $p(x)$ is the ...
0
votes
1answer
33 views

The intuition of fair odds (information theory)

I'm reading about gambling in Elements of Information theory. As stated in the book, given that the gambler bets $o_i$-for-$1$ on horse $i$, Fair odds (w.r.t some distribution): the odds is fair if $\...