# Questions tagged [shannon-entropy]

The tag has no usage guidance.

39 questions
Filter by
Sorted by
Tagged with
0answers
131 views

### Error in entropy properties in Mathematical Theory of Cryptography by Claude E. Shannon

I am reading this classic paper by Claude E. Shannon and I think there may be a couple of errors in his description of the properties of Entropy/Uncertainty. The screenshot shown at the bottom of this ...
1answer
98 views

### Why isn’t information-probability relationship linear? [closed]

I am completely new to information theory. I was learning about information content but couldn’t make sense of why the relationship between information content and probability isn’t linear? And why it ...
0answers
10 views

### Capacity of spike-based neuronal code

Assume that a neuronal population $A$ is connected to a neuronal population $B$ by a bunch of synapses - one-directional channels that propagate spikes. For simplicity assume that the current ...
1answer
146 views

### Generating $k$ random bits from a pdf with entropy $H(p) = k$

All the sources online say that, intuitively, a distribution with entropy $k$ has $k$ bits of pure randomness in it. So can we formalize this as follows? Suppose I can only sample from my distribution,...
1answer
248 views

### Entropy-like quantity

For $p\in[0,1]^{\mathbb{N}}$ and $\alpha\ge1$, define $$H_\alpha(p) = \sum_{i\in\mathbb{N}}p_i|\log(p_i)|^\alpha.$$ When $\sum_i p_i=1$ and $\alpha=1$, $H_1(p)$ is just the Shannon entropy of the ...
1answer
117 views

1answer
106 views

### Can entropicly secure encryption algorithms be used on low-entropy messages by adding noise

There exist information-theoretic notions of security like Shannon's "perfect security" that one-time pads exhibit. All methods which achieve perfect security will require long keys, however. If we ...
1answer
525 views

### Relation between variance and mutual information

Given two discrete random variables $X,Y$ such that $X,Y \in \mathbb{R}$ and $0 \leq X,Y \leq 1$, is it true that $$|\text{Cov}[X,Y] \leq \sqrt{\frac{1}{2} \text{I}[X,Y]}|.$$ This bound may be ...
1answer
385 views

### Word length using entropy : Maximum entropy criteria

The question is based on research paper titled, Markovian language model of the DNA and its information content In the supplementary document, the Authors show how they determine the word length of ...
1answer
124 views

### Lower bound on the number of objects in the universe [closed]

From Cover & Thomas' Elements of Information Theory: Player A chooses some object in the universe, and player B attempts to identify the object with a series of yes–no questions. Suppose ...
2answers
797 views

### How does the Multiplicative Weights Update method maximize entropy?

"The Multiplicative Weights Update (MWU) method is known to maximize both utility and entropy". This is a comment by C. Papadimitriou on MWU. I understand that MWU maximizes utility as it solves ...
2answers
254 views

0answers
114 views

### Inf-entropy rate and min-entropy

I am reading the paper "Generating random bits from an arbitrary source: fundamental limits" by Vembu and Verdu. This paper is written in the language of information theory, however, I need to ...
0answers
57 views

### What is entropy of a variable described by Knightian uncertainty?

Given a discrete variable whose value is characterized by Knightian uncertainty, that is, belief and plausibility, as in Dempster-Shafer theory, what is its entropy?
0answers
81 views

### Entropy criterion of efficiency for (comparison using hashing)

I understand that hash is effective iff the "domain" size is smaller than the size of the "general set" - set of all possible objects. E.g., "domain" is the set of valid english phrases with length ...
0answers
150 views

### How hard is it to compute an approximately optimal non-greedy CART tree?

The question itself is closer to the bottom of this post, and is formulated without any rerefence to the term "CART". Motivation: In traditional CART (Classification and Regression Trees), one ...
3answers
4k views

1answer
417 views

### What is full-entropy bit-strings?

I was going through the description of NIST Randomness Beacon. I would like to know the meaning of the term full-entropy bit-strings used in the third paragraph.
0answers
190 views

### Geometric Intuition behind Locally testable codes

Conventional coding theory provides a good geometric picture behind linear error correction codes in terms of Hamming distance. What additional geometric requirement one should add to make a code ...
0answers
925 views

3answers
4k views

### Are Shannon entropy and Boltzmann entropy mutually convertible?

Are Shannon entropy and Boltzmann entropy mutually convertible, much like mass and energy according to Einstein's formula?
3answers
2k views

### On the entropy of a sum

I am looking for a bound on the entropy $H(X+Y)$ of the sum of two independent discrete random variables $X$ and $Y$. Naturally, $$H(X+Y) \leq H(X) + H(Y) ~~~~~~(*)$$ However, applied to the sum of $n$...
0answers
599 views

### Information channel with symmetric channel matrix

It took me a while to figure out that a "symmetric channel" does not mean a channel with a symmetric channel matrix. (Rather, "symmetric channel" means that the rows of the matrix are all permutations ...
2answers
728 views

### Arithmetic coding, the termination symbol, and the empty string

Suppose the source alphabet is $a, b, c$ with $a$ as the termination symbol and so the unit interval is correspondingly divided as $[0, P(a), P(a)+P(b), 1]$. Strings consisting of a bunch of $b$'s ...
1answer
204 views

### Landauer's principle internals - how it works

I attached a picture, where the energy dissipation (entropy increase) on information erasure is explained. Is the explanation correct? "RESTORE TO ONE" - is it correct to identify the operation as "...
2answers
390 views

### Can reversible computations alone be used to create a computer?

We are able to perform universal computations with the reversible model. Basically, during the computations, no information should be erased, so that no involved entropy increase would occur. Are ...
2answers
407 views

### Channel coding results using Kolmogorov complexity

Usually Shannon entropy is used to prove channel coding results. Even for source-channel separation results shannon entropy is used. Given the equivalence between Shannon (global) vs Kolmogorov (local)...