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


17

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


16

In practice the only difference is that Boltzmann entropy deals with a thermodynamical constant $K_B$: $ H = -K_B\sum_{i=1}^{N} P_i log_e\ P_i $ i assume you already know that if $K_B=1$ you have Shannon entropy in a different base. However the conceptual backgrounds are important; probability of events (Shannon) and probability of a particle being in one ...


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


13

As has already been answered, Shannon entropy and Boltzman entropy are the same thing, although they are measured in different units. You also asked whether there is a practical link. It may not be practical yet, but the idea of algorithmic cooling uses the link between these two concepts, and has indeed been experimentally demonstrated.


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

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

Bob's best bet is to guess the $t$ values with largest probability. If you're willing to use Rényi entropy instead, Proposition 17 in Boztaş' Entropies, Guessing and Cryptography states that the error probability after $t$ guesses is at most $$ 1 - 2^{-H_2(\mu)\left(1-\frac{\log t}{\log n}\right)} \approx \ln 2 \left(1-\frac{\log t}{\log n}\right) H_2(\mu), ...


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


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

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


8

For channel capacity, it seems difficult to replace Shannon entropy by Kolmogorov complexity. The definition of channel capacity does not contain any mention of entropy. Using the Shannon entropy gives the right formula for channel capacity (this is Shannon's theorem). If you replaced the formula with Shannon entropy by a formula with Kolmogorov complexity, ...


7

As far as I know, people conjecture that for Polar codes and any fixed DMBSC (discrete memoryless binary symmetric channel), $\log M \leq nC - O(n^{1-c})$ for some absolute constant $c > 0$ and vanishing error probability should be possible (or in other words, in order to be $\epsilon$ close to capacity, only a polynomially large $n$ in $1/\epsilon$ would ...


7

Unfortunately there is no good answer to your question. John Pliam [PhD Thesis, 2 papers in the LNCS series] was the first to observe the disparity between Shannon entropy and expected number of guesses. His thesis is easy to find online. In section 4.3, by choosing a suitable probability distribution for $X$ (dependent on an arbitrary positive integer $N$) ...


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

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

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

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


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


5

A great example is the paper "Sorting and Entropy" by Kahn and Kim. The entropy method is used to find an algorithm that given a known poset $P$ and an unknon linear extension of $P$, find the linear extension by $O(\log |X|)$ queries where $X$ is the set of linear extensions of $P$.


5

In one form, your question is actually a clustering question that is addressed by the information bottleneck method. Roughly, $Y$ represents the rows of a joint distribution and $X$ represents the columns. The random variable $Z$ then represents a distribution over the rows ($Y$) that is highly compressed (because $I(Z;Y)$ is small) but represents the ...


5

The question this response was trying to answer, roughly: "What is a way to reveal information about the outcome of $n$ i.i.d. coin flips that helps you learn the bias of the coin, but wihout revealing too much about the individual bits?" Since the bits are i.i.d., the numbers $h$ and $t$ (number each of heads and tails) are completely sufficient to ...


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