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

425
questions

**5**

votes

**0**answers

183 views

### What is the status of the Born Rule in axiomatic QM?

While physicists have tried multiple times and failed to derive the Born Rule (for example: https://arxiv.org/pdf/quant-ph/0409144.pdf). I was wondering what axiomatic Quantum Mechanics had to say ...

**-1**

votes

**0**answers

36 views

### Entropy density equals limit of conditional entropy

Consider a probability distribution of m-length sequences $P_m(x_1,x_2......,x_m)$ where $x_i\in\{1,-1\}$. We then have that $h=\lim_{m\to \infty}\frac{H_m}{m}$ where $H_m$ is defined as
$$H_m :\, =\...

**1**

vote

**0**answers

53 views

### Convexity of conditional relative entropy for Markov distributions

Consider two Markov processes $p$ and $q$. The conditional relative entropy between them is
\begin{align}
D(p\parallel q)& =\sum_a p(a)\sum_b p(b\mid a)\log\frac{p(b\mid a)}{q(b\mid a)}\\
& =\...

**2**

votes

**1**answer

43 views

### Entropy of distribution with block matrix support

Let $P(X_1,X_2)$ be a discrete bivariate distribution that has the form shown in the figure below, i.e. its support can be split into blocks that do not overlap on either dimensions.
Let's build $P'(...

**2**

votes

**1**answer

69 views

### Relationship between $\alpha$-divergences?

I am working with $\alpha$-divergences and was wondering how understand the relationship between the definitions of Renyi and Amari?
Renyi:
$D_{\alpha}[p||q] = \frac{1}{\alpha - 1} \log \int p^{\...

**4**

votes

**1**answer

84 views

### Convexity of exponential family

It is known that (given a $\sigma$-finite Borel reference measure $\nu$ on $\mathbb{R}$) the parameter space of an exponential family is convex in Euclidean space. However, my question is, for an the ...

**0**

votes

**0**answers

147 views

### Non-negative interaction information for special trivariate case

Consider a discrete trivariate distribution $P(X_1, X_2, Y)$, which satisfies
$$
p(x_1, x_2, y) = \min( p(x_1,y), p(x_2,y) ),
$$
for all $x_1$ and $x_2$ for which $p(x_1, x_2) > 0$ and for all ...

**26**

votes

**2**answers

1k views

### Is there a Kolmogorov complexity proof of the prime number theorem?

Lance Fortnow uses Kolmorogov complexity to prove an Almost Prime Number Theorem (https://lance.fortnow.com/papers/files/kaikoura.pdf, after theorem $2.1$): the $i$th prime is at most $i(\log i)^2$. ...

**2**

votes

**1**answer

97 views

### Mutual information inequality

I am trying to prove three inequalities that would help me solve the proof of a larger theorem.
Let $P(X,Y)$ be a discrete bivariate distribution and
$$
I(X;Y) = \sum_{i,j} p(x_i, y_j) \log \frac{p(...

**0**

votes

**0**answers

47 views

### Information theoretic lower bounds for sparse recovery

For the well-known problem of sparse recovery using $\ell_1$ minimization, it was shown in this paper that for any random measurement matrix, a recovery procedure that succeeds with constant ...

**0**

votes

**0**answers

51 views

### How to derive formula (10) norm to obtain formula (11) in Uncorrelated Group LASSO?

In Uncorrelated Group LASSO, Eq. (10) and Eq. (11) are as follows:
$J_2(W)=f(W)+\alpha Tr(W^TFW)$. (10)
$F_{ii}=\sum_{g}\frac{(I_{G_{g}})_i||W_{G_g}||_{2,1}}{||W_{G_g}^i||_2}$. (11)
where $w_{...

**2**

votes

**0**answers

76 views

### Shannon-McMillan-Breiman theorem for expander graphs: rate of convergence?

Is the following uniform SMB theorem for random walks on expander graphs true?
For simplicity, I will state it for a finite group $G=\langle S \rangle$ and a uniform probability measure $\mu$ on the ...

**2**

votes

**0**answers

166 views

### On the difference of conditional differential entropy of two correlated random variables

Problem Definition
Let $\mathbf{G}$ and $\mathbf{S}$ be jointly distributed random variables where
$\mathbf{S}$ is continuous and is related to $\mathbf{G}$ through a conditional pdf $f(s|g)$ defined ...

**1**

vote

**0**answers

74 views

### Binary search extension for determining a hyperplane splitting a set of points in $\mathbb{R}^d$

We are given a set $S$ of $n$ points in $\mathbb{R}^d$ and a (hidden) vector $\mathbf{w}\in\mathbb{R}^d$, where each point $\mathbf{v}\in S$ is associated with a binary label equal to the sign of $\...

**9**

votes

**1**answer

201 views

### Conceptual explanation for the appearance of entropy in $\frac{d}{dp}\|x\|_p$

For $x\in \mathbb{R}^d$, an elementary computation yields that
$$\frac{d}{dp}\log \|x\|_p =\frac{1}{p^2}\sum_{i=1}^d \frac{|x_i|^p}{\|x\|_p^p}\log \frac{|x_i|^p}{\|x\|_p^p}=-\frac{1}{p^2}\operatorname{...