Covers theoretical and experimental aspects of information theory and coding.

**1**

vote

**0**answers

80 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

**0**answers

19 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$ ...

**0**

votes

**0**answers

13 views

### Whats the difference between math.SE and mathoverflow? [migrated]

i wanted to know that :
Whats the difference between math.SE and mathoverflow ?
Are they of SE community or different ?

**2**

votes

**1**answer

112 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

**0**answers

61 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

**0**answers

35 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

**1**answer

55 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

**2**answers

92 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

**0**answers

41 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

**0**answers

55 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

**0**answers

74 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 ...

**2**

votes

**0**answers

62 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

**0**answers

123 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 ...

**0**

votes

**0**answers

30 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

**1**answer

180 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

**0**answers

38 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

**0**answers

135 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

**0**answers

93 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

**1**answer

112 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

**2**answers

110 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

**0**answers

62 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

**3**answers

368 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

**1**answer

86 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

**1**answer

136 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

**1**answer

90 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

**0**answers

98 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

**0**answers

78 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

**0**answers

68 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 ...

**3**

votes

**0**answers

76 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

**2**answers

309 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

**1**answer

92 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

**3**answers

713 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

**1**answer

81 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

120 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

101 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

**0**answers

675 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

**0**answers

69 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

135 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

106 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

**1**answer

207 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

**2**answers

403 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

124 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

329 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

45 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

129 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

76 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 ...

**2**

votes

**0**answers

112 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

199 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

199 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

383 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 ...