# 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$ ...