Recently, I've become interested in applied cryptography and stumbled upon a link explaining how Linux estimates entropy.
At some point, we're told that entropy estimation is based on first, second and third differences of the timestamps of certain system events. Fair enough. What I didn't understand was the intuition behind this, explained in the link as follows:
This use of deltas is approximately the same as attempting to fit an n degree polynomial to the previous n+1 points, then looking to see how far the new point is from the best prediction based on the previous n points. The minimum of the deltas is used, which has the effect of taking the best fit of a 0th, 1st or 2nd degree polynomial, and using that one.
To clarify, here's what (I think) I've understood. Taking the example of mouse events in the link:
Mouse event times 1004 1012 1024 1025 1030 1041
1st differences 8 12 1 5 11
2nd differences 4 11 4 6
3rd differences 7 7 2
Fit an n degree polynomial to the previous n+1 points: I guess that would be taking the (i+1)-th diff, which are the 1st diffs of the i-th diffs. These could be used to predict the next values of the i-th diff, hence the 'fitting'. E.g. the 1st diff explains how consecutive values of the mouse event line (0th diff) change.
How far the new point is from the best prediction based on the previous n points: I guess this is given by the (i+2)-th diff? E.g. after the last mouse event time, 1041, the 2nd diff is 6, which is how far 1041 (the new point) is from 1035 (the best prediction). The prediction is obtained by taking the previous 0th diff value, 1030, added to the previous 1st diff value, 5.
Use of minimum delta: My best guess is that the entropy estimator chooses minimum value, because it is the best fit for the (i-1)-th diff (or (i-1)-th degree polynomial). I think I understand how this method picks the best fit, but I really didn't get the 'why' though.
My doubts/questions are:
- I may be overlooking something obvious, but I still don't see the relation between my idea of n degree polynomial fitting (e.g. polynomial regression using a least squares method).
- What's the actual rationale behind choosing the minimum delta? Why does it provide a good measure of how unexpected the next data point is? Is it because the minimum delta is the most conservative?