Martin-Löf randomness and Galton-Watson processes

DOI10.1016/J.APAL.2011.06.010MaRDI QIDQ764271zbMATH OpenOpenAlexFDO

Authors Bjørn Kjos-Hanssen, David Diamondstone

Publication date 13 March 2012

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.2875

zbMATH Keywords

computability theoryGalton-Watson processesrandom closed setsMartin-Löf randomness

Mathematics Subject Classification ID

Combinatorial probability (60C05) Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: The members of Martin-L"of random closed sets under a distribution studied by Barmpalias et al. are exactly the infinite paths through Martin-L"of random Galton--Watson trees with survival parameter $frac23$. To be such a member, a sufficient condition is to have effective Hausdorff dimension strictly greater than $gamma=lo{g}_{2}frac32$, and a necessary condition is to have effective Hausdorff dimension greater than or equal to $gamma$.

Recommendations

• Members of Random Closed Sets
• Random closed sets viewed as random recursions
• Algorithmic Randomness of Closed Sets
• Martin-Löf random generalized Poisson processes
• Logical Approaches to Computational Barriers

Cites work

• scientific article; zbMATH DE number 1670880 (Why is no real title available?)
• scientific article; zbMATH DE number 44693 (Why is no real title available?)
• scientific article; zbMATH DE number 1249699 (Why is no real title available?)
• scientific article; zbMATH DE number 2216397 (Why is no real title available?)
• scientific article; zbMATH DE number 2222024 (Why is no real title available?)
• Algorithmic Randomness of Closed Sets
• Effective dimension of points visited by Brownian motion
• Effectively closed sets of measures and randomness
• Infinite subsets of random sets of integers
• Lowness for Kurtz randomness
• Martin-Löf random generalized Poisson processes
• Members of Random Closed Sets
• On the relation between descriptional complexity and algorithmic probability
• Random walks and percolation on trees
• Relations between varieties of kolmogorov complexities
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• Trees Generated by a Simple Branching Process

Cited in

(11)

• Algorithmically Random Functions and Effective Capacities
• Pathwise-randomness and models of second-order arithmetic
• Schnorr randomness for noncomputable measures
• Layerwise computability and image randomness
• Energy randomness
• Effective randomness of unions and intersections
• The Intersection of Algorithmically Random Closed Sets and Effective Dimension
• Martin-Löf random generalized Poisson processes
• The random members of a \({\Pi }_{1}^{0}\) class
• PA RELATIVE TO AN ENUMERATION ORACLE
• On semimeasures predicting Martin-Löf random sequences

This page was built for publication: Martin-Löf randomness and Galton-Watson processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q764271)