Questions tagged [entropy]

The tag has no usage guidance.

101 questions
Filter by
Sorted by
Tagged with
5k 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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
942 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 (...
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 ...
7k views

999 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)$. ...
213 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 ...
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 ...
732 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 ...
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, ...
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 ...
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 ...
1k views

61 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 &...
123 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. ...
80 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 ...
143 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}$. ...
195 views

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 ... 1answer 127 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 ... 1answer 332 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 <... 1answer 166 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 ... 1answer 154 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)] = -\...
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 ...
(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$ ...