Decidable lim sup and Borel–Cantelli-like lemmas for random sequences

We prove computable versions of limsup events and Borel–Cantelli-like results for algorithmically random sequences using a coefficient from Kolmogorov complexity. In particular we show that under suitable conditions on events, limsup is layerwise decidable.

MoreLess

Year of publication:	2013
Authors:	Davie, George
Published in:	Statistics & Probability Letters. - Elsevier, ISSN 0167-7152. - Vol. 83.2013, 1, p. 278-285
Publisher:	Elsevier
Subject:	Algorithmically random sequence \| Layerwise decidable \| Effective Borel–Cantelli lemmas \| Kolmogorov complexity \| Compressibility coefficient

More details

Type of publication:	Article
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10010593912