19

For such questions, you often get the right intuition by thinking of "flat" random variables. That is, think of $X$ as the uniform distribution over a set $A$ of size $2^{H(X)}$ and of $Y$ as the uniform distribution over a set $B$ of size $2^{H(Y)}$. So, the question you're asking is (roughly speaking) what can you say about the size $|A+B|$ compared to $|...


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


16

You're right to think of hash functions in terms of "random bits produced". So if you have a hash function that produces a 64 bit hash, you can treat is as 4 16-bit hashes (by splitting), and so on. For the scheme described above (which should be attributed to Dillinger and Manolios; Kirsch/Mitzenmacher just analyzed it), that means you're correct; if ...


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


16

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


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

Gzip. Cilibrasi and Vitanyi have a really nice article where they use gzip as an approximation of Kolmogorov complexity to do clustering. Clustering by Compression


10

As you mention, it is possible to determine the optimal average success probability numerically, which can be done efficiently via semidefinite programming (see e.g. this paper by Eldar, Megretski and Verghese or these lecture notes by John Watrous), but no closed form expression is known. However, there are several known upper and lower bounds on the ...


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

There are enough connections between information theory and computational complexity to merit a graduate course, e.g. this one: http://www.cs.princeton.edu/courses/archive/fall11/cos597D/


9

There is no such $C$. Define $g\colon\mathbb{Z}_2^n\to\mathbb{R}$ by $$g(x_1,\dots,x_n)=\begin{cases} 2^{2n/3}&\text{ if $x_1=\dots=x_n=0$}\\ 1&\text{ otherwise.}\end{cases}$$ Then $g*g$ satisfies $$(g*g)(x_1,\dots,x_n)=\begin{cases} 2^{4n/3}+2^n-1&\text{ if $x_1=\dots=x_n=0$}\\ 2^{2n/3}\cdot 2+2^n-2&\text{ otherwise.}\end{cases}$$ Let $f=g/...


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


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


8

I had a brief look at this paper, and it appears that the answer to your question is yes (that is - no need for randomization). Also, the Introduction section surveys previous algorithms, information theoretic lower bounds and so on.


8

Such a bound is not possible. Consider the case where $f$ is the distribution that is uniform over some set $S$ of size $2^{\delta \cdot n}$, and let $\tilde{f}$ be the distribution that with probability $\delta$ outputs a uniformly distributed element of $S$, and otherwise outputs a uniformly distributed string. It is not hard to see that you can get from $...


8

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


7

Suppose we have $n$ points in $\ell_2^d$ and want to do a dimension reduction. If we want pairwise distances change by at most $1 \pm \epsilon$, then we can reduce our dimension from $d$ to $O(\log n / \epsilon^2)$. This is Johnson-Lindenstrauss Lemma. For a decade the best known lower bound for a dimension was $\Omega(\log n / (\epsilon^2 \log(1 / \epsilon))...


7

Many people have mentioned Kolmogorov complexity or its resource-bounded variants, but I think something closer to what you're looking for is the notion of (logical) depth. There are several variants on depth, but they all try to get at something like what you're talking about. In particular, neither purely random strings nor very highly ordered/repetitive ...


7

You're confused because the example didn't cover all possible cases, and you're extrapolating improperly. Negation is the operation 0 → 1, 1 → 0. This is reversible, and can theoretically be performed using an arbitrarily small amount of energy. Restore to one is the operation 0 → 1, 1 → 1. This is not reversible, and ...


7

A partial answer is that for even $k$ such a labeling does not exist. For a set of $t$ disjoint subsets $S_1, \ldots, S_{t}$ (of size $n/k$, let $f(S_1, \ldots, S_t)$ denote the sum of their values). Claim: if $t < k$ and $S_1 \cup \ldots \cup S_t \ne S'_1 \cup \ldots \cup S'_t$ then $f(S_1, \ldots, S_t) \ne f(S'_1, \ldots, S'_t)$. To see why the claim ...


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

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

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


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