# Questions tagged [it.information-theory]

Theoretical and experimental aspects of information theory and coding theory. This tag covers but is not limited to following branches: information theory, information geometry, optimal transportation theory, coding theory.

**1**

vote

**0**answers

51 views

### Correspondence between information theoretic and coding theoretic language?

In information theory capacity or best rate achievement techniques are through showing existence if typical sequences of certain measure while in coding theory performance is measured by number of ...

**-1**

votes

**0**answers

117 views

### Entropy of moments of integers

Let $x \in \{0,1\}^n$ be uniformly at random. What is an estimate for the entropy of moments, $H(\sum_i x_i, \sum_i i\cdot x_i, \sum_i i^2\cdot x_i)$ ?
$H(.)$ here is the Shannon entropy

**0**

votes

**1**answer

108 views

### Shortest possible good codes?

Good codes (those with positive rate $r=k/n$ and positive relative distance $\delta=d/n$) will achieve capacity on $BSC$ (binary symmetric channel) if the codes have lower rates than capacity where ...

**3**

votes

**1**answer

63 views

### Polynomial time decodable binary linear codes achieving $GV$ bound?

Are there explicit or random construction of linear codes that achieve the $GV$ bound with polynomial time decodable property with alphabet size $q=2$?
Tsfasman, Manin, Vladut beat the bound at ...

**3**

votes

**1**answer

101 views

### Maximal correlation and independence

Let $X$ and $Y$ be random variables. Then the maximal correlation $\rho_m(X;Y)$ is defined as
$$ \rho_m (X;Y) := \max_{(f(X),g(Y))\in S} \mathbb{E} [f(X)g(Y)] $$
where $S$ is the collection of pairs ...

**5**

votes

**0**answers

52 views

### Functional Equation of Zeta Function on Statistical Model

I've been studying [1] because I was interested in his ideas on the zeta function. I'll define it here (c.f. p. 31):
The Kullback-Leibler distance is defined as
$$
K(w)=\int q(x)f(x, w)dx\quad
f(x,w)...

**4**

votes

**1**answer

141 views

### Information for discovering an item-colour assignment in a combinatorial game

We are given a set $S=\{i_1, i_2, \ldots, i_n\}$ of items and a set $C=\{c_1, c_2, \ldots, c_m\}$ of colours. Each item in $S$ is tinted with one colour $c\in C$. Let $\mathcal{A}$ be the set of all ...

**4**

votes

**1**answer

133 views

### Generating bitstring combinations using a butterfly network

I'm using a butterfly network to generate a random combination of a bitstring of length $n$ and weight $w$. Let me clarify it with an example. Suppose I want a random bitstring of length 8 and Hamming ...

**4**

votes

**1**answer

194 views

### A balls into bins problem with combinatorial constraints

We are given $m$ balls and $n$ bins, with $m \ge n$. Each bin can contain at most $c$ balls (we assume that $c$ is an even integer). In a sequential fashion, at each time step, one ball is placed into ...

**2**

votes

**2**answers

139 views

### Lower bound Renyi divergence between two discrete probability distributions

I am trying to understand the proof of Lemma 1 in this paper (Section 9.2).
The proof shows that given a discrete probability distribution $P=(p_1,p_2,...,p_k)$ where $p_1 \geq p_2 \geq ... \geq p_k$,...

**1**

vote

**0**answers

62 views

### Jensen-Shannon Divergence of Sample Distributions

Given normal distributions with a single positional and variation parameter each, $p_1=\big[\mu_1, \sigma_1\big]$, $p_2=\big[\mu_2, \sigma_2\big]$, we define their Jensen-Shannon divergence as:
$$
\...

**2**

votes

**3**answers

167 views

### Asymptotic value of the Shannon entropy

I would like to evaluate the asymptotic value of the following sum:
$$f(N)=\frac{1}{2^N}\sum_{n=0}^{N} \binom{N}{n} \log_{2} \binom{N}{n}$$
This is related to the computation of the Shannon entropy. ...

**7**

votes

**1**answer

136 views

### Lower Bound of KL-Divergence Between Two Gibbs Measures

Suppose we have two Gibbs measures with densities
$$
p_f(x) \propto \exp(f(x)),\quad q_g(x)\propto \exp(g(x)).
$$
Consider the KL-divergence between $p_f$ and $q_g$, as a functional of $f$ and $g$, ...

**1**

vote

**1**answer

126 views

### Find probability of non-stationary inputs into Turing machine?

Consider some finite string $x=(x_1,x_2,...,x_{n-1},x_n)$ that is drawn from a non-stationary process. Would it be possible to use the algorithmic probability formula, defined by Solomonoff as,
$$
P_M(...

**1**

vote

**1**answer

57 views

### What is the distribution of a Cartesian power of a collection of iid uniform points? (renewed)

The following question was asked recently at http://www.4124039.com/questions/326631/what-is-the-distribution-of-a-cartesian-power-of-a-collection-of-iid-uniform-poi :
Take a rectangle with ...