18 votes

The utility of Renyi entropies?

Renyi entropy is analogous, in some sense, to $\ell_p$-norms, so let's first recall why those norms are useful. Suppose we have a vector of numbers $a \in \mathbb{R}^n$. We want to have a single ...
user avatar
  • 5,190
18 votes
Accepted

Entropy and computational complexity

Yes, but most of the work so far (except very recently, see below) has focused on turning irreversible computations into reversible ones, thereby hoping to avoid any entropy generation. (Note: there ...
user avatar
16 votes
Accepted

The utility of Renyi entropies?

Consider trying to make atomic guesses for an unknown random variable $X$ distributed over some finite set $A.$ In Shannon entropy, it is assumed that you can query bit by bit, i.e., if $A=\{1,\ldots,...
user avatar
  • 1,996
12 votes
Accepted

A converse to Fano's inequality ?

Consider the following reconstruction procedure $P(y)$: given $y$, output $x$ such that $\Pr[X = x \mid Y = y]$ is maximized. The probability that this procedure succeeds is $\max_x \Pr[x \mid Y = y]$....
user avatar
  • 3,708
11 votes
Accepted

A Question on Convex Conjugate Duality for KL Divergence

To make it easier let's assume $X$ is finite, of size $n$ and associate the density of $Q$ with an $n$-dimensional vector $q$. Assume also that $q$ is everywhere positive - otherwise replace $X$ with ...
user avatar
11 votes

The utility of Renyi entropies?

Renyi entropy (of order 2) is useful in cryptography for analyzing the probability of collisions. Recall that the Renyi entropy of order 2 of a random variable $X$ is given by $$H_2(X) = - \log_2 \...
user avatar
  • 10.5k
10 votes
Accepted

What are some standard books/papers on Information Theory?

This is a list of recommended books, videos and web sites copied from the Further Readings section of my book on information theory (given at the end of this post). Applebaum D (2008). Probability ...
user avatar
9 votes

description of continuous probability distribution

You're confusing the Shannon entropy of a discrete probability distribution with the differential entropy of a continuous probability distribution. The minimum distribution length is only given by the ...
user avatar
9 votes
Accepted

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

Yes. Time-bounded Kolmogorov complexity is at least one such "generalization" (though strictly speaking it's not a generalization, but a related concept). Fix a universal Turing machine $U$. The $t(n)$...
user avatar
7 votes
Accepted

Does Huffman coding always produce shorter codes than the Shannon code?

This is actually problem 5.12 in Cover and Thomas's information theory textbook; show that the probability distribution ${1/12,1/4,1/3,1/3}$ gives a counterexample. And if you want a really nice ...
user avatar
7 votes
Accepted

Relation between group theory and information theory

Sadly, group structure is nearly so limited that there isn't much one can do with it to be of use in information theory, thus the literature is prone to be fairly sparse. Even Abelian groups aren't ...
user avatar
7 votes
Accepted

Why don't we transmit at rates higher than the Shannon capacity if we are going to get a nonzero probability of error anyways ?

Look at the strong converse to Shannon's theorem: for rates above the channel capacity, if $n$ bits are to be transmitted, the probability of error is exponentially close to 1, so $1-e^{c n}$ for ...
user avatar
7 votes
Accepted

Improving Bloom filter - can we distinguish elements of a database using less than 2.33275 bits/element?

2.09 bits per element is practically achievable. See http://cmph.sourceforge.net/: "[Compress, Hash, Displace] can generate MPHFs that can be stored in approximately 2.07 bits per key." 1.44 bits per ...
user avatar
  • 11k
7 votes

Is algorithmic information theory still evolving?

A modern tweak on algorithmic information theory is algorithmic randomness which was developed intensively in the 2000s (2009-2009) and is still quite active. The most notorious open problem there ...
user avatar
7 votes
Accepted

Is a binary sequence computable iff the Kolmogorov complexity of its initial segments is bounded?

Chaitin in his 1976 paper Chaitin, Gregory J., Information-theoretic characterizations of recursive infinite strings, Theor. Comput. Sci. 2, 45-48 (1976). ZBL0328.02029. studied sets such that ...
user avatar
6 votes

What is empirical mutual information?

I agree with @usul. I've also never seen the term empirical mutual information mentioned, but I've seen the term empirical entropy quite a lot, especially in the compression community. The definition ...
user avatar
  • 1,101
6 votes

Showing that interval-sum queries on a binary array can not be done using linear space and constant time

I wouldn’t be so sure such an algorithm doesn’t exist; there are certainly algorithms that get very close. Below, $\log n$ is $\log_2n$, $\log^{(k)}n$ is $\mathop{\underbrace{\log\dots\log}_{k\text{ ...
user avatar
6 votes
Accepted

Showing that interval-sum queries on a binary array can not be done using linear space and constant time

I believe that what you are looking for is a compact data structure supporting the rank operation. See... https://en.m.wikipedia.org/wiki/Succinct_data_structure Specifically, you can modify Emils (...
user avatar
6 votes
Accepted

Can entropicly secure encryption algorithms be used on low-entropy messages by adding noise

Here is the problem: if $M$ has low entropy (for example, if the attacker has side information that narrows $M$ down to just two possible messages), then conditioned on $M+K$, the key $K$ also has low ...
user avatar
6 votes
Accepted

Converting a Bernoulli to a Gaussian

Suppose you had such a randomized procedure that takes a value in $\{-1,1\}$ and outputs a real number. Let $P$ and $Q$ be the output distribution on input $+1$ and $-1$ respectively. Consider the ...
user avatar
  • 76
5 votes

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

Marzio's comment gives a link to a formal proof that the Chaitin constant $\Omega$ is normal. Let me give some higher level intuition. $\Omega$ is definened to be an algorithmically random number, ...
user avatar
5 votes

Information complexity of query algorithms?

Yes, information theory is useful for proving lower bounds on the query complexity of problems in Computer Science. Alexander Golynski gave a good example in his ground breaking paper titled "Cell ...
user avatar
  • 2,511
5 votes
Accepted

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

$m = \Omega(k \log(n/k))$ is a lower bound for any compressive sensing scheme, not just $\ell_1$-minimization using RIP guarantees on the measurement matrix. In fact, the recovery algorithm need not ...
user avatar
  • 6,950
5 votes
Accepted

Is joint Kolmogorov Complexity order invariant?

You don't need symmetry of information. The invariance theorem does the trick. Let $p$ the smallest program such that $U(p) = \langle x, y\rangle$. One way of producing $(y, x)$ is to take make a ...
user avatar
  • 449
5 votes

Information-theoretic Diffie-Hellman

No, there is no information-theoretic analog that is secure against computationally-unbounded adversaries. To form an analog, we'd need an injection $\varphi$ that maps $x$ in fine representation to $...
user avatar
  • 10.5k
5 votes

Kolmogorov Complexity of a Decidable Language

Yes, depending on what kinds of inputs you consider (see below). $KC(x) =^* KCDL(L_x)$, where $L_x$ is the language which consists only of the string $x$, and $=^*$ means equals up to an additive ...
user avatar
5 votes

Generating $k$ random bits from a pdf with entropy $H(p) = k$

The relevance of Shannon entropy is to repeated sampling: Given $n$ independent samples from a source with binary Shannon Entropy $k$, you can extract $nk(1+o(1)$ i.i.d. uniform bits as $n$ tends to ...
user avatar
5 votes

Information and Coding Theory Texts

Maybe not so math oriented but with math rigor: Elements of Information Theory by Thomas M. Cover, Joy A. Thomas Essential Coding Theory by Venkatesan Guruswami, Atri Rudra and Madhu Sudan
user avatar
5 votes
Accepted

Maximal uniquely decodable codes

Maximal implies sharp, even for uniquely decodable codes. Proof: If there is some sequence of letters which will never appear in the middle of a concatenation of codewords, then we can add this ...
user avatar
4 votes
Accepted

Introductions to steganography from an information-theoretic standpoint

Here is a brief overview and introduction to steganography: Christian Cachin. Digital steganography. In Henk C.A. van Tilborg, editor, Encyclopedia of Cryptography and Security. Springer, 2005 Since ...
user avatar
  • 10.5k

Only top scored, non community-wiki answers of a minimum length are eligible