# 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,121 questions
Filter by
Sorted by
Tagged with
13 views

### Mutual Information between $v_1$ and $v_2$ coming from the same Inverse-Wishart distribution?

Say that $\left(\begin{matrix} v_1 & c\\ c & v_2 \end{matrix}\right)$ is a bivariate covariance matrix that comes from an Inverse-Wishart distribution $W^{-1}(\Psi, \nu)$. Then what is the ...
29 views

### Inequality relating entropy to mutual information

Let $\{X_n\}$ be a sequence of independent, discrete random variables, and let $Z$ be another discrete random variable. Show that $$H(Z)\geq\sum_{i=1}^\infty I(X_i;Z)$$ where $H$ is the entropy and $I$...
1 vote
57 views

41 views

### Expected number of pairs with Hamming distance $d$ for a sample of $k$ random bit strings of length $n$

Say we were to uniformly sample $k$ times from a bit string with length $n$. What is the expected number of pairs with a Hamming distance $d$? In the limit of Hamming distance 0, I realize this ...
36 views

### Stochastic Mutual Information Estimator

I am reading https://openreview.net/forum?id=ByxaUgrFvH and do not understand why they need a "complicated" derivation, because it seems to follow immediately. Problem Let $\mathbf{x}$ be a ...
1 vote
45 views

### Chemical Entropy vs. Mathematical Entropy

In high school physics and chemistry classes, we were told that entropy is a measure of disorder in a physical system. For example, molecules that are relatively stationary correspond to a lower ...
124 views

### How can one compute schema quality using information theory?

Definitions Password Schemas Definition (Taken from Human-Usable Password Schemas: Beyond Information-Theoretic Security): Password schemas are deterministic functions which map challenges (typically ...
127 views

21 views

### Entropy of convex combination of dirac points are positive

Let $X$ be a compact metric space. $T:X \to X$ be a homeomorphism. Assume that the measure$\mu=\lambda \delta_{a}+(1-\lambda)\delta_{b},$ where $\delta$ is the Dirac measure and $0<\lambda<1.$ ...
37 views

27 views

### Is there an efficient algorithm to verify that a finite binary code is uniquely decodeable?

Is there an efficient algorithm to verify that a finite binary code is uniquely decodeable? Say we have some finite alphabet of symbols $\mathcal{A}$ and some encoding for each symbol $C$. What is the ...
103 views

### What is the role of the logarithm in Shannon's entropy?

I am a layman interested in understanding why the foundation of Shannon's entropy is logarithmic. To that end I've read the answers here, at the Cross Validated Stack, but I'm not technical enough to ...
41 views

### Kullback-Leibler divergence Information Theory

I have density functions $f_{X,Y}(x,y)=f_X(x)f_Y(y)$ and $g_{X,Y}(x,y)=g_X(x)g_Y(y)$. I am supposed to show that I must have $KL(f_{X,Y} || g_{X,Y})=KL(f_{X} || g_{X})+KL(f_{Y} || g_{Y})$. I don't not ...
17 views

### Proof of the information bottleneck equations

In The Information Bottleneck Method, the third term of Eq.(31) is $P_{t+1}(y|\tilde{x})=\sum_yp(y|x)p_t(x|\tilde{x})$, which minimizes the term $D_{KL}[p(y|x)|p(y|\tilde{x})]_{<p(x,\tilde{x})>}$...
21 views

### Combining Shannon Entropy with a notion of bit-rate

If you have a sequence of samples from a finite alphabet where the $i$th symbol has probability $p_i$ the shannon entropy of each symbol $H = \sum_i p_i \log_2(p_i)$. That is each symbol carries $H$ ...
67 views

### Dice roll, conditional expectation and Information.

I am currently trying to learn about conditional expectation and I have the following textbook problem I try to solve. Problem Fred rolls a die and observes the outcome. He tells Gretel and Hansel if ...
30 views

### Mutual Information of Vectors with Large Inner Product

If we have a joint distribution of two (complex) vectors $x,y\in \mathbb{C}^d$ of norm $1$ such that their inner product $\langle x|y\rangle$ is $1-\epsilon$, can we lower bound the mutual information ...
69 views

### How do I quantify the amount of information in the following expression?

Suppose that $N = \mbox{factorial}(9999999999)$. The number $N$ is mindbogglingly huge and, yet, can be represented very neatly and compactly as $\mbox{factorial}(9999999999)$. I have two questions: ...
1 vote
56 views

### Identify a ternary change using the least amount of memory

Suppose we have an $n$-tuple of ternary values (0, 1, or 2). At most one of the elements will change its value. What is the least amount of information we need to remember in advance to correctly ...
389 views

1 vote
36 views

### In information entropy, how do nats relate to any representation of states?

Calculating the information entropy depends on taking the logarithms of probabilities in some base. If I use base 2, then the entropy is in "bits". The measure of bits is close to the ...
29 views

### Decay rates of eigenvalues of Hilbert-Schmidt integral operator

Let $\Omega \subset \mathbb{R}^n$ be bounded. Suppose we have an integral kernel $K: \Omega^2\to \Omega$ with $\int_{\mathbb{R}^n}\int_{\mathbb{R}^n}|K(x,y)|^2dxdy < \infty$. We know that the ...
55 views

### Algorithim to choose comparison pairs for topological sorting

I'm trying to find or create an algorithm to roughly sort arbitrary objects using pairwise comparison where the only concern is minimizing the number of comparisons. So my question is essentially is ...
18 views

### Information Gain Using Gini

How do you calculate Information Gain Using Gini? The set is a classification between watching a series or a movie: For choosing to watch a Series, I have: (0, 0, 0, 1) (0, 0, 0, 1) (0, 0, 1, 1) (1, 1,...
31 views

### What is information in the context of entropy? [duplicate]

I am trying to wrap my head around the concept of information in the context of entropy. Let me first introduce some things to make it clear what I mean with the terms I am using. Entropy: : https:/...
30 views

### Information gain calculation for decision tree when choosing root node

I want to know if my calculation is wrong or correct, because i got a different result when i use an online calculator. Here is the dataset: ...
1 vote