Timeline for Why do statistical randomness tests seem so ad hoc?
Current License: CC BY-SA 2.5
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 26, 2010 at 20:31 | comment | added | R Hahn | Well, the KC is defined for finite strings. But 1.) it is only defined up to an additive constant (translating between Turing machines) and 2.) it isn't computable...yeah, Conway's Life is super fun. | |
| Sep 26, 2010 at 19:35 | comment | added | Yaroslav Bulatov | Shortest program for which Turing Machine? Here's a cool one rendell-attic.org/gol/utm/index.htm | |
| Sep 26, 2010 at 18:33 | comment | added | R Hahn | @Yaroslav Isn't Kolmogorov complexity defined in terms of finite objects. According to Li and Vitanyi (arxiv.org/pdf/cs/9901014v1) "the Kolmogorov complexity of a finite object $x$ is the length of the shortest effective binary description of $x$." (Appendix C of the linked manuscript is all about randomness tests and may be relevant to the OP.) | |
| Sep 15, 2010 at 18:08 | comment | added | Yaroslav Bulatov | But how do you define Kolmogorov complexity for finite string... | |
| Sep 2, 2010 at 18:59 | comment | added | Steve Huntsman | Kolmogorov complexity can be used to inform an entropy that captures the information in the OP's question as well as the latent information in intrasequence correlations. Without accounting for this, you can shuffle up chunks of a sequence so that the doublet, triplet,...,k-let frequencies match and yet the sequences themselves will be very different globally. | |
| Sep 2, 2010 at 18:39 | history | answered | Yaroslav Bulatov | CC BY-SA 2.5 |