Hot answers tagged

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.


75

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


43

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


31

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


21

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

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

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


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

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


8

Edit: A colleague informed me that my method below is an instance of the general method in the following paper, when specialized to the entropy function, Overton, Michael L., and Robert S. Womersley. "Second derivatives for optimizing eigenvalues of symmetric matrices." SIAM Journal on Matrix Analysis and Applications 16.3 (1995): 697-718. http://ftp.cs....


8

Is this even true? Consider an undirected graph which is a star. That is, a central vertex $V_0$ is connected to all other vertices $V_1, V_2, \dots, V_{n-1}$, and there are no other edges in the graph. Then, if you start with an equal distribution on $V_1, V_2, \ldots, V_{n-1}$, after one step all the weight is on the central vertex $V_0$. So in one step ...


8

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


8

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


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

Suppose $p_1 = \max_i p_i$. We have $$ p_1^n \leq \sum_{i=1}^N p_i^n \leq N p_1^n. $$ Therefore $$ \frac{n \log p_1 + \log N}{1-n} \leq H_n(X) \leq \frac{n \log p_1}{1-n}. $$ As $n \rightarrow \infty$, $\log N/(1-n) \rightarrow 0$ while $n/(1-n) \rightarrow -1$.


7

Back to the definitions: $$H(L\mid A) = \sum_a p(A=a) H(L \mid A=a).$$ As you compute, $P(A=true)=6/8$ and $P(A=false)=2/8$. However, you don't compute $H(L\mid A=true)$ but instead compute $P(L=positive\mid A=true)$. [and the same for $A=false$.]. With standard definition of $H()$ we get, $$H(L\mid A=true) = - 4/6\log_2(4/6) - 2/6\log_2(2/6) = 0....


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

By Landauer's principle, if you want to take a uniform random permutation of $n$ keys to a sorted one, and not keep any bits in the computer which reveal what the uniform random permutation was, you need to erase $log n! \approx n \log_2 n$ bits. This will take $(n \ln n) k T$ energy. On the other hand, the computation taking the sorted array and $n \log_2 n$...


6

This is a consequence of the asymptotic equipartition property (AEP), which is a form of the law of large numbers. The AEP states that if a random variable has (binary) entropy $H$ and you take $n$ copies of it, then most of the data points have probability roughly $2^{-nH}$. This is only true for most data points, which is the source of the small ...


6

I'm not entirely sure if I understood the question the way it was intended, but what computers do is that they operate on electricity, so they don't have two discrete logical values $0$ and $1$ per se. What they do have is electricity with voltage, and they are made to operate as if there were two logical values $0$ and $1$ if the voltage at a gate is below ...


6

If you look at wikipedia you see that topological entropy is modeled after Kolmogorov-Sinai (KS) entropy, but it is defined without reference to a probability measure $\mu$ on the space. For KS entropy, you need to use Shannon entropy: $-\sum_i\mu(X_i) \log \mu(X_i)$ for some partition of the space $\{X_i\}$, which can only be defined if you have some ...


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