Questions tagged [entropy]
The entropy tag has no usage guidance.
9
questions
39
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 ...
11
votes
4answers
6k 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 ...
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, ...
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 ...
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 ...
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 ...
6
votes
2answers
185 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 ...
3
votes
1answer
120 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) = ...
2
votes
2answers
501 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 ...