Balls-in-Bins Processes with Feedback and Brownian Motion

DOI10.1017/S0963548307008577zbMATH Open1140.60041arXivmath/0510648OpenAlexW1985336848WikidataQ126235820 ScholiaQ126235820MaRDI QIDQ5448992FDOQ5448992

Roberto I. Oliveira

Publication date: 10 March 2008

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Abstract: In a balls-in-bins process with feedback, balls are sequentially thrown into bins so that the probability that a bin with n balls obtains the next ball is proportional to f(n) for some function f. A commonly studied case where there are two bins and f(n) = n^p for p > 0, and our goal is to study the fine behavior of this process with two bins and a large initial number t of balls. Perhaps surprisingly, Brownian Motions are an essential part of both our proofs. For p>1/2, it was known that with probability 1 one of the bins will lead the process at all large enough times. We show that if the first bin starts with t+lambdasqrt{t} balls (for constant lambdain R), the probability that it always or eventually leads has a non-trivial limit depending on lambda. For pleq 1/2, it was known that with probability 1 the bins will alternate in leadership. We show, however, that if the initial fraction of balls in one of the bins is >1/2, the time until it is overtaken by the remaining bin scales like Theta({t^{1+1/(1-2p)}}) for p<1/2 and exp(Theta{t}) for p=1/2. In fact, the overtaking time has a non-trivial distribution around the scaling factors, which we determine explicitly. Our proofs use a continuous-time embedding of the balls-in-bins process (due to Rubin) and a non-standard approximation of the process by Brownian Motion. The techniques presented also extend to more general functions f.

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

Recommendations

• The onset of dominance in balls-in-bins processes with feedback
• On the power of two choices: balls and bins in continuous time
• scientific article; zbMATH DE number 2119677
• scientific article; zbMATH DE number 7662444
• A scaling result for explosive processes

zbMATH Keywords

discrete-time Markov processball-in-bins pocess

Mathematics Subject Classification ID

Brownian motion (60J65) Discrete-time Markov processes on general state spaces (60J05)

Cites Work

• Statistical mechanics of complex networks
• Reinforced random walk

Cited In (11)

• Large deviations for generalized Polya urns with arbitrary urn function
• On the duration and intensity of cumulative advantage competitions
• Asymptotics of generalized Pólya urns with non-linear feedback
• A scaling result for explosive processes
• Title not available (Why is that?)
• Stochastic processes with competing reinforcements
• Title not available (Why is that?)
• Decision-making with distorted memory: escaping the trap of past experience
• First passage properties of a generalized Pólya urn
• The onset of dominance in balls-in-bins processes with feedback
• Random walks exhibiting anomalous diffusion: elephants, urns and the limits of normality

This page was built for publication: Balls-in-Bins Processes with Feedback and Brownian Motion

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