Poisson trees, succession lines and coalescing random walks
Pablo A. Ferrari, C. Landim, H. Thorisson · 2013
Abstract. We give a deterministic algorithm to construct a graph with no loops (a tree or a forest) whose vertices are the points of a d-dimensional stationary Poisson process S ⊂ R d. The algorithm is independent of the origin of coordinates. We show that (1) the graph has one topological end —that is, from any point there is exactly one infinite self-avoiding path; (2) the graph has a unique connected component if d = 2 and d = 3 (a tree) and it has infinitely many components if d ≥ 4 (a forest); (3) in d = 2 and d = 3 we construct a bijection between the points of the Poisson process and Z using the preordertraversal algorithm. To construct the graph we interpret each point in S as a space-time point (x, r) ∈ R d−1 × R. Then a (d − 1) dimensional random walk in continuous time continuous space starts at site x at time r. The first jump of the walk is to point x ′ , at time r ′> r, (x ′ , r ′ ) ∈ S, where r ′ is the minimal time after r such that |x − x ′ | < 1. All the walks jumping to x ′ at time r ′ coalesce with the one starting at (x ′ , r ′). Calling (x ′ , r ′ ) = α(x, r), the graph has vertex set S and edges {(s, α(s)), s ∈ S}. This enables us to shift the origin of S ◦ = S +δ0 (the Palm version of S) to another point in such a way that the distribution of S ◦ does not change (to any point if d = 2 and d = 3; point-stationarity). Key words and phrases. Poisson processes, random trees, Palm measure, coalescing random walks, point-stationarity, Palm theory.