<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] Let $p_i$ denote the number of ways we can obtain $i$ tosses.Obviously $2\le i\le (n+1)$
To find $p_i$ -
1.First find the number of ways we can put $(i-1)$ balls in the bins such that no two go into the same bin

Number of ways = $^np_{i-1}$

2.Put the next ball in one of the bins that already has a ball

Number of ways = $i-1$

$\therefore p_i=(i-1)^np_{i-1}$

$\therefore$ The total number of ways=$$\sum^{n+1}_{i=2}(i-1)^np_{i-1}$$ 
Putting the values in each case, we can obtain the required expected value for the number of tosses as $$\sum^{n+1}_{i=2}\frac{i(i-1)^np_{i-1}}{\sum^{n+1}_{i=2}(i-1)^np_{i-1}}=\frac{\sum^{n+1}_{i=2}i(i-1)^np_{i-1}}{\sum^{n+1}_{i=2}(i-1)^np_{i-1}}$$
</s>