Random minimal directed spanning trees and Dickman-type distributions (Q4662233)

Scatter \(n\) vertices on the unit square, and (using Euclidean distance \(\| \cdot \| \)), add an arc from each vertex to its nearest neighbor to the southwest (lower left), or, if there is no such neighbor, then to the origin. The result is a ``minimal directed spanning tree'' as introduced by \textit{A. G. Bhatt} and \textit{R. Roy} [Adv. Appl. Probab. 36, 19--42 (2004; Zbl 1055.60002)]. This paper derives limits for two random variables derived from these distributions. To do this, the paper first develops a ``generalized Dickman distribution'' GD(\(\theta\)) for each real \(\theta > 0\), and associates with it random variables \(X\), such that \(X \overset{D}{=} U^{1/\theta} (1 + X)\), for \(U\) being uniform on the unit interval and independent of \(X\). It also develops a ``max-Dickman distribution,'' and associates with it random variables \(M\) such that \(X \overset{D}{=}\max (1 - U, UM)\), \(U\) being uniform on the unit interval and independent of \(X\). This section is useful in itself, and as a result of its presence, the paper is quite accessible. The paper presents two results, each for either initially scattering \(n\) vertices uniformly on the unit square, or initially generating points with a Poisson point process of intensity \(n\). Either way, the following hold. Call a selected vertex point minimal if it has no nearest neighbor to the southwest, so that its arc runs to the origin. 1. Given \(\alpha > 0\) and \(n\), let \(\mathcal L\) be the following random variable. Given the minimal directed spanning tree, and letting \(X\) range over the minimal vertex points, let \(\mathcal L = \sum_X \| X \| ^{\alpha}\). Then as \(n \to \infty\), \(\mathcal L\) is asymptotically generalized Dickman, of parameter \(\theta = 2/\alpha\). 2. If \(\mathcal M\) is the maximal length of any edge, it is a random variable distribution asymptotically approaching that of the maximum of two ``max-Dickman'' random variables.