Suppose I throw $m$ balls in $n$ bins uniformly and independently. Now the question is to analyse the probability that a given bin (say the first bin) has atleast $k$ balls.
Intuitively, I can choose $k$ balls out of $m$ first and then place them in that particular bin and I don't care about the rest of the balls so the answer should be $\leq {m \choose k} \left(\frac{1}{n}\right)^k$
Working this out rigorously:
Pr[atleast $k$ balls] = $\sum_{i=k}^m$ Pr[exactly $i$ balls]
$$ = {m \choose k}\left(\frac{1}{n}\right)^k\left(1-\frac{1}{n}\right)^{m-k} + {m \choose k+1}\left(\frac{1}{n}\right)^{k+1}\left(1-\frac{1}{n}\right)^{m-k-1}+\cdots + {m \choose m}\left(\frac{1}{n}\right)^m\left(1-\frac{1}{n}\right)^{m-m}$$
$$= {m \choose k}\left(\frac{1}{n}\right)^k \left(\left(1-\frac{1}{n}\right)^{m-k} + \cdots\right)$$
How do I show that the number in brackets is $\leq 1$?
My calculation:
Let $p=\frac{1}{n}$ and $q=1-p=1-\frac{1}{n}$
\begin{align*}
&= {m \choose k}p^kq^{m-k} + {m \choose k+1}p^{k+1}q^{m-k-1}+\cdots + {m \choose m}p^m \\
&= p^k q^{m-k} \left({m \choose k} + {m \choose k+1}\frac{p}{q}+\cdots + {m \choose m}\left(\frac{p}{q}\right)^{m-k} \right) \\
&= p^k q^{m-k} \left(\frac{q}{p}\right)^k \left({m \choose k}\left(\frac{p}{q}\right)^k + {m \choose k+1}\left(\frac{p}{q}\right)^{k+1}+\cdots + {m \choose m}\left(\frac{p}{q}\right)^{m} \right) \\
&\leq p^k q^{m-k} \left(\frac{q}{p}\right)^k \left(1+\frac{p}{q}\right)^{m} = 1\\
\end{align*}
which is obviously true. How do I find better bounds?
To give some more context, I was looking at the randomized load balancing problem (Page 14).
Best Answer
It's actually quite trivial if I had once sat down and spent some more time on it.
Want to prove: $$\sum_{l=k}^m {m \choose l} \left(\frac{1}{n}\right)^l \left(1-\frac{1}{n}\right)^{m-l} \leq {m \choose k}\left(\frac{1}{n}\right)^k$$
That is, $${m \choose k} \left(\frac{1}{n}\right)^k \left(1-\frac{1}{n}\right)^{m-k} + {m \choose k+1} \left(\frac{1}{n}\right)^{k+1} \left(1-\frac{1}{n}\right)^{m-k-1} + \cdots + {m \choose m} \left(\frac{1}{n}\right)^m \left(1-\frac{1}{n}\right)^{m-m} \leq {m \choose k}\left(\frac{1}{n}\right)^k$$
Simplifying: $$\left(1-\frac{1}{n}\right)^{m-k} + \frac{{m \choose k+1}}{{m \choose k}} \left(\frac{1}{n}\right) \left(1-\frac{1}{n}\right)^{m-k-1} + \cdots + \frac{{m \choose m}}{{m \choose k}} \left(\frac{1}{n}\right)^{m-k} \leq 1$$
The LHS resembles something close to: $${m-k \choose 0} \left(1-\frac{1}{n}\right)^{m-k} + {m-k \choose 1} \left(\frac{1}{n}\right) \left(1-\frac{1}{n}\right)^{m-k-1} + \cdots + {m-k \choose m-k} \left(\frac{1}{n}\right)^{m-k} = \left(\frac{1}{n} + 1 - \frac{1}{n}\right)^{m-k}$$
So if we prove that: $$\frac{{m \choose l}}{{m \choose k}} \leq {m-k \choose l-k} \forall m \geq l \geq k$$ then we will be done.
Induction makes this a piece of cake. For $l=k$, you can immediately see this is true and
\begin{align} \frac{{m \choose l+1}}{{m \choose k}} &=& \frac{{m \choose l+1}}{{m \choose l}} \frac{{m \choose l}}{{m \choose k}} \\ &\leq& \left(\frac{m-l}{l+1}\right) {m-k \choose l-k} \\ &=& \left(\frac{m-l}{l+1}\right) \frac{(m-k)!}{(l-k)!(m-l)!} \\ &=& \left(\frac{l-k+1}{l+1}\right) \frac{(m-k)!}{(l-k+1)!(m-l-1)!} \\ &\leq& {m-k \choose l+1-k} \\ \end{align}