A linearly distributed version of the balls into bins problem

Question

Some years ago, I found a paper with all the formulas for the balls into bins problem when the "areas" (i.e., probabilities to capture a ball) of the bins are all different. However, the formulas looked quite involved and cumbersome in the general case. Now, I am instead trying to solve an elementary version of the balls into bins problem with a non-uniform probability of capturing balls, which I firmly believe has a simple and clean answer.

---

We are given $n$ bins $b_1, b_2, \ldots, b_n$. In a sequential fashion, at each time step, one ball is placed into bin $b_i$ with probability $p_i$, where $\sum_{i=1}^{n} p_i=1$, and $p_i=\alpha i p_1$ for a given constant $\alpha\ge 1$ for all integer $i\in\{2,3\ldots,n\}$.

---

Question: What is expected number $m$ of balls that we need to throw to have that all $n$ bins contains at least one ball?

---

---

Edit: For any given fixed value of $n\in\mathbb{N}$, as $\alpha$ grows, the required expected number of balls $m p_1$ cannot increase. For the minimum value of $\alpha$ in the problem, which is $1$ ($\alpha\ge 1$), it seems that $m=\frac{\beta}{p_1}$ for some constant $\beta$. Since $\frac{1}{p_1}$ balls are always necessary to make bin $b_1$ non-empty, I guess that there is a constant $\gamma(\alpha)\in [1,\beta]$ depending on $\alpha$ such that $\frac{\gamma(\alpha)}{p_1}$ is the expected number of balls required, but I do not know how $\gamma$ varies with $\alpha$. Anyway for $n\to\infty$ we always have $m\in\Theta\left(\frac{1}{p_1}\right)$ (which is equal to $\Theta(n^2)$ for $\alpha=1$).

Answer 1

From the referenced paper, I am writing in terms of their variables, $k$ is the number of bins or type of coupons:

Let $n_1$ be the time where the last of the missing events is observed. Let $n_2$ be the time where the second last of the missing events is observed, etc. until $n_k$:

Define $$ S_kf(p_1,\ldots,p_m)=\sum_{1\leq i_1<i_2<\cdots<i_k\leq m}f(p_{i_1},\ldots,p_{i_m}), $$ which means that the function is $f$ is to be formed for all $\binom{k}{m}$ combinations of the $k$ indices indicated in the subscript of $S$ and that all these terms are to be added. For example $$ S_3 \frac{1}{p_1+p_2}= \frac{1}{p_1+p_2}+\frac{1}{p_2+p_3}+\frac{1}{p_1+p_3} $$ The general equation given below is still not really clean, but you can simplify using your constraint of linear probabilities. The paper has the distribution and the cumulative distribution as well. However we have the expectation which follows in inclusion-exclusion manner thus $$ \mathbb{E}(n_m)=S_k \left\{ \binom{m-1}{m-1} \frac{1}{p_1+p_2+\cdots+p_m}+\right. $$ $$ -\binom{m}{m-1}\frac{1}{p_1+p_2+\cdots+p_{m+1}} +\cdots $$ $$ \left. +(-1)^{k-m} \binom{k-1}{m-1}\frac{1}{p_1+p_2+\cdots+p_k}. \right\} $$