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

Improve this question
$\endgroup$
5
  • $\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
    Commented Oct 25, 2016 at 18:15
  • $\begingroup$ You're right, let me rephrase it. $\endgroup$
    – guy
    Commented Oct 25, 2016 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
    Commented Oct 25, 2016 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
    Commented Oct 25, 2016 at 18:23
  • $\begingroup$ The math sounds about right to me. $\endgroup$
    – SEJPM
    Commented Oct 25, 2016 at 20:29

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks tylo. For this theoretical case it is exact but I understand your point. $\endgroup$
    – guy
    Commented Oct 26, 2016 at 13:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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