Poisson-Dirichlet branching random walks (Q1948689): Difference between revisions

Let \(T\) be the Ulam-Harris tree: a Ulam-Harris tree has vertex set \(V= \bigcup^\infty_{n=0} \mathbb{N}^n\), \(\mathbb{N}^0=\emptyset\), is rooted at \(\emptyset\) and has an edge from \(v\) to \(v_i\) for each \(v\in V\) and each \(i\in\mathbb{N}\). Let \({\mathbf X}= \{X_i: i\in\mathbb{N}\}\) be a random vector, \(X_i\in\mathbb{R}\cup\{+\infty\}\), the \(X_i\) are not necessarily independent of each other. Mark each vertex \(v\) with an independent copy \({\mathbf X}^v= \{X^v_i: i\in\mathbb{N}\}\) of \({\mathbf X}\). Then \({\mathcal T}:= (T,\{{\mathbf X}^v: v\in V\})\) is a branching random walk with displacement vector \({\mathbf X}\): for each \(v\in V\) and \(i\in\mathbb{N}\), \(X^v_i\) is the displacement from \(v\) to \(v_i\). Let \(S(v)= S(v,{\mathcal T})\) be the sum of the displacements on the path from the root to \(v\). Then \(M_n:= \inf\{S(v): v\in\mathbb{N}^n\}\) is the minimal displacement of any individual in the \(n\)th generation. Denote by \(\widetilde M_n\) the median of \(M_n\). If \({\mathbf X}\) has exponential steps, i.e., for all \(i\), \(X_i\) is distributed as the sum of \(i\) independent random variables exponentially distributed with parameter 1, then \(\widetilde M_n= n/e+ (3/2e)\log n+ O(1)\) and, for any \(c_1< e\) and any \(c_2< 1\), \(\operatorname{P}(M_n\leq\widetilde M_n- x)\ll c_1\exp\{-c_1x\}\) and \(\operatorname{P}(M_n\geq\widetilde M_n+ x)\ll c_2\exp\{-c_2 x\}\), \((n\geq 1,\;x\geq 0)\). As a corollary, the expected height of a random recursive tree is obtained within \(O(1)\). Two examples are the Poisson-Dirichlet branching random walk and the Poisson-weighted infinite tree.