Questions tagged [entropy]
The entropy tag has no usage guidance.
117
questions
0
votes
0
answers
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 ...
- 101
1
vote
1
answer
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 ...
- 13
0
votes
0
answers
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
1
answer
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
0
votes
0
answers
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 ...
- 101
1
vote
0
answers
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 ...
user157955
0
votes
0
answers
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-...
- 101
0
votes
1
answer
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 ...
- 103
1
vote
2
answers
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 ...
- 111
1
vote
0
answers
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 ...
- 163
0
votes
1
answer
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, ...
0
votes
0
answers
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 ...
- 8,308
1
vote
1
answer
21
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)\...
- 313
0
votes
0
answers
23
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 ...
1
vote
0
answers
89
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 ...
- 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
...
- 131
0
votes
0
answers
11
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 ...
- 101
1
vote
2
answers
151
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 ...
2
votes
1
answer
75
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
...
- 123
2
votes
1
answer
180
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 ...
- 23
0
votes
2
answers
258
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 ...
- 101
3
votes
1
answer
122
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 &...
- 149
1
vote
0
answers
33
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 ...
- 141
1
vote
0
answers
164
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. ...
- 11
1
vote
1
answer
439
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:
...
- 11
0
votes
1
answer
111
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 ...
- 203
1
vote
1
answer
47
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 ...
- 121
2
votes
0
answers
148
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 ...
- 21
0
votes
1
answer
149
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&...
0
votes
0
answers
42
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)$$
...
- 199
2
votes
1
answer
794
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)] = -\...
- 131
2
votes
1
answer
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 ...
- 213
0
votes
0
answers
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 ...
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 ...
- 51
0
votes
1
answer
280
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....
user119620
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'$ ...
- 262
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{...
- 215
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 ...
- 171
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 ...
- 1,602
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 ...
- 121
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 ...
- 133
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 ...
- 171
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 ...
- 1,081
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 ...
- 129
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 "...
- 333
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 ...
- 1,081
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$$
...
- 121
1
vote
2
answers
847
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 ...
- 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 ...
- 453