Random Trees

Reading topics - March 21, 2024

Random trees are trees that are formed by stochastic processes.

Random binary trees correspond to random closed sets in the Cantor space.

Random trees in probability

They are produced by branching processes, point processes or recursively.

Random trees from point and branching processes

• Trees and Matchings from Point Processes

• Asymptotic genealogy of a critical branching process

• Random Trees, Levy Processes and Spatial Branching Processes

• Random trees and applications

• Probability on Trees and Networks (book)

Recursive constructions of random trees (Mauldin)

• Random recursive constructions

• Recursive construction of continuum random trees

• Random closed sets viewed as random recursions

Algorithmically random trees

They are based on algorithmic analogues of the probabilistic constructions.

Effective branching processes (Cenzer)

• Algorithmic randomness and capacity of closed sets

• Random Closed Sets

• Effective Capacity and Randomness of Closed Sets

• Algorithmic Randomness of Closed Sets

• Martin-lof randomness and Galton–Watson processes

• The intersection of algorithmically random closed sets and effective dimension

Effective point processes (Axon)

• Algorithmically random closed sets and probability (PhD thesis)

• Martin-lof randomness in spaces of closed sets

• Martin-lof random generalized Poisson processes

• Algorithmically random closed sets and probability (slides)

Path-randomness (trees with random paths)

• Pathwise-random trees and models of second-order arithmetic

• Growth and irreducibility in path-incompressible trees

• Dimensionality and randomness