Asymptotic results of a multiple-entry reinforcement process

DOI10.1016/J.SPA.2023.03.010MaRDI QIDQ6157009zbMATH OpenOpenAlexFDO

Authors Caio Alves, Rodrigo Ribeiro, Daniel Valesin

Publication date 19 June 2023

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

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

zbMATH Keywords

random graphsstochastic processes with reinforcement

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(4)

• MATRIX-MFO tandem workshop: Stochastic reinforcement processes and graphs. Abstracts from the MATRIX-MFO tandem workshop held March 5--10, 2023
• Clustering and cliques in preferential attachment random graphs with edge insertion
• Stochastic processes with competing reinforcements
• Asymptotic behavior for the principal eigenvalue of a reinforcement problem

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)