Balls-in-Bins Processes with Feedback and Brownian Motion

DOI10.1017/S0963548307008577MaRDI QIDQ5448992zbMATHOpenAlexWikidataFDO

Authors Roberto I. Oliveira

Publication date 10 March 2008

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

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

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)

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.

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

Cites work

• Reinforced random walk
• Statistical mechanics of complex networks

Cited in

(11)

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

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)