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


1 Answer 1


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} $$

  • $\begingroup$ The expected value of each $X_i$ should be differ from a geometric distribution, since after you send an attack to the server, the whole message become $n$ instead of $n-1$, so each trail is not independent and the success rate keep decreasing as you sent more attack. $\endgroup$
    – Bayesian
    Jul 22, 2022 at 5:43
  • $\begingroup$ @Bayesian I think you misunderstood the question. The moment nth message is sent, one of the messages is forwarded, maintaining the n-1 messages at all times. $\endgroup$
    – Stats Noob
    Jul 22, 2022 at 5:50
  • $\begingroup$ @vijayK If the new message arrives, this new message itself could be the one to be sent out, so $E[X_1] = \frac{n}{n-1}$. Similarly for all your other expectations. $\endgroup$
    – frank
    Jul 22, 2022 at 7:39
  • $\begingroup$ @frank thanks for pointing it out, corrected the solution $\endgroup$
    – Stats Noob
    Jul 22, 2022 at 18:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.