Back to Search Start Over

On the Longest Head-Run in an Individual Random Sequence

Authors :
V. V. V'yugin
Source :
Theory of Probability & Its Applications. 42:541-546
Publication Year :
1998
Publisher :
Society for Industrial & Applied Mathematics (SIAM), 1998.

Abstract

In the framework of the Kolmogorov approach to verifying the theory of probability an analysis of a result of S. S. Samarova on the length of the longest head-run for the Markov chain with two states is given. This result is a refinement and generalization of P. Erdos and P.~Revesz's corresponding results. An analogous assertion is formulated and proved for individual random sequences. A complexity characterization of its application is also given.

Subjects

Subjects :
Statistics and Probability
Combinatorics
Discrete mathematics
Markov chain
Kolmogorov complexity
Chain rule for Kolmogorov complexity
Stochastic process
Kolmogorov structure function
Variable-order Markov model
Statistics, Probability and Uncertainty
Kolmogorov's criterion
Algorithmically random sequence
Mathematics

Details

ISSN :
10957219 and 0040585X
Volume :
42
Database :
OpenAIRE
Journal :
Theory of Probability & Its Applications
Accession number :
edsair.doi...........b1f6413790b4142944e52324c968ff9c
Full Text :
https://doi.org/10.1137/s0040585x97976337
Full Text Access
View/download PDF

Tools

Authors Abstract Subjects Details