6
votes
Accepted
Can entropicly secure encryption algorithms be used on low-entropy messages by adding noise
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 ...
- 878
6
votes
Accepted
How does the Multiplicative Weights Update method maximize entropy?
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 ...
- 198
5
votes
Generating $k$ random bits from a pdf with entropy $H(p) = k$
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 ...
- 441
4
votes
Difference between self-information and entropy
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 ...
- 141
4
votes
Is uniform convergence faster for low-entropy distributions?
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 ...
- 2,803
4
votes
Is uniform convergence faster for low-entropy distributions?
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 ...
- 10.2k
3
votes
Accepted
Relation between variance and mutual information
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 ...
- 1,419
3
votes
Lower bound on the number of objects in the universe
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.
- 2,070
2
votes
How does the Multiplicative Weights Update method maximize entropy?
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 ...
- 121
2
votes
Accepted
Entropy-like quantity
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".
- 4,465
1
vote
Information Bottleneck - Calculating the Mutual information between the Labels and the Features
This is only a partial answer. I might update it if I decide to look at the implementation.
I understand this as being fixed network layers that don't get updated
in training. Am I mistaken?
Note ...
- 11
1
vote
Does this notion of entropy have a name?
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 ...
- 4,011
1
vote
Entropy-like quantity
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).
- 10.2k
1
vote
Volume of elements mapped to the same codeword is $2^{H(X|\hat{X})}$
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 ...
- 4,011
1
vote
Accepted
An equation relating Time complexity, Space complexity, and entropy of output
(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 ...
- 7,565
1
vote
Is uniform convergence faster for low-entropy distributions?
We have largely resolved the question for product measures. I'm going to change the notation from the OP to be in line with our paper,
https://arxiv.org/abs/2209.04054
I'll be writing $\mu$ rather ...
- 10.2k
1
vote
Word length using entropy : Maximum entropy criteria
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 ...
- 2,070
Only top scored, non community-wiki answers of a minimum length are eligible