18

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 number that represents, in some sense, how does the typical element of $a$ look like. One way to do so is to take the average of the numbers in $a$, which roughly ...


18

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 is an important difference between energy needed to make a computation run, and entropy generated by the computation and put out into the environment, typically ...


15

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,N\}$ you can ask: Is $X\in \{1,\ldots,N/2\}$ ? (assume $N$ even or use floor/ceiling functions) In crypto and some decoding scenarios this is not realistic. ...


12

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]$. This is also $2^{-H_\infty(X | Y = y)}$, where $H_\infty(X \mid Y = y)$ is the min-entropy of the random variable $X$ conditioned on $Y = y$. We know that $H_\...


11

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 the support of $q$. Then the conjugate is $$ f^*_q(x) = \sup_p\ \langle x, p \rangle - \sum_{i = 1}^n{p_i\log(p_i/q_i)}. $$ where the supremum is over the ...


11

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 \sum_x \Pr[X=x]^2.$$ It turns out that $H_2(X)$ lets us measure of the probability that two values drawn i.i.d. according to the distribution of $X$ happen to be ...


10

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 and Information: An Integrated Approach. A thorough introduction to information theory, which strikes a good balance between intuitive and technical explanations. ...


9

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)$-time-bounded Kolmogorov complexity of a string $x$ given a string $y$ (relative to $U$), denoted $K^t_U(x | y)$ (the subscript $U$ is often supressed) is ...


9

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 Shannon entropy for discrete probability distributions. What the fact that the differential entropy is 0 for this probability distribution means is that for ...


7

Here is another approach, based on information theory and heavily inspired by @usul's answer. It shows that $\epsilon_n=O(1)$ with very few calculations, and can be used to prove that $\epsilon_n \rightarrow \log_2 \sqrt{e}$ and to derive good estimates on the rate of convergence with less calculations than @usul's approach. In fact, I find a closed-form ...


7

Here is a table of the best known (linear and non-linear) binary codes for distance 3, for $n \leq 512\,$. Distance 3 is equivalent to being able to correct one error. The table only gives you the number of codewords, but the references given in the table will tell you how to construct the codes themselves. The best known codes for $n$ not in this table can ...


7

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 counterexample, consider the many non-isomorphic Huffman trees you can make when you have probabilities proportional to $$1,1,1,2,3,5,8,13,21,34$$ (the Fibonacci ...


7

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 some constant $c$ depending on the channel. Also, look at rate distortion theory. This gives a formula for the highest rate at which you can transmit if you ...


7

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 element is optimal. See "Hash, displace, and compress" "Improved Bounds For Covering Complete Uniform Hypergraphs" Data Structures and Algorithms , Vol. 1: ...


7

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 may be whether Kolmogorov-Loveland randomness (in which martingales are computable but are allowed to bet on bits out of order) is the same as Martin-Löf ...


7

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 there exists b ∈ℕ with $$\forall n\quad C(A\upharpoonright n)\leq C(n)+b.$$ where $C$ denotes the plain Kolmogorov complexity. These sets are known as C-trivial ...


6

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 of empirical information is $-\Sigma p_i \log p_i$, where $p_i$ are the empirical probabilities, i.e. the fraction of the time that each value appears in your ...


6

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{ times}}}n$, $\log^*n$ is iterated logarithm, and $\tilde O(t(n))$ is $O(t(n)\operatorname{polylog}(t(n)))$. Proposition: There are algorithms that achieve ...


6

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 (first) solution to remove the pop count operation and replace it with a lookup table (for the details see the wiki article). By reducing the size of a block to (...


6

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 enough structure. Even basic abstract algebra texts which have some basic coding theory applications generally provide examples using field theory or linear ...


6

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 entropy (there are only two possibilities for $K$). If the eavesdropper stores the first message (which was an encryption of $K$), then she can use it to ...


6

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 extreme case of $\mu = +1$. In this case $Y = +1$ for sure, and you are outputting a sample from $P$, which means that $P$ should be an $\mathcal{N}(\nu, 1)$ ...


5

I think the term is deletion channel. As the Wikipedia article says, this "should not be confused with the binary erasure channel".


5

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, in the Kolmogorov complexity sense. Check this beautiful answer by Laurent for a quick description of algorithmic randomness, or the wiki page. Or check the book ...


5

$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 be polynomial time, and the measurement matrix may be adaptive (in the sense that the $i$'th row of the matrix can depend on the inner product of the input ...


5

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 probe lower bounds for succinct data structures", presented at SODA 2009. He uses information theory to prove a lower bound on query complexity, which in turns ...


5

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 program $q$ that runs whatever program it is given as input, interprets the output as a pair, and flips the two parts. This gives you a program $\overline{q}p$ to ...


5

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 $x$ in coarse representation. But then Diffie-Hellman involves Alice sending $\varphi(x)$ publicly, and Bob sending $\varphi(y)$ publicly. An eavesdropper can ...


5

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 constant. The reverse is probably not possible (I think I proved this at one point but can't find it right now). The idea is that Kolmogorov complexity can be ...


5

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 infinity with probability tending to 1. This follows e.g. from the Keane-Smorodinsky [1] finitary isomorphism theorem. See also [2]-[5] below. [1] M. Keane and M....


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