Asymptotic results of a multiple-entry reinforcement process

DOI10.1016/J.SPA.2023.03.010zbMATH Open1523.60173arXiv1908.10260OpenAlexW3135076699MaRDI QIDQ6157009FDOQ6157009

Authors: Caio Alves, Rodrigo Ribeiro, Daniel Valesin 

Publication date: 19 June 2023

Published in: Stochastic Processes and their Applications (Search for Journal in Brave)

Abstract: We introduce a class of stochastic processes with reinforcement consisting of a sequence of random partitions ${mathcal{P}_t}_{tge1}$, where $mathcal{P}_t$ is a partition of $1,2,dots,Rt$. At each time~$t$,~$R$ numbers are added to the set being partitioned; of these, a random subset (chosen according to a time-dependent probability distribution) joins existing blocks, and the others each start new blocks on their own. Those joining existing blocks each choose a block with probability proportional to that block's cardinality, independently. We prove results concerning the asymptotic cardinality of a given block and central limit theorems for associated fluctuations about this asymptotic cardinality: these are proved both for a fixed block and for the maximum among all blocks. We also prove that with probability one, a single block eventually takes and maintains the leadership in cardinality. Depending on the way one sees this partition process, one can translate our results to Balls and Bins processes, Generalized Chinese Restaurant Processes, Generalized Urn models and Preferential attachment random graphs.

Full work available at URL: https://arxiv.org/abs/1908.10260

Recommendations

• A survey of random processes with reinforcement
• Interacting reinforced-urn systems
• Asymptotics for the number of blocks in a conditional Ewens-Pitman sampling model
• A random clustering process
• Asymptotics of random partitions of a set

zbMATH Keywords

random graphsstochastic processes with reinforcement

Mathematics Subject Classification ID

Random walks on graphs (05C81) Other physical applications of random processes (60K40)

Cites Work

• On tail probabilities for martingales
• Emergence of Scaling in Random Networks
• Exchangeable and partially exchangeable random partitions
• The Maximum Degree of the Barabási–Albert Random Tree
• Complex graphs and networks
• Reinforced random walk
• The sampling theory of selectively neutral alleles
• A survey of random processes with reinforcement
• A time-dependent version of Pólya's urn
• Urn-related random walk with drift \(\rho x^{\alpha } / t^{\beta }\)
• Edge Exchangeable Models for Interaction Networks
• Spatial preferential attachment networks: power laws and clustering coefficients
• Pólya urns with immigration at random times
• Concentration in the generalized Chinese restaurant process
• Large deviation principles for the Ewens-Pitman sampling model
• Preferential attachment random graphs with edge-step functions
• An approximate theory for substructure propagation in clusters
• Disparity of clustering coefficients in the Holme‒Kim network model

Cited In (2)

• Asymptotic behavior for the principal eigenvalue of a reinforcement problem
• Clustering and cliques in preferential attachment random graphs with edge insertion

This page was built for publication: Asymptotic results of a multiple-entry reinforcement process

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6157009)