Covers theoretical and experimental aspects of information theory and coding.

learn more… | top users | synonyms

8
votes
1answer
143 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 ...
-1
votes
0answers
44 views

vector-matrix notation and expectation of matrix and Hermitian product [closed]

Let $\textbf{h} \in \mathbb{C}^{N\times 1}$, $\textbf{a} \in \mathbb{C}^{N\times 1}$, $\textbf{b} \in \mathbb{C}^{N\times 1}$ and $\textbf{c} \in \mathbb{C}^{N\times 1}$. The variable $h_i$ is defined ...
0
votes
0answers
13 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
3answers
89 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
0answers
37 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
0answers
63 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 ...
1
vote
0answers
73 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
0answers
148 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 ...
4
votes
0answers
149 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
2answers
302 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 ...
1
vote
0answers
122 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
1answer
120 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
1answer
351 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 ...
2
votes
0answers
67 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
2answers
273 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
1answer
629 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
1answer
270 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
0answers
101 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
1answer
89 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
0answers
84 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 ...
0
votes
1answer
160 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
1answer
85 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
1answer
151 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
0answers
88 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
1answer
266 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
0answers
79 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
1answer
89 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 ...
2
votes
0answers
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 ...
4
votes
0answers
68 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
2answers
155 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
1answer
77 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
2answers
339 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
0answers
100 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 ...
13
votes
1answer
676 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 ...
28
votes
1answer
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
1answer
166 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
2answers
211 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
3answers
409 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
0answers
150 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 ...
2
votes
1answer
257 views

A Johnson-Lindenstrauss lemma for finite fields?

Given $m$ points in $\mathbb{R}^N$, the Johnson-Lindenstrauss lemma guarantees the existence of a linear operator $\mathbb{R}^N\rightarrow\mathbb{R}^n$ that nearly preserves pairwise distances between ...
1
vote
1answer
306 views

how to prove a conjecture on a “canonical equivalent” of factoring

The following statement about finite differences of the positions of the ordered multiset of factors of $n$ in the sequence of primes seems to be true based on my empirical tests. Let $n=p_0^{j_0} ...
0
votes
1answer
100 views

order of convergence of the conditional entropy

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(X_n)$ then by Fano's inequality ...
0
votes
2answers
225 views

smallest number of comparisons needed

I have $n$ variables $b_1,\ldots,b_n$, each one $b_k\in \{0,1\}.$ Associated to each binary vector ${\bf b}=[b_1,\ldots,b_n]$ there are strictly positive function values $f({\bf b})$, and these are ...
3
votes
1answer
452 views

Stability in algebraic geometry

Suppose I have a collection of polynomials with multiple variables (more polynomials than variables, say), and I'm given noisy versions the values of these polynomials at a certain unknown point. I ...
5
votes
0answers
149 views

Chernoff bound in the not-quite-sub-exponential case

In Terry Tao's notes on Concentration of measure, Exercise 7 indicates that the Chernoff bound can be generalized to sub-exponential random variables: ...
1
vote
0answers
231 views

How to estimate the quantum fidelity between two given states

There is a well-known theorem, firstly obtained by Denes Petz, in quantum information theory, which is described as follows: $\mathbf{Theorem.}$ Let $\rho$ and $\sigma$ be two states on $\mathcal H$, ...
6
votes
8answers
1k views

Existence of unknowable algorithms ?

Here by «algorithm» I mean a (halting) Turing machine with finite alphabet and memory. Is it possible to obtain by purely existential (i.e. non-constructive) means the existence of an algorithm ...
1
vote
1answer
274 views

Convexity and semicontinuity of the relative entropy function

There are several different definitions of relative entropy, and some of them are not equivalent. Following is the definition we will use in this question. Let $M$ be a closed manifold and ...
2
votes
1answer
160 views

KL divergence(s) comparison,

Hi, $P_1$, $P_2$, $P_3$ are probability distributions defined on the same support. Knowing that $H(P_1) < H(P_2) < H(P_3)$, can we compare $D_{KL}(P_2,P_1)$ and $D_{KL}(P_3,P_1)$ ? (H is the ...
1
vote
2answers
488 views

A question about the size of a L1 ball

I met with a problem when I am reading a paper "On the Redundancy of Slepian-Wolf Coding" by He, DK; Lastras-Montano, LA; Yang, EH; Jagmohan, A; Chen, J, IEEE TRANSACTIONS ON INFORMATION THEORY, ISSN ...