Hipster random walks
- PDF / 586,239 Bytes
- 37 Pages / 439.37 x 666.142 pts Page_size
- 53 Downloads / 233 Views
Hipster random walks L. Addario-Berry1
· H. Cairns2 · L. Devroye3 · C. Kerriou1 · R. Mitchell1
Received: 18 September 2019 / Revised: 25 May 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract We introduce and study a family of random processes on trees we call hipster random walks, special instances of which we heuristically connect to the min-plus binary trees introduced by Robin Pemantle and studied by Auffinger and Cable (Pemantle’s Min-Plus Binary Tree, 2017. arXiv:1709.07849 [math.PR]), and to the critical random hierarchical lattice studied by Hambly and Jordan (Adv Appl Probab 36(3):824–838, 2004. https://doi.org/10.1239/aap/1093962236). We prove distributional convergence for the processes, after rescaling, by showing that their evolutions can be understood as a discrete analogues of certain convection–diffusion equations, then using a combination of coupling arguments and results from the numerical analysis literature on convergence of numerical approximations of PDEs. Keywords Recursive distributional equations · Random trees · Numerical analysis · Burgers’ equation · Porous medium equation · PDEs · Interacting particle systems Mathematics Subject Classification 60F05 · 65M75 · 60B10 · 60G18
B
L. Addario-Berry [email protected] H. Cairns [email protected] L. Devroye [email protected] C. Kerriou [email protected] R. Mitchell [email protected]
1
Department of Mathematics and Statistics, McGill University, Montréal, Canada
2
Department of Mathematics, Cornell University, Ithaca, USA
3
School of Computer Science, McGill University, Montréal, Canada
123
L. Addario-Berry et al.
1 Introduction Let T denote the complete rooted infinite binary tree. The root receives label ∅; children of node v receive labels v0 and v1. In this way generation-n nodes of T are labeled by the set Ln := {0, 1}n . For n ≥ 1, write Tn for the binary tree consisting of the root of T and its first n generations of descendants. The leaves of Tn are the nodes Ln in generation n; its internal nodes are precisely the nodes of Tn−1 . Fix any assignment F = ( f v , v ∈ T ) of binary functions f v : R × R → R to the nodes of T . Then for any n ≥ 1, the functions Fn = ( f v , v ∈ Tn ) may be viewed as turning Tn into a recursively constructed function of arity 2n , with inputs at the leaves of Tn and output at the root of Tn . More precisely, given real values z = (z v , v ∈ T ) for n ≥ 1 let Fnz : Tn → R be given by Fnz (v)
=
zv f v (Fnz (v0), Fnz (v1))
if v ∈ Ln if v ∈ Tn−1 .
(1)
When either the functions comprising F are random, or the inputs are random (or both), then Fn is itself a random function; a large number of problems in probability can be phrased in terms of such random functions. As a very simple example, fix p ∈ (0, 1), and independently for each v ∈ T define f v by f v (x, y) =
1 x +y+1
with probability p, with probability 1 − p.
Then Fn1 (∅) is distributed as the total number of individuals in the first n generations of a branching process with
Data Loading...
