Questions tagged [it.information-theory]

Theoretical and experimental aspects of information theory and coding theory. This tag covers but is not limited to following branches: information theory, information geometry, optimal transportation theory, coding theory.

Filter by
Sorted by
Tagged with
-1
votes
0answers
18 views

Maximum mutual information of random unitary transformation

Let $\mathbf{U}$ and $\mathbf{V}$ be random unitary matrices independent of random input vector $\mathbf{x}$. Moreover, $\mathbf{z}$ be random iid complex Gaussian vector with zero mean and unit ...
5
votes
1answer
107 views

Kullback–Leibler chains

The following question was asked and then deleted by the post author: Let $P$ and $Q$ be two probability distributions defined over the same space, with $KL(P \parallel Q) < \infty$. For $\epsilon ...
2
votes
1answer
105 views
+50

Mutual Information after Applying Random Unitary Matrix

Let $\mathbf{U}$ be a random unitary matrix and $\mathbf{z}$ be a random i.i.d complex Gaussian vector (unitary invariant). Assume that the following relation is satisfied: \begin{align} \mathbf{y}=\...
-1
votes
0answers
28 views

Table of common relative entropies?

Does anyone know where I can find a table of relative entropies between common distributions? I don't have an immediate application in mind, but I feel like this is a piece of reference material that ...
0
votes
0answers
26 views

Channel capacity for sequences of length n

Discrete memoryless channel is described by a stochastic matrix $(P_{b|a})_{a\in A,b\in B}$, where $A$ and $B$ is an input and an output alphabet, respectively. The capacity $C$ is the maximum of the ...
1
vote
1answer
109 views

paper only available in Russian (Kozachenko Leonenko entropy estimator)

this paper is only available in Russian: http://www.mathnet.ru/links/9f144b1d16e600dac49acbfe5acf938f/ppi797.pdf According to MathSciNet, there is no link to the English article or journal publication ...
0
votes
0answers
36 views

intuition about Gaussian processes over a finite space

In a paper that I am reading the authors defines $\mathbb P(n,q)$ the space of covariance tensors for $\mathbb R^q$-valued Gaussian processes on an abstract finite space $K=\{x_1,\dots,x_n\}$. In his ...
8
votes
2answers
223 views

Maximum of the weighted binomial sum $2^{-r}\sum_{i=0}^r\binom{m}{i}$

Let $m$ be a positive integer and let $f_m(r)=2^{-r}\sum_{i=0}^r\binom{m}{i}$. Clearly $f_m(0)=f_m(m)=1$ and $f_{2r+1}(r)=2^{2r}$. Conjecture: If $m>12$, then the maximum value of $f_m(r)$ for $r\...
1
vote
0answers
192 views

Maximum mutual information of a matrix representation

Let $\mathbf{Z}$ be a $m\times n$ matrix with zero-mean unit-variance i.i.d complex Gaussian entries. What is the maximum value of mutual information $I(\mathbf{X}_1,\mathbf{X}_2;\mathbf{Y})$ such ...
1
vote
1answer
60 views

KL-divergence and sub-$\sigma$-algebras

I am trying to understand if the following claim is true: Let $P$, $Q$ be probability measures on $\mathcal{X}$. For any $\sigma$-algebra $\mathcal{G}$, with countably many atoms (sets with $\...
1
vote
1answer
85 views

Almost-parallel corners of the hypercube in high dimensions

Say I would like a collection of k "almost-parallel" boolean vectors $X_1,...,X_k \in \{\pm 1\}^n$, such that $(X_i,X_j)/n \approx 1-\epsilon$ for some small $\epsilon$. How many ways are ...
1
vote
1answer
59 views

Simple non-asymptotic upper-bound for packing number of a hamming cube

Looking for a simple upper-bound for the packing number of hamming cube, I'm led to consider the following. Fix $p \in (0,1/2]$. For a positive integer $n$, define $S_n(p) := \sum_{i=1}^{\lfloor np\...
5
votes
1answer
128 views

reverse KL-divergence: Bregman or not?

I am having a little trouble getting my head around the two "directions" of the Kullback-Leibler divergence: Definition (Kullback-Leibler divergence) For discrete probability distributions $...
5
votes
0answers
76 views

Computing the zeta transform of a Boolean function: Space-time tradeoff

Let $f : \mathbb{F}_2^n \to \mathbb{F}_2$ be a Boolean function in $n$ variables. The zeta transform of $f$ is the Boolean function $\zeta_f : \mathbb{F}_2^n \to \mathbb{F}_2$ defined by $$\zeta_f(y) :...
0
votes
0answers
102 views

A basic property of maximal correlation

Let $𝑋$ and $𝑌$ be random variables. Then the maximal correlation $\rho_{m}(X;Y)$ is defined as: $$\rho_{m}(X;Y):=\max_{f,g}\mathbb{E}[f(X)g(Y)],$$ where the maximization is taken over real-valued ...
1
vote
0answers
55 views

Normalizing constants preserve metric entropy

Suppose $\mathcal{F}=\left\{f\in L^2([a,b]): 0<\underline{c}\leq f\leq\overline{c} \right\}$. Consider the following transformation $$\tilde{\mathcal{F}} := \left\{\frac{f}{\int f d\mu}: f\in \...
14
votes
2answers
2k views

information-theoretic derivation of the prime number theorem

Motivation: While going through a couple interesting papers on the Physics of the Riemann Hypothesis [1] and the Minimum Description Length Principle [2], a derivation(not a proof) of the Prime Number ...
2
votes
1answer
116 views

Monotonicity of Dirichlet form of Markov chain

Consider a continuous-time, irreducible Markov chain $X_t$ on a finite state space $E$. Assume the jump rates are $R(x,y)$ for $x,y\in E$, the generator is $L$, i.e for any function $f$ on E, $$Lf(x)=\...
0
votes
1answer
85 views

Parameterization of exponential family

Let $\{\mathbb{P}_{\theta}\}_{\theta}$ be an exponential family of probability measures, all with finite mean. Under what conditions is the parameterization map $\theta\mapsto \mathbb{P}_{\theta}$ ...
1
vote
1answer
98 views

Do enough permutations of an initial set eventually probably cover most permutations?

Fix $\alpha, \epsilon \in(0,1)$. Take $(S_n)_n$ to be any sequence of sets with each $S_n$ containing $ \lceil (n!)^\alpha\rceil$ permutations of $n$ elements. Also build another sequence of sets $(...
5
votes
2answers
168 views

Comparison of Information and Wasserstein Topologies

There are many possible metrics one can place on the space of Gaussian probability measures on $\mathbb{R}^n$, with strictly positive definite co-variance matrices. Let's denote this space by $X$. I'...
0
votes
1answer
170 views

Integrability of $\int \log(f(x)) f(x) dx$ for a probability density function $f$

I am looking for weak conditions when a probability density function $f$ on $\mathbb{R}^d$ has a finite integral $$ \int_{\mathbb{R}^d} \log(f(x)) f(x) dx. $$ Any references would be appreciated.
2
votes
0answers
95 views

The uniform “probability” on $\mathbf{N}$: What occurs beyond logarithmic density?

This is a follow-up to Question #47134. There is obviously no uniform probability distribution on $\mathbf{N}$ (or $\mathbf{Z}$); however, using the notion of amenability, you can show that any ...
6
votes
1answer
183 views

Probability of a deviation when Jensen’s inequality is almost tight

This is a cross-post to a yet unanswered question in Math StackExchange https://math.stackexchange.com/questions/3906767/probability-of-a-deviation-when-jensen-s-inequality-is-almost-tight Let $X>0$...
1
vote
0answers
72 views

A variant of Huffman code

Given an alphabet of $n$ symbolswith probabilities $p_i$ for symbol $i$, we need to encode the symbols (in a prefix-free way) to binary codewords $c(i)$ with length $\ell(c(i))$ to minimize the ...
0
votes
1answer
55 views

Lower bound for reduced variance after conditioning

Let $X$ be a random variable with variance $\tau^2$ and $Y$ be another random variable such that $Y-X$ is independent of $X$ and has mean zero and variance $\sigma^2$. (One can think of $Y$ as a noisy ...
1
vote
1answer
84 views

error correcting huffman code [closed]

I am looking for a code that can correct errors with variable and limited length like huffman code. I am not an expert in coding theory. Is there any code or related literature on this?
0
votes
1answer
96 views

Encoding numbers with relationship into one and back

Given a set of many variables $S=\{x_1,x_2, ...., x_i\}$, and any subset $S'$ of $S$, I need a function $f$ which maps $S'$ to a value $x$ and a function $f'$ which maps $x$ back to set $S'$. I know ...
3
votes
1answer
66 views

Information monotonicity of divergence => function of $f$-divergence

It is well-known that $f$-divergences defined on $\mathcal P(\mathcal X)$ where $\mathcal X$ is a measure space with $\sigma$-algebra $\mathcal B$ satisfy the property of information monotonicity: ...
5
votes
3answers
343 views

Is there a quantum analog of Kolmogorov Complexity?

Kolmogorov Complexity (interpreted in terms of shortest program computing a string) and Shannon Entropy are quite similar. Since there is a quantum entropy is it reasonable to ask if there is quantum ...
8
votes
1answer
266 views

The entropy of a partition of unity

A partition of unity can be thought of as a blurred out set partition: identify the fibers of the set partition with their indicator functions; the sum of these indicators is $1$. I would like to ...
2
votes
0answers
183 views

Linear independence of Vandermonde matrix in systematic Reed-Solomon code

My question is about using a Vandermonde matrix vs a Cauchy matrix in erasure coding. In the Reed-Solomon (RS) code, encoding is done by multiplying a $N\times K$ ($N>K$) matrix with the code words ...
2
votes
0answers
72 views

Finding k elements with count queries

Given a 'count in range' query access to an array of $N$ elements, our goal is to find $K$ missing elements with as few queries as possible (worst case, deterministic). To clarify, we can query how ...
0
votes
1answer
89 views

Entropy of a refinement of a partition

We consider a probability space $(X, B, \mu)$. Let $\alpha$ and $\beta$ be countable partitions of X. We suppose $\beta$ is a refinement of $\alpha$, ie that every set in $\alpha$ is a union of sets ...
5
votes
2answers
251 views

Shannon entropy and doubly stochastic matrices

Suppose that $A$ is a stochastic matrix. We know that if $A$ is doubly stochastic, then $H(Ap)\geq H(p)$ where $H$ is Shannon entropy and $p$ is a probability vector. Is the converse true? i.e., if $H(...
10
votes
0answers
258 views

Measuring the randomness of texts

The question concerns statistic properties of random words in a finite alphabet $A$. By $A^{<\omega}$ we denote the set of all words in the alphabet $A$, i.e. finite sequences of elements of $A$. ...
2
votes
0answers
189 views

An inequality of KL Divergence for two different distributions passing through a same channel

Let $X$ be a random variable which takes values in $\mathcal{X}$. Assume that we pass $X$ through two independent conditional pdf $p_{X_1|X}$ and $p_{X_2|X}$ and choose $X_1$ with probability $\lambda$...
6
votes
1answer
112 views

Smallest $\mathrm{D}(Q\|P)$ given fixed marginals $\mathrm{D}(Q_X\|P_X)$ and $\mathrm{D}(Q_Y\|P_Y)$

Let $P$ be a distribution on a set $U\times V$ with marginal distributions $P_X$ and $P_Y$. Suppose we have two values $d_x, d_y\in\mathbb R$, and we want to find the distribution $Q$ absolutely ...
1
vote
1answer
106 views

How much reduction in expected variance can we get from a single bit?

Consider the following protocol: Alice has a number $X$, chosen according to a known distribution $\mathcal D$ (e.g., $X\sim U[0,1]$). She can send a bit to Bob, giving him more information about $X$ (...
1
vote
1answer
153 views

Trace entropies

I'm studying relationships between trace entropy functionals and combinatorics and I'm faced with the following problem. Lets $\mathcal {D}$ be the following differential operator $1 -x\cdot \cfrac{d}{...
4
votes
1answer
129 views

Information density of proofs?

I am a CS person so please excuse the hand-waving. Given a set of machine-represented proofs, each different (but not necessarily proving a different thing), what sort of information-theoretic ...
1
vote
0answers
138 views

A new notion of probability coupling

Let $X$ and $Y$ be two discrete random variables distributed according to $\mu$ and $\nu$, respectively. Consider the following optimization problems $$\inf_{\pi\in \Pi(\mu, \nu)}\Pr(X\neq Y),$$ ...
2
votes
1answer
92 views

Conditional entropy - solve example

Given a random variable $X$ that is uniformly distributed on $[-b,b]$ and $Y=g(X)$ with $$g(x) = \begin{cases} 0, ~~~ x\in [-c,c] \\ x, ~~~ \text{else}\end{cases}$$ Now I want to compute the ...
2
votes
1answer
73 views

Strong Data Processing Inequality for capped channels

Let $X$ and $Y$ be two $\rho$ correlated Gaussian vectors, such that $X,Y\sim N(0,1)^n$ and $E[X_iY_i]=\rho$. Let $M_X = f(X)$ and $M_Y = f(Y)$ be $k$-bit functions of $X$ and $Y$, that is $H(X)=H(Y)=...
2
votes
1answer
102 views

Information theory for uncountably infinite-dimensional continuous random variable

I'm exploring the possibility to apply information theory on an uncountably infinite-dimensional scenario. I found the concept of generalized entropy for continuous random variables defined on finite-...
0
votes
0answers
148 views

Is there a difference between using nats and bits to express entropy?

It seems to me like questions involving decimal vs binary representations of some number are not particularly interesting: for instance $\pi$ or $\sqrt{2}$ are conjectured to be normal in every base, ...
4
votes
1answer
170 views

Books to develop a deep understanding of Algorithmic Information Theory?

I'm mathematical physicist working with hydrodynamics modelling. Recently, I had to turn to modelling of flows with particles and some questions I have I think are related to Algorithmic Information ...
8
votes
3answers
295 views

Identifying a subset with as few tests as possible

Informal description: You are given a set of $n$ blood samples, each having probability $p$ of being infected with a disease. Your goal is to determine the set $P$ of infected samples with as few ...
4
votes
1answer
156 views

$\varepsilon$-net of a $d$-dimensional unit ball formed by power set of $V = \{+1, 0 -1\}^d$

I have a set of $d$-dimensional vectors $V = \{+1, 0, -1\}^d $. Then $P(V)$ constitutes the power set of $V$. I now construct a set of unit vectors $V_{\mathrm{sum}}$ from the power set $P(V)$ such ...
5
votes
0answers
318 views

Can information be extracted more precisely using more random trials?

Write $n$ iid draws of $(x,y)$ as $(x^n, y^n)$. Fix $R\in (0,H(x))$. What is the min of $n^{-1}H(y^n|f(x^n))$ over $f$ with $H(f(x^n))\leq nR$, taking $n\to \infty$?

1
2 3 4 5
10