Martin-Löf randomness and Galton-Watson processes

Abstract

The members of Martin-Löf random closed sets under a distribution studied by Barmpalias et al. are exactly the infinite paths through Martin-Löf random Galton--Watson trees with survival parameter $\frac{2}{3}$. To be such a member, a sufficient condition is to have effective Hausdorff dimension strictly greater than $\gamma ={\log }_2\frac{3}{2}$, and a necessary condition is to have effective Hausdorff dimension greater than or equal to $\gamma$.

Preliminary version: Members of random closed sets, Computability in Europe, Lecture Notes in Computer Science, vol. 5635, Springer, Berlin, 2009, pp. 144--153

References in corpus (2)

• Effective dimension of points visited by Brownian motion
• Infinite subsets of random sets of integers

Cited by in corpus (2)

• Finding subsets of positive measure
• Layerwise computability and image randomness