×

zbMATH — the first resource for mathematics

Martin-Löf randomness and Galton-Watson processes. (English) Zbl 1247.03085
Summary: 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 23\). To be such a member, a sufficient condition is to have effective Hausdorff dimension strictly greater than \(\gamma = \log_2 \frac 32\), and a necessary condition is to have effective Hausdorff dimension greater than or equal to \(\gamma \).

MSC:
03D32 Algorithmic randomness and dimension
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
60C05 Combinatorial probability
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Logan Axon, Random closed sets and probability, Doctoral Dissertation, University of Notre Dame, 2010. · Zbl 06835068
[2] Barmpalias, George; Brodhead, Paul; Cenzer, Douglas; Dashti, Seyyed; Weber, Rebecca, Algorithmic randomness of closed sets, J. logic comput., 17, 6, 1041-1062, (2007), MR 2376074 (2008m:68069) · Zbl 1155.03031
[3] Diamondstone, David; Kjos-Hanssen, Bjørn, Members of random closed sets, (), 144-153 · Zbl 1233.03049
[4] Falconer, Kenneth, Fractal geometry, Mathematical foundations and applications, (1990), John Wiley & Sons Ltd. Chichester, MR 1102677 (92j:28008) · Zbl 0689.28003
[5] Gács, Péter, On the relation between descriptional complexity and algorithmic probability, Theoret. comput. sci., 22, 1-2, 71-93, (1983), MR 693050 (84h:60010) · Zbl 0562.68035
[6] Greenberg, Noam; Miller, Joseph S., Lowness for Kurtz randomness, J. symbolic logic, 74, 2, 665-678, (2009), MR 2518817 (2010b:03050) · Zbl 1168.03033
[7] Hawkes, John, Trees generated by a simple branching process, J. London math. soc. (2), 24, 2, 373-384, (1981), MR 631950 (83b:60072) · Zbl 0468.60081
[8] Kjos-Hanssen, Bjørn, Infinite subsets of random sets of integers, Math. res. lett., 16, 1, 103-110, (2009), MR 2480564 (2010b:03051) · Zbl 1179.03061
[9] Kjos-Hanssen, Bjørn; Merkle, Wolfgang; Stephan, Frank, Kolmogorov complexity and the recursion theorem, Trans. amer. math. soc., 363, 10, 5465-5480, (2011) · Zbl 1236.03032
[10] Kjos-Hanssen, Bjørn; Nerode, Anil, Effective dimension of points visited by Brownian motion, Theoret. comput. sci., 410, 4-5, 347-354, (2009), MR 2493984 (2009k:68100) · Zbl 1158.68017
[11] Lutz, Jack H., (), 902-913, MR 1795945 (2001g:68046)
[12] Lyons, Russell, Random walks and percolation on trees, Ann. prob., 18, 3, 931-958, (1990), MR 1062053 (91i:60179) · Zbl 0714.60089
[13] Mattila, Pertti, Geometry of sets and measures in Euclidean spaces, (), MR 1333890 (96h:28006) · Zbl 0911.28005
[14] Peter Mörters, Yuval Peres, Brownian Motion, Draft version of May 25, 2008. http://www.stat.berkeley.edu/ peres/.
[15] Jan Reimann, Computability and Fractal Dimension, Doctoral Dissertation, Universität Heidelberg, 2004. · Zbl 1080.03031
[16] Reimann, Jan, Effectively closed sets of measures and randomness, Ann. pure appl. logic, 156, 1, 170-182, (2008), MR 2474448 (2010a:03043) · Zbl 1153.03021
[17] Reimann, Jan; Stephan, Frank, Effective Hausdorff dimension, (), 369-385, MR 2143904 (2006b:03052) · Zbl 1098.03050
[18] Uspensky, V.A.; Shen, A., Relations between varieties of Kolmogorov complexities, Math. systems theory, 29, 3, 271-292, (1996), MR 1374498 (97c:68074) · Zbl 0849.68059
[19] Zvonkin, A.K.; Levin, L.A., The complexity of finite objects and the basing of the concepts of information and randomness on the theory of algorithms, Uspekhi mat. nauk, 25, (1970), no. 6(156), 85-127 (in Russian) MR 0307889 (46 #7004) · Zbl 0222.02027
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.