The probability density function of the number of coins to first fill one box of $N$

Question

Given $N$ boxes with the same capacity $C$, I toss coins into the boxes uniformly, one by one. When any one of the boxes is full, the sum of the coins in all boxes is denoted $S$. How to compute the probability density function of $S(N,C)$?

Answer 1

(I change notation from $N,C$ to $n,c$ since I use capitals throughout to denote rvs).

Let $X_i$ be the random variable "number of the box the $i$-th coin", then $X_1,X_2,\ldots$ is an i.i.d. sequence of random variables (each uniformly distributed on $\{1,\ldots,n\}$) and
you are asking for the distribution of the time of the first $c$-fold repeat in this sequence.
(The capacity of the boxes is immaterial here, since the process is stopped when the first box is filled to its capacity. In the sequel I assume that the boxes have unlimited capacity.)

Variants of this problem are well studied.

Let $Y_1(k),\ldots,Y_n(k)$ be the random variables $Y_i(k):=$ "number of coins in box $i$" that have been filled in at "time" $k$. Clearly the joint distribution of ($Y_1(k),\ldots,Y_n(k)$) is multinomial with parameters $k$ and $p_1=\ldots=p_n={1\over n}$. We therefore have

Proposition The generating function of (the joint distribution of) $Y_1(k),\ldots,Y_n(k)$ is given by: \begin{equation*} \mathbb{E}\, t_1^{Y_1(k)}\ldots t_n^{Y_n(k)}=\frac{k!} {n^k}[t^k] e^{t(t_1+\ldots +t_n)} \end{equation*}

(I) The distribution of $S(n,c)$

Let $p_c(t):=\sum_{i=0}^{c-1} {t^i \over i!}$ be the $c-$th partial sum of $\exp(t)$. Since $\{\,S(n,c) > k\}=\{\,Y_1(k)\leq c-1,\ldots,Y_n(k)\leq c-1\,\}$ the above gives \begin{equation*} \mathbb{P}(S(n,c)> k) =\frac{k!}{n^k}[t^k] \big(p_c(t))^n \end{equation*}

(II) The expectation of $S(n,c)$

Further, using $\mathbb{E} S=\sum_{k\geq 0} \mathbb{P}(S>k)$ and writing ${k! \over n^k} = n\,\int_0^\infty s^k e^{-ns}\,ds$ leads to $$\mathbb{E}(S(n,c))=n\int_0^\infty \big(p_c(s)e^{-s}\big)^n\,ds$$ This goes back to Klamkin and Newman [1]

(III) The asymptotic distribution of $S(n,c)$

In the situation above let $j\in\{0,\ldots,k\}$ and denote by $U_j^{k,n}$ the random variable "no. of boxes which contain exactly $j$ coins at time $k$".

The asymptotic distribution of $S(n,c)$ can be deduced from the following result of von Mises [2]:

Theorem (von Mises) Let $j\in\{0,\ldots,k\}$ be fixed and $\alpha=\frac{k}{n}$. Then

(a) $\mathbb{E}(U_j^{k,n})=n{k \choose j}(\frac{1}{n})^j(1-\frac{1}{n})^{k-j}\;,$

(b) If $k,n\longrightarrow \infty$ s.th. $n\frac{\alpha^j}{j!} e^{-\alpha}$ tends to a finite positive limit $a_j$, then asymptotically $U_j^{k,n}$ is Poisson distributed with parameter $a_j$.

The random variable $N_c^{k,n}:=\sum_{i=c}^n {i \choose c}\,U_i^{k,n}$ gives the number of $c-$fold repetitions at time $k$ (because if a box has $i$ coins, each $c$-subset of these coins balls defines an $c$-fold repetition). Using $(a)$ we find that $\mathbb{E}(N_c^{k,n})=\frac{1}{n^{c-1}}{k \choose c}$.

The first $c$-fold repetitions will thus appear at times of order $t_{c,n}:=(c!\,n^{c-1})^{1/c}$. Clearly $\{S(c,n)>k\}=\{N_c^{k,n}=0\}$. Therefore the theorem above has the following corollary:

Corollary Let $c\geq 2$ be fixed and $x>0$. Then $\mathbb{P}(S(c,n)> t_{c,n} x)\longrightarrow e^{-x^c}\;\;\;(n\longrightarrow \infty) $

Proof: Let $x>0$ and in the sequel $k=k(x,n):=\lceil x\,t_{c,n}\rceil$ and $n\longrightarrow \infty$. Then $0\leq N_c^{k,n} -U_c^{k,n}\longrightarrow 0$ (since $\mathbb{E}(S_c^{k,n}-U_c^{k,n})=\frac{1}{n^{c-1}}{k \choose c}\left(1-(1-\frac{1}{m})^{k-c}\right)\longrightarrow 0$). Thus $N_c^{k,n}$ and $U_c^{k,n}$ have the same limit distribution. The conditions of (b) are fulfilled with $a_c=x^c$. Thus $\mathbb{P}(S(c,n)>k(x,m))=\mathbb{P}(N_c^{k(x,n),n}=0)\longrightarrow e^{-x^c}$ End of Proof

Equivalently $\mathbb{P} (S(n,c) >n^{1-1/c}x)\longrightarrow e^{-{x^c \over c!}}$. (The particular case $c=2$ of this corollary is very well known from its appearance in the "birthday paradox".) So they are indeed asymptotically Weibull-distributed.

[1] Klamkin, M.S. and Newman, D.J., Extensions of the Birthday Surprise, Journal of Combinatorial Theory 3 (1967), pp.~279--282.

[2] von Mises, R., Über Aufteilungs- und Besetzungswahrscheinlichkeiten, Revue de la Facult$\acute e$ des Sciences de l' Universit$\acute e$ d'Istanbul 4 (1939), pp.~145--163.

Answer 2

$\newcommand{\bP}{\mathbb{P}}$ Denote by $E_i$ the event that the $i$-th box is the one first filled to capacity. Then

$$\bP(S=s)=\sum_{i=1}^N \bP(S=s, E_i)= N\bP(S=s, E_1). $$

We have

$$\bP(S=s, E_1)=\frac{1}{N^s}\sum_{\substack{0\leq k_2,\cdots k_N\leq C-1\\ k_2+\cdots k_N=s-c}}\binom{s}{C, k_2,\dotsc,k_N}. $$

We have

$$\sum_{C\leq s\leq (C-1)N+1} \bP(S=s, E_1)t^s=\sum_{\substack{0\leq k_2,\cdots k_N\leq C-1\\ k_2+\cdots k_N=s-c}}\binom{s}{C,k_2,\dotsc,k_N}\left(\frac{t}{N}\right)^s. $$

Set $u:=\frac{t}{N}$. The probability generating function of $S$ is

$$f_S(t):=\sum_{s}\bP(S=s)t^s=N\sum_{c\leq s\leq (N-1)C+1} \bP(S=s, E_1)t^s $$ $$=N\sum_{\substack{0\leq k_2,\cdots k_N\leq C-1\\ k_2+\cdots k_N=s-c}}\binom{s}{C,k_2,\dotsc,k_N}u^{s}. $$

Example 1. $N=2$. $\newcommand{\bE}{\mathbb{E}}$

$$p_s:=\bP(S=s)=\frac{1}{2^{s-1}}\binom{s}{C},\;\;s=C,\dotsc, 2C-1.$$

This is related related to the famous Banach matchbox problem. Suppose that we have two boxes, each filled with $C$ balls. We randomly draw a ball from each box until one becomes empty. Then $S$ denotes the number of drawn balls. The expectation of $S$ is

$$\mu=\mu_C=\sum_{s=c}^{2C-1}\frac{s}{2^{s-1}}\binom{s}{c}$$

We observe that

$$p_{s+1}=\frac{s+1}{2(s+1-C)}p_s$$

so $$(s+1-C)p_{s+1}=\frac{s}{2}p_s +\frac{1}{2}p_s, $$

so that $$\sum_{s=C}^{2C-1}(s+1-C)p_{s+1}=\sum_{s=C}^{2C-1}\frac{s}{2}p_s +\frac{1}{2}\sum_{s=C}^{2C-1}p_s.$$

We have $$\sum_{s=C}^{2C-1}\frac{s}{2}p_s+\frac{1}{2}\sum_{s=C}^{2C-1}p_s=\frac{\mu}{2}+\frac{1}{2}. $$

On the other hand

$$ \sum_{s=C}^{2C-1}(s+1-C)p_{s+1}=\sum_{t=C+1}^{2C}tp_t-C\sum_{t=C+1}^{2C}p_t $$

$$=\mu-Cp_C+2Cp_{2C}-C+Cp_C-Cp_{2C}=\mu-C+Cp_{2C},$$

Hence

$$2\mu-2C+2Cp_{2C}=\mu+1, $$

$$\mu=2C+1-2Cp_{2C}=2C+1-\frac{C}{2^{2C-1}}\binom{2C}{C}.$$

Using Stirling formula we deduce that as $C\to\infty$ we have

$$p_{2C}=\frac{1}{2^{2C-1}}\binom{2C}{C}\sim\frac{\sqrt{2\pi C}}{2\pi C}\frac{2^{2C}}{2^{2C-1}}=\sqrt{\frac{2}{\pi C}}. $$