Covers theoretical and experimental aspects of information theory and coding.

learn more… | top users | synonyms

2
votes
1answer
87 views

Enumerator Polynomials for Linear Anytime Codes

Let $C = \{c \in \mathbb{F}^n_2 : Hc=0\}$ be a binary linear code where $H \in \mathbb{F}^{k \times n}_2$ is a block lower-triangular matrix of full rank called the parity-check matrix of $C$. Clearly ...
3
votes
1answer
184 views

Information theory from negative probability

Szekely provides a convincing argument of negative probability here: http://www.wilmott.com/pdfs/100609_gjs.pdf What does a reformulation of classical information theory built from negative ...
2
votes
0answers
28 views

MLE and CRLB with mismatched likelihoods

Suppose that I can do a Karhunen-Loeve expansion of a log-likelihood function $p(\bf{x};\theta)$ into N terms and that these accounts for a fraction $1-\delta$ of the total energy. Now consider ...
1
vote
0answers
54 views

Precise statement of Gersho's conjecture

Here is the Gersho's conjecture from his paper "Asymptotically optiaml block qunatization" "For $N$ sufficiently large the optimal(distortion-minimizing) quantizer for a random vector uniformly ...
3
votes
0answers
148 views

Where can I find a proof of this result on optimal tessellation of a unit square?

Here is an excerpt from the paper "The Hexagon Theorem" by Donald J.Newman Does anyone know where I can find a proof of the underlined statement? Newman states it without a proof, and I could get ...
1
vote
0answers
47 views

How do you use the bits you get back from Bits Back Coding?

Bits Back coding is a scheme to transmit an observation x. You can read about it here [1]. To my understanding, it works like this: The encoder samples a message z from a distribution Q(z|x) that it ...
0
votes
1answer
88 views

Information theoretic common sequence agreement (not secret key)

Supposing Alice and Bob share $\rho$-correlated sequences in $\{0,1\}^n$, what coding theory based schemes are available for Alice and Bod to extract sequences $A,B\in\{0,1\}^n$ respectively such that ...
3
votes
1answer
149 views

A Generalized Version of Maximal Correlation and Hypercontractivity of Conditional Expectation Operator

Given a pair of random variables $(X,Y)$ over a product space $\mathcal{X}\times \mathcal{Y}$, the maximal correlation coefficient is defined as ...
1
vote
1answer
51 views

Rate-Distortion theory: What is the distribution of distortion on an optimal encoder?

If we wish to encode a gaussian source, $X\sim\mathcal{N}(0,\sigma^2)$ at rate $R$, then decode it to create an estimate $\hat{X}$, rate-distortion theory tells us that the lowest mean-squared-error ...
9
votes
2answers
347 views

Expected centered entropy of the binomial distribution

In short, the function I am interested in is the following: $$I_n(p) = \sum_{k=0}^n \binom{n}{k} p^k (1-p)^{n-k} \left[h(p) - h\left(\tfrac{k}{n}\right)\right],$$ where $h(x) \triangleq -x \log x - ...
1
vote
0answers
40 views

Channels of Practical Interest

Are there channels of practical interest whose capacity achieving probability distributions belong to a parametric family of probability measures? Specifically, suppose $ \theta= (\theta_1 \theta_2 ...
2
votes
0answers
280 views

Good covering of a sphere

Consider a sphere $S_r(0)$ with center at zero and radius $r$ in the Hamming space $\{0,1\}^n$. We will be interested in covering this sphere with balls of radius $\rho < r$. We know that there ...
0
votes
0answers
92 views

Upper bound for chi-square divergence in terms of KL divergence

In my research I need an upper bound for chi-square divergence in terms KL divergence which works for general alphabets. To make this precise, note that for two probability measures $P$ and $Q$ ...
1
vote
1answer
242 views

Coupon Collector Problem for Non-Uniform Coupons: Bound on the number of missed Coupons

Suppose $\mathcal B=\{1,2,..,b\}$ is the set of all possible coupons, with $\mathbf p = ( p_1,p_2,...,p_b)$ assigning the probability of occurrence for all coupons in $\mathcal B$. The "traditional ...
3
votes
0answers
83 views

On Rényi entropy/divergence

The Rényi entropy for a probability density function $f$ with dominating measure $\mu$ of order $\alpha>0$ is defined as $$H_\alpha(f)={1 \over {\alpha-1}}\log\int f^\alpha d\mu.$$ If $f$ is ...
0
votes
0answers
45 views

minimal entropy approximation of a truncated discrete measure

Consider a measure $\mu$ on $\mathbb{N}$ given by the sequence $(\mu(n))_{n \geq 0}$ with $\mu(0)>0$. For example $\mu(n)=n^2+1$ on the figure below. For each $n$, let $X_n \sim \mu(\cdot \mid ...
1
vote
1answer
123 views

Correlation between two continuous-time stochastic processes

Consider two continous-time stochastic processes $\{A(t)\}_{t \ge 0}$ and $\{B(t)\}_{t \ge 0}$ with $A(t)=t$ and $B(t)=t$. Each process starts at $t=0$ and emits "ticks" at increasing time slots. For ...
2
votes
2answers
119 views

What is the sum capacity of a scalar gaussian broadcast channel?

"On the Achievable Throughput of a Multiantenna Gaussian Broadcast Channel" by Giuseppe Carie and Shlomo Shamai talks, in part, about the following type of link (paraphrasing): A transmitter with ...
2
votes
0answers
55 views

minimal entropy approximation of a discrete random variable

Let $X$ be a $\mathbb{N}$-valued random variable. Define $$ H^\epsilon_n(X) = \inf_f H(f(X)) $$ where $f$ runs over all functions $\mathbb{N} \to \mathbb{N}$ such that $\Pr(f(X)\neq X)<\epsilon$ ...
0
votes
0answers
69 views

Continuous self-information

Let $I(X,Y)$ be the mutual information between two continuous random variables $X$ and $Y$. We have $I(X,Y) = H(X)-H(X|Y)$, and setting $X=Y$ leads to $I(X,X) = H(X)-H(X|X)$. If $X$ was discrete, ...
2
votes
0answers
85 views

On subset of Deterministic games

Denote strings $u,v$ from $\{0,1\}^n$. Denote concatenated pair $[uv]$. Denote $$[uv]_{1}=\{[uv]\oplus e_i\}_{i=1}^{2n}$$ collection of pairs with Hamming distance $1$ from $[uv]$ string ...
3
votes
0answers
157 views

Convex Conjugate of Relative Entropy

The convex conjugate of a function, say, $f:X\mapsto \mathbb{R}$ is a function $f^*:X^*\mapsto \mathbb{R}$ defined as $$f^*(x^*):=\sup_{x\in X} ~\langle x, x^*\rangle-f(x),$$ where $X^*$ is the ...
2
votes
0answers
163 views

Interpretation of Shannon Entropy Application

Consider a collection of increasing positive integers $\{a_i\}_{i=1}^m$ and the distribution $p_i=\frac{a_i}{\sum_{i=1}^ma_i}$. Let entropy of $\mathcal{A}=\{a_i\}_{i=1}^m$ be given by ...
1
vote
0answers
33 views

Multidimensional Filters

Say you want to design a LP FIR filter with low pass cutoff $fc$, transition band $fc$ to $fs$ and ripple factor $dp$ at passband and $ds$ at stop band. If one divides the frequencies by $\pi$, then ...
8
votes
1answer
197 views

Higher moments of information and Renyi entropy

For a given discrete probability distribution, Shannon entropy can be though as an expectation value $\langle - \log p \rangle$ (see also: What is entropy, really?, What is the role of the logarithm ...
1
vote
0answers
39 views

Distributing partially known data between n parties

Assume that $n = 2r+1$. There are $n$ elements $a_1,a_2,\ldots,a_n$ from a finite field $\mathcal{F}$, and $n$ parties. Each party knows the values of at least $r+1$ elements out of those $n$ ...
7
votes
0answers
146 views

Cramer's theorem in Hilbert spaces

I am interested under what conditions Cramer's theorem applies in random variables taking values in Hilbert spaces. Following these lecture notes, but using a Hilbert space: Let $X_1,X_2,\cdots$, be ...
4
votes
0answers
99 views

Large Deviations: Exponential decay in normed spaces

Let $(X_1,X_2,\cdots)$ be a sequence of independent and identically distributed random variables taking values in some general normed space $(V,||\cdot||)$. Denote $\mu=E[X_1]$ and ...
0
votes
1answer
167 views

On the inverse problem of Dobrushin

Dobrushin, in this paper, looked into the following problem. Suppose We are given a Markov kernel (conditional distribution) $P_{Y|X}$. Information theorist usually call $W$ a channel. It is known ...
0
votes
2answers
120 views

Form of the Shannon capacity for Heptagon?

Is the $0$-error capacity of $7$-cycle: $(1)$ known to be of form $7^q$ for some $q\in \mathbb Q$?
1
vote
1answer
100 views

Coding for channels with concentrated error

Can we implement a reduced-error transmission over a channel with error frequency having $\liminf<\frac{1}{2}$ and $\limsup>\frac{1}{2}$? We know that if a channel with error flips (in the ...
2
votes
3answers
405 views

Asking for an English version of a paper

I have been looking for the paper "almost independence and secrecy capacity" by Csiszar. But all I could find was a Russian version published in Problems of Information Transmission. I am wondering ...
-1
votes
1answer
101 views

Noise reduction in capacity-0 channels

Suppose we have a binary symmetric channel with $p=\frac{1}{3}$; that is, a communications channel in which each bit is flipped with independent probability $\frac{1}{3}$. I know that there is a code ...
1
vote
1answer
160 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
103 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 ...
3
votes
0answers
107 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
85 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
76 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 ...
1
vote
2answers
366 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
116 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 ...
8
votes
3answers
748 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$ ...
1
vote
1answer
106 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
136 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
111 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 ...
19
votes
0answers
711 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 ...
1
vote
0answers
78 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
149 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
110 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$ ...
3
votes
1answer
261 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
437 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 ...