In Information Theory, entropy is defined as the unpredictability of information content and, as such, the entropy of the output from so-called pseudo random number generators (PRNG) is often measured as a test of their "randomness". An interesting paradox arises with this definition... Start with a suitable seed, \(S_n\), consisting of an array of n previously generated pseudo-random numbers from the function \(PRNG(seed)\). In order to maximize the randomness of \(PRNG\) we want \(PRNG(S_n)\) to return a result such that the entropy of \(S_{n+1}\) is also maximized. Such a result can be distinct, given a suitable seed. However, in an effort to maximize the randomness of \(PRNG\) we have now created a process which is deterministic and completely predictable, which directly contradicts the proclaimed unpredictability of information content through high entropy. Please Register or Log in to view the hidden image!
I would say information entropy is the unpredictability of transmitting a message down some channel, that is, it's basically the difference between being able or unable to detect if the message has been modified by transmission. Because a sender can be modelled by an encoder, likewise a receiver "decodes" a message, these two elements don't change the message (information is preserved by "successful" transmission, i.e. communication). In other words, if a message is sent but the receiver doesn't "expect" it because it's been changed, it has more entropy than an unchanged message. Say the message is some line from Shakespeare, but the words get rearranged by the transmission, then the result has more entropy because it isn't expected (or it's been "randomised"). That's my somewhat simplistic take on it, but I've only studied Information Theory and Encoding Theory at 3rd year level, maybe we need a graduate. Oh, wait, I am a graduate.
This was really just a philosophical point that a "perfect" RNG, even one which does not qualify as a PRNG, would actually be deterministic.
Sure, anything that uses a logical process (such as an algorithm) to determine a result is deterministic.
But your seed won't be random, unless it can model random changes to some message, i.e. unless it models the transmission, with errors, of a message.
The seed can be anything we want, pulled from any arbitrary source, it doesn't have to have been previously produced by PRNG. The problem stems from the fact that our PRNG function "knows about" the evaluation function, kind of like a Volkswagen running diesel fuel. Please Register or Log in to view the hidden image!
These days, randomization seeds themselves require "entropy inputs": http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf
There's a big misconception here. The entropies used in information theory are all defined in terms of underlying probability distributions. For example, for a probability distribution \(p(x)\), the Shannon entropy associated with it is defined as \(\displaystyle H(X) = - \sum_{x} p(x) \log_{2} \bigl( p(x) \bigr) \,.\)This means that "measuring" an entropy amounts to the same problem as estimating a probability distribution. There isn't a general method for doing this that always works. In particular, you cannot in general look at a sequence of outcomes and immediately know what its entropy (or rather, the entropy associated with the process that produced it) is. It's possible that some people might "measure" an entropy by, e.g., counting in what fraction of cases each possible outcome is seen in repeated trials and putting the frequencies in the formula for the Shannon (or some other) entropy, but then there are caveats: The result is only likely to be a good estimate of the corresponding information-theoretic entropy (and randomness) if certain appropriate conditions hold (e.g., the underlying process is i.i.d.). Deterministic processes could easily be attributed "high entropy" if such conditions don't hold. E.g.: the deterministic string 0101010101010101... could be attributed high binary entropy if this is "measured" by naively counting the frequency of 0s and 1s. This doesn't mean you can't "measure" the entropy like this to test a PRNG, but if you do, it's significance would be comparable to other tests that are used (i.e., high entropy wouldn't guarantee a good PRNG but low entropy could be considered a sure sign of a bad one).
I'll have another go at it, although przyk has done quite a good job. Continuing with the notion of messages being received from some channel, the problem is for the receiver to determine which message (from some set of messages) was sent, or generally determining what the message is. If the channel modifies the message there is a probability that the receiver can determine what the unmodified message is using some error correcting algorithm, except the receiver can't be certain that the algorithm has corrected all (or any) errors. Transmission of information is probabilistic then; we can only design coding systems and error correction algorithms with a high probability of working properly, but not 100% probability. Or consider taking a poll of some kind. The poll is taken because the outcome isn't known (or can only be estimated), and the results give new information; the results of such a poll are analogous to a received message with a high entropy. That is, the information gained from the poll has more entropy than a subsequent poll for the same information, whose result should not give much new information, so it has less entropy than the results of the first poll. So this is like receiving two similar messages, and similar messages have low relative entropy of information. The polling method and gathering of results is analogous to an encoding (with or without error detection/correction).
The entropy-measurement function itself is arbitrary (it could consist of many different processes, including digit frequency), the only important aspect of it is that when the function is applied to the seed a unique solution is given to increase entropy. I was working under the presumption of an equal probability distribution ("no bias") but another poster and I discussed on PhysicsForums that this would also work with biased outcomes if the entropy-measuring function was aware of this bias. On PhysicsForums I also mentioned that a "suitable seed" is precisely one which deviates from an ideal distribution (i.e. a distribution in which entropy can be increased). I considered a PRNG with a seed of a million digits in which the 8 is grossly underrepresented: the PRNG would do well to return a result of 8 if it aspired for the highest entropy of \(S_{n+1}\). But, knowing this as observers, the 8 becomes perfectly predictable. My trivial conclusion is that this whole distraction really just supports the notion that high entropy is unpredictable. Please Register or Log in to view the hidden image!
The last part of my response also applies to arbitrary functions. There is no paradox because in general there is no test that can prove that a given sequence of digits was produced by a truly random process. The best a randomness test can do is weed out bad randomness generators (e.g. by looking for patterns that you wouldn't expect to see in a randomly generated sequence). (Also, I don't see what your point is even supposed to be. One of the uses of randomness tests is to test the quality of PRNGs, which are deterministic, so it should already be a given that deterministic processes can score well on "randomness" tests.) Huh? Functions like the Shannon entropy are always maximised by the uniform probability distribution. This means that if you use the frequency of outcomes as an estimate of the probability distribution then any "unbiased" string will always have maximal entropy, including strings that just cycle through the available alphabet like 0101010101 or ABCABCABC.
Note my wording in the OP. It's my personal opinion that there is simply no such thing as a truly random process but that's another issue. I'm not claiming that this thread is making some sort of profound statement, just that paradoxically a PRNG aspiring to be as unpredictable (random) as possible paradoxically becomes predictable under certain circumstances. It's like a student who cheats on a test and actually fails because he copied the answer key perfectly. Of course this is true. Again, please refer to the wording in the OP. A simple measurement of frequency by itself would be a pretty rotten measurement of unpredictability. I didn't propose a specific method for measuring entropy, I just mentioned the fact that entropy is often used to rate PRNGs.
Whether a string of symbols is random, or whether the string has been produced by a random process, are different things. A random 'machine' can produce strings that aren't random. Toss a coin enough times and some pattern will emerge for a while, just through probability. If a poll is unintentionally biased because more people who support one side are polled than people who support the other side, is the polling method still random?
What does this mean, "any minimal program is necessarily random"?, how is it proved? Furthermore, is there a relation between a minimal program and a minimal FSA that accepts the output of a program? My question is: given some formal language, L, over an alphabet, are expressions that define strings in L congruent with minimal algorithms? Well, here's an easy example. A coin toss is a minimal algorithm, and you can define all possible strings of coin tosses of a fair coin just with \( (0,1)^*\), or substitute \( (0,1)^n \), for any n. Coin tosses are always random, even with a biased coin.
