# Suggestions for dealing with the “timed” balls-into-bins model

Definitions: Let $T$ (for "time") be a random variable $T \sim \text{Exp}(\lambda)$ and $\Delta t$ is a realization (or called an observed value) of $T$. Let $D$ (for "delay") be a random variable $D \sim \text{Exp}(\mu)$. All the random variables (including those involved below) are mutually independent.

Timed Balls-into-Bins Model: There are $n$ bins. Consider two robots $R_1$ and $R_2$ which can produce multiple balls instantaneously.
At time 0, robot $R_1$ (1) produces $n$ balls instantaneously; (2) Immediately, these $n$ balls are independently sent to the $n$ bins, one ball per bin; (3) The delays for the balls going from the robot to its destination bin are IID with the same distribution as $D$ defined above.
At time $\Delta t$ (defined above), robot $R_2$ independently does exactly the same thing as robot $R_1$ does (i.e., (1), (2), and (3) for robot $R_1$ above).

Consider the time point $t$ when half (more precisely, $\lfloor n/2 \rfloor + 1$) of the $n$ bins have received the balls from $R_2$ (no constraints on the balls from $R_1$), and denote the set of these $\lfloor n/2 \rfloor + 1$ bins by $B$.

Question: What is the probability $\mathbb{P}$ of the event $E$ that there exists a bin $b_{\Box} \in B$ which receives a ball from $R_1$ before receiving a ball from $R_2$?

Have similar balls-into-bins models been studied in the literature?
Any suggestions (not a complete solution) towards a closed form/approximation/numerical results (by using mathematical systems)/(even) simulations of the probability $\mathbb{P}$?
It is OK to simplify this model for possible tractability, for example, by using $D \sim U(a,b)$.

• It seems odd to allow a negative delay. – Douglas Zare May 28 '15 at 3:09
• @DouglasZare oops, thanks for pointing it out. I have changed it to an exponential random variable $D \sim \text{Exp}(\mu)$ – hengxin May 28 '15 at 3:22

(I use the notation from my comments). By symmetry, $$\mathbb{P}(E^c)={n \choose m}\,\mathbb{P}(E^c, B=\{1,\ldots,m\})\;\;.$$ If $D_1=M_m\;\;$ we have to compute $$I_1:=\mathbb{P}(D_1^\prime>t+M_m,D_2^\prime>t+D_2,\ldots,D_m^\prime>t+D_m, D_{m+1}>M_m,\ldots,D_n>M_m)$$ Conditioning on $M_m=D_1,D_2,\ldots,D_m$ and using the independence assumptions gives $$I_1=\int e^{-\mu_1(t+s)}\left(\prod_{i=2}^m e^{-\mu_1(t+x_i)}\right) e^{-\mu_2(n-m)s} f(s,x_2,\ldots,x_m)\,dx_2\ldots dx_m\,ds$$ where $f(s,x_2,\ldots,x_m)=1_{[0,\infty[}(s) \mu_2e^{-\mu_2s} \prod_{i=2}^m \mu_2e^{-\mu_2x_i}1_{[0,s]}(x_i)$. After carrying out the $x_i$ integrals $$I_1=e^{-m\mu_1t}\mu_2^m\int_0^\infty e^{-(\mu_1+\mu_2)s}\left({1-e^{-(\mu_1+\mu_2)s}\over \mu_1 +\mu_2}\right)^{m-1} e^{-\mu_2(n-m)s}\,ds$$ and the substitution $y=1-e^{-(\mu_1+\mu_2)s}$ gives $$I_1=e^{-m \mu_1 t}\alpha^m\,B(m,\alpha (n-m)+1)$$ Finally, by symmetry the cases $D_2=M_m$,...,$D_m=M_m$ give the same result, so that$$\mathbb{P}(E^c)=m{n\choose m} e^{-m\mu_1t}\alpha^m\,B(m,\alpha(n-m)+1)=e^{-m\mu_1t}{\alpha^m\,B(m,\alpha(n-m)+1)\over B(m,n-m+1)}$$

• What if I interchange $t$ with $−t$ from the beginning (i.e., $D'_i > D_i - t$ now)? It seems that in the final result only $t$ needs to be changed to $−t$. However, this may give probability values larger than 1. Could you please give me some suggestions? Thanks. – hengxin Jun 14 '15 at 6:33
• For the case of $D'_i > D_i - t$ ($t \ge 0$), the corresponding probability $\mathbb{P}(D'_i > x_i - t)$ depends on the relation between $x_i$ and $t$: if $x_i - t \ge 0$, it is $e^{\mu_1(t-x_i)}$; otherwise, it is $1$. How should I take into account both cases in the calculations? My basic idea is to integrate each $x_i$ over $[t,s]$ and $s$ over $[t,\infty[$. However, can we still obtain an explicit formula for this case? What do you think of it? Thanks. – hengxin Jun 14 '15 at 8:13
• You clearly can still reduce to a one-dimensional integral, but because here the integrand changes at $s=t$ I don't expect an explicit formula in terms of classical functions. – esg Jun 14 '15 at 14:49
• I have integrated your result here into a paper (which will be available at arXiv in two days). Now I cite your contributions through the link to this MO problem. What else should I do? If you want to obtain a copy of the paper or have any questions, please feel free to contact me. (You can find my email in my profile.) Thanks a lot. – hengxin Jul 7 '15 at 7:30
• I haven't found your paper. Is it on the arXiv yet? – esg Jul 19 '15 at 19:26

Note: I am writing my own attempt as a possible approach. Please correct me if it does not make sense.

First, for simplicity, I fix $\Delta t = \frac{1}{\lambda}$, the expected value of the random variable $T$.

For any bin $b_\square \in B$, let $D_{R_1}$ denote the time it takes for the ball sent from $R_1$ to arrive at the bin $b_{\square}$, $D_{R_2}$ denote the time it takes for the ball sent from $R_2$ to arrive at the bin $b_{\square}$, and $D_{\lfloor n/2 \rfloor + 1}$ denote the $(\lfloor n/2 \rfloor + 1)$-order statistic of $n$ random variables $D_i$ ($i = 1, 2, \ldots, n)$, all of which are identically and independently distributed with the same distribution as $D$.

In terms of the notations above, for any bin $b_\square \in B$, it receives a ball from $R_1$ before receiving a ball from $R_2$ if and only if $D_{R_1} - \Delta t \le D_{R_2} \le D_{\lfloor n/2 \rfloor + 1}$. Therefore, we have

\begin{align} \mathbb{P}(E) = 1 - \left (1 - \mathbb{P}(D_{R_1} - \Delta t \le D_{R_2} \le D_{\lfloor n/2 \rfloor + 1})\right)^{\lfloor n/2 \rfloor + 1} \end{align}

• This doesn't make sense to me. Maybe you mean something different by all of the terms like "popping" that are not usually used that way (popping usually suggests annihilating balloons or bubbles, not moving balls). I thought what you were asking was that the probability is that a sample from an $\operatorname{Exp}(\lambda)$ distribution is less than the $\lfloor n/2 \rfloor+1$-order statistic of $n$ $\operatorname{Exp}(\mu)$ random variables. I don't understand what is going on with E2 and E3. If $n$ balls go into $n$ bins, one per bin, all at the same time, why is there a chance to miss? – Douglas Zare May 29 '15 at 4:45
• @DouglasZare By "pop", I mean "produce" (see the revised post). The robots produce balls and send them to bins. The $n$ balls go into $n$ bins at the same time. But they don't necessarily arrive at bins at the same time because of the random delays. – hengxin May 29 '15 at 8:36
• @DouglasZare The condition that a sample from an $\text{Exp}(\mu)$ r.v is less than the $\lfloor n/2 \rfloor + 1$-order statistic of $n$ $\text{Exp}(\mu)$ r.vs (plus $\Delta t$) cannot ensure that the corresponding ball $b_{\circ}$ from $R_1$ falls into one bin in $B$: it may go to other bins. Furthermore, given that the ball $b_{\circ}$ does fall into one bin in $B$, it may reach the bin after a ball from $R_2$. $E_3$ excludes this situation. (Note that I have reordered $E_1$ and $E_2$.) Thanks for your comments. Looking forward to other comments and suggestions. – hengxin May 29 '15 at 8:38
• In the question, it looks like the delay is the same for each ball sent by $R_1$, since you say the delays "follow" the variable $D$ rather than that they are, for example, IID with the same distribution as $D$. Since you don't mean that, please clarify the question. – Douglas Zare May 30 '15 at 0:44
• Your formula is not correct. Let $m=\lfloor n/2 \rfloor +1$ and denote the delay times of the first rep. second shot by $D_i^\prime$ resp. $D_i$. The correct formula is $\mathbb{P}(E^c)={n \choose m}\mathbb{P}(E^c, B=\{1,\ldots,m\}$). Let $M_m=\max \{D_1,\ldots,D_m\}$. Compute $\mathbb{P}(E^c, B=\{1,\ldots,m})$ by integrating $\mathbb{P}(D_1^\prime>t+x_1,\ldots, D_m> t+x_m, D_1=x_1,...,D_m=x_m, M_m=s, D_{m+1}>s,\ldots, D_n>s)$ (first the $x_i$ from $0$ to $s$, then $s$ from $0$ to $\infty$). – esg Jun 10 '15 at 19:55