# 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.

2,262 questions
Filter by
Sorted by
Tagged with
41 views

### Validity of a proof of the Fisher Information Data Processing inequality, $I(f(X)) \le I(X)$.

I'm trying to prove that taking a function of a random variable never creates a better estimator (in the terms of Fisher information) than using the original random variable directly. I have a proof (...
• 4,326
31 views

• 21
36 views

### Why does the common information $C\equiv X\wedge Y$ give $H(X)=H(CX)$?

Given two random variables $X,Y$, their common information $X\wedge Y$ is defined in (Wolf and Wultschleger 2004) as the random variable $X\wedge Y=f_X(X)=f_Y(Y)$ constructed as follows: Let $G$ be ...
• 6,113
62 views

### Finding efficient encoding scheme for combinatorial problem

An online store is selling rings, necklaces, bracelets, and pendants. Suppose there are $m$ different types of each of these four commodities. A typical customer wants to buy one item of each of the ...
• 305
42 views

### Finding binary vectors with guaranteed Hamming distance

Let $n > 10^6$ be a large square. Bob knows $n$ pairs $(x_1, y_1),(x_2, y_2), \ldots ,(x_n, y_n)$ of binary vectors. Each vector $x_i$ and $y_i$ is length $n$ and for each $i$, the Hamming distance ...
• 305
82 views

### KL divergence for distribution representing sums of iid random variables

Sorry if my description is inaccurate, I hope it's understandable. Given $X_1,...,X_n$, a series of $n$ iid Bernoulli RVs with means $p$, and a similar series $Y_1,...,Y_n$ with means $q$, we know ...
• 47
1 vote
17 views

### Min-Sum Belief Propagation not working on a chain model with equal unary potentials

Given is a chain factor graph as presented in the image below with the following properties: Each node can take values 0 or 1 All unary potentials are equal (e.g. $U(a) = 0$ for every node) All ...
77 views

### How is this formula on Stirling's approximation derived?

The following paragraph (equation 1.41) is from the book "Information theory, Inference, and Learning Algorithms" I don't quite understand how the first approximation in 1.41 is derived. Can ...
• 131
13 views

### How do you find the exact minimum descriptive length?

My friend asked me how to find the exact minimum dimensionality of a manifold that can embed a dataset, in a rigorous lossless way. I'm pretty sure this is impossible, but I wanted to ask you guys &...
• 317
55 views

### How many unique solutions are there to the coin-weighing problem from Cover and Thomas?

The coin weighing problem in question: Suppose that one has $n$ coins, among which there may or may not be one counterfeit coin. If there is a counterfeit coin, it may be either heavier or lighter ...
• 1,105
34 views

### Joint entropy of sum and difference of random variables

Let $X$~$U\left\{1,8 \right\}$ , $Y$~ $\begin{pmatrix} 1 & 2 & 3 & \dots \\ \frac{1}{2} & \frac{1}{4} & \frac{1}{8} & \dots \end{pmatrix}$. I need to calculate $H(X+Y,X-Y)$. ...
• 367
1 vote
38 views

• 1,596
55 views

### Maximum value of $-\sum_{i=1}^{n}p_i \log_2(p_i)$ for $\sum_{i=1}^{n}p_i=P<1$ [duplicate]

It is known that the entropy $$H=-\sum_{i=1}^{n}p_i \log_2(p_i)$$ Is maximized when $p_i=1/n$. However, this is under the assumption that $\sum_{i=1}^{n}p_i=1$. Does this still hold true if the sum of ...
• 979
25 views

### Is the average Shannon entropy of a process equal to that of its time-reversed process?

Consider an infinite sequence of characters $\ldots, x_{t-1}, x_t, x_{t+1}, \ldots$ which each belong to a finite alphabet and are generated according to an arbitrary stochastic process. For example, ...
1 vote
36 views

### Directed Acyclic Graph Complexity Measures

I have many (millions) of collider-less directed acyclic graphs (DAGs) (they're actually causal graphs, but that's unimportant for this question) I am using to model a process, and I would like to ...
• 9,879
120 views

### Information Geometry and Divergences

I've been reading Amari's Information Geometry book and, on page $10$ he defines what a divergence is. It goes as follows: Let us consider two points $P$ and $Q$ in a manifold $M$, of which ...
1 vote
40 views

• 143
1 vote
48 views

### Rewriting linear code representation (coding theory).

Linear codes: In coding theory, we have a linear codes where a message is passed through an encoder to get a code. A linear code is the situation where a message $u=(u_1,\dots,u_k)\in\{0,1\}^k$ (...
• 484
65 views

### Could you help me prove this information theory inequality

Greetings and many thanks in advance. Let $h(p)=-p\log_2 p-\bar{p}\log_2 \bar{p}$ be the binary entropy function, where $\bar{p}=1-p$. Prove that $$(1-h(p))h(x)-h(p*x)+h(p)\geq 0,\forall x\in [0,1],$$ ...
802 views

### Is there a chain rule for Sibson's mutual information?

Mutual Information satisfies the chain rule: $$I(X,Y;Z) = I(X;Z) + I(Y;Z|X).$$ The chain rule is useful and the proof is simply linearity of expectations. Sometimes we want something stronger than ...
• 800
37 views

• 2,862
33 views

### Entropy calculation of splitted experiment

Let's say, that we have a set of probabilities $X = \{0.4, 0.3, 0.2, 0.1\}$, each for some event of an experiment. The entropy for this set is equal to $H(X) = 1.2798$. Now, if we divide $X$ into two ...
• 149
31 views

### Optimal messages's probability problem

https://i.stack.imgur.com/gb9SD.png Translation: Set of two messages m1, m2 is given. Those messages are coded as follows: C(m1) = 01, C(m2) = 101 Find a probabilities those messages in such a way, ...
43 views

### Maximum Entropy with Inequality Constraints

It is well known that, maximizing the entropy of the joint distribution $P(x_1,...,x_n)$ of a random vector $(X_1,...,X_n)$ subject to equality constraints for the mean vector ($\mu$) and the variance ...
• 2,796
22 views

### Rewriting channel transition probability

I have a channel transition probability for the Mixture-of-Experts (MoE) model in machine learning: \begin{align*} &\mathbb{P}\Big[y_i\Big|\langle X_i,\beta^{(1)}\rangle,\dots,\langle X_i,\beta^{(...
• 484
7 views

### Derivation of the analytical solution for conditional mutual information

I am aware of the derivation of the mutual information's closed form solution when data is (multivariate-)Gaussian from an existing post and Wikipedia. And some academic papers say that conditional ...
• 155
24 views

### Finding the rate distortion function

Let $\mathcal{X}=\{0,1,...,k-1\}=\mathcal{\hat{X}}$ for $k\geq 3$ and let $X$ be uniformly distributed over the source alphabet. Consider a distortion function given by \begin{align*} d(x,\hat{x}) = \...
31 views

### Maximum Expected Long Term Utility.

I have the following question in Dynamic Games where the first player completely knows the state over all the period $T$ and tries to send signals to the second player (second player only knows the ...
46 views

• 141
43 views

### Upper bound on the mutual information for a mixture distribution

Assume we have two random variables $X$ and $Y$. Suppose further that $X$ is generated from a mixture distribution $P$ with $n$ components $P_i$ with corresponding weights $w_1,\dots,w_n$. Is it the ...
• 101