Questions tagged [shannon-entropy]
The shannon-entropy tag has no usage guidance.
32
questions
1
vote
0answers
118 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 ...
7
votes
0answers
189 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 ...
1
vote
0answers
82 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, ...
2
votes
1answer
157 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 ...
7
votes
2answers
214 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 $\...
7
votes
2answers
708 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 ...
2
votes
2answers
3k 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) = - \...
4
votes
1answer
78 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 ...
3
votes
1answer
320 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 ...
4
votes
1answer
234 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 ...
-2
votes
1answer
105 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 ...
4
votes
2answers
242 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 ...
7
votes
4answers
617 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\...
2
votes
1answer
82 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 ...
4
votes
0answers
112 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 ...
9
votes
1answer
270 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 ...
1
vote
0answers
51 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?
1
vote
0answers
79 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 ...
2
votes
0answers
143 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 ...
0
votes
0answers
166 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 ...
8
votes
2answers
155 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\}\...
12
votes
2answers
348 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)...
4
votes
1answer
388 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.
7
votes
0answers
887 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 ...
5
votes
1answer
301 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, ...
12
votes
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$...
1
vote
1answer
199 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-...
7
votes
3answers
3k 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?
1
vote
2answers
663 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 ...
1
vote
0answers
595 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 ...
2
votes
1answer
177 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 "...
3
votes
2answers
385 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 ...
