Covers theoretical and experimental aspects of information theory and coding.

learn more… | top users | synonyms

1
vote
1answer
81 views

Total conditional complexity

By $C(|)$ denote conditional complexity. By $CT(|)$ denote total conditional complexity. For every n there exist two strings $x$ and $y$ of length $n$ such that $C(x|y) = O(1)$ but $CT(x|y) \ge n $. ...
1
vote
1answer
67 views

Entropy on a draw from a random distribution.

Suppose I am attempting to calculate the entropy of a continuous, normally distributed random variable $X$, from the distribution $\mathcal{N}(\mu, \sigma)$. This is easy to to do - I just calculate ...
2
votes
0answers
84 views

Applications of list decoding

This is citation from http://en.wikipedia.org/wiki/List_decoding: Algorithms developed for list decoding of several interesting code families have found interesting applications in computational ...
4
votes
0answers
55 views

$q$-deformations of fundamental equation of information and entropies

Classical information theory: fundamental equation of information In classical information theory, the information $I(A)$ of an event $A$ (any element of the $\sigma$-algebra $\mathcal F$ of a ...
3
votes
0answers
56 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 ...
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
247 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
76 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
681 views

A conjecture about the entropy of matrix vector products

Consider a random $m$ by $n$ partial circulant matrix $M$ whose entries are chosen independently and uniformly from $\{0,1\}$ and let $m < n$. Now consider a random $n$ dimensional vector $v$ ...
0
votes
1answer
63 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
110 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
76 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
534 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
57 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
93 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$ ...
2
votes
1answer
161 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
349 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
91 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
292 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
28 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
68 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
71 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
95 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
179 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
344 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
154 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
368 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
82 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
296 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
680 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
293 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
105 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
223 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
94 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
161 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
294 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
89 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
95 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
85 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
347 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, ...