Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [shannon-entropy]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
6 votes
1 answer
170 views

Number of random bits necessary to approximate an arbitrary distribution

Given a discrete distribution $X$ and $\varepsilon\in(0,1)$, consider the minimal $m\in\mathbb{N}$ such that $\mathbf{SD}(f(U^m),X)\leq\varepsilon$, for some (the best, possibly inefficient) ...
Nathan's user avatar
  • 179
1 vote
1 answer
121 views

Information Bottleneck - Calculating the Mutual information between the Labels and the Features [closed]

I am trying to understand the Nonlinear Information Bottlecneck paper along with their implementation, but I am confused as to what is actually being calculated in the Mutual information $(I(Y, M))$ ...
Liam F-A's user avatar
0 votes
0 answers
57 views

Does Co-occurrence Information Differ Qualitatively From Shannon and Algorithmic Information?

In Distributed Computation as Hierarchy Michael Manthey argues that co-occurrence of indistinguishables (critical for quantum theory) supplies spatial information that qualitatively differs from both ...
James Bowery's user avatar
1 vote
0 answers
46 views

Will the maximum entropy joint distribution given a known set of marginal distributions have the maximum plausible support?

Define $[n] = \{1, 2, ..., n\}$. Given a distribution $P : \{0, 1\}^{[n]} \rightarrow [0, 1]$ and a subset $S \subseteq [n]$, we can define the $S$-marginal of $P$, $P_S : \{0, 1\}^S \rightarrow [0, 1]...
Samuel Schlesinger's user avatar
0 votes
0 answers
62 views

Interesting statistical experiment concerning data compression

I want to present the following statistical experiment concerning data compression, on which I will ask you to predict the result obviously justifying the choice made. The statistical experiment is ...
Alix's user avatar
  • 1
4 votes
0 answers
260 views

Maximize the mutual information between 2 discrete random variables

I have two random variables $X$ and $Y$. $X$ follows Poisson-Binomial distribution with parameters $\{q_1, \ldots, q_k\}$. Thus, $X$ can take values in the set $\{0,1,\ldots,k\}$. $Y$ is a binary ...
wanderer's user avatar
3 votes
0 answers
55 views

Hardness of computing entropy of a function on uniform input distribution

Let $p \geq q \in \mathbb{N}_+$, and let $L_\mathsf{max-entropy} := \{(f,k) \in \{0,1\}^{\lambda^p} \times \{0,1\}^{\log\lambda} | \lambda \in \mathbb{N} \wedge \mathrm{H}(\underbrace{C_f(\mathcal{U}_{...
Nicholas Brandt's user avatar
4 votes
1 answer
208 views

Does this notion of entropy have a name?

Recently I stumbled upon the following notion of entropy which seems quite natural to me. I am looking for its "real" name and/or any references where it might come up. I tried searching ...
dkaeae's user avatar
  • 300
0 votes
0 answers
173 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 ...
nuggimane's user avatar
0 votes
1 answer
118 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 ...
Aether's user avatar
  • 133
0 votes
0 answers
15 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 ...
Aleksejs Fomins's user avatar
4 votes
1 answer
201 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,...
Karagounis Z's user avatar
3 votes
2 answers
292 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 ...
Aryeh's user avatar
  • 10.6k
0 votes
1 answer
154 views

Volume of elements mapped to the same codeword is $2^{H(X|\hat{X})}$

In this paper by Tishby, Pereira and Bialek they mention on page 4 in the Relevant quantization chapter the setting is the following; Given some signal space $X \sim p(x)$ and a quantized codebook $\...
sn3jd3r's user avatar
  • 133
2 votes
0 answers
110 views

Representing data with Shannon entropy predicted bits

Let us assume a file based on a character set where each character has equal probability of occurance. This will result in the maximum entropy for that character set. On calculating the entropy, let ...
Paddy's user avatar
  • 121
1 vote
0 answers
418 views

Minimum number of hours of speech needed to train a neural net to recognize speech [closed]

From a theoretical computer science point of view, is there a lower limit on the number of hours of speech needed to train a neural net to translate speech to text? An estimate from CMU is 3000-5000 ...
Lars Ericson's user avatar
1 vote
0 answers
117 views

Entropy bounds on solutions to problems in BPP and other complexity classes based on entropy demands

Has anyone studied the asymptotics of problems in complexity classes like $BPP$? The thought came to me that if a problem in $BPP$ only requires $O(log(n))$ bits of entropy to solve then, intuitively, ...
Jake's user avatar
  • 1,203
2 votes
1 answer
274 views

An equation relating Time complexity, Space complexity, and entropy of output

Is there an equation that relates minimum time complexity, minimum space complexity, and entropy of the output of a function? It seems to me that there should be a relatively intuitive relationship ...
William Oliver's user avatar
10 votes
3 answers
683 views

Is uniform convergence faster for low-entropy distributions?

Let $\mathcal D$ be a probability distribution on $\{0,1\}^d$. Let $X_1, \cdots, X_n \in \{0,1\}^d$ be i.i.d. samples from $\mathcal D$. Let $\mu \in [0,1]^d$ be the mean of $\mathcal D$ and let $\...
Thomas's user avatar
  • 2,803
4 votes
1 answer
145 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 ...
Jake's user avatar
  • 1,203
4 votes
1 answer
1k 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 ...
Rona Lee's user avatar
4 votes
1 answer
491 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 ...
SKM's user avatar
  • 141
-2 votes
1 answer
163 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 ...
user42880's user avatar
7 votes
2 answers
916 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 ...
salmAn's user avatar
  • 93
4 votes
2 answers
265 views

Conditional entropy: $H(X | Y)$ large implies $H(X | Y, X \neq Y)$ large?

Suppose that $X$ and $Y$ are two random variables that are defined on the same support. Furthermore, suppose that $H(X | Y) = \log n$ for some $n$. I am now interested in how much the term $H(X | Y, X ...
Chris's user avatar
  • 79
2 votes
1 answer
90 views

Sufficient Statistics of $X$ from $Y$

I am reading the paper New Monotone and Lower Bounds in Unconditional Two Party Computation by Wolf and Wullschleger. In Definition 2 on the third page, they define $f(x):=P_{Y|X}(\cdot|x)$ and they ...
SAmath's user avatar
  • 425
8 votes
4 answers
795 views

Expected empirical entropy

I'm thinking about some properties of the empirical entropy for binary strings of length $n$ when the following question crosses my way: $\underbrace{\large\frac{1}{2^{n}}\normalsize\sum\limits_{w\in\...
Danny's user avatar
  • 500
4 votes
0 answers
123 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 ...
SAmath's user avatar
  • 425
1 vote
0 answers
59 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?
Anixx's user avatar
  • 99
1 vote
0 answers
89 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 ...
mclaudt's user avatar
  • 11
2 votes
0 answers
157 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 ...
user avatar
3 votes
3 answers
5k views

Difference between self-information and entropy

I get a bit confused about different definitions of entropy and/or self-information. Entropy? $$ H(X) = - \sum_{x \in X} P_X(x) \cdot \log{\left(P_X(x)\right)} $$ Self-information? $$ I(x) = - \...
Guarana Joe's user avatar
0 votes
0 answers
195 views

Can the self-information be infinite?

I was wondering about the self-information, the information content . If I have data and I measure different words in it, their probability and take the average mean of that, what is the lowest and ...
Guarana Joe's user avatar
8 votes
2 answers
167 views

Smoothly leaking information over time

Say I have a one bit random variable $X \in \{0,1\}$, and let $n$ be a natural number. I want a sequence of random variables $0 = X_0, X_1, \ldots, X_n = X$ s.t. $$H\left(X~|~\{X_0,\ldots,X_k\}\...
Geoffrey Irving's user avatar
4 votes
1 answer
516 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.
Omar Shehab's user avatar
7 votes
0 answers
199 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 ...
Turbo's user avatar
  • 12.9k
7 votes
0 answers
1k views

Partitioning DAG into Paths

What bounds (lower or upper) are known about the complexity of partitioning a Directly Acyclic Graph (DAG) into paths of respective sizes $n_1,\ldots,n_w$, such that to minimize their entropy $n{\cal ...
J..y B..y's user avatar
  • 2,776
5 votes
1 answer
604 views

Given discrete rvs X,Y, find Z s.t. I(Z;X) is high and I(Z;Y) is low. -- known problem?

Consider the following problem. Let $X$ and $Y$ be discrete random variables. The goal is to find a random variable $Z$ such that, informally, $I(Z;X)$ is high and $I(Z;Y)$ is low. More precisely, ...
Matt's user avatar
  • 113
9 votes
1 answer
410 views

Who coined the term "empirical entropy"?

I know of Shannon's work with entropy, but lately I have worked on succinct data structures in which empirical entropy is often used as part of the storage analysis. Shannon defined the entropy of ...
deleted user 42's user avatar
1 vote
1 answer
204 views

How to choose a correct prior

Consider a Bernoulli experiment, such as flipping a not necessarily fair coin, which results in a positive outcome (heads) with probability $p$ and with a negative outcome (tails) with probability $(1-...
jan-glx's user avatar
  • 121
7 votes
3 answers
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?
Mok-Kong Shen's user avatar
13 votes
3 answers
3k 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$...
robinson's user avatar
  • 775
1 vote
0 answers
613 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 ...
Keenan Pepper's user avatar
1 vote
2 answers
849 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 ...
user782220's user avatar
2 votes
1 answer
287 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 "...
Mooncer's user avatar
  • 431
3 votes
2 answers
399 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 ...
Mooncer's user avatar
  • 431
12 votes
2 answers
447 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)...
v s's user avatar
  • 2,208