Suppose I have a file with random binary strings of the same length in each line

Question

Suppose I have a file with random binary strings of the same length in each line.

If I'm computing the conditional entropy H(Y|X) where Y is the variable string of fixed length l which is after X, and X is the variable string of length m, and I find (lets say) l=5 and m=10 that the value of conditional entropy is 3. Does that mean that, given 10 bits, it is enough to predict 3 of the next to fully recover the next 5 bits? Simpler asked: does that mean my strings are not really randomly generated?

Explanation / Answer

It means that, given the 10 bits of X, then on average Y has 3 bits of entropy (the average taken over the possible values of X).

Thus, for your parameters, it does mean your strings are not really randomly generated (they weren't drawn uniformly at random from all possible strings of that length).

It doesn't mean that given X, Y will always have exactly 3 bits of entropy, regardless of X. The amount of entropy in Y might depend upon the specific value of X you are given. Example: it might be that if you're given X=0000000000, Y has 2 bits of entropy, but if you're given X=1111111111, Y has 4 bits of entropy.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.