Questions tagged [entropy]
The entropy tag has no usage guidance.
97
questions
40
votes
7answers
4k views
Can PRNGs be used to magically compress stuff?
This idea occurred to me as a kid learning to program and
on first encountering PRNG's. I still don't know how realistic
it is, but now there's stack exchange.
Here's a 14 year-old's scheme for an ...
35
votes
6answers
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 ...
32
votes
7answers
2k views
Is there a connection between the halting problem and thermodynamic entropy?
Alan Turing proposed a model for a machine (the Turing Machine, TM) which computes (numbers, functions, etc.) and proved the Halting Theorem.
A TM is an abstract concept of a machine (or engine if ...
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 ...
25
votes
11answers
10k 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 ...
20
votes
2answers
6k views
How does an operating system create entropy for random seeds?
On Linux, the files /dev/random and /dev/urandom files are the blocking and non-blocking (respectively) sources of pseudo-random ...
18
votes
2answers
907 views
What's harder: Shuffling a sorted deck or sorting a shuffled one?
You have an array of $n$ distinct elements. You have access to a comparator (a black box function taking two elements $a$ and $b$ and returning true iff $a < b$) and a truly random source of bits (...
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 ...
12
votes
2answers
2k 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 ...
11
votes
4answers
7k views
Compression of Random Data is Impossible?
A few days ago this appeared on HN http://www.patrickcraig.co.uk/other/compression.htm. This refers to a challenge from 2001 - where someone was offering a prize of \$5000 for any kind of reduction to ...
10
votes
1answer
3k views
How to practically measure entropy of a file?
I'm trying to measure now much non redundant (actual) information my file contains. Some call this the amount of entropy.
Of course there is the standard p(x) log{p(x)}, but I think that Shannon was ...
10
votes
1answer
2k views
Constrainted Optimization Problem in Matrix Entropy
I have a constrainted optimization problem in the (Shannon) matrix entropy $\mathtt{(sum(entr(eig(A))))}$. The matrix $A$ can be written as the sum of rank 1 matrices of the form $[v_i\,v_i^T]$ where $...
8
votes
1answer
945 views
Rényi entropy at infinity or min-entropy
I'm reading a paper that refers to the limit as n goes to infinity of Rényi entropy. It defines it as ${{H}_{n}}\left( X \right)=\dfrac{1}{1-n} \log_2 \left( \sum\limits_{i=1}^{N}{p_{i}^{n}} \right)$. ...
7
votes
2answers
196 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 ...
7
votes
3answers
10k views
Shannon's entropy for an image
Shannon's entropy [plog(1/p)] for an image is a probabilistic method for comparing two pixels or a group of pixels.Suppose an image with a matrix of 3x3 has pixel intensity values
...
7
votes
1answer
723 views
Shannon Entropy to Min-Entropy
In many papers I've read that it is well known that the Shannon entropy of a random variable can be converted to min-entropy (up to small statistical distance) by taking independent copies of the ...
6
votes
2answers
2k views
Compressing normally distributed data
Given normally distributed integers with a mean of 0 and a standard deviation $\sigma$ around 1000, how do I compress those numbers (almost) perfectly? Given the entropy of the Gaussian distribution, ...
6
votes
1answer
1k views
Showing that the entropy of i.i.d. random variables is the sum of entropies
The shannon entropy of a random variable $Y$ (with possible outcomes $\Sigma=\{\sigma_{1},...,\sigma_{k}\}$) is given by
$H(Y)=-\sum\limits_{i=1}^{k}P(Y=\sigma_{i})\;\log(P(Y=\sigma_{i}))$.
For a ...
6
votes
1answer
1k views
Measuring entropy for a table (e.g., SQL results)
We're running some benchmarks for an approximative query-answering system. It's sufficient to just think of it as running some SQL queries with joins. We are counting the results returned as part of ...
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{...
5
votes
2answers
451 views
How do computers compute?
This is a kind of follow-up to a question I asked on superuser, where I asked for the definitions of a 'distinghuisable state' and a 'memory cell'. My questions where properly answered, but I was ...
5
votes
1answer
935 views
Mutual information intuition
I was creating an example for a casual talk on mutual information. I considered a system of two coins, which with probability 1/2 are copies of each other, and with probability 1/2 are independent.
...
5
votes
1answer
1k 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 ...
5
votes
2answers
808 views
Estimate entropy, based upon observed frequency counts
Suppose I have $n$ independent observations $x_1,\dots,x_n$ from some unknown distribution over a known alphabet $\Sigma$, and I want to estimate the entropy of the distribution. I can count the ...
5
votes
1answer
2k views
Pointwise mutual information vs. Mutual information?
I am learning about information theory and mutual information. However, I am quite confused with MI(Mutual information) vs. PMI(Pointwise mutual information) especially signs of MI and PMI values. ...
4
votes
1answer
359 views
Conceptual question about entropy and information
Shannon's entropy measures the information content by means of probability. Is it the information content or the information that increases or decreases with entropy? Increase in entropy means that ...
4
votes
2answers
163 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 ...
4
votes
2answers
359 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{...
4
votes
1answer
2k views
What units should Shannon entropy be measured in?
The only examples I've seen use bits as a measurement of entropy, but all these examples happen to use binary code alphabets. If we wanted to see how well a coding with a code alphabet of length n ...
4
votes
0answers
369 views
Is there a relationship between graph entropy and node entropy?
Eagle, et al [1] discuss the notion of node entropy and this is captured in igraph via the diversity metric. I was wondering if there was any relationship between these node entropies and the idea of ...
3
votes
1answer
1k views
Why is the Shannon entropy 0.94 in this example?
Suppose I have a decision tree in which there is a label $L$ under which is the attribute $A$ as shown below. I am given that the Shannon entropy of label $L$ is $H(L) = 0.95$.
I must find the ...
3
votes
2answers
831 views
Why Shannon's Entropy is said to be a measure of information?
I got a bit of how Shannon explained to find the number of bits required to represent a message and Shannon's Entropy.But it's natural to know that to code alphabet letters you need ...
3
votes
1answer
227 views
Source entropy and other questions related to information theory
Kolmogorov-Sinai entropy (KS) explains the mathematical concept behind KS entropy.
$$h ( T ) =\sup\limits_{\xi} \, h ( T , \xi )$$
defines the formula for KS where the left-hand side is nothing but ...
3
votes
1answer
302 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 ...
3
votes
1answer
237 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 $...
3
votes
1answer
120 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 ...
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 ...
3
votes
1answer
121 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
119 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. ...
3
votes
1answer
74 views
Maximum entropy probability distribution among Solomonoff priors
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 ...
3
votes
0answers
141 views
How to compare conditional entropy and mutual information?
I am solving a problem of information theory. The problem reads,
Consider a stationary memoryless channel specified by the channel matrix
$T = \begin{pmatrix}1-q&q\\r&1-r\end{pmatrix}$. ...
2
votes
2answers
524 views
How to extract randomness from a file?
I have a generator of files with approximately 7 bits /byte entropy. The files are about 30KB each in length. I'd like to use these as sources of entropy to generate random numbers. Theoretically I ...
2
votes
1answer
190 views
Increasing entropy of random walk
Let $P$ be a transition matrix of a random walk in an undirected (may not regular) graph $G$. Let $\pi$ be a distribution on $V(G)$. The Shannon entropy of $\pi$ is defined by
$$H(\pi)=-\sum_{v \in ...
2
votes
1answer
119 views
Entropy notation: What does this mean?
If you look at page 13 of the lecture slides here there is this line
$H(Y) = H((1-\pi)(1-\alpha), \alpha, \pi(1-\alpha))$
I don't really understand what the term on right hand side is. At first I ...
2
votes
1answer
256 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 <...
2
votes
1answer
153 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 ...
2
votes
1answer
68 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)] = -\...
2
votes
1answer
28 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 ...
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$ ...
2
votes
1answer
176 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 ...
