Comment

Comment by njohnson41

Right, the amount of entropy per bit of sequence is always between 0 (deterministic) and 1 (every bit is independent and 50/50) (... or between 0 and log2(k) in general if the element varies over a set of k things). These "weak" sources just have low entropy per bit. They could be biased (more 0s than 1s) or correlated (long runs of 0s/1s or periodicity), or just have some other pattern that sometimes holds.

A deterministic PRNG's sequence has exactly the entropy of it's seed, actually, but it has 0 bits of entropy per symbol, because its sequence is infinite.

The thing most people get confused about with entropy is in thinking that entropy is a property of some single object, like a bit string. Really, entropy is always a measurement about a probability distribution, just like mean or variance is. In the usual case with random streams, the distribution is P(x_i | x_i-1 ... x_0) for bits x_i in the stream, i.e. the distribution remaining for the current bit even if we know all previous bits. For a deterministic PRNG, once we can extract the key from the history (given unlimited compute power) that distribution becomes deterministic, so the entropy is 0.

parent njohnson41 10 years ago

Discussion

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton