Martin-Löf randomness and Galton-Watson processes

DOI10.1016/J.APAL.2011.06.010zbMATH Open1247.03085arXiv1408.2875OpenAlexW2130722800MaRDI QIDQ764271FDOQ764271

Bjørn Kjos-Hanssen, David Diamondstone

Publication date: 13 March 2012

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

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$.

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)

Cites Work

• Title not available (Why is that?)
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• On the relation between descriptional complexity and algorithmic probability
• Random walks and percolation on trees
• Title not available (Why is that?)
• Lowness for Kurtz randomness
• Kolmogorov complexity and the Recursion Theorem
• Relations between varieties of kolmogorov complexities
• Title not available (Why is that?)
• Effectively closed sets of measures and randomness
• Title not available (Why is that?)
• Members of Random Closed Sets
• Algorithmic Randomness of Closed Sets
• Infinite subsets of random sets of integers
• Effective dimension of points visited by Brownian motion
• Trees Generated by a Simple Branching Process
• Title not available (Why is that?)
• Martin-Löf random generalized Poisson processes

Cited In (11)

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

   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 👍 👎

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)