Calculate probability Assume that a remailer reorders messages. It has a pool of n-1 messages at all times. When the nth message arrives, one of the n messages is selected at random and forwarded. An attacker fools the server with enough messages to force the n - 1 messages in the original pool to be sent. Assuming that the message to be sent is chosen according to a uniform
random distribution, what is the expected number of messages that the attacker would have to send to achieve this goal?
Could you give me some hints about how to solve this problem. Thank you

Let, Y be the number of fake messages sent by trickster for all the original messages to be forwarded.  E[Y] be the expected number of fake messages sent.
We can write
\begin{equation}
 Y = X_1+X_2+\ldots + X_{(n-1)},
\end{equation}
where Xi is number of additonal fake messages to send for forwarding the ith of the original messages. (assuming i-1  original messages were already forwarded)
Initially, Probability that each attempt will  result  in forwarding of original message, $$p = \frac{n-1}{n} $$  (total n-1 original messages out of n total messages)
$$=>E[X_1] = \frac{n}{n-1} $$
Calculating E[X2]:
Probability for each try to be successful, $$p = \frac{n-2}{n}$$, since we have n-2 original messages out of n total
$$E[X_2] = \frac{n}{n-2}$$
Final Result
Similarly, we calculate other E[Xi]'s, and we get below answer
$$E[Y] = \frac{n}{n-1} + \frac{n}{n-2} + \frac{n}{n-3} +----+ \frac{n}{1} $$
