Tag Info

100

If you're using some hardware source of entropy/randomness, you're not "attempting to generate randomness by deterministic means" (my emphasis). If you're not using any hardware source of entropy/randomness, then a more powerful computer just means you can commit more sins per second.

76

Just because you can't see a pattern doesn't mean that no pattern exists. Just because a compression algorithm can't find a pattern doesn't mean that no pattern exists. Compression algorithms are not silver bullets that can magically measure the true entropy of a source; all they give you is an upper bound on the amount of entropy. (Similarly, the NIST ...

45

You've got a brilliant new compression scheme, eh? Alrighty, then... ♫ Let's all play, the entropy game ♫ Just to be simple, I will assume you want to compress messages of exactly $n$ bits, for some fixed $n$. However, you want to be able to use it for longer messages, so you need some way of differentiating your first message from the second (it cannot be ...

39

A lot of casual descriptions of entropy are confusing in this way because entropy is not quite as neat and tidy a measure as sometimes presented. In particular, the standard definition of Shannon entropy stipulates that it only applies when, as Wikipedia puts it, "information due to independent events is additive." In other words, independent events must ...

32

The title and the body of your question ask two different questions: how the OS creates entropy (this should really be obtains entropy), and how it generates pseudo-randomness from this entropy. I'll start by explaining the difference. Where does randomness come from? Random number generators (RNG) come in two types: Pseudo-random number generators (PRNG),...

28

Wow, great question! Let me try to explain the resolution. It'll take three distinct steps. The first thing to note is that the entropy is focused more on the average number of bits needed per draw, not the maximum number of bits needed. With your sampling procedure, the maximum number of random bits needed per draw is $N$ bits, but the average number of ...

22

There are $2^N-1$ binary strings of length less than $N$, and $2^N$ binary strings of length exactly $N$. This means that whatever your compression algorithm is, there must be some string which it can't compress at all, just because the mapping from original string to compressed string must be injective (one-to-one). This is the driving force behind many ...

20

I've always understood the quote to mean that a deterministic algorithm has a fixed amount of entropy, and although the output can appear "random" it can't contain more entropy than the inputs provide. From this perspective, we see that your algorithm smuggles in entropy via System.nanoTime() - most definitions of a "deterministic" algorithm would disallow ...

18

Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin. When you interpret "living in a state of sin" as "doing a nonsense", than it's perfectly right. What you did is using a rather slow method System.nanoTime() to generate rather weak randomness. You measured some ... entropy rate of ~5.3 bits/...

18

Here is a concrete encoding that can represent each symbol in less than 1 bit on average: First, split the input string into pairs of successive characters (e.g. AAAAAAAABC becomes AA|AA|AA|AA|BC). Then encode AA as 0, AB as 100, AC as 101, BA as 110, CA as 1110, BB as 111100, BC as 111101, CB as 111110, CC as 111111. I've not said what happens if there is ...

16

The entropy you've calculated isn't really for the specific string but, rather, for a random source of symbols that generates $A$ with probability $\tfrac{8}{10}$, and $B$ and $C$ with probability $\tfrac1{10}$ each, with no correlation between successive symbols. The calculated entropy for this distribution, $0.922$ means that you can't ...

14

Let's look at a slightly different way of thinking about Huffman coding. Suppose you have an alphabet of three symbols, A, B, and C, with probabilities 0.5, 0.25, and 0.25. Because the probabilities are all inverse powers of two, this has a Huffman code which is optimal (i.e. it's identical to arithmetic coding). We will use the canonical code 0, 10, 11 for ...

14

I thought I'd chime in on the meaning of "random". Most answers here are talking about the output of random processes, compared to the output of deterministic processes. That's a perfectly good meaning of "random", but it's not the only one. One problem with the output of random processes is that they're hard to distinguish from the outputs of deterministic ...

13

I am not at all an expert in this area, but I believe you will be interested in reversible computing. This involves, among other things, the study of the relationship between processes that are physically reversible and processes that are logically reversible. I think it would be fair to say that the "founders" of the field were/are Ralph Landauer and ...

13

Let $\mathcal{D}$ be the following distribution over $\{A,B,C\}$: if $X \sim \mathcal{D}$ then $\Pr[X=A] = 4/5$ and $\Pr[X=B]=\Pr[X=C]=1/10$. For each $n$ we can construct prefix codes $C_n\colon \{A,B,C\}^n \to \{0,1\}^*$ such that  \lim_{n\to\infty} \frac{\operatorname*{\mathbb{E}}_{X_1,\ldots,X_n \sim \mathcal{D}}[C_n(X_1,\ldots,X_n)]}{n} = H(\mathcal{...

12

No, if the algorithm is lossless no steps in the compression sequence can reduce its entropy - otherwise it would not be able to be decompressed/decoded. However, the additional entropy may be stored in 'out-of-band' information - such as the list that needs to be maintained in order to decode the move-to-front transform.

10

Here's the Kolmogorov complexity argument that @YuvalFilmus mentions in his answer. Your input here is a sed script of some size plus an input file of some size. Say the total size of the sed script plus the file is $n$ bits. There can be only $2^n$ inputs of size $n$ bits. Even if I let you have a sed script of less than $n$ bits (and don't charge you ...

10

You can't. Randomness is a property of the source, not a property of the values you get from that source. In other words, randomness is a statement about the probability distribution, not about some specific values sampled from that distribution; from a finite sample, you can't give a definite answer to your question. Or, to quote Dilbert: What you can ...

10

The two answers agree, with the following change: it's 1.63263 nats, not bits. That is, the value 1.63263 is calculated using the natural logarithm.

9

Entropy is a feature of a random variable. A given file has zero entropy, since it is constant. Entropy makes sense in many situation in which there is no channel, and you can apply it to a random ensemble of, say, WAV files, generated from a given source. In this case, your $x$ is the entire WAV file. The actual WAV file (excluding the header) can be ...

7

Mutual information tells you how much you learn about $X$ from knowing the value of $Y$ (on average over the choice of $Y$). In other words, mutual information measures how many fewer bits you need to encode $X$ if you already know $Y$, than if you didn't. In your example, learning $Y$ enables you to guess $X$ correctly with probability 0.75, but as $H_2(0.... 7 Imagine that your seed$s$has length$k$. Your PRNG is a deterministic function of the seed, so it outputs at most$2^k$different sequences of length$n$. There are$2^n$of these, so your scheme isn't going to work unless it falls back on just sending the whole$n$-bit string when there is no corresponding$s$. (As another answer noted, this will ... 7 Compression isn't an accurate test of randomness, and nor is looking at an image and saying "that looks random". Randomness is tested by empirical methods. There are in fact suites of specially designed software/algorithms for testing randomness, for example TestU01 and the Diehard tests. Furthermore, your image is in fact a 1D string of number mapped onto ... 6 I'm not familar with Carnot's Theorem, except what I've just read in Wikipedia, but even from that cursory introduction, there is a connection in the structure of the proofs, and that may be interesting to you, as it's a proof technique that is applicable in many domains. They're both proofs by contradiction in which to show that no thing in a given class ... 6 It is always possible to compress a single file. Given a file$f$, here is an encoding scheme which is especially good for compressing$f$. The empty string is used to encode$f$. Every other string encodes itself. We have succeeded reducing$f$to zero bytes! What is the catch? We didn't take into account the length of the decompression procedure. When we ... 6 In practice, in about 95% of cases, the correct answer is probably going to be: forget about those files, use /dev/urandom or CryptGenRandom() (or equivalent). They provide very high quality random numbers -- That's what they're designed for. So this is the most pragmatic answer, and it will provide excellent quality randomness. Let's say you can't do ... 6 They reduce the apparent entropy inherent in the structure of the original message. Or in other words they tune the message to make use of the strengths of the next stages of compression. One simple example would be replacing the name in the end tags of xml with a special symbol. You can perfectly recreate the original xml from that but the compressor doesn'... 6 Entropy coders do not compress the message to the minimum number of bits needed to represent it. I know it's tempting to think that, but it's not what they do. They aren't magic and they can't achieve that. Instead, they do something a bit less magical -- but still useful. Suppose for the moment that we knew that each character of the message was chosen ... 5 Yes, of course. Shannon's work was on the transmission of information over discrete, noisy channels. It centred on the trade-off between bandwidth and signal-to-noise ratio, and, grossly over-simplifying it, in particular what the maximum transmission rates could be with and without the presence of noise induced error and how to construct suitable codes. ... 5 A paper Computing the Entropy of a Large Matrix by Thomas P. Wihler, Bänz Bessire, André Stefanov suggests approximating$x \lg x\$ with a polynomial. Then you can use the trace of powers of the matrix to sum the results of applying that polynomial to each of the eigenvalues. (The polynomial-via-power-and-trace thing works because density matrices have ...

Only top voted, non community-wiki answers of a minimum length are eligible