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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
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 ...
user avatar
  • 1,612
2 votes
1 answer
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$...
user avatar
1 vote
1 answer
57 views

Fano's Inequality without conditioning

Suppose $X\sim P$ is a random variable taking values on an alphabet $\mathcal{A}=\{1,\dots,m\}$, such that $p:=P(1)>P(k)$ for $k\neq1$. The minimum-probability-of-error predictor of $X$ is $\hat{X}=...
user avatar
1 vote
0 answers
32 views

Example of random variable with infinite entropy

Let $X\sim P$ on $A=\{2,3,\dots\}$, where $P(k)=\frac{C}{k(\log k)^2}$ for $k\geq2$ with $C$ some normalising constant. Show that $H(X)=\infty$. My attempt so far: I have shown, by direct computation ...
user avatar
1 vote
1 answer
31 views

How to think about self-information?

Recently, I've been struggling a bit with the concept of self-information. In particular, I don't know how I'm supposed to interpret an event "having more information" than another. For ...
user avatar
  • 21
0 votes
0 answers
19 views

Confused about notation for conditional mutual information

Consider discrete random variables $Z$, $W$, $X$, and some event $\mathcal{E}$: I'm confused about the meaning of the conditional mutual information $I[ Z : W \mid X, \mathcal{E} ]$. I'm aware of the ...
user avatar
  • 29
0 votes
0 answers
17 views

Understanding problem of chain Rule for mutial information

So I have to proof $ I(X;Z|Y) = I(Z;Y|X) - I(Z;Y) + I(X;Z) $ Write mutual information in terms of entropy or use the chain rule for mutual information for an immediate proof. So I want to directly ...
user avatar
  • 103
0 votes
1 answer
34 views

Entropy: Show $ H(X|Y) + H(Y|Z) \geq H(X|Z) $

I got following exercise: Let $X$; $Y$; $Z$ be random variables. Show that $H(X \mid Y) + H(Y \mid Z) \geq H(X \mid Z)$. Hint: consider $H(X, Y \mid Z)$. We showed in the lecture that $H(X,Y \mid Z) = ...
user avatar
  • 103
0 votes
2 answers
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 ...
user avatar
3 votes
1 answer
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 ...
user avatar
1 vote
0 answers
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 ...
user avatar
3 votes
0 answers
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 ...
user avatar
3 votes
1 answer
127 views

Permuted Hamming distance

Suppose Alice wants to send a message to Bob, they agree on a $n$ letters alphabet $\Omega = \{a_1, \cdots, a_n\}$ and they both agree on a shared secret $\omega=\omega_1 \cdots \omega_m$ $\omega_i \...
user avatar
3 votes
1 answer
77 views

Relation between the entropies $h(\sum w_i f_i)$, $h(\sum w_i g_i)$, when $h(f_i) \ge h(g_i)$?

Problem $f_i, g_i$ are the probability density functions of the symmetric, unimodal distributions with the common center $c_i$. Assume the following: All $g_i$ are the translations of $g_0$ (whose ...
user avatar
  • 1,934
1 vote
1 answer
29 views

Derivation of the Conditional Maximum Entropy distribution

I am trying to derive the conditional maximum entropy distribution in the discrete case, subject to marginal and conditional empirical moments. We assume that we have access to the empirical moments, $...
user avatar
  • 532
0 votes
0 answers
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.$ ...
user avatar
  • 516
0 votes
0 answers
37 views

Trying to relate information theory basics and physics

I am a layman interested in information, and wondered how far off this idea is: Imagine 2 levels and 3 particles (in the physics sense, indistinguishable), and the different permutations: 1 arrange $$...
user avatar
  • 13
0 votes
0 answers
20 views

Visually undestanding weighed information

Background Both Shannon and Boltzmann used a common mathematical formula to define a new quantity known as entropy. The formula is: $$ {\large\displaystyle \mathrm {H} (X)=-\sum _{i=1}^{n}{\mathrm {P} ...
user avatar
  • 13
2 votes
1 answer
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 ...
user avatar
4 votes
2 answers
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 ...
user avatar
0 votes
1 answer
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 ...
user avatar
  • 1
0 votes
0 answers
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})>}$...
user avatar
0 votes
1 answer
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$ ...
user avatar
  • 1,900
0 votes
1 answer
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 1
0 votes
1 answer
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: ...
user avatar
  • 3
1 vote
1 answer
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 ...
user avatar
  • 23
10 votes
2 answers
389 views

Entropy of fair but correlated coin flips

Consider the joint distribution, $p(\xi_1,...\xi_N)$, with components defined as $\xi_i=\mathrm{sign}(x_i)$, with $(x_1,...,x_N)\sim\mathcal{N}(0,\Sigma)$ with $ \Sigma_{ij}=\delta_{ij}+(1-\delta_{ij})...
user avatar
  • 165
0 votes
0 answers
28 views

Mutual information as supermodular function under independence?

Let $Y$ be a response variable and $F$ be a set of features such that $f,x \in F$ and $S \subset F$. I am interested in the difference of mutual informations and would like to show the following ...
user avatar
  • 195
0 votes
1 answer
38 views

Is it possible for a programme to return an output with more entropy than the entropy of the programme's code itself?

Suppose that $P$ is a random variable that takes values in the space of computer programmes. So, basically, $P$ is some code (e.g. C, Python, or some theoretical one like the one used in the tapes of ...
user avatar
  • 385
1 vote
2 answers
74 views

What's the intuition behind typical sequences?

Given a probability distribution $x\mapsto p(x)$, some integer $n>0$, and some $\epsilon>0$, one defines $\epsilon$-typical sequences as those sequences $\boldsymbol{x}\equiv(x_1,...,x_n)$ $$\...
user avatar
  • 5,523
0 votes
2 answers
69 views

Why does $H(X|Y)$ equal the "missing information" of $Y$ about $X$?

I've seen mentioned in (Horodecki, Oppenheim, Winter 2005) the fact that the conditional information equals the amount of information that Alice needs to send Bob in order for him to fully reconstruct ...
user avatar
  • 5,523
5 votes
2 answers
116 views

Can a chess game be represented by less than 10N bits, where N is the number of moves (ply) in the game?

I started wondering how much information is required to encode a Chess game. Since there are 64 squares on the board, it seemed that 12 bits would be required to encode a move, 6 for the starting ...
user avatar
0 votes
1 answer
31 views

Calculation for the entropy of binomial random graph

In my classes, we found that for a graph $\mathbf{a}\in G(n,p)$, where we have labelled the graphs by their adjacency matrices, $P(\mathbf{a}) = \prod _{i<j}p^{a_{ij}}(1-p)^{(1-a_{ij})}$ We define ...
user avatar
  • 2,947
5 votes
2 answers
71 views

Entropy and probabilistic Algorithms

Recall entropy, from basic information theory: The entropy of a probability distribution $D$ on a finite set $X$ is $$H(D)=\sum_{x\in X}{p(x) \cdot \log_2{\!(1/p(x))}}$$ I was able to prove that the ...
user avatar
3 votes
0 answers
57 views

When is the Kullback–Leibler divergence continuous?

For two probability measures $P,Q$, if $P\ll Q$, then the Kullback–Leibler divergence (or the relative entropy) is defined as: $$D_{KL}(P||Q)=\int\log\bigg(\frac{dP}{dQ}\bigg)dP.$$ It is well known ...
user avatar
  • 298
3 votes
0 answers
52 views

Encoding $I(X;Y)$ into a random variable $Z$ such that $H(Z) = I(X;Y)$ and $I(X;Z) = I(Y;Z) = I(X,Y)$

Is it possible to encode the mutual information $I(X;Y)$ between two random variables $X$ and $Y$ into another random variable $Z$, such that $Z$ "contains" exactly the information that $X$ ...
user avatar
  • 171
0 votes
0 answers
27 views

Estimate entropy from samples under multivariate Bernoulli distribution

Could you find any way to estimate entropy from samples under multivariate Bernoulli distribution? Formally, for a multivariate Bernoulli distribution, getting its joint probability is somehow not ...
user avatar
1 vote
1 answer
42 views

How to find the maximal minimal distance between m points in a k-dimension Hamming space?

Assume we have m points in a k-dimension Hamming space. I wish all points are spread as far as they can in the space. So I wish to optimize the max-minimal distance between any pairs. Is there any ...
user avatar
  • 13
2 votes
0 answers
44 views

Is there a way to keep track of an infinite list of numbers without taking up too much "room"?

This started out as me pondering what it would be like to live forever. I realized if one was to live forever that you would still want to keep track of time and what the date was. Eventually though, ...
user avatar
0 votes
0 answers
23 views

comparing mutual information under different constraints

Consider a random variable $X$ taking values in $\{0,1,\ldots,n\}$ and $Y$ takes values in $\{0,1\}$. Let $a_{i}=P\left(X={i}\right), b_{j}=P(Y=j)$. Also, $ p_{i}=P\left(Y=0 \mid X=x_{i}\right), q_{i}=...
user avatar
1 vote
0 answers
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 ...
user avatar
  • 371
0 votes
0 answers
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 ...
user avatar
  • 51
0 votes
1 answer
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 ...
user avatar
0 votes
0 answers
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,...
user avatar
0 votes
0 answers
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: [1]: https:/...
user avatar
0 votes
0 answers
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: ...
user avatar
  • 1
1 vote
2 answers
92 views

The Kraft and McMillan Inequalities for Infinite Codes

I have a copy of the Jones and Jones Information and Coding Theory book. It states the Kraft inequality for instantaneously decodable codes and the McMillan inequality for uniquely decodable codes, ...
user avatar
  • 13
0 votes
0 answers
68 views

Maximizing the variance of weights of Bernoulli RV maximize mutual information?

I have a random variable $X=a_1X_1+a_2X_2 + \ldots a_kX_k$ where $X_i \sim Bern(q)$, $X_i \perp X_j, \forall i,j\in \{1,2\ldots,k\}$. Also $\sum_{i=1}^{k} a_i=k$ and $a_i \in \mathbb{N} \bigcup \{0\...
user avatar
6 votes
2 answers
91 views

Can we approximate the most likely event's probability if we know the distribution's entropy?

Suppose that we know that a distribution $p$ over small $n$ elements has entropy $H(p)=0.01$. I intentionally chose a small number. Is there some kind of inequality or aproximation to the probability $...
user avatar
  • 11.9k

1
2 3 4 5
43