2022 Developer Survey is open! Take survey.

Questions tagged [shannon-entropy]

The tag has no usage guidance.

42 questions
Filter by
Sorted by
Tagged with
4 votes
0 answers
201 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 ...
• 99
3 votes
0 answers
48 views

• 131
2 votes
0 answers
105 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 ...
• 121
1 vote
0 answers
234 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 ...
• 107
1 vote
0 answers
101 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, ...
• 1,131
2 votes
1 answer
235 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 ...
9 votes
2 answers
344 views

• 79
2 votes
1 answer
87 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 ...
• 415
8 votes
4 answers
701 views

• 2,391
5 votes
1 answer
559 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, ...
• 113
9 votes
1 answer
342 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
1 answer
202 views

2 votes
1 answer
231 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 "...
• 431
3 votes
2 answers
392 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 ...
• 431
12 votes
2 answers
424 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)...
• 2,198