Questions in Information Theory

learn more… | top users | synonyms

-1
votes
0answers
21 views

“Elements of Information Theory”: Some (basic) help needed here

I was following the textbook by Cover & Thomas (2006): Elements of Information Theory. (hyperlink is not owned by me) I have one question that has been irking for me some time. It is regarding ...
1
vote
0answers
32 views

Initialization of errata evaluator polynomial for simultaneous computation in Berlekamp-Massey for Reed-Solomon

This is a continuation of this post on SO. I am trying to implement an errata (errors-and-erasures) decoder for Reed-Solomon. My current approach is to use Berlekamp-Massey (because it's the most ...
7
votes
1answer
182 views

Information theory and convex optimization

I'm taking a graduate level course in information theory and I'm constantly struck by how much convex optimization there is in this subject. However, the proofs seem to shy away from using the full ...
0
votes
0answers
27 views

On a Generalized Maximal Correlation

I posted this question in here last week, but did not get any response. Given a pair of random variables $(X,Y)$ over a product space $\mathcal{X}\times \mathcal{Y}$, the maximal correlation ...
9
votes
4answers
353 views

The utility of Renyi entropies?

Most of us are familiar with — or at least have heard of — the Shannon entropy of a random variable, $H(X) = -\mathbb{E} \bigl[ \log p(X)\bigr]$, and all the related information-theoretic ...
15
votes
1answer
272 views

Information complexity of query algorithms?

Information complexity has been a very useful tool in communication complexity, mainly used to lower bound the communication complexity of distributed problems. Is there an analogue of information ...
1
vote
0answers
31 views

An upper bound for chi-square divergence in terms of KL divergence for general alphabets

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$ ...
4
votes
1answer
159 views

Introductions to steganography from an information-theoretic standpoint

Can I get some introductory references for steganography from an information-theoretic standpoint? I recently listened to a talk on it, and the speaker said that he knew of no good introductions to ...
3
votes
0answers
66 views

One kind of dependence relation between a pair of random variables

I have been working on privacy and come across a neat problem. Suppose two random variables $X$ and $Y$, over finite alphabets $\mathcal{X}$ and $\mathcal{Y}$, are given with joint distribution ...
1
vote
1answer
102 views

A Question on Convex Conjugate Duality for KL Divergence

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 ...
4
votes
2answers
104 views

Conditional entropy: $H(X | Y)$ large implies $H(X | Y, X \neq Y)$ large?

Suppose that $X$ and $Y$ are two random variables that are defined on the same support. Furthermore, suppose that $H(X | Y) = \log n$ for some $n$. I am now interested in how much the term $H(X | Y, X ...
3
votes
2answers
136 views

Lower bound proof for compressive sensing (Gel'fand widths)?

Let $x \in \mathbb{R}^n$ have $k$ non-zero entries. The main insight of compressive sensing is that there exist $m\times n$ matrices $A$ with $m = O(k \log n/k)$ such that any $x$ can be recovered ...
1
vote
1answer
117 views

Question about “typical set” in Shannon's source coding theorem

I was following the textbook by David Mackay: Information theory inference and learning algorithms. I have question on asymptotic equiparition' principle: For an ensemble of $N$ $i.i.d$ random ...
2
votes
0answers
115 views

Strong Dependence

I asked this question on MO, but no answer. I don't know if this definition has been already given. Suppose $X$ and $Y$ are two random variables over finite alphabets $\mathcal{X}$ and ...
0
votes
1answer
111 views

Source Coding Theorem: what happen when we go below N*H(x) bits?

I was following the textbook by David Mackay: Information theory inference and learning algorithms. I have question on Shannon's source coding theorem (p81): $N$ i.i.d. random variables each with ...
-1
votes
1answer
135 views

How can you prove that all halting probabilites are normal real numbers?

Wikipedia claims that any halting probability (Chaitin's constant) is a normal number. Since Chaitin's constant is uncomputble, how is a proof the the normalcy of the number possible? Computable ...
9
votes
3answers
244 views

Is there a generalization of information theory to polynomially knowable information?

I apologize, this is a bit of a "soft" question. Information theory has no concept of computational complexity. For example, an instance of SAT, or an instance of SAT plus a bit indicating ...
6
votes
0answers
29 views

Different definitions of optimal decompressors

Let $B^{<\omega}$ be the set of finite binary strings. I will only consider functions from $B^{<\omega}$ to $B^{<\omega}$. I recall the definition of the algorithmic complexity of a string ...
9
votes
1answer
274 views

A converse to Fano's inequality ?

Fano's inequality can be stated in many forms, and one particularly useful one is due (with a minor modification) to Oded Regev: Let $X$ be a random variable, and let $Y = g(X)$ where $g(\cdot)$ ...
2
votes
1answer
75 views

Sufficient Statistics of $X$ from $Y$

I am reading the paper New Monotone and Lower Bounds in Unconditional Two Party Computation by Wolf and Wullschleger. In Definition 2 on the third page, they define $f(x):=P_{Y|X}(\cdot|x)$ and they ...
1
vote
1answer
151 views

description of continuous probability distribution

The minimum description length of the realization of a random variable $x$ is given by the entropy of its probability mass function. It can be asymptotically communicated at this rate with an optimal ...
0
votes
0answers
68 views

deterministic randomness extractor and privacy

Suppose $X$ is a message which takes values on the set $\{x_1, \dots, x_m\}$ with probability distribution $P_X$. We transmit the message $X$ over the channel $P_{Y|X}$ which outputs $Y$ taking ...
6
votes
4answers
536 views

Expected empirical entropy

I'm thinking about some properties of the empirical entropy for binary strings of length $n$ when the following question crosses my way: ...
4
votes
0answers
69 views

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 ...
5
votes
0answers
101 views

Largest size for randomness extractor

Suppose we have a source $X$ with min-entropy $\ell$. A randomness extractor is defined as a function $f$ which satisfies the total variation $||f(X, R)-U_M||_{TV}\leq \epsilon$ where $R$ is an ...
1
vote
1answer
143 views

Good resources to learn loopy belief propagation

What are some of the good references to understand loopy belief propagation and the need for it? I am looking for both theory and applications (for instance in coding/information and learning theory). ...
4
votes
2answers
168 views

The length of non perfect binary 1 error correcting codes

I am interested in the best known number of code words in binary 1 error correcting codes of length $n$. I am aware of the Hamming code when $n=2^r-1$, but i would like to get lower bounds for other ...
4
votes
0answers
121 views

Lovasz Theta as a short certificate

Lovasz Theta Function provides short proof for the question, "is the Shannon Capacity of a graph($\Theta(G)$) greater than $r\in\Bbb R$?" if the answer is NO when $r$ is above a certain value (this ...
0
votes
1answer
78 views

grover's algorithm

Grover's algorithm searches an unstructured database (or an unordered list) with N entries. what type of data it works on? will it be possible to search data about some images that is stored in ...
6
votes
0answers
180 views

Physical Proof for P versus BPP

Lipton asks for a physical proof of $P\neq NP$. Can we even ask for a physical proof for understanding $P=BPP$ or $P\neq BPP$? Is there anything in physics that lets us avoid randomness? ...
0
votes
1answer
70 views

Mutual information and entropy to prove minimal Relevance Maximum Dependency

I'm reading through a paper on feature selection: Feature Selection Based on Mutual Information: Criteria of Max-Dependency, Max-Relevance,and in-Redundancy but I'm unable to understand parts of the ...
4
votes
0answers
96 views

Games where $\omega(G) < \omega^*(G) < \omega^{ns}(G) < 1$?

A two player game $G = (I,O,V,p)$ is such that, if two non-communicating players Alice and Bob are given questions $(x,y)\in I^2$ drawn from the probability distribution $p$, they are supposed to ...
1
vote
1answer
67 views

Numeral system information density

What is an "informational density" and why numeral system with the base of e (2,71828...) has the maximum informational density? How do you calculate "informational density" of a given numeral system? ...
4
votes
2answers
99 views

Reference Request: Error correction code for a random projection

I'm interested in a variant of the Binary Channel, where the bits aren't flipped with some probability, but rather they are completely erased. Output words therefore vary in length. I'm quite sure ...
0
votes
1answer
655 views

Difference between self-information and entropy

I get a bit confused about different definitions of entropy and/or self-information. Entropy? $$ H(X) = - \sum_{x \in X} P_X(x) \cdot \log{\left(P_X(x)\right)} $$ Self-information? $$ I(x) = - ...
6
votes
0answers
118 views

Information theoretic characterization and consequences of reductions between computational problems

For two computational problems $A$ and $B$ in complexity class C (let say $NP$), the existence of a reduction $A <_m^L B$ computable in class (say $L$) implies that $A$ is not computationally ...
0
votes
0answers
138 views

Can the self-information be infinite?

I was wondering about the self-information, the information content . If I have data and I measure different words in it, their probability and take the average mean of that, what is the lowest and ...
7
votes
2answers
147 views

Smoothly leaking information over time

Say I have a one bit random variable $X \in \{0,1\}$, and let $n$ be a natural number. I want a sequence of random variables $0 = X_0, X_1, \ldots, X_n = X$ s.t. ...
5
votes
0answers
284 views

Explanation of polar decoding?

Polar decoding, according to Arikan's paper, can be decoded using a successive cancellation (SC) decoder, which is based on calculating the likelihood ratio, as seen in the image below. How can I ...
8
votes
3answers
494 views

Kolmogorov Complexity applications in Number Theory

What are the applications of Kolmogorov Complexity in Number Theory and on proofs related fields? (The monograph by Li & Vitanyi doesn't have many applications related to Number Theory.) One of ...
1
vote
1answer
47 views

A theorem regarding statistically-hiding commitment schemes

Let $C_n$ be a non-interactive statistically-hiding commitment scheme, able to commit to an $n$-bit string. To commit to $m \in \{0,1\}^n$, the sender picks a random $r$ (of proper length), and sends ...
3
votes
1answer
144 views

On the Shannon Capacity of Cycles

Let $\alpha(C_{n}^{\boxtimes k})$ be independence number of $k$-fold strong product of an $n$-vertex cycle graph $C_{n}$. $\forall n > 6$, is $\alpha(C_{n}^{\boxtimes (k+r)})^{\frac{1}{k+r}} \geq ...
5
votes
1answer
192 views

Given discrete rvs X,Y, find Z s.t. I(Z;X) is high and I(Z;Y) is low. — known problem?

Consider the following problem. Let $X$ and $Y$ be discrete random variables. The goal is to find a random variable $Z$ such that, informally, $I(Z;X)$ is high and $I(Z;Y)$ is low. More precisely, ...
3
votes
2answers
1k views

Comparison Huffman Encoding and Arithmetic Coding dependent on Entropy

Where can I get an understanding of how Arithmetic Coding and Huffman Encoding compare as entropy increases. I know Arithmetic Coding is better for low entropy distributions, but how can I get a sense ...
13
votes
0answers
149 views

Fano's inequality in the high error regime

Fano's inequality says that given a random variable $X$, and a random variable $Y$ that "guesses" $X$ correctly with some probability, we can lower bound the information that $Y$ gives on $X$. More ...
1
vote
1answer
188 views

How to choose a correct prior

Consider a Bernoulli experiment, such as flipping a not necessarily fair coin, which results in a positive outcome (heads) with probability $p$ and with a negative outcome (tails) with probability ...
7
votes
1answer
354 views

Can Polar Codes (or any other efficient codes) reach the second order capacity?

In channel coding, it is known (e.g. Yury Polyanskiy's thesis, and the arxiv article A Tight Upper Bound for the Third-Order Asymptotics of Discrete Memoryless Channels) that certain codes, for ...
2
votes
0answers
41 views

Boltzmann sampling software

I'm looking for an implementation of Boltzmann sampling for combinatorial structures. Recent paper in the area for context: ...
1
vote
0answers
54 views

Finding Most Compressible Vector Within Bounds?

Given large positive integers $m$ and $n$: Let $S$ be the set of integers $\{1,2,\dots,m\}$ We are given as input two vectors $L$ and $U$ both over $S^n$ such that: $$\bigwedge_{i=1}^{n}{L_i \le ...
7
votes
1answer
195 views

Conditional Kolmogorov Complexity: $K(y|x^*)$ vs $K(y|x)$

In "The Similarity Metric" Li, et al give the first definition of the normalized information distance as $\displaystyle d(x,y) = \frac{\max \left \{ K(x|y^*), K(y|x^*) \right \}}{\max \left \{ K(x), ...