The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [entropy]

The tag has no usage guidance.

81 questions
Filter by
Sorted by
Tagged with
14 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 ...
22 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 ...
8 views

Calculating spatial “orderedness” at each position in a binary image: entropy? lacunarity?

Let's say I have image where all pixel values are either 0 or 1. What I'd like to do is to be able to generate a new image with the same dimensions where each pixel represents how "ordered" the area ...
47 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 ...
60 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 ...
36 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 ...
54 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 ...
23 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 "...
25 views

How to calculate entropy of a symbol and entropy rate?

I've been stuck on this question from my text book for a while now: A box contains 4 dice: 2 fair 4-sided dice A and B: p(i) = 1/4 i={1, 2, 3, 4} 1 loaded 4-sided dice C: p(2) = 1 1 loaded 4-sided ...
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 ...
41 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$$ ...
74 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 ...
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 ...
35 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$ ...
95 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 ...
10 views

Is there a classification scenario with cross-entropy loss such that the loss as a function of the predictor/neural net's parameters is a function s.t it satisfies the properties of (a) having a ...
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 ...
41 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?
43 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 ...
57 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 (...
78 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 <...
119 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 ...
160 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 ...
1k views

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 ...
140 views

181 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 ...
96 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) = ...
192 views

775 views

Computing Von Neumann Entropy Efficiently

The Von Neumann entropy $S$ of a density matrix $\rho$ is defined to be $S(\rho)= -\text{tr}(\rho \lg \rho)$. Equivalently, $S$ is the classical entropy of the eigenvalues $\lambda_k$ treated as ...
1k views

Is there a generalization of Huffman Coding to Arithmetic coding?

In trying to understand the relationships between Huffman Coding, Arithmetic Coding, and Range Coding, I began to think of the shortcomings of Huffman coding to be related to the problem of fractional ...
47 views

Approach to data compression with unknown patterns [closed]

Let's say I have a file with symbols of an alphabet [0,N-1], N around 50. The actual data is a file with a lot of lines, each containing 100 of these symbols. I want to compress this data. By doing a ...
If we take Solomonoff's prior $m$, defined here and normalize it we get a probability mass function on all finite words. But, the pmf isn't completely determined until we fix a universal Turing ...