# Questions tagged [entropy]

The tag has no usage guidance.

117 questions
Filter by
Sorted by
Tagged with
21 views

### Minimum mean length of code words

I need help with this task, so if anyone is willing to help me, I would be grateful. The task is: Given a discrete information source that generates symbols from the set ...
1 vote
28 views

### Is it possible to avoid encoding the state in streaming ANS?

regular ANS collects all the data into one big integer and provides optimal compression. In cases where all the symbol probabilities are powers of two, it is just as good as huffman coding (because ...
28 views

### Calculation of compression ratio using arithmetic encoding?

Arithmetic encoding is one of the most famous entropy encoding techniques, and I am using it to encode an image. For this, I am using the built-in function of Matlab that also gives other values such ...
1 vote
44 views

### Why do simple Logical Gates have an Irrational amount of Bits?

Suppose $2$ bits are used to encode a message, A and B. If you know $A$ is $1$, you have one bit of information. If you know $A\land B$ is $1$, you have two bits of information. If you know $A\land B$...
13 views

### One-shot capacity achieving input, permutation invariance and i.i.d. decomposition

Suppose I have $n$ iid copies of a channel $W_{Y|X}$ and denote this by $W_{Y|X}^{\otimes n}$. I found a one-shot capacity of $W_{Y|X}^{\otimes n}$ to be an entropic quantity (specifically, it is the ...
1 vote
66 views

### How can the mutual information be equal to minus conditional entropy? [closed]

I am reading the following paper: https://arxiv.org/abs/2301.06941 The authors in Eq.(8) have obtained a relation which has the mutual information, $i$, in the exponent of the exponential on the RHS ... 56 views

### Classifying succinct data structures

The wikipedia page for "Succinct Data Structures" says: [...] a succinct data structure is a data structure which uses an amount of space that is "close" to the information-...
38 views

### Which system has higher entropy?

Suppose that I have two random processes. Process $X$ has probability 0.5 to be in state A and probability 0.5 to be in state B. Process $Y$ has probability 0.4 to be in state A and probability 0.6 to ...
1 vote
97 views

### Comparing the entropy of a painting to a photograph

This is a quote from the book, "The Three-Body Problem" (page 112 in the paperback): He remembered taking a class in information theory as a third-year student in college. The professor had ...
1 vote
16 views

### the principle behind asking the minimum amount of questions for determining information entropy

This certain Khan Academy videos introduces the intuition about information entropy: https://www.youtube.com/watch?v=2s3aJfRr9gE&t=102s . It relates information entropy to the expected number of ...
52 views

### How many bits are required to encode information in probability set G = [0.001, 0.002, 0.003, 0.994]?

I am currently working on data compression and thought it would be a good time to read up on the basics of information theory to better understand data compression and its algorithms. As I understand, ...
40 views

### Algebra of error models and error correcting codes?

In coding theory we typically consider the situation where we have a channel that connects a sender and receiver. The messages flowing from the sender to the receiver are corrupted by an error source ...
1 vote
21 views

47 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 ...
25 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 ...
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 ...
280 views

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 1 answer 876 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' ... 4 votes 2 answers 1k 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 0 answers 52 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 1 answer 253 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 1 answer 44 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 1 answer 53 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 1 answer 194 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 1 answer 242 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 0 answers 51 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 1 answer 281 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 0 answers 83 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 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 ... 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 ...
1 vote
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 ...