Avoiding defeat in a balls-in-bins process with feedback
From MaRDI portal
Publication:6476232
arXivmath/0510663MaRDI QIDQ6476232FDOQ6476232
Authors: Roberto I. Oliveira, Joel Spencer 
Publication date: 30 October 2005
Abstract: Imagine that there are two bins to which balls are added sequentially, and each incoming ball joins a bin with probability proportional to the p-th power of the number of balls already there. A general result says that if p>1/2, there almost surely is some bin that will have more balls than the other at all large enough times, a property that we call eventual leadership. In this paper, we compute the asymptotics of the probability that bin 1 eventually leads when the total initial number of balls is large and bin 1 has a fraction alpha<1/2 of the balls; in fact, this probability is exp(c_p(alpha)t + O{t^{2/3}}) for some smooth, strictly negative function c_p. Moreover, we show that conditioned on this unlikely event, the fraction of balls in the first bin can be well-approximated by the solution to a certain ordinary differential equation.
Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Combinatorial probability (60C05)
This page was built for publication: Avoiding defeat in a balls-in-bins process with feedback
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6476232)
