Covers theoretical and experimental aspects of information theory and coding.

learn more… | top users | synonyms

3
votes
0answers
45 views

Assumption of equal prior message probabilities in the standard proofs of the converse of Shannon's theorem

One of the first steps in the standard proofs for the (weak) converse of the Shannon's theorem (a.k.a. noisy-channel coding theorem) for the discrete memoryless sources is the assumption that messages ...
0
votes
0answers
26 views

Apply 'splitting' in regenerating codes in locally repairable codes

In network coding for distributed storage system, regenerating codes are known to exist only in theory due to its complex implementation in storage system. In the codes, 'splitting' is applied in the ...
2
votes
0answers
63 views

How many samples to accurately estimate the entropy

Consider a discrete random variable $N$ with range $\{1,\dots,1000\}$, say. How many samples do you need to take to be sure that you can, at least in principle, compute the entropy Shannon entropy ...
1
vote
2answers
235 views

decomposition of Hilbert space into tensor product $L^2([0,\tfrac{1}{2}]) \otimes L^2([\tfrac{1}{2},1]) \simeq L^2([0,1])$

The definition of entanglement entropy in Quantum Field Theory involves decompositing a Hilbert space into a tensor product $\mathcal{H} = \mathcal{H}_A \otimes \mathcal{H}_B$. As an example, is it ...
2
votes
1answer
71 views

Mutual information staying constant under composition of channels

Consider the following scenario: one has 2 communication channels $C_1$ and $C_2$. Denote by $p(x)$ the input probability distribution. The mutual information between the input and the output of ...
7
votes
3answers
597 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
1answer
61 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
1answer
107 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
0answers
73 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 ...
18
votes
0answers
520 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
0answers
56 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
2answers
129 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
0answers
92 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
1answer
143 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
2answers
341 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
1answer
90 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
2answers
285 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
0answers
26 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
115 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
1answer
67 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
70 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
0answers
89 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
169 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
0answers
176 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
343 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
0answers
131 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
152 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
367 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
0answers
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
2answers
293 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 ...
16
votes
1answer
673 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
288 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
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
1answer
94 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
104 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
215 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
92 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
160 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
94 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
290 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
88 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
94 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
0answers
88 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
0answers
77 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
170 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
83 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
346 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
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 ...
18
votes
2answers
1k 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 ...
30
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 ...