Application of Kolmogorov complexity and universal codes to identity testing and nonparametric testing of serial independence for time series

DOI10.1016/j.tcs.2006.06.004zbMath1097.68048OpenAlexW2121295993WikidataQ61711448 ScholiaQ61711448MaRDI QIDQ2503313

Jaakko T. Astola, Alexander Gammerman, Boris Ya. Ryabko

Publication date: 14 September 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.06.004

zbMATH Keywords

computational complexityalgorithmic information theoryhypothesis testingKolmogorov complexityalgorithmic complexitytheory of computationuniversal coding

Mathematics Subject Classification ID

Stationary stochastic processes (60G10) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Non-Markovian processes: hypothesis testing (62M07) General topics in the theory of algorithms (68W01) Source coding (94A29)

Related Items

Using data compressors to construct order tests for homogeneity and component independence ⋮ Testing composite hypotheses about discrete ergodic processes ⋮ Unnamed Item ⋮ Using ideas of Kolmogorov complexity for studying biological texts ⋮ Notes on sum-tests and independence tests ⋮ Application of data compression methods to nonparametric estimation of characteristics of discrete-time stochastic processes ⋮ Uniform hypothesis testing for finite-valued stationary processes ⋮ Discrimination between B-processes is impossible ⋮ Hydrozip: how hydrological knowledge can be used to improve compression of hydrological data

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Using information theory approach to randomness testing
• Universal codes as a basis for time series testing
• Twice-universal coding
• Prediction of random sequences and universal coding
• Monkey tests for random number generators
• The complexity and effectiveness of prediction algorithms
• Universal artificial intelligence. Sequential decisions based on algorithmic probability.
• The consistency of the BIC Markov order estimator.
• Universal codes as a basis for nonparametric testing of serial independence for time series
• Can an individual sequence of zeros and ones be random?
• Clustering by Compression
• The Similarity Metric
• Universal coding, information, prediction, and estimation
• Asymptotically optimal classification for multiple tests with empirically observed statistics
• Estimating the number of states of a finite-state source
• Minimum description length induction, Bayesianism, and Kolmogorov complexity
• Grammar-based codes: a new class of universal lossless source codes
• Universal lossless source coding with the Burrows Wheeler transform
• A universal predictor based on pattern matching
• On optimal sequential prediction for general processes
• On classification with empirically observed statistics and universal data compression
• On the estimation of the order of a Markov chain and universal data compression
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• The definition of random sequences