1Introduction
A participant who wishes to leave a group email thread may request removal by replying to all recipients. If other participants also wish to leave, a removal request can give rise to further removal requests. We consider a list on which every recipient wishes to be removed and on which removal is processed only after the thread has become quiet. The messages being counted are the requests for removal themselves.
The rule for suppressing duplicate requests matters. A participant may avoid sending a second request in the ancestry of a message while still responding to separate branches of the thread. We compare this rule with bounded ancestry memory and with a shared registry that permits only one request per participant across the whole thread. In each case, all requests are sent to the original list; a previously sent request does not remove its sender from the list.
The ancestry of a request is a word over the participant set. With full ancestry memory it is a self-avoiding walk on a complete graph, a setting studied by Slade [3] and Deng et al. [1]. The enumeration of the resulting words also follows from standard constructions for labelled sequences [2]. We use this representation to count requests, deliveries, and the number of people who have already requested removal along a typical ancestry.
The distinction between local and shared memory is substantial. With full ancestry memory the thread stops, but its request count grows factorially. For a list of ten, it contains 986,410 requests before removal can be processed. If only the nine most recent senders in each ancestry are remembered, the thread never becomes quiet. A shared registry reduces the count to ten.
2Model
Let with , and let participant 1 send an initial removal request. Each message is addressed to all other participants. A recipient who is eligible under the chosen memory rule sends exactly one reply to all, also requesting removal. All eligible replies are eventually delivered, and each message retains its own chain of ancestors. Different branches are not merged.
We identify a message at depth with its sender sequence , where . Its parent is obtained by deleting . Every eligible recipient gives a distinct child, so message counts are counts of such sequences, not counts of distinct message bodies. The initial request has depth zero. A delivery is one message received by one recipient; it is distinct from a sent message.
Under the memory- rule, for , a recipient replies if and only if they do not occur among the last senders of the message’s ancestry, or anywhere in that ancestry if it contains fewer than senders. Thus the current sender is always ineligible. The rule is applied separately on every branch. In particular, a request on one branch does not suppress a request by the same person on another.
For we call the rule full ancestry memory. Since there are only participants, no sender can recur on a branch. As a comparison, the shared-registry rule admits at most one request per participant across all branches, using an atomic check when the request is sent. Each of the other participants receives the initial request and sends one reply, so the total is exactly .
These are deterministic counting models. They do not require a probability of replying or a distribution of delivery times. In particular, a pending reply is counted even if a different branch has already produced a request from its sender.
3Counts by depth
Let be the number of messages at depth , and write with .
Theorem 1 (Bounded ancestry memory). For and ,
For full ancestry memory,
Proof. At depth , the last senders are distinct. This is true at the root and remains true when a sender outside that suffix is appended. Every message at depth therefore has exactly children. Multiplying these factors from the root gives Eq. (1). When , the factors are , yielding Eq. (2).∎
Corollary 2 (Termination threshold). The thread becomes quiet after finitely many depths if and only if . For , there are requests at every depth .
Proof. For , every sufficiently deep message has children. At , Eq. (1) reduces to for . For , Eq. (2) eventually vanishes.∎
The threshold includes the two-person case: with memory one, the two participants continue to reply to one another; with full ancestry memory, the second request has no eligible recipient. Figure 1 shows the first six depths for a list of six. Counts at depth six and later are zero under full memory, so they are omitted from the logarithmic plot.
4Full ancestry memory
Denote the total number of requests by . Every request is delivered to recipients, including recipients who have already appeared on its ancestry. Consequently the total number of deliveries is .
Theorem 3 (Total requests). For ,
Proof. The first expression follows from Eq. (2) and the second by setting . For , the omitted tail of is positive and at most : after the first omitted term , successive terms decrease by factors at most . Taking the floor proves the result.∎
Writing for the one-person case, the exponential generating function in the number of non-initiators is
This is the product of the exponential series and the ordinary sequence generating function; it also gives .
Proposition 4 (Individual traffic). The initiator sends one request and receives deliveries. Every other participant sends requests and receives deliveries.
Proof. The initiator occurs at the start of every ancestry and cannot appear again. All non-initiators are interchangeable under permutations that fix participant 1, and together they send the remaining requests. Every message is delivered to all participants except its sender, giving the stated receipt counts.∎
The identity holds for . Thus each non-initiator on a ten-person list sends as many requests as the entire full-memory process on nine people. Table 1 gives exact values; the shared-registry benchmark sends requests in each row.
| List size | Requests | Requests per non-initiator | Deliveries |
|---|---|---|---|
| 3 | 5 | 2 | 10 |
| 4 | 16 | 5 | 48 |
| 5 | 65 | 16 | 260 |
| 6 | 326 | 65 | 1,630 |
| 7 | 1,957 | 326 | 11,742 |
| 8 | 13,700 | 1,957 | 95,900 |
| 9 | 109,601 | 13,700 | 876,808 |
| 10 | 986,410 | 109,601 | 8,877,690 |
5A uniformly selected request
Choose one of the messages uniformly after the full-memory process has finished. Let be the number of participants who have not yet appeared in its ancestry. For , messages with have depth . Hence
Proposition 5 (Remaining eligible senders). As , converges in distribution to a Poisson random variable of mean one. Its exact expectation is
Proof. The probabilities in Eq. (5) tend to , which sums to one. The mean follows by summing for .∎
In particular, the proportion of requests with no eligible sender left on their ancestry tends to . These terminal requests still go to all other participants. They produce no further replies under full memory, but their delivery is part of the traffic.
6Verification and scope
We checked Eq. (1) and Eq. (2) by explicitly generating every sender sequence for , every memory length , and depths through six. All 20 parameter pairs agreed with the formulas. Table 1 was calculated using integer arithmetic from Eq. (3). The plot uses the exact depth counts; there are no sampled observations.
A shared registry removes duplicates across branches, whereas ancestry memory removes them only along a single branch. This is a difference in the scope of the record, not its retention time. The shared-registry comparison assumes atomic admission and reliable delivery of the initial request. It does not model delayed or lost mail, partial participation, departures during the process, or messages with any purpose other than requesting removal. Under the stated rule, removal occurs only after the last request has been delivered; bounded memory with therefore never reaches that point.
References
- [1]Youjin Deng, Timothy M. Garoni, Jens Grimm, Abrahim Nasrawi, and Zongzheng Zhou. The Length of Self-Avoiding Walks on the Complete Graph. Journal of Statistical Mechanics: Theory and Experiment, 2019:103206, 2019. doi: 10.1088/1742-5468/ab3da3.
- [2]Philippe Flajolet and Robert Sedgewick. Analytic Combinatorics. Cambridge University Press, Cambridge, 2009. doi: 10.1017/CBO9780511801655.
- [3]Gordon Slade. Self-Avoiding Walk on the Complete Graph. arXiv preprint arXiv:1904.11149, 2019. doi: 10.48550/arXiv.1904.11149.