# Problem 56: Efficient Measures of “Surprisingness” of Sequences

Consider a sequence of i.i.d. random bits $S\in\{0,1\}^n$.
Question: Find efficient measures of how surprising/unbelievable $S$ appears to be. (Good heuristic for measuring how probable/improbably a string is.)
For example, if we see $0,0,0,\ldots$, we won't believe it is random (i.e., it is surprising.)
One existing measure is the ($k^{th}$-order) Shannon entropy $H_k$ ($H_0$ would correspond to taking the entropy of the empirical frequencies of 0s and 1s). However, it fails to say that a string like $(0,0,\ldots,0,1,1,\ldots,1)$ is surprising (from the point of view of densities it looks pretty random).