# Tag Info

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 $|... 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 ... 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. 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 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 ... 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 The meaning is a bit string$x$which is distributed uniformly on$\{0,1\}^{|x|}$. 5 I believe this paper by Harremoes proves that if you take a sum of$n$Bernoulli random variables$Z_1,Z_2,...,Z_n$, each with parameter$p$then then entropy of$Z_1+Z_2+...+Z_n$is less that the entropy of a Poisson distribution with the mean$np$. From a quick look at Wikipedia, it seems that for large values of$np$the entropy of a Poisson is$\frac{1}{...

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

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

Here's one way to look at it, based on usul's comment. Let the gains of each expert $i$ at time $t$ be given by $g_i^t$. Then the expected gains of the algorithm are: $$\sum_{u=1}^{t-1}\sum_i p_i^t g_i^u$$ We can then define the potential function $$\Phi=\epsilon \sum_{u=1}^{t-1}\sum_i p_i^t g_i^u + \sum_i p_i^t \ln \left(\frac{1}{p_i^t}\right)$$ Where ...

4

(Edited from previous version, 2014-04-08.) I believe that the answer is $\epsilon_n \to \log(\sqrt{e}) \approx 0.7213475...$ where the logarithm is base 2. This seems to match simulation results. I don't have a full formal proof, but give the heuristic approximations/calculations. I think it's easier to note that your question is equivalent to: What ...

3

This is very much a partial answer to my question. I'm hoping for a much better bound (or a counterexample). I managed to show a very weak bound. It is not very useful, but it does at least show that uniform convergence can be bounded using entropy. As Aryeh observes, it suffices to bound $\mathbb{E}[\|\overline X - \mu\|_\infty]$. First, use the duality ...

3

First, let's use McDiarmid's inequality to conclude that $$\mathbb{P}\left[|| \bar X - \mu ||_\infty \ge \mathbb{E}|| \bar X - \mu ||_\infty + \varepsilon \right] \le e^{-2n\varepsilon^2},$$ so it remains to bound $\mathbb{E}|| \bar X - \mu ||_\infty$. Using Jensen's inequality, $$(\mathbb{E}|| \bar X - \mu ||_\infty)^2\le \mathbb{E}|| \bar X - \mu ||_\... 3 I think you can show it as follows, and even get a better constant in the end. Forewarning, there's enough cleverness here that I'm kind of suspect that everything is right. But the basic idea is simple enough: reduce to the case where X and Y take values in \{0,1\}, where we can exploit a nice relationship between covariance and total variation ... 3 Because an optimal prefix free code, e.g. a Huffman code, can be shown to be within one bit of source entropy. This is certainly in Cover and Thomas, I am pretty sure. 3 Here is a proof that the quantity # that OP considers tends to n(1-o(1)). Claim: #=n-o(n) First, note that for any function f:\{0, 1\}^n \rightarrow \mathbb{R}, \frac{1}{2^n} \sum_{w \in \{0,1\}^n} f(w) is exactly the same as \mathbb{E}_{w \in \{0,1\}^n} f(w). So you're asking whether \mathbb{E}_{w \in \{0,1\}^n} H(w) = 1-o(1). To see this, ... 3 Self-information applies to an individual outcome, x. It measures how surprising that specific outcome is. The entropy of process X is the average amount of Shannon self-information something coming out of X will have, assuming that things come out according to the P_X distribution. It's the average amount of surprise. Let's say we have a random ... 3 The entropy refers to a set of symbols (a text in your case, or the set of words in a language). The self-information refers to a symbol in a set (a word in your case). The information content of a text depends on how common the words in the text are wrt the global usage of those words. E.g. "Next saturday morning" should have less self-information (as a ... 3 I am interested in "empirical entropy" like you and the earliest paper I find was that from Kosaraju like the user "Marzio De Biasi" told in his comment. But in my opinion the real definitions of "empirical entropy" are made later by generalizing the former concepts: "Large Alphabets and Incompressibility" by Travis Gagie (2008) "Emprical entropy" by ... 2 I just found the following paragraphs from J. R. Pierce, An Introduction to Information Theory, p.206, which I surmise would also support the thinking that one could practically use a computer and a deterministic program to turn a string A into a string B of higher Shanon entropy: "We can regard any process which specifies something concerning which state a ... 2 Via Michael Kass: let Y(t) be a Wiener process starting at Y(0) = X, and define$$f(t) = H(X~|~Y(t))$$Then f(0) = 0, f(\infty)=1, and f(t) is smoothly strictly increasing in between. Thus, for any k we can find 0 \le t \le \infty s.t. X_k = Y(t) has the desired conditional entropy (t will be a decreasing function of k). 2 For convenience let H(X|Y) = \log(n), then$$ -\infty ~~\leq~~ H(X|Y) - H(X|Y,X\neq Y) ~~\leq~~ \log\left(\frac{n}{n-1}\right) $$and both sides have tight examples (i.e. as p\to 0 it can be arbitrarily negative, and your example matches the upper bound). More specifically, if p = \Pr[X \neq Y], then:$$ H(X|Y) - H(X|Y,X\neq Y) ~~ \geq ~~ -\frac{(1-...

2

This might be a partial answer to your question: Let $X$ and $Y$ be random variables with the same range. Let $Z$ be the indicator of the event $X \ne Y$. By the chain rule, $$H(X|Y,Z) = H(X,Z|Y)-H(Z|Y).$$ Since $Z$ is determined by $X$ and $Y$, we have $H(X,Z|Y)=H(X|Y)$. Now, by the definition of conditional entropy, H(X|Y,Z) = \underset{z \leftarrow Z}{\...

2

The details are on page 3 of the paper Algorithms, games, and evolution by Erick Chastain, Adi Livnat, Christos Papadimitriou, and Umesh Vazirani. They explain how the multiplicative weights update rule $x_i^{t+1}(j) = \frac{x_i^t(j)}{Z^t} (1 + \epsilon u_i^t(j))$ can be recovered by imagining that we want to design an update rule that maximizes some convex ...

1

(Too long for a comment.) There are two aspects to your question. There is the idea of a time-"space" tradeoff, and the idea of entropy as a measure or bound for how hard this tradeoff must be for a problem. Both aspects have some issues relating to how theorists usually study these problems. Here is why and some suggestions. Regarding entropy: This is an ...

1

Disclaimer: This is based on generic information theory knowledge only. Too long for a comment. Summary: The pointwise product of your two plots should go to some limit, as the relevant blocklengths and sequence lengths increase. I don't know if this applies to DNA but in theory if your sequence is ergodic (stationary, and time averages are the same as ...

1

The function $f$ maps $x$ to the conditional distribution of $Y$ given that $X = x$. This is a "deterministic" function. The expression $f(X)$ is a random variable depending on $X$. When $X = x$, the value of this random variable is $f(X) = f(x)$. In words, the random variable $f(X)$ gives the distribution of $Y$ conditional on the value of $X$. Given $f(X)$...

1

I am not sure what you are talking about when you use the local/global qualifiers on Shannon's entropy and Kolmogorov's complexity. So correct me if I am wrong. Shannon's entropy is computable. Kolmogorov's complexity is not. Therefore they do not describe the same problem. You could see Shannon's entropy as an upper bound to Kolmogrov's complexity.

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