2025/01/06 by Alan Frieze, Ravi Kannan, Frieze, Alan +3
Computer Science · Mathematics · #Data Management and Algorithms #FOS: Mathematics #Mathematical Dynamics and Fractals #Probability (math.PR) #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2501.03359
openalex publication_date 2025/01/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
We consider a simple model of a growing cluster of points in \Red,d≥ 2. Beginning with a point X1 located at the origin, we generate a random sequence of points X1,X2,…,Xi,…,. To generate Xi,i≥ 2 we choose a uniform integer j in [i-1]=\1,2,…,i-1\ and then let Xi=Xj+Di where Di=(δ1,…,δd). Here the δj are independent copies of the Normal distribution N(0,σi), where σi=i-α for some α>0. We prove that for any α>0 the resulting point set is bounded a.s., and moreover, that the points generated look like samples from a β-dimensional subset of \Red from the standpoint of the minimum lengths of combinatorial structures on the point-sets, where β=min(d,1/α).