Covers theoretical and experimental aspects of information theory and coding.

**0**

votes

**0**answers

47 views

### A conjecture about the entropy of matrix vector products

Consider a random $n$ by $n$ circulant matrix $M$ whose entries are chosen independently and uniformly from $\{0,1\}$. Let $M'$ be the $m$ by $n$ matrix which is formed by taking the first $m$ rows of ...

**0**

votes

**1**answer

50 views

### Invariance of mutual information

Let $I(X,Y):=H(X)+H(Y)-H(X,Y)$ be the mutual information of the joint probability distribution $p_{XY}$ (here $H(\cdot)$ is the Shannon entropy of its argument). I know that the mutual information is ...

**5**

votes

**1**answer

98 views

### Is this graph of reciprocal power means always convex?

Let
$$
p = (p_1, \ldots, p_n)
$$
be a finite probability distribution, which for convenience I'll assume to have no zeroes: thus, $p_i > 0$ for all $i$ and $\sum_i p_i = 1$.
Is the function
...

**2**

votes

**0**answers

66 views

### Lower convex envelope of a function involving entropy

Suppose two discrete random variables $X$ and $Y$ defined on finite sets $\mathcal{X}$ and $\mathcal{Y}$ are given and also suppose the conditional distribution $P_{Y|X}$ (i.e, channel) is fixed. We ...

**16**

votes

**0**answers

498 views

### conjectures regarding a new Renyi information quantity

In a recent paper http://arxiv.org/abs/1403.6102, we defined a quantity that we called the "Renyi conditional mutual information" and investigated several of its properties. We have some open ...

**0**

votes

**0**answers

54 views

### Variance of continuous stochastic process

In the paper "Directed Information, Causal Estimation, and Communication in Continuous Time" the author show an example of continuous Gaussian Channel:
Let $\{B_t\}$ be a standard Brownian motion and ...

**4**

votes

**2**answers

120 views

### Another formulation of error-correcting coding problem

Consider classic error-correcting problem:
there is finite set $A$ and string $a_1...a_n$, $a_i \in A$ in the begin.
in the end we have $b_1...b_n$. Set places of errors $E = \{i| a_i\not= b_i \}$, ...

**3**

votes

**0**answers

89 views

### Will relative entropy increase with majorization?

Suppose that three probability distributions have the relation $P\succ Q\succ R$, then do the following relations between their relative entropy valid? (assume that $p_1\geq p_2\geq\cdots \geq p_n$ ...

**1**

vote

**1**answer

126 views

### Mutual information decrease with coarse-graining

Let $X,A,Y,B,C,D$ be random binary variables. $D$ is independent from $X,A,C$ and $C$ is independent from $Y,B,D$.
Is it true that:
If $I(Y:B|D=0)\leq \epsilon$ then $I(X\oplus Y:A\oplus ...

**1**

vote

**0**answers

80 views

### Two questions on conditional independence [closed]

I have two simple questions about conditional independence.
Suppose two random variables $X$ and $Y$ are independent. Then I want to show that they are independent given any arbitrary random ...

**1**

vote

**2**answers

334 views

### Geodesic equation from Christoffel symbols

Let $\mathcal{P}:=\mathcal{P}(\mathcal{X})$ be the manifold of all (strictly positive) probability vectors (distributions) on $\mathcal{X}=\{x_0,\dots,x_n\}$,
i.e., each $p=(p(x_0),\dots,p(x_n))\in ...

**0**

votes

**1**answer

75 views

### Why private randomization does not help the Shannon's source coding

I am wondering why stochastic encoder and decoder can not help the Shannon source coding? I know the achievability scheme of source coding, which is based on typicality, is deterministic, and hence we ...

**9**

votes

**2**answers

275 views

### Entropy for Haar measure on $O(n)$

Let $G$ be a locally compact group. A measure $\mu$ is the right-Haar measure on $G$ if for every $g\in G$ and $E\subseteq G$ Borel set $\mu(Eg)=\mu(E)$. It is known that every locally compact group ...

**0**

votes

**0**answers

20 views

### How to generalize uncertainty coefficient to set-valued classes?

This question is the reason I asked How to estimate the entropy of a distribution on a power set?
Proficiency (AKA uncertainty coefficient) is an information-theoretic measure of predictor quality, ...

**1**

vote

**3**answers

110 views

### How to estimate the entropy of a distribution on a power set?

Given a probability distribution $(X,p)$, its entropy is defined as $H=-\sum_{x\in X} p(x)\log p(x)$.
Given a sample of observations $x_n,n=1..N$, one can estimate $p(x)=\frac{\#\{i:x_i=x\}}{N}$ and ...

**1**

vote

**1**answer

65 views

### Connection between inf-entropy rate and min-entropy

I am reading the paper "Generating random bits from an arbitrary source: fundamental limits" by Vembu and Verdu. This paper is written in the language of information theory, however, I need to ...

**0**

votes

**0**answers

67 views

### An attempt to solve “Maximization of a total variation distance subject to another total variation distance in Markov chain”

I have been trying to solve Maximization of a total variation distance subject to another total variation distance in Markov chain. As a recall, suppose we have a pair of correlated random variables ...

**2**

votes

**0**answers

82 views

### Is there an universal (dis)similarity measure between two structures?

I'm always wondering is there an universal (dis)similarity measure
between two structures (let's say between two undirected simple
graphs)? I mean, not "the measure with universal parameter that we
...

**3**

votes

**0**answers

163 views

### Maximization of a total variation distance subject to another total variation distance in Markov chain

Suppose two dependent random variables $X$ and $V$ from finite alphabets $\mathcal{V}$ and $\mathcal{X}$ with known joint and marginal distributions are given. Let $P_{XV}$ and $P_X$ and $P_V$ are the ...

**5**

votes

**0**answers

170 views

### Maximizing Renyi entropy for a certain channel

The channel under consideration is $T = A + B$, where $A$ and $B$ take on values in $\{0, 1\}$ according to a probability mass function. Let (joint) random vector $(A_1, A_2,\ldots, A_n)$ be denoted ...

**8**

votes

**2**answers

334 views

### Inequality in information theory

I am reading the paper "chain independence and common information" (http://ttic.uchicago.edu/~yury/papers/independ.pdf). In this paper, an inequality is used several times (without proof) which looks ...

**2**

votes

**0**answers

130 views

### An optimization in Markov Chain

We are given two correlated random variables $V$ and $X$ supported over a finite alphabets $\mathcal{V}$ and $\mathcal{X}$. Suppose the marginal $P_V$ and conditional distribution $P_{X|V}$ are ...

**0**

votes

**1**answer

148 views

### Approximation of the sum involving binary entropy function

Given the following sum:
$S(n) = \sum_{i=1}^{n} \frac{1}{(1-\operatorname{H}(p))^i}$
where $H$ is the binary entropy function defined as:
$\operatorname{H}(p) = -p\log p - (1-p)\log (1-p) $.
Let ...

**3**

votes

**1**answer

366 views

### Simple reason that a mathematician cannot do better than random when guessing contents of a box?

I have a question about the finite analog of the puzzle proposed here involving mathematicians guessing the contents of boxes.
Specifically, suppose there are $k$ unopened boxes each containing a ...

**3**

votes

**0**answers

80 views

### Certain subgroup of automorphism groups of binary codes

Suppose that $C$ is an binary linear code of length $n$ and dimension $k$ (i.e. it's a $k$-dimensional linear subspace of $\mathbb{F}_2^n$). As usual, the automorphism group of $C$ is the subgroup of ...

**2**

votes

**2**answers

288 views

### What is the maximum entropy distribution on the natural numbers?

On the reals $\mathbb{R}$, the maximum entropy distribution with a given mean and variance is the Gaussian distribution.
Let $\mu, \sigma > 0$. What is the maximum entropy distribution on the ...

**15**

votes

**1**answer

665 views

### Gini Coefficient and Renyi Entropy

Gini coefficient (aka Gini Index) is a quantity used in economics to describe income inequality. It is 0 for uniformly distributed income, and approaches 1 when all income is in hands of one ...

**2**

votes

**1**answer

284 views

### A submanifold of the space positive definite matrices

Consider the space of $n \times n$ positive definite symmetric matrices and let $\Sigma$ be one such matrix. We make this space into a Riemannian manifold $M$ by means of the metric ...

**1**

vote

**0**answers

109 views

### expected inverse of circulant plus random diagonal

I have a deterministic circulant matrix $R$ and a random diagonal matrix $X$ where all elements are IID and positive.
I need to determine the expected inverse of $R+X$, that is: Evaluate, in closed, ...

**2**

votes

**1**answer

93 views

### A (Hard?) combinatorial optimization problem involving the representation numbers

Given a (suppose prime order) group G, for any two partions $\{A_i\}_{i\in I}$ and $\{B_j\}_{j\in J}$ of the group $G$ consider the following quantity
$$ E = \sum\limits_{i \in I,j \in J} \max_{g} ...

**4**

votes

**0**answers

100 views

### Fully Homomorphic Error Correction?

Consider a field $F$. Suppose we have two vectors $a,b\in F^n$, and an invertible matrix $G\in F^{n\times n}$. Let $c\in F^n$ be the point-wise product of $a$ and $b$, that is, $c_i=a_ib_i$. Let ...

**1**

vote

**1**answer

196 views

### Size of KL-divergence neighbourhoods

I am new here. I was reading another
post
here and this got me wondering what can be said about the size of the following kl divergence neighborhoods.
Consider these two kl-divergence neighbourhood ...

**-3**

votes

**1**answer

89 views

### “logical distance” link algorithmic complexity to statistical information [closed]

Someone mentioned what I think was referred to as 'logical distance'.
My hard drive crashed and I dont have the link anymore.
I do recall that I ran across it on this site, in response to linking ...

**1**

vote

**1**answer

159 views

### Set of distributions that minimize KL divergence,

Assuming that $p,q$ are probability distributions defined on the same support $\{x_i\}_{0 \leq i \leq n}$, $\epsilon$ a small real number, and $D_{KL}$ the Kullback-Leibler divergence,
is there a ...

**2**

votes

**0**answers

93 views

### Information theoretic privacy and distance of probability measures!

I came across the notion of information theoretic privacy in the paper of Yamamoto ("A source coding problem for sources with additional outputs to keep secret from the receiver or wiretappers "). The ...

**1**

vote

**1**answer

286 views

### Cyclic Hamming Code

I know that Hamming codes can be arranged in cyclic form. But my question is how can I prove this.
My idea was to find a generator/primitive polynomial $p(x)$?
For example I want to show that the ...

**2**

votes

**0**answers

84 views

### order of convergence of the conditional entropy (3)

I'm sorry for having open two questions which have been solved by elementary counter-examples provided by @AnthonyQuas. Actually I'm not an expert in information theory and I expected that a positive ...

**1**

vote

**1**answer

93 views

### order of convergence of the conditional entropy (2)

Let $X_n$ be a random variable distributed on $A_n:=\{1, \ldots, n\}$ and $g_n\colon A_n \to A_n$ such that $\Pr\big(X_n \neq g_n(X_n)\big) \to 0$. Putting $Y_n=g_n(X_n)$, then by Fano's inequality ...

**1**

vote

**0**answers

87 views

### Capacity of Cycle Graphs

Shannon capacity $\Theta(G)$ of pentagon is achieved at $2$-fold strong product of the pentagon.
It is also known that the Lov\'asz theta $\vartheta(G)^m\neq\alpha(G^{\boxtimes m})$ for any finite ...

**3**

votes

**0**answers

75 views

### Is there a known generalization of the Schmidt decomposition based on a maximal set of “locally orthogonal” vectors?

I came across the following unusual generalization of the Schmidt decomposition in my work, which I describe below. I would like to know if this structure has been studied before so I can read more ...

**3**

votes

**2**answers

168 views

### Binary codes with upper bound on pairwise distance

A fundamental problem in coding theory is:
Given positive integers $k\le n$, determine or bound the maximal cardinality of a set $S\subset \mathbb{F}_{2}^{n}$ such that $\forall x,y\in S: x\ne ...

**5**

votes

**1**answer

81 views

### a measure of difference for arrangements of sphere points

Suppose one has a distribution of $N$ points on the sphere. Is there an agreed upon metric for the difference of this distribution and $N$ equidistant points on the sphere? To me entropy seems like ...

**8**

votes

**2**answers

345 views

### Where should I learn about Kolmogorov complexity of overlapping substrings?

I would like to know more about the relationship between the Kolmogorov complexity of a string and that of its substrings. The relation that up to an additive constant, $K(x,y) = K(x) + K(y\ |\ x, ...

**2**

votes

**0**answers

101 views

### Looking for Camion - Abelian codes

I am looking for a copy of the old report "Paul Camion - Abelian codes", Technical Report 1059, University of Wisconsin 1971. I have asked Paul himself, but he could not help me. Anyone out there has ...

**16**

votes

**1**answer

838 views

### An Entropy Inequality (generalized)

Let $X,Y$ be probability measures on $\{1,2,\dots,n\}$. For $0\le \alpha \le 1$, set $K=\sum_i X(i)^\alpha Y(i)^{1-\alpha}$ so that $Z:=\frac{1}{K}X^\alpha Y^{1-\alpha}$ is also a probability ...

**29**

votes

**1**answer

2k views

### An Entropy Inequality

Let $X,Y$ be probability measures on $\{1,2,\dots,n\}$, and set $K=\sum_i\sqrt{X(i)Y(i)}$ so that $Z:=\frac{1}{K}\sqrt{XY}$ is also a probability measure on $\{1,2,\dots,n\}$. How can we prove the ...

**0**

votes

**1**answer

170 views

### Comparison Huffman Encoding and Arithmetic Coding dependent on Entropy

Where can I get an understanding of how Arithmetic Coding and Huffman Encoding compare as entropy increases. I know Arithmetic Coding is better for low entropy distributions, but how can I get a sense ...

**4**

votes

**2**answers

218 views

### Is there a code which corrects corruption of any two bits in a block?

Background
I've just learned a bit about linear codes. Hamming codes have the property that up to one bit in a block can be corrupted, and we still communicate the message correctly. This is done by ...

**4**

votes

**3**answers

435 views

### Incremental entropy computation

After a quick internet search I found no method for incremental entropy computation.
Question 1
Let $\{x_i\}_{i=1}^n$ and $\{x_i\}_{i=1+n}^{n+m}$ be two samples and let $S_i^j:=\sum_{k=i}^j x_k$. ...

**3**

votes

**0**answers

162 views

### Axioms for Mutual Information

I am interesting in axiomatic justifications for concepts in information theory. I have found many axiomatizations for Shannon's entropy and for the Kullback-Leibler divergence, as well as their ...