Let $p\_1, ... ,p\_k$ denote the probabilities of drawing bin $1, .. ,k$, where $\sum\_{i = 1}^{k} p\_i= 1$. My question is if we draw $n$ times, how can I show that the probability that all bins are drawn less than $C$ times is maximized by $p\_1 = p\_2 = ... = p\_k = 1/k$ ? 


I've tried using conditional probability to solve inductively such as assuming bin $i$ is drawn $<C$ times and trying to reason about the remaining $k-1$, but no luck so far. Computing explicitly seems to be really difficult.



Birthday problem extension to unequal probabilities and multiple collisions
Here is a proof using generating functions. Let $c\geq 2$ and $k\geq 2$ be fixed.


Let $X=(X\_1(n),\ldots,X\_k(n))$ be the $k$-tuple of occupancy numbers at time $n$, i.e. $X\_i(n)$ = number of bins of type $i$ drawn at time $n$.  

Clearly $X$ has the multinomial distribution with parameters $n$ and $p=(p\_1,\ldots,p\_k)$.
Therefore  

$$\mathbb{P}( \max X\_i(n)\leq c-1)=n!\,[t^n] \prod \_{i=1}^n q\_c(p\_it)$$


where $q\_c(t):=\sum\_{j=0}^{c-1}\frac{t^j}{j!}$ is the $c$th partial sum of $\exp(t)$.


The following lemma is the key.


**Lemma**  

When $p\_i,p\_j$ are each replaced by their arithmetic mean $a:=(p\_i+p\_j)/2$  

$\mathbb{P}(\max X\_i(n) \leq c-1 )$ will not decrease.  

If $c\leq n \leq k(c-1)$ and all other $p\_\ell$ are positive $\mathbb{P}(\max X\_i(n) \leq c-1 )$ will strictly increase if
$p\_i\not = p\_j$.


**Proof**
Consider first the case of two factors. Let $x,y\in\mathbb{R}\_+,x<y$. We show that $$ [t^m] q\_c(xt)q\_c(yt)\leq [t^m] \left(q\_c(((x+y)/2)t\right)^2\;\;.$$It is easy to see that
equality holds for $m\leq c-1$ and $m>2c-2$. Let $c\leq m \leq 2c-2$. We have
$$m!\,[t^m] q\_{c}(xt)q\_c(yt)=(x+y)^m-\sum\_{i=0}^{m-c} {m \choose i}\left(x^i y^{m-i}+y^i x^{m-i}\right)
$$
For fixed sum $s=x+y$ the function $x \mapsto f(x):=\sum\_{i=0}^{m-c} {m \choose i}\left(x^i y^{m-i}+y^i x^{m-i}\right)$ has the derivative
$f^\prime(x)=(m-c+1){m \choose c} \left(x^{m-c+1}(s-x)^c-(s-x)^{m-c+1}x^c\right)$. Thus $x\mapsto f(x)$
is strictly decreasing (resp. increasing) on $[0,s/2]$ (resp. $[s/2,s]$), attaining its minimum at $x=s/2$.
The rest is easy.
**End proof.**


For any distribution $p=(p\_1,\ldots,p\_k)$ we have that
$\mathbb{P}( \max X\_i(n)\leq c-1)=1$ for $n\leq c-1$, and $\mathbb{P}( \max X\_i(n)\leq c-1)=0$ for $n > k(c-1)$, so that
only the cases $c\leq n \leq k(c-1)$ are of interest.


**Corollary**  

For $c\leq n \leq k(c-1)$ the uniform distribution $p\_1=\ldots=p\_k=\tfrac{1}{k}$
uniquely maximises $\mathbb{P}(\max X\_i(n) \leq c-1 )$.


**Proof**: Since we are maximising a continuous function
(multivariate polynomial) on a compact set (simplex) the maximum is attained.
Let $p$ be a maximising distribution. No $p\_i$ can be $0$ (else replacing the last $0$ strictly increases the probability).
But then $p$ can
only be maximising if $p$ is the uniform distribution. **End proof**.


**Remark** Lemma 2 shows that the probability $\mathbb{P}(\max X\_i(n) \leq c-1 )$ is a Schur-concave function on the simplex $p\_i\geq 0, \sum\_{i=1}^k p\_i=1$. Possibly the result can be found under this heading in the literature (but a brief Google-search didn't reveal anything).


