Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.