Covers theoretical and experimental aspects of information theory and coding.

**8**

votes

**1**answer

78 views

### Digital physics and “Gandy-like” machines

Various physicists, famously John Wheeler, have asserted that physical information is the central object of study in physics, in the sense that an object or concept is "physically meaningful" if it ...

**2**

votes

**3**answers

63 views

### Quadratic estimation error differential entropy

I am reading the book "Elements of information theory" by thomas M. Cover and Joy A. Thomas, second edition. In page 255 of the book there is a theorem:
For any random variables $X$ and estimator ...

**4**

votes

**1**answer

115 views

### Can samples be compressed?

The Fisher information of a random variable $Y$ about a parameter $\theta$ upon which the probability of $Y$ depends is:
$\mathcal{I}_Y(\theta)= -E\left[\left.\strut \frac{\partial^2}{\partial ...

**2**

votes

**0**answers

82 views

### Maximum number of $4$-cycles

Suppose we have a balanced bipartite planar maximum degree $k$ graph.
How many such graphs on $2n$ vertices have at most $f(n)$ maximum number of $4$ cycles for a given function $f:\Bbb ...

**4**

votes

**0**answers

64 views

### Mutual Information - Correlation, Continuous Random Variables

For the Gaussian case $I(X,Y)=f( \varrho )$ where $\varrho $ is the correlation coefficient, and $f$ is a known increasing function. Is there any known joint distribution where the $f$ is not strictly ...

**0**

votes

**0**answers

88 views

### Does this set of (structured) equations always have a solution?

Let $r_1,\ldots,r_K$ be arbitrary positive numbers.
Does
$$|\mathcal{A}|\log\left(1+\frac{1}{|\mathcal{A}|}\left(\sum_{n\in \mathcal{A}} \sqrt{x_n(\exp(r_n)-1)}\right)^2\right)\leq \sum_{n\in ...

**3**

votes

**1**answer

107 views

### Sharpened Pinsker inequality for special case

Let $B(p)$ denote the Bernoulli distribution over $\{0,1\}$ and $B(p)^n$ the corresponding product distribution over $\{0,1\}^n$. For $n>1$ and $0<x<1$, define
$$P_n(x):=B(\frac12+\frac ...

**4**

votes

**2**answers

69 views

### About optimization with Renyi divergence

Can someone link me to some pedagogic example of computing the Renyi divergence between two discrete/continuous distributions? Like examples where someone has been able to obtain a neat closed form ...

**2**

votes

**1**answer

119 views

### About Renyi entropy

If one is given a joint probability distribution over a finite set of discrete random variables then I guess there a notion of $\alpha-$Renyi entropy defined for it as $S_\alpha (X_1,..,X_n) = ...

**1**

vote

**0**answers

50 views

### variance of log of ratio of chi-square variables

Let X be a chi-square variable with two degrees of freedom.
Let A and B be to arbitrary constants, with $A>B>0$.
I need the variance of
$Y=\log(1+AX)-\log(1+BX).$
The mean is, maybe not ...

**1**

vote

**0**answers

161 views

### “Kolmogorov complexity” of models of computation

This question was partly inspired by my learning about John Tromp's binary lambda calculus and similar minimal languages such as Jot. A more detailed discussion of some of these ideas is in Michael ...

**3**

votes

**0**answers

75 views

### An inequality involving conditional variance and its connection to information theory

Given absolutely continuous random variables $(X, Y)$ with joint distribution $P_{XY}$, we construct $Z:=\sqrt{\gamma} Y+N_\mathsf{G}$ where $N_\mathsf{G}\sim N(0, 1)$ and is independent of $(X,Y)$ ...

**3**

votes

**0**answers

78 views

### How does Jensen Shannon divergence and KL divergence correlate?

I am wondering if there is way to derive the correlation between Jensen Shannon divergence and KL divergence for two distributions: P and Q, in order to show that if JSD(P,Q) decreases, KLD(P,Q) ...

**2**

votes

**1**answer

96 views

### An Inequality Regarding the Squared Conditional Variance

Given absolutely continuous random variables $(X, Y)$ with joint distribution $P_{XY}$, we construct $Z:=\sqrt{\gamma} Y+N_\mathsf{G}$ where $N_\mathsf{G}\sim N(0, 1)$ and is independent of $(X,Y)$. ...

**1**

vote

**0**answers

73 views

### Increase mutual information for binary symmetric channel

I have a question about increasing mutual information for the binary channel. Assuming there is an independently $K$ dimensional binary source signal denoted by $X=[X_1, X_2, \cdots, X_K]$, a parallel ...

**1**

vote

**1**answer

96 views

### Do there exist random variables that force transitivity of dependence? [closed]

In general, statistical dependence is not transitive. If $Y$ and $X_{1}$ are dependent, and $Y$ and $X_{2}$ are dependent, then $X_{1}$ and $X_{2}$ are NOT necessarily dependent.
However, in some ...

**0**

votes

**0**answers

46 views

### Maximal Correlation with Weak Gaussian Perturbation

Let a pair of random variables $(X,Y)$ be continuous random variables (i.e., they both have density with respect to Lebesgue measure) with joint distribution $P_{XY}$. The maximal correlation ...

**7**

votes

**2**answers

190 views

### concentration inequality for entropy from sample

Consider a measure $\mu$ on a finite set, and let $x_1, \ldots, x_n$ be i.i.d samples from $\mu$. Then the expression $S_n = -\frac{1}{n} \sum_{i=1}^n \log \mu(x_i)$ converges by a.s. to the entropy ...

**6**

votes

**0**answers

107 views

### Maximal Correlation versus Correlation Coefficient When one RV is Gaussian

Let a pair of random variables $(X,Y)$ be continuous random variables (i.e., they both have density with respect to Lebesgue measure) with joint distribution $P_{XY}$. The maximal correlation ...

**0**

votes

**0**answers

56 views

### Is there a geometric meaning behind these specific triples?

Consider the set of triples $(g_1,g_2,g)\in(\Bbb R^+)^3$ such that $$\log g=(\log g_1)(\log g_2)$$
Is there any geometric or information theoretic meaning behind such triples?
We have $$2\log g=2 ...

**2**

votes

**1**answer

74 views

### Do product distributions (or graph products) eventually cluster as more products are taken?

Say we have a joint distribution on a finite alphabet $\mathcal{X}\times \mathcal{Y}$. It could be a communication link where we want to send a random message $X$ over a channel, but it gets garbled ...

**1**

vote

**0**answers

51 views

### How effective is using local property to test Shannon capacity?

A key tool in graph theory is the laplacian which is a local property. We can form a semidefinite programming and get an upper bound for Shannon capacity using laplacian.
Shannon capacity is ...

**12**

votes

**3**answers

312 views

### What characterizations of relative information are known?

Given two probability distributions $p,q$ on a finite set $X$, the quantity variously known as relative information, relative entropy, information gain or Kullback–Leibler divergence is defined ...

**1**

vote

**0**answers

123 views

### Chain Rule for Maximal Correlation

Let a pair of random variables $(X,Y)$ be defined over finite alphabet $\mathcal{X}\times \mathcal{Y}$ with joint distribution $P_{XY}$. The maximal correlation $\rho(X;Y)$ between $X$ and $Y$ is ...

**1**

vote

**1**answer

86 views

### An inequality for Maximal Correlation over a Markov Chain

Let a pair of random variables $(X,Y)$ be defined over finite alphabet $\mathcal{X}\times \mathcal{Y}$ with joint distribution $P_{XY}$. The maximal correlation $\rho(X;Y)$ between $X$ and $Y$ is ...

**1**

vote

**1**answer

137 views

### Uniquely describing a graph

According to answers here http://math.stackexchange.com/questions/1524598/a-general-incidence-problem// an unigraph comes from unigraphic degree sequences if it can be uniquely determined by its ...

**2**

votes

**0**answers

161 views

### Capacity of a channel with random phase rotation

Consider a wireless channel $h=e^{j\theta}$, where $\theta$ is a uniform random variable in $[0,2\pi]$ independent of the input messages and the independent of the noise. The channel randomly rotates ...

**0**

votes

**0**answers

29 views

### Is it possible to estimate the Interaction information of three variables without knowing their joint distributions?

I want to have a measure of the "synergy" between two players in a game. Each player has its own win ratio (won/played), which I'm modeling as two binomial distributed random variables X and Y. A ...

**5**

votes

**1**answer

311 views

### An Inequality of KL Divergence

Given two probability distributions $P$ and $Q$ defined over a finite set $\mathcal{X}$, one can define the KL divergence between $P$ and $Q$ as
$$D(P||Q):=\sum_{x\in ...

**1**

vote

**0**answers

88 views

### Maximize mutual information

Assume $P \in \mathbb{R}^{n \times n}$ describe the joint distribution of the random variable $J$ over the finite set $\mathcal{X}\times \mathcal{X} $.
I am interested in finding a right stochastic ...

**7**

votes

**0**answers

135 views

### De Bruijn sequence inside De Bruijn sequence

A binary De Bruijn sequence of index $n$ is a circular sequence $S=a_1a_2\ldots a_{2^n}$, with $a_i∈\{0,1\}$, and such that each of the $2^n$ binary $n$-tuples occurs exactly once in $S$.
What is ...

**6**

votes

**0**answers

94 views

### irregular LDPC code construction algorithm

I want to construct a sparse random binary matrix ${{\bf{H}}_{m \times n}}$ that has the following properties
1- Faction of columns of weight $i$ is ${v_i}$ .
2- Fraction of rows of weight ...

**0**

votes

**0**answers

35 views

### Reference on interaction information

I am looking for the most complete reference on interaction information/co-information/multivariate mutual information.
What are the properties of such quantities? Are they convex, like entropy? When ...

**13**

votes

**0**answers

369 views

### Research situation in the field of Information Geometry

I am now doing an article survey on the field of information geometry started by S.Amari and Barndorff-Nielson. I want to know some research situation in this field.
I have read (4) and parts of (3). ...

**3**

votes

**1**answer

106 views

### Effects of many degree-2 variable nodes in the Tanner graph during the decoding of LDPC codes

Suppose that we have a LDPC code $C$ with a $(n -k )\times n $ parity check matrix $H$, and there exist approximately $ \sqrt n$ numbers of degree-2 columns. It means that there are approximately ...

**0**

votes

**0**answers

68 views

### Efficient recognition of sequences sortable by transpositions?

While reading the post, Probability of generating a desired permutation by random swaps, by Aaronson, I got interested in this sorting problem:
Input: a sequence $A$ of $2N$ positive integers.
...

**4**

votes

**1**answer

219 views

### Do binary symmetric channels maximize mutual information?

Consider the following setup: $(X, Y)$ is a doubly symmetric binary source with parameter $0 < p < 1/2$, i.e., $X \sim \text{Bernoulli}(1/2)$, $Z \sim \text{Bernoulli}(p)$ and $Y = X \oplus Z$. ...

**2**

votes

**1**answer

108 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

**1**answer

261 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

**0**answers

35 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

**0**answers

85 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

**1**answer

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

**7**

votes

**1**answer

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

**5**

votes

**1**answer

93 views

### Rate-Distortion theory: What is the distribution of distortion on an optimal Gaussian 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

**2**answers

472 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

**0**answers

42 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

**0**answers

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

**1**

vote

**1**answer

352 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

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

**1**

vote

**1**answer

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