1
$\begingroup$

Let's say you are looking to collect some randomness from your computer. At a given time stamp, you can always collect the following 16bits as part of the time stamp:

  • First 5 bits are fixed and always the same
  • The next 4 bits are not perfectly random and exhibit a probability of 1/8 for the different possibilities
  • Finally the last 7 bits are perfectly random, always

What would be the min entropy of one time stamp?

My intuition thinks the min entropy would be 3 bits (from the 4 imperfect bits) + 7bits from the last section, giving Min Entropy = 10 bits for one time stamp. Does this make sense?

EDIT: Rephrased the 2nd bullet point

$\endgroup$
  • $\begingroup$ Your second sentence makes no sense. There are 16 possible combinations, they can't all have the probability 1/8, since that's 200%. Also that'd be uniform "perfectly random". $\endgroup$ – CodesInChaos Oct 25 '16 at 18:15
  • $\begingroup$ You're right, let me rephrase it. $\endgroup$ – guy Oct 25 '16 at 18:17
  • $\begingroup$ I still don't get your second point. You mean that 8 of the 16 possible values are chosen with probability 1/8 and the other 8 possible values are never chosen? $\endgroup$ – CodesInChaos Oct 25 '16 at 18:20
  • $\begingroup$ Yes exactly! Let me know if I should rephrase it again. I understand it is strange. (Hence my confusion) $\endgroup$ – guy Oct 25 '16 at 18:23
  • $\begingroup$ The math sounds about right to me. $\endgroup$ – SEJPM Oct 25 '16 at 20:29
0
$\begingroup$

If your probabilities are exact, then your math is right. But even if they are off by the slightest amount (e.g. $2^{-10000}$), it doesn't hold any more. For a practical system like timestamps in a computer, it's quite unlikely that your have exact values for the probabilities. If those probabilities are average measurements, then the resulting entropy is also only an average and not a lower bound (minimum).

$\endgroup$
  • $\begingroup$ Thanks tylo. For this theoretical case it is exact but I understand your point. $\endgroup$ – guy Oct 26 '16 at 13:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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