Covers theoretical and experimental aspects of information theory and coding.

learn more… | top users | synonyms

2
votes
0answers
73 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
0answers
61 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
0answers
85 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
1answer
106 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
1answer
63 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
1answer
114 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
0answers
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
0answers
156 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
0answers
72 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
0answers
71 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
1answer
95 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
0answers
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
1answer
95 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
0answers
45 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
2answers
185 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
0answers
103 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
0answers
54 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
0answers
43 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
0answers
50 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
3answers
308 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
0answers
121 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
1answer
83 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
1answer
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
0answers
158 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
0answers
28 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
1answer
306 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
0answers
87 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
0answers
133 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
0answers
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
0answers
34 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
0answers
359 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
1answer
101 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
0answers
67 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
1answer
200 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
1answer
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
1answer
260 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
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
0answers
79 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
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
1answer
247 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
1answer
90 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
2answers
467 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
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
0answers
301 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
1answer
337 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
95 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
1answer
348 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 ...
3
votes
2answers
155 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 ...
1
vote
0answers
83 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
88 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 ...