Tag Info

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

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  finitary isomorphism theorem. See also - below.  M. Keane and M....

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

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

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

2

It's the $\alpha^{\mathrm{th}}$ moment of the Tribus surprisal. This generalizes the statement that entropy = expected surprisal. Or in Ross's textbook, "expected surprise".

1

This is called "output entropy". Suppose you have a communications channel that takes a string and then outputs a random string within a relative $\delta$ radius of it. If you use the input distribution $X$ for communicating over this channel, the entropy of the output distribution would be the quantity you are after.

1

So we ended up calling this quantity the $\alpha$th moment of information and proving some inequalities about it: https://arxiv.org/abs/2004.12680 (paper to appear in the NIPS 2021 conference).

1

If I understand right what "average volume" means here, I don't think this is correct. For example, let's say you map $n$-bit strings (under uniform distribution) to $n$-bit strings as follows: Given an input $x$, if the first bit is 0, output $x$, and otherwise output "1". The average volume would be $\frac{1}{2}(2^{n-1}+1)$, whereas the $2^{H(X|\hat{X})} ... 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)\$...

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