<s>[INST] A Problem Dealing with putting balls in bin and Expected Value - possible wrong answer Please consider the problem below. Is my answer correct. If is not correct then where did I go wrong?
Problem:
You keep tossing balls into $n$ bins until one of the bins has two balls. For each toss there is a $\frac{1}{n}$ probability that the ball you toss lands in any one of the bins. What is the expected number of tosses?
Answer:
Let $p_i$ be the probability that after $i$ tosses we have at least one bin
with two balls.
\begin{eqnarray*}
p_1 &=& 0 \\
p_2 &=& 1 - ( 1 - \frac{1}{n} ) = \frac{1}{n} \\
p_3 &=& 1 - (1 - \frac{1}{n})(1 - \frac{1}{n-1}) \\
p_3 &=& 1 - (\frac{n-1}{n})(\frac{n-1-1}{n-1}) \\
p_3 &=& 1 - (\frac{n-2}{n}) = \frac{2}{n} \\
p_4 &=& 1 - (1 - \frac{1}{n})(1 - \frac{1}{n-1})(1 - \frac{1}{n-2}) \\
p_4 &=& 1 - ( \frac{n-1}{n} )( \frac{n-2}{n-1} )( \frac{n - 2 -1}{n - 2} ) \\
p_4 &=& 1 - \frac{n-3}{n} = \frac{3}{n} \\
\end{eqnarray*}
Now for $1 <= i <= n$ we have: $p_i = \frac{i-1}{n}$.
\begin{eqnarray*}
E &=& 2p_2 + 3p_3 + 4p_4 + ... (n+1)p_{n+1} \\
E &=& \sum_{i = 1}^{n} \frac{i(i+1)}{n} = \frac{1}{2n} \sum_{i=1}^{n} i^2 + i \\
E &=& \frac{1}{2n}(\frac{n(n+1)(2n+1)}{6} + \frac{n(n+1)}{2} ) \\
E &=& \frac{n+1}{4n} ( \frac{2n+1}{3} + 1 ) \\
\end{eqnarray*}
Here is an update to my answer:
Let $p_i$ be the probability that after $i$ tosses we have at least one bin
with two balls.
\newline
\begin{eqnarray*}
p_1 &=& 0 \\
p_2 &=& 1 - ( 1 - \frac{1}{n} ) = \frac{1}{n} \\
p_3 &=& 1 - (\frac{n-1}{n})( \frac{n-2}{n}) \\
p_3 &=& 1 - \frac{(n-1)(n-2)}{n^2} = \frac{n^2 - (n^2 - 3n + 2)}{n^2} \\
p_3 &=& \frac{3n-2}{n^2} \\
p_4 &=& 1 - (\frac{n-1}{n})(\frac{n-2}{n})(\frac{n-3}{n}) \\
p_4 &=& 1 - \frac{(n^2-3n+2)(n-3)}{n^3}\\
p_4 &=& 1 - \frac{n^3-3n^2+2n - 3n^2 +9n - 6}{n^3}\\
p_4 &=& \frac{3n^2-2n + 3n^2 - 9n + 6}{n^3}\\
p_4 &=& \frac{3n^2 + 3n^2 - 11n + 6}{n^3}\\
\end{eqnarray*}
\begin{eqnarray*}
E &=& 2p_2 + 3p_3 + 4p_4 + ... (n+1)p_{n+1} \\
\end{eqnarray*}
Now, am on the right track? That is, is what I have so far correct?
Thanks,
Bob
 [/INST] Use the pigeonhole principle. 
If the number of tosses ($n$) $\geq b+1$ , then at least one bin will contain $2$ balls. If the number of tosses is $0 < n < b$, the probability that each ball will go into a different bin is $$\frac{1 \times 2 \times ...(b-n+1)}{b^n} = \frac{b!}{n!\times b^n}$$
So the probability that a bin contains more than one ball after $n$ tosses is $$1-\frac{b!}{n!\times b^n}$$
So the expected number of tosses can be found with $$E(b) = 1+ \sum_{k=1}^{b} \frac{b!}{\left(b-k\right)!b^k}$$
Visualized, this looks like:

</s>