Questions tagged [shannon-entropy]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...