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 ...
Adam Smith's user avatar
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 ...
Richard's user avatar
  • 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 ...
Yuval Peres's user avatar
5 votes
Accepted

Number of random bits necessary to approximate an arbitrary distribution

There is no $H(X)+\log(1/\epsilon)$ bound. I think your $H(X)/\varepsilon$ bound is tight. Example 1. Suppose $X$ is uniformly distributed on $\{1,2,\dots,2^n\}$. Then the optimal encoding has ...
D.W.'s user avatar
  • 12.1k
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 ...
Post169's user avatar
  • 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 ...
Thomas's user avatar
  • 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 ...
Aryeh's user avatar
  • 10.5k
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 ...
Andrew Morgan's user avatar
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.
kodlu's user avatar
  • 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 ...
Mmmh mmh's user avatar
  • 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".
Bjørn Kjos-Hanssen's user avatar
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 ...
Nichlas L.R's user avatar
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 ...
Mahdi Cheraghchi's user avatar
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).
Aryeh's user avatar
  • 10.5k
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 ...
Mahdi Cheraghchi's user avatar
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 ...
usul's user avatar
  • 7,615
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 ...
Aryeh's user avatar
  • 10.5k
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 ...
kodlu's user avatar
  • 2,070

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