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
0
votes
1
answer
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
0
votes
0
answers
31
views
Out-of-distribution Slepian-Wolf coding
Background
The standard way in which source coding theorem is formulated is
$\forall_{D} \forall_{\epsilon>0} \exists_N$ exists a code that encodes N i.i.d. variables with distribution $D$ in $N(H(...
- 101
2
votes
0
answers
31
views
Interpreting Gaussian measurements in terms of information theory
I have a quantity that I want to measure, and I have obtained three sets of measurements A, B, and C, each represented by their mean $\mu_A$, $\mu_B$, $\mu_C$, and standard deviation $\sigma_A$, $\...
- 21
2
votes
2
answers
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
2
votes
1
answer
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
2
votes
1
answer
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
2
votes
2
answers
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
0
answers
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 ...
3
votes
2
answers
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
0
votes
0
answers
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
2
votes
1
answer
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
0
votes
0
answers
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
0
answers
38
views
Generalization of Shannon's Reconstruction Theorem
Suppose $f$ is of moderate decrease and that its Fourier transform $\hat{f}$ is supported in $I=[-1/2, 1/2]$, $\lambda > 1$. Show that:
$$
f(x)=\sum_{n=-\infty}^{\infty}\frac{1}{\lambda}f(\frac{n}{\...
- 45
0
votes
0
answers
78
views
Prove KL Divergence $\displaystyle \int_{\chi}p(\textbf x) \text{log}\frac{p(\textbf x)}{q\left(\textbf x, V\right)}d\textbf x$ is Convex w.r.t. V
Problem: I have two kernel density estimates of distributions, call these $p(\textbf x)=\displaystyle \frac{1}{|X|} \sum_{\textbf x_i \in X} K_H(\textbf{x}-\textbf{x}_i)$ and $q(\textbf x)=\frac{1}{|W ...
- 115
2
votes
0
answers
26
views
Upper bound on relative entropy variance
Consider a finite alphabet $\mathcal{X}$ and probability distributions $p(\mathrm{X})$ and $q(\mathrm{X})$ respectively. The relative entropy variance is defined as
$$V(p \| q):=\operatorname{Var}\...
- 1,596
0
votes
2
answers
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
0
votes
0
answers
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, ...
- 203
1
vote
0
answers
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
3
votes
1
answer
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 ...
- 408
1
vote
0
answers
40
views
"A New Outlook on Shannon’s Information Measures" abstract clarification
I was curious about the paper A New Outlook on Shannon’s Information Measures by Yeung. However, I don't really understand the abstract
Let. $X_i,i = 1,. . .,n$, be discrete random variables, and
$\...
- 1,154
1
vote
0
answers
35
views
Wallis' derivation of information entropy
In Wallis' combinatorial derivation of the information entropy (see here or wiki, the text is copied down below), I don't understand what the information $I$ is in
If it happens to conform to the ...
- 1,154
0
votes
0
answers
14
views
Optimal variable-time sampling of a real-time data stream
Crossposted from stats stackexchange
Here's a signal processing/information theory problem that I've encountered in a software engineering context:
Say I have a logging utility in my application that ...
- 1,105
1
vote
0
answers
34
views
Why is relative entropy negative in this computation?
I am running some tests using relative entropy on physical systems in equilibrium, and I am seeing some strange results. I wonder if this is an issue in Mathematica itself, but here goes.
I have two ...
- 287
2
votes
0
answers
36
views
Under what conditions is the $f$-divergence a distance?
It is well known that the total variation is a distance, whereas the KL-divergence is not. I am wondering under what conditions on $f$, the induced $f$-divergence is a distance? Or consider a weaker ...
- 375
0
votes
0
answers
41
views
Beginning algorithmic information theory
I was wondering if the stack-exchange community could provide me with some resources for beginning studies in algorithmic information theory, with a focus on how it intersects with computability, ...
- 91
0
votes
1
answer
27
views
Number of bits from entropy calculations
To calculate the entropy for a an event of a uniform distribution of this kind
Events: "red" or "blue"
Probabilities: P(red) = 0.5, P(blue) = 0.5
We just do $e = -\log_2(0.5)$
In ...
- 39
2
votes
1
answer
50
views
How to show this equivalence between two definitions of channel capacity
Let us consider a random variable $X$ on alphabet $\mathcal{X}$ with probability distribution $p_X$ and a conditional probability distribution (channel) $W_{Y|X}$ that generates a random variable $Y$ ...
- 1,596
0
votes
0
answers
59
views
Textbook on information theory with solutions to exercises for self-study
Currently, I'm self-studying information theory through an online course taught by R. W. Yeung. The goal is to eventually understand and do research on algorithmic (Kolmogorov) complexity and the MDL ...
- 5,910
0
votes
0
answers
29
views
Unique minimum of Kullback-Leibler-Information
The K-L-information, for the 'true' density $g$ and candidate approximating densities $\{ f( \cdot | \theta) \}_{\theta \in \Theta} $, is defined as $ I(f(\cdot | \theta),g) := \mathbb{E}_{X \sim g} [...
- 143
1
vote
1
answer
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
3
votes
0
answers
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],$$
...
- 121
8
votes
1
answer
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
0
votes
1
answer
37
views
Finding a continuous distribution that maximizes differential entropy
Continuous distribution (known mean $\mu$ and variance $\sigma^2$) - Maximum Entropy:
Given mean $\mu$ and variance $\sigma^2$, what is the continuous distribution that maximizes differential entropy $...
- 1
2
votes
1
answer
50
views
How is it the Kullback-Leibler divergence is always non-negative but differential entropy can be positive or negative?
According to wikipedia, we have $$
D_{KL}(f ||g ) \geq 0
$$
always, but if $f$ is the pdf of a random variable $X$ and $g$ is the density of the un-normalized Lebesgue measure i.e. the constant ...
- 2,892
3
votes
2
answers
94
views
Upper Bounding the Discrete Entropy by the Expectation
Let $\mathcal P$ be the set of probability mass functions (pmfs) on $\mathbb Z_{>0}$, i.e. for $p=(p(x))_{x\in\mathbb Z_{>0}}\in\mathcal P$ we have $p\ge 0$ and $\sum_{x=1}^\infty p(x)=1$.
Let $...
- 2,862
0
votes
1
answer
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
0
votes
1
answer
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, ...
- 1
0
votes
1
answer
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
0
votes
0
answers
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
0
votes
0
answers
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
0
votes
1
answer
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}) =
\...
2
votes
0
answers
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 ...
- 31
0
votes
1
answer
46
views
Solve an inequality involving entropy of random variable X [closed]
Im working through Elements of Information Theory and came across a question which is stumping me. The problem states Let $p(x)$ be a probability mass function. Prove, for all $d\ge0$ that $$\text{Pr}(...
1
vote
1
answer
31
views
Is there a standard term for the log cardinality, or entropy, of the pre-image of an element with respect to a function?
Suppose $h: X \to Y$ where $X$ and $Y$ are finite, i.e., $|X|, |Y| < \infty$. Is there a standard name for the quantity:
$$S_h(y) \equiv \log_2 |\text{Pre-image}_h(y)|?$$
For example, if the ...
- 141
0
votes
1
answer
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
0
votes
0
answers
27
views
Is there a lower bound on the rate of growth of distinct algorithms (vs. description size) in a Turing-complete system?
...where a "distinct algorithm" is approximately defined as an algorithm that returns a value distinct from all others thus far.
I would think not, because you can always construct some ...
- 5,504
0
votes
0
answers
31
views
Show that the entropy with repetition is greater than the entropy without repetition
Let $n\in\mathbb Z_{>0}$ and $k\in\{0,\dots,n\}$. Consider $n$ iid Bernoulli variables $X=(X_1,\dots,X_n)\in\{0,1\}^n$ with success probability $p=k/n$ and let $Y\in\{0,1\}^n$ have the same law as $...
- 2,862
0
votes
1
answer
39
views
How do I calculate conditional entropy?
Consider the events X = {Raining, Not raining}, Y = {Cloudy, Not cloudy} and the following probabilities.
cloudy
not cloudy
raining
24/100
1/100
not raining
25/100
50/100
What is the entropy of ...
- 1
2
votes
1
answer
85
views
Complete Codes and Kraft Inequality
Li and Vitanyi define a complete code as a uniquely decodable code to which no codeword can be added while keeping it uniquely decodable. They claim that this is easily seen to be equivalent to ...
- 1,944
0
votes
0
answers
15
views
Is there a way to approximate a posterior distribution over markov matrix with restricted information capacity?
Let a matirx $M^\ast$ is a stochastic matrix with its steady state distribution $\mu(s)$ where the row of $M^\ast$ is a probability of transition to next state $s \in S$ among a finite set of states $...
- 1