Open Problems:56 - Revision history

Krzysztof Onak: updated header

2013-03-07T02:00:02Z

updated header

Krzysztof Onak at 04:53, 12 December 2012

2012-12-12T04:53:39Z

Andoni: Created page with "{{Header |title=Efficient measures of ''surprisingness'' of sequences |source=dortmund12 |who=Rina Panigrahy }} Consider a sequence of iid random bits $S\in\{0,1\}^n$. '''Que..."

2012-12-12T01:51:03Z

Created page with "{{Header |title=Efficient measures of ''surprisingness'' of sequences |source=dortmund12 |who=Rina Panigrahy }} Consider a sequence of iid random bits $S\in\{0,1\}^n$. '''Que..."

New page

{{Header
|title=Efficient measures of ''surprisingness'' of sequences
|source=dortmund12
|who=Rina Panigrahy
}}
Consider a sequence of iid 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,...0,1,1,...1)$ is surprising (from the point of view of
densities it looks pretty random).

Ideal solution is to consider the Kolmogorov complexity, but it is
hard (impossible) to compute.

A particular setting of the strings to consider may be: suppose each
bit is generated from a biased independent coin, but the bias of the
coin changes (slowly?) over time. Is there a good compression here?

@@ Line 1: / Line 1: @@
 {{Header
 |source=dortmund12
 |who=Rina Panigrahy

@@ Line 1: / Line 1: @@
 {{Header
-|title=Efficient measures of ''surprisingness'' of sequences
+|title=Efficient Measures of &ldquo;Surprisingness&rdquo; of Sequences
 |source=dortmund12
 |who=Rina Panigrahy
 }}
-Consider a sequence of iid random bits $S\in\{0,1\}^n$.
+Consider a sequence of i.i.d. random bits $S\in\{0,1\}^n$.
-'''Question''': Find efficient measures of how surprising/unbelievable $S$
+'''Question:''' Find efficient measures of how surprising/unbelievable $S$
 appears to be. (Good heuristic for measuring how probable/improbably a
 string is.)
@@ Line 16: / Line 16: @@
 would correspond to taking the entropy of the empirical frequencies of
 s and 1s). However, it fails to say that a string like
-$(0,0,...0,1,1,...1)$ is surprising (from the point of view of
+$(0,0,\ldots,0,1,1,\ldots,1)$ is surprising (from the point of view of
 densities it looks pretty random).