Questions tagged [entropy]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
30 views

Proving an entropy inequality

I am given that $Z$ is independent of $(X,U)$, where $Z$ and $X$ are binary random variables while $U$ is an arbitrary random variable. I need to prove the following: $$ H(X\oplus Z|U) \geq H(X|U)$$ ...
1
vote
1answer
22 views

How is expected value in entropy derived?

I was self learning about entropy and came across this equation. $$ H = - \sum p(x) \log p(x) $$ The equation for entropy in expected value, $$ H(x) = \operatorname*{\mathbb{E}}_{X \sim P}[I(x)] = -\...
1
vote
1answer
21 views

Worked out example of Slepian-Wolf Theorem

Note: First posted this on Theoretical Computer Science Stack Exchange, but deleted it from there since it seems to be off-topic. The Slepian-Wolf theorem states that sequences of outputs from two ...
0
votes
0answers
20 views

Typical sets size

I am currently studying Shannon's entropy and I have just come across an exercise related to typical sets. More specifically, given a certain type $t$ for the set, the exercise asks to demonstrate ...
2
votes
1answer
22 views

Bob has to find Alices hidden gold by questioning yes/no questions

Suppose that Alice has $n$ places to hide the gold $v_1, ..., v_n$ and that Bob knows the probability of each place. Bob has to ask Alice a series of yes/no questions to find the gold. I have done ...
0
votes
1answer
36 views

Data compression - Entropy

Let's say I have an alphabet $$\Sigma = \{A, B, C, D, E\}$$ with probabilities $$P(A) = P(B) = P(C) = 0.25 \text{ and } P(D)=P(E) = 0.125.$$ I know that the entropy then is: $$H(\Sigma) = 3 \cdot 0....
2
votes
1answer
136 views

Collision entropy definition

The collision entropy is defined as the Renyi entropy for the case $\alpha = 2$. It is given by $$\mathrm{H}_{2}(X)=-\log \sum_{i=1}^{n} p_{i}^{2} \tag{1}$$ Take two random variables $X$ and $X'$ ...
0
votes
0answers
8 views

Categorical crossentropy on one hot encoded 6 dimensional target columns as output classes in keras

In keras , I have 6 targets which I one hot encoded , now I have 6 column of either 1 or 0. When I used categorical crossentropy I get 1% validation accuracy and when I used binary crossentropy I get ...
3
votes
2answers
97 views

In information theory, why is the entropy measured in units of bits?

In information theory, we have the quantity "information". Suppose we have some discrete random variable $X$, that can take values $\{{a,b,c\}}$ with corresponding probability distribution $\{{\frac{...
0
votes
0answers
31 views

Cross entropy minimization

I just read about Cross-entropy cost function for my work. and I see a notation that said "the minimization of cross entropy of some data is equal to maximization of their log likelihood." How can I ...
1
vote
1answer
51 views

How to calculate conditional entropy

I'm new to information theory and I am struggling to understand this problem. Let $p(x,y)$ given by: How can we calculate $H(X|Y)$? I know $H(X|Y)=H(X|Y=0)+H(X|Y=1)$ but then I don't know how to go ...
0
votes
1answer
41 views

Is there any scenario whereby randomly shufflying a sequence improves it's compressibility?

I'm performing some correlation assessment à la NIST Recommendation for the Entropy Sources Used for Random Bit Generation, § 5.1. You take a test sequence and compress it with a standard ...
2
votes
1answer
28 views

Proof high-entropy sequences are hard to compress

When comparing random-variable sequences generated from probability distributions, what's a formal proof that a distribution with higher entropy produces a sequence that's "harder" to compress? In ...
0
votes
1answer
75 views

information theory, find entropy given Markov chain

There is an information source on the information source alphabet $A = \{a, b, c\}$ represented by the state transition diagram below: a) The random variable representing the $i$-th output from this ...
2
votes
1answer
111 views

When Huffman coding is inefficient?

I have a question regarding the redundancy of Huffman coding. I know that for a general prefix code we have the following inequality: $$ H(X) \le R \le H(X) + 1 $$ $R$ being the rate (average ...
0
votes
0answers
39 views

Is entropy a good indicator of the quality of a lossy compression?

Say I want to quantitively evaluate the effectiveness of several color-to-grayscale conversion algorithms, which can be considered as lossy compression. Would entropy be a good indicator? To ...
0
votes
1answer
137 views

How to calculate information gain in ID3?

I am trying to implement a decision tree classifier using ID3 algorithm. According to Aritificial Intelligence - A Modern Approach, information gain of attribute A ...
1
vote
0answers
34 views

Difference between a regular and a stationary source?

As far as I understand a stationary source is a regular source but it's not necessarily true the other way around. And a stationary source is a source for which its distribution is unaffected by a "...
31
votes
2answers
2k views

Simulating a probability of 1 of 2^N with less than N random bits

Say I need to simulate the following discrete distribution: $$ P(X = k) = \begin{cases} \frac{1}{2^N}, & \text{if $k = 1$} \\ 1 - \frac{1}{2^N}, & \text{if $k = 0$} \end{cases} $$ The most ...
2
votes
0answers
49 views

What is the compressibility of this simple “book”?

Compressibility is defined as $$C=\frac{2^{HN}}{2^{H_{max}N}}$$ The book is made up of a simple alphabet of only {a,b,c,d} which occur with probabilities $$P(a)=0.2, P(b)=0.4, P(c)=0.1, P(d)=0.3$$ ...
1
vote
2answers
181 views

Why it is not a Huffman code

I have been given several examples I the aim is to explain why it is not a Huffman code. So, for instance, the first one was: $\{00,01,10,110\}$ This code is not Huffman becuase it has just one ...
35
votes
6answers
7k views

Do lossless compression algorithms reduce entropy?

According to Wikipedia: Shannon's entropy measures the information contained in a message as opposed to the portion of the message that is determined (or predictable). Examples of the latter ...
2
votes
1answer
38 views

Is there an algorithm to achieve optimal compression in a “streamed” manner, assuming equal probability of each possibility?

(Sorry for the question title; edits are welcome.) Let's say that you have a set of data made of repeating units, consisting of a value with $2$ possibilities, a value with $3$ possibilities, $5$ ...
3
votes
1answer
100 views

Dependency on adjacent blocks decreases as block count increases

The following is an excerpt from Information Theory: A Tutorial Introduction, page 65. Now, supposing the identity of each letter in English does not depend on any letter that is more than 10 letters ...
14
votes
3answers
2k views

Shannon Entropy of 0.922, 3 Distinct Values

Given a string of values $AAAAAAAABC$, the Shannon Entropy in log base $2$ comes to $0.922$. From what I understand, in base $2$ the Shannon Entropy rounded up is the minimum number of bits ...
1
vote
1answer
44 views

Maximizing entropy under constraint

How do I prove that entropy is maximal for $P(A_2) = \cdots = P(A_n) = (1-a) /(n-1)$ while $P(A_1) = a$ (a fixed number) and $A_1,…, A_n$ is a partition of the sample space?
1
vote
1answer
59 views

How can Kolmogorov complexity help me practically with measuring entropy?

A comment was made to me saying the following in relation to Kolmogorov complexity:- You're not the first to think non-computability = impractical or even useless. But it can be useful. In particular ...
1
vote
0answers
59 views

Upper bound on the average path length in binary search tree

I have been reading the chapter 6.2.2 in Knuth's book about lower and upper bound on the average path length in binary search tree. And I have problems with understanding small details of Theorem M (...
2
votes
1answer
141 views

How to prove Landauer's principle [closed]

I have some questions about energy emitted when one bit of information is processed. Landauer's principle states the minimum possible amount of energy required to erase one bit of information is <...
0
votes
1answer
182 views

Applying Shannon Entropy to data storage

I know Shannon Entropy is defined for messages. When it's said the size of a file stored in a HDD is 1 MB, are we talking about the Shannon Entropy? If so, how do we extend the definition to static ...
2
votes
1answer
242 views

How realistic is the i.i.d assumption in the definition of Shannon's entropy?

Let me first say I come from a physics background and have about zero exposure to computer science, so the question may be very naive. Shannon's entropy looks perfectly natural and useful from a ...
5
votes
1answer
1k views

The Entropy of the phrase “Eile Mit Weile”

I want to calculate the Entropy of the phrase "Eile mit Weile". I found the probability of each letter as the following $$P(e)=\frac{4}{12}$$ $$P(i)=\frac{3}{12}$$ $$P(l)=\frac{2}{12}$$ $$P(m)=\frac{...
3
votes
1answer
106 views

Is there a fundamental difference in LIFO and FIFO entropy coding?

The top two competing entropy coders at the moment are Arithmetic Coding (AC) and Asymmetrical Number Systems (ANS). A very interesting difference between the two is that AC is FIFO and ANS is LIFO. ...
0
votes
1answer
81 views

Finding the Entropy of a random experiment with probability of $\frac{1}{3}$

Entropy is the randomness collected by an operating system or application for use in Cryptography or other uses that require random data. The formula for Entropy is $$H(p_1, ..., p_k)=-\sum_{i=1}^{k} ...
25
votes
11answers
9k views

Is von Neumann's randomness in sin quote no longer applicable?

Some chap said the following: Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin. That's always taken to mean that you can't generate ...
0
votes
1answer
250 views

Entropy and Information Gain for multi attributes

Is there any way that for specific dataset I can measure entropy and information gain for two or more attributes together? Let's say we have the following dataset: $\begin{array}{cccccc|c} x1 & ...
0
votes
0answers
72 views

Is it possible for a [futuristic] computer to contain the information of the whole universe?

(This is a question of information theory, data compression and entropy, so I believe it fits CS forum) Does the fact that the computer itself is a part of the universe make it logically impossible ...
1
vote
0answers
68 views

What is the relationship between entropy rate and quantization?

I have a totally random source of signal data that looks like a typical normal distribution. I've included an image as I like pictures:- The source has a mean of 0, and a standard deviation of 1. ...
1
vote
0answers
142 views

Compression of gaussian variables

Say I have 2 Gaussian sources X and Y. They are generated with mutivariate gaussian distribution with ...
1
vote
1answer
188 views

Higher order empirical entropy is not the entropy of the empirical distribution?

Basically, the problem is that I always thought that the (unnormalized) $k$th order empirical entropy $n\cdot H_k(x)$ (see "Backround" at the end of this post for more information) for a given string $...
0
votes
1answer
234 views

Calculate joint entropy of a Hamming Code over a Binary Symmetric Channel?

I have a normal (7,4,3) Hamming Code over GF(2) and a parity check matrix for it (not posted, because I don't think it's involved). I have a set X of 4 bit source vectors called x. They all have ...
3
votes
1answer
118 views

Finding the dichotomy that maximizes information gain for a classifier?

Suppose that $\Omega$ is a finite probability space,with measure $P$ (we can take $P$ uniform). Let $C \in \{\pm 1 \}$ be a random variable on $\Omega$, the classifier. Let $$H(C) = H(C, \Omega, P) = ...
3
votes
1answer
225 views

Complexity of / best algorithm for finding the dichotomy that maximizes information gain?

Suppose that $X$ is a finite set with a probability measure $P$. I want to find the subset $A \subset X$ so that the information gain of conditioning on ${A, A^c}$ is maximal. That is, I want to find $...
2
votes
1answer
167 views

Can Von Neumann bit extraction be made more efficient?

I want to develop a previous question regarding Von Neumann debiasing /randomness extraction. The typical solution (as posted) is to take pairs of throws and output a bit based on a comparison of ...
2
votes
1answer
141 views

Kraft's inequality and Shannon's noiseless coding theorem for an encoding

A discrete memoryless source W has words $w_1,w_2,w_3,w_4,w_5,w_6$ that occur with probablilities $0.05,0.05,0.15,0.2,0.25,0.3$ respectivley. Does there exist a compact instantaneous binary encoding ...
1
vote
0answers
67 views

Approximate conditional entropy

Given a set of random variables $X = \{x_1, x_2, \dots, x_n\}$. If the conditional entropy for all $Y \subset X - \{X_i\}$ where $|Y| \leq 5$. How to approximate conditional entropy when $|Y| = 10$ ...
3
votes
1answer
119 views

Extracting Randomness from Mouse Acceleration

I'm working on trying to make an "entropy pool" that will be fed as input into an RNG (as in, ex, Fortuna). In order to do so, I need to take various collected data and extract as much entropy as ...
0
votes
1answer
83 views

Numerical example of theoretical diff file size using Kullback Leibler?

I understand that the theoretical size of a diff patch between two similar files can be calculated using Kullback Leibler (KL) as described @ Wikipedia. Can anyone point me to a numerical example of ...
6
votes
2answers
178 views

How best to statistically verify random numbers?

Lets say I have 1000 bytes that are supposedly random. I want to verify to a certain certainty that they are indeed random and evenly distributed across all byte values. Aside from calculating the ...
4
votes
2answers
119 views

Measuring the information of a document?

I'd like to measure how much information a document $D$ contains. Clearly, the New York Times published yesterday contains more information than my diary wrote on the same day. But, I do not know ...