Questions tagged [entropy]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
36 views

Alternative axiomatic derivation of the Shannon entropy

I'm actually interested in the derivation of the information measure $I(p)=-\log p$ of a single event of probability $p$, as the Shannon entropy can then be defined as the average over all events. ...
user avatar
  • 151
1 vote
1 answer
20 views

Conditional entropies of sum relations

Let $(X_1,Y_1)$ and $(X_2,Y_2)$ be identically and independently distributed. Also consider $Z=X_1+X_2$. I am trying to prove the following inequality: $$ H(X_2 \vert Y_1 Y_2 Z) \leq H (X_1 \vert Y_1)\...
user avatar
  • 313
0 votes
0 answers
21 views

Entropy of a single Hint

Assume that the probability that a woman is above 80 years old is 3 times that of a man. How much information (in bits) do you get if you are given that a 80 year old person is a male? How should I ...
user avatar
1 vote
0 answers
36 views

Length of optimal Huffman and arithmetic coding

I'm new to this page and I used the search function, but did not find the exact question. I'm asking here because my classmates and I have been wondering about this, but did not find an answer. I have ...
user avatar
  • 11
3 votes
0 answers
30 views

Is there a context-agnostic concept of automatic (log-)text parsing that supports human reader filtering out redundancy?

This question is about ideas I regularly think about, and I would like to know what concepts already exist. Also I am not sure at all if this really makes sense, by now it is just a crazy idea ...
user avatar
  • 131
0 votes
0 answers
10 views

Is there an entropy evaluation method with an unified length?

For entropy, the most common one is Shannon entropy, however, it ignores time series of data. For instance, data 0x00001111 and 0x01010101 are given the same entropy. It is obvious that the second ...
user avatar
1 vote
2 answers
81 views

What is the entropy of an unordered list?

I'm trying to compress unordered lists of a few thousand integers for transmission over HTTP, and Claude Shannon is disappointing me with his mathematical ambiguity :) Each integer is 6-digits, so ...
user avatar
1 vote
1 answer
57 views

Is an AI upscaler incapable of reducing entropy?

I was reading the description of Anime4K (a video upscaler software) and I found a statement triggering my attention: [upscaling is done] without any meaningful decrease in entropy (lost information ...
user avatar
  • 113
2 votes
1 answer
105 views

Deriving a lower bound on the conditional entropy, conditioned on an event

I came across Lemma 19 in Certifying Equality With Limited Interaction, which states the following for jointly distributed random variables $Z$, $W$, where $Z$ takes values in $\{0,1\}^n$, and some ...
user avatar
0 votes
2 answers
94 views

How to find the compression method used on an unknown sequence of bytes? [closed]

I have a sequence of bytes: https://drive.google.com/file/d/17sfchPgsySi2ilIxLuBb1q-UUqq5lO87 What the data is, is unknown (see NOTE below). I'm pretty sure this data is compressed in some way, due to ...
user avatar
  • 101
3 votes
1 answer
73 views

Capacity of Binary Erasure Channel

Consider the the binary erasure channel, with input and output alphabet $\{0,?,1\}$ and channel matrix \begin{bmatrix} 1-\lambda-\mu & \mu & \lambda\\ 0 & 1 & 0\\ \lambda & \mu &...
user avatar
1 vote
0 answers
31 views

Why does attempting to estimate the entropy of text by randomly choosing chars in it and counting how often they are equal give wildly wrong results?

Why does attempting to estimate the entropy of a string, by randomly choosing pairs of (not necessarily adjacent) characters in it, and counting how often the selected characters in the pairs are ...
user avatar
1 vote
0 answers
62 views

How to calculate the entropy of a system with multiple states

I'm stuck in trying to compute an overall entropy calculation with an agent. Let me first introduce some background of the problem. Basically, I'm doing some work with the contextual bandit problems. ...
user avatar
  • 11
1 vote
1 answer
288 views

Binary cross Entropy derivative?

I am just learning backpropagation algorithm for NN and currently I am stuck with the right derivative of Binary Cross Entropy as loss function. Here it is: ...
user avatar
  • 11
0 votes
1 answer
77 views

Prime factorization for compressing streams of random numbers

We covered compression/encoding/decoding of data streams very briefly last lecture and I had an odd idea: Let's say I have a stream of random 8-Bit numbers. Now the probabilty to encounter each number ...
user avatar
  • 203
1 vote
1 answer
36 views

Upper bound on size of minimal binary coverage code

Let $1 \le r \le n$ b e integer(with $n$ large) and let $\mathscr X_n$ be the set set of all $2^n$ binary strings of length $n$. A binary $r$-coverage code is a subset $S$ of $\mathscr X_n$ such that ...
user avatar
  • 121
2 votes
0 answers
102 views

Is arithmetic coding slightly more efficient than rANS?

I'm extending a framework for lossy compression of multidimensional floating-point data. At some point in the pipeline, sequences of symbols from a non-uniform distribution are losslessly compressed ...
user avatar
0 votes
1 answer
108 views

Probability of loss using a binary symmetric channel

Today we talked about Information Theory and the binary symetric channel. For newbies here is a little explanation : For instance if I want to send a binary to someone : The bit will be "flipped&...
user avatar
0 votes
0 answers
36 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)$$ ...
user avatar
2 votes
1 answer
274 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)] = -\...
user avatar
  • 131
2 votes
1 answer
35 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 ...
user avatar
0 votes
0 answers
24 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 ...
user avatar
2 votes
1 answer
30 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 ...
user avatar
  • 53
0 votes
1 answer
105 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....
user avatar
2 votes
1 answer
578 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'$ ...
user avatar
4 votes
2 answers
711 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{...
user avatar
  • 215
0 votes
0 answers
48 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 ...
user avatar
1 vote
1 answer
172 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 ...
user avatar
  • 161
0 votes
1 answer
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 ...
user avatar
  • 1,582
2 votes
1 answer
39 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 ...
user avatar
0 votes
1 answer
154 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 ...
user avatar
  • 133
2 votes
1 answer
199 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 ...
user avatar
  • 161
0 votes
0 answers
46 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 ...
user avatar
  • 1,071
0 votes
1 answer
218 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 ...
user avatar
1 vote
0 answers
65 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 "...
user avatar
31 votes
2 answers
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 ...
user avatar
  • 1,071
2 votes
0 answers
68 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$$ ...
user avatar
  • 121
1 vote
2 answers
514 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 ...
user avatar
  • 115
35 votes
6 answers
8k 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 ...
user avatar
  • 453
2 votes
1 answer
45 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$ ...
user avatar
  • 125
3 votes
1 answer
101 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 ...
user avatar
14 votes
3 answers
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 ...
user avatar
  • 143
1 vote
1 answer
51 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?
user avatar
1 vote
1 answer
82 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 ...
user avatar
  • 1,582
1 vote
0 answers
72 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 (...
user avatar
  • 285
2 votes
1 answer
363 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 <...
user avatar
  • 121
0 votes
1 answer
265 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 ...
user avatar
  • 71
3 votes
1 answer
360 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 ...
user avatar
5 votes
1 answer
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{...
user avatar
  • 453
3 votes
1 answer
125 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. ...
user avatar
  • 12.3k