There are all sorts of definitions of "random". I tend to be more interested in random bit generators, rather than random streams of bits; there's a reason. Indeed, strings do not have entropy, a systems of messages (with messages composed of a particular alphabet) have an entropy.

A less formal definition (well, less burdened with the artifacts of formal information theory, anyway), let X be a random variable which takes on a finite set of values: x_1, x_2, x_3..., x_n, with probability P(X = x_i) = p_i, (where p_i is the standard 0 <= p_i <= 1) and Sum[from i = 1 to n] (p_i) = 1, the entropy of X is expressed as H(X) = Sum [from i=1 to n] (p_i * lg(1/p_i)).

OK, sorry about that. Anyway, notice that we're talking about the entropy of X (the system), here, not the entropy of x_1 (a message of the system). When we talk about strings being low or high entropy, it's really shorthand for saying "This string was produced by a system that has low entropy".

So, a string doesn't have an entropy separate from its system. Now, having said that, strings _do_ have something called "Kolmogorov Complexity". Kolmogorov Complexity is the size of the smallest program that can produce a particular string. For a string, the highest Kolmogorov Complexity it can have is the size of the string. The lowest would be a very small program that produces a very large string.

As you might expect, entropy and Kolmogorov Complexity are related. You would expect a message from a high entropy system to have a high Kolmogorov Complexity (in fact, the Kolmogorov Complexity should be comparable to the entropy of the system). Further, you get some intuitively nice results where the Kolmogorov Complexity of any output of a PRNG is the size of the PRNG state, plus a bit for the PRNG algorithm, which agrees nicely with the entropy of the system, which is (at best) size of the PRNG state.

Anyway, further, I just wanted to mention that the attack goals for PRNGs revolve around two goals: 1) A PRNG should pass all polynomial-time statistical tests; that is to say, that no polynomial-time algorithm should be able to distinguish between an output of your PRNG and a truly random source. (Note, the attacker gets oracles for both a truly random source and your PRNG here...) 2) The PRNG should pass the next-bit test (which is the one you mentioned). So, there should be no polynomial-time algorithm that after seeing the first l bits of output should be able to predict the l+1 bit with probability better than .5. It just so happens that you can prove that the PRNG passes the next-bit test if and only if the PRNG passes all polynomial-time algorithm statistical tests.