On the power of two choices: balls and bins in continuous time (Q2572391): Difference between revisions

The asymptotic behaviour of the following stochastic system is investigated: there are \(n\) bins, and balls arriving according to a Poisson process of intensity \(\lambda n\); upon each arrival, \(d\) of the \(n\) bins are chosen at random, and the new ball is placed into one of the least loaded of these \(d\) bins (\(d\geq 1\) is fixed). The \(\mathbb{Z}_+^n\)-valued process \((X_t)_{t\geq 0}\) indicating the number of balls present in each of the \(n\) bins in the course of time is obviously a Markov chain, but the main focus of the paper is on the asymptotics of \(M_t=\max_{1\leq j\leq n}X_t(j)\) as \(n\rightarrow\infty\), when time \(t\) varies in a polynomial interval \([0;n^K]\) (\(K>0\) fixed). The cases \(d=1\) and \(d\geq 2\) are considered separately, since the corresponding results and their proofs are quite different. One of the main results is the following: for \(d\geq 2\) and a process \((X_t)_{t\geq 0}\) started in equilibrium, fixing a constant \(K>0\), there exists a \(c=c(K)>0\) for which \[ P\left\{\max_{0\leq t\leq n^K} \biggl| M_t-\frac{\ln\ln n}{\ln d}\biggr| \leq c \right\}@>n\rightarrow\infty>> 1. \] Crucial to the proof of this result is a concentration inequality for the equilibrium measure of \((X_t)\), stating that for \(n\) sufficiently large and \(f\) any Lipschitz function on the state space \(\mathbb{Z}_+^n\), the equilibrium probability \(P\{| f(Y)-E[ f(Y)]| \geq u\}\) is bounded from above by \(e^{-(u^2/n)^{1/3}}\) for all values \(u\geq n^{1/2}\ln^{3/2}n\).