Questions tagged [shannon-entropy]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
0answers
102 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 ...
1
vote
0answers
76 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
147 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
204 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 $\...
4
votes
1answer
71 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
278 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
226 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
91 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 ...
7
votes
2answers
676 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 ...
4
votes
2answers
221 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 ...
2
votes
1answer
81 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 ...
7
votes
4answers
613 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\...
4
votes
0answers
110 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 ...
1
vote
0answers
49 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
78 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
137 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 ...
3
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) = - \...
0
votes
0answers
164 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
154 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\}\...
4
votes
1answer
379 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
188 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 ...
7
votes
0answers
858 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
296 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, ...
9
votes
1answer
265 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
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?
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
0answers
594 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 ...
1
vote
2answers
653 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 ...
2
votes
1answer
174 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
383 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 ...
12
votes
2answers
344 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)...