{"template":"article","title":"On the Enumeration of Removal Requests in Broadcast Threads","short_title":"Enumeration of removal requests","authors":[{"name":"Elara J. Selnor","affiliations":[1]}],"affiliations":["Department of Discrete Mathematics, Orisel Institute of Mathematical Sciences, Veyport"],"abstract":"We study a broadcast thread in which recipients request removal by replying to all, while removal is deferred until no replies remain. Under a memory-$h$ rule, a recipient replies to a request unless they occur among its $h$ most recent ancestral senders. For a list of $n$ participants, the thread terminates if and only if $h=n$. With full ancestry memory the number of requests is $\\lfloor e(n-1)!\\rfloor$ for $n\\geq2$, although no participant sends twice on a single ancestry. With memory $n-1$, there are $(n-1)!$ requests at every sufficiently large depth. We derive the depth counts, individual traffic, and the limiting distribution of the number of eligible senders on the ancestry of a uniformly selected request. An atomic shared registry instead admits exactly $n$ requests. The counts are verified by explicit enumeration of sender sequences.","keywords":["enumeration","self-avoiding walks","branching","broadcast communication"],"body":"# Introduction {#sec:intro}\n\nA 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.\n\nThe 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.\n\nThe 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 @slade2019 and @deng2019. The enumeration of the resulting words also follows from standard constructions for labelled sequences [@flajolet2009]. We use this representation to count requests, deliveries, and the number of people who have already requested removal along a typical ancestry.\n\nThe 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.\n\n# Model {#sec:model}\n\nLet $X=\\{1,\\ldots,n\\}$ with $n\\geq2$, and let participant 1 send an initial removal request. Each message is addressed to all other $n-1$ 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.\n\nWe identify a message at depth $t$ with its sender sequence $(x_0,\\ldots,x_t)$, where $x_0=1$. Its parent is obtained by deleting $x_t$. 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.\n\nUnder the *memory-$h$* rule, for $1\\leq h\\leq n$, a recipient replies if and only if they do not occur among the last $h$ senders of the message's ancestry, or anywhere in that ancestry if it contains fewer than $h$ 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.\n\nFor $h=n$ we call the rule *full ancestry memory*. Since there are only $n$ 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 $n$.\n\nThese 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.\n\n# Counts by depth {#sec:depth}\n\nLet $M_t(n,h)$ be the number of messages at depth $t$, and write $(a)_r=a(a-1)\\cdots(a-r+1)$ with $(a)_0=1$.\n\n::: theorem {#thm:depth title=\"Bounded ancestry memory\"}\nFor $1\\leq h<n$ and $t\\geq0$,\n$$\nM_t(n,h)=(n-1)_{\\min(t,h-1)}(n-h)^{\\max(0,t-h+1)}.\n\\label{eq:bounded}\n$$\nFor full ancestry memory,\n$$\nM_t(n,n)=\\begin{cases}\n(n-1)_t,&0\\leq t\\leq n-1,\\\\\n0,&t\\geq n.\n\\end{cases}\n\\label{eq:full}\n$$\n:::\n\n::: proof\nAt depth $t$, the last $\\min(h,t+1)$ senders are distinct. This is true at the root and remains true when a sender outside that suffix is appended. Every message at depth $t$ therefore has exactly $n-\\min(h,t+1)$ children. Multiplying these factors from the root gives @eq:bounded. When $h=n$, the factors are $n-1,n-2,\\ldots,1,0$, yielding @eq:full.\n:::\n\n::: corollary {#cor:termination title=\"Termination threshold\"}\nThe thread becomes quiet after finitely many depths if and only if $h=n$. For $h=n-1$, there are $(n-1)!$ requests at every depth $t\\geq n-2$.\n:::\n\n::: proof\nFor $h<n$, every sufficiently deep message has $n-h\\geq1$ children. At $h=n-1$, @eq:bounded reduces to $(n-1)!$ for $t\\geq n-2$. For $h=n$, @eq:full eventually vanishes.\n:::\n\nThe 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. @fig:depth 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.\n\n![Requests by depth for six participants under three memory rules. Full ancestry memory has no requests after depth five.](depth){#fig:depth width=0.78}\n\n# Full ancestry memory {#sec:full}\n\nDenote the total number of requests by $T_n=\\sum_t M_t(n,n)$. Every request is delivered to $n-1$ recipients, including recipients who have already appeared on its ancestry. Consequently the total number of deliveries is $(n-1)T_n$.\n\n::: theorem {#thm:total title=\"Total requests\"}\nFor $n\\geq2$,\n$$\nT_n=\\sum_{t=0}^{n-1}\\frac{(n-1)!}{(n-1-t)!}\n=(n-1)!\\sum_{j=0}^{n-1}\\frac1{j!}\n=\\left\\lfloor e(n-1)!\\right\\rfloor.\n\\label{eq:total}\n$$\n:::\n\n::: proof\nThe first expression follows from @eq:full and the second by setting $j=n-1-t$. For $m=n-1\\geq1$, the omitted tail of $em!$ is positive and at most $(m+2)/(m+1)^2<1$: after the first omitted term $1/(m+1)$, successive terms decrease by factors at most $1/(m+2)$. Taking the floor proves the result.\n:::\n\nWriting $T_1=1$ for the one-person case, the exponential generating function in the number of non-initiators is\n$$\n\\sum_{m\\geq0}T_{m+1}\\frac{z^m}{m!}=\\frac{e^z}{1-z}.\n\\label{eq:egf}\n$$\nThis is the product of the exponential series and the ordinary sequence generating function; it also gives $T_n\\sim e(n-1)!$.\n\n::: proposition {#prop:senders title=\"Individual traffic\"}\nThe initiator sends one request and receives $T_n-1$ deliveries. Every other participant sends $(T_n-1)/(n-1)$ requests and receives $T_n-(T_n-1)/(n-1)$ deliveries.\n:::\n\n::: proof\nThe 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 $T_n-1$ requests. Every message is delivered to all participants except its sender, giving the stated receipt counts.\n:::\n\nThe identity $(T_n-1)/(n-1)=T_{n-1}$ holds for $n\\geq3$. Thus each non-initiator on a ten-person list sends as many requests as the entire full-memory process on nine people. @tbl:totals gives exact values; the shared-registry benchmark sends $n$ requests in each row.\n\nTable: Full ancestry memory. Deliveries count one copy per recipient; each non-initiator's requests are counted across all branches. {#tbl:totals}\n\n| List size $n$ | Requests $T_n$ | Requests per non-initiator | Deliveries |\n|--------------:|---------------:|---------------------------:|-----------:|\n| 3 | 5 | 2 | 10 |\n| 4 | 16 | 5 | 48 |\n| 5 | 65 | 16 | 260 |\n| 6 | 326 | 65 | 1,630 |\n| 7 | 1,957 | 326 | 11,742 |\n| 8 | 13,700 | 1,957 | 95,900 |\n| 9 | 109,601 | 13,700 | 876,808 |\n| 10 | 986,410 | 109,601 | 8,877,690 |\n\n# A uniformly selected request {#sec:typical}\n\nChoose one of the $T_n$ messages uniformly after the full-memory process has finished. Let $U_n$ be the number of participants who have not yet appeared in its ancestry. For $j=0,\\ldots,n-1$, messages with $U_n=j$ have depth $n-1-j$. Hence\n$$\n\\Pr(U_n=j)=\\frac{1/j!}{\\sum_{q=0}^{n-1}1/q!}.\n\\label{eq:distribution}\n$$\n\n::: proposition {#prop:limit title=\"Remaining eligible senders\"}\nAs $n\\to\\infty$, $U_n$ converges in distribution to a Poisson random variable of mean one. Its exact expectation is\n$$\n\\mathbb{E}U_n=\\frac{\\sum_{q=0}^{n-2}1/q!}{\\sum_{q=0}^{n-1}1/q!}.\n\\label{eq:mean}\n$$\n:::\n\n::: proof\nThe probabilities in @eq:distribution tend to $e^{-1}/j!$, which sums to one. The mean follows by summing $j/j!=1/(j-1)!$ for $j>0$.\n:::\n\nIn particular, the proportion of requests with no eligible sender left on their ancestry tends to $e^{-1}$. 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.\n\n# Verification and scope {#sec:scope}\n\nWe checked @eq:bounded and @eq:full by explicitly generating every sender sequence for $2\\leq n\\leq6$, every memory length $1\\leq h\\leq n$, and depths through six. All 20 parameter pairs agreed with the formulas. @tbl:totals was calculated using integer arithmetic from @eq:total. The plot uses the exact depth counts; there are no sampled observations.\n\nA 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 $h<n$ therefore never reaches that point.\n","bibliography":"@article{slade2019,\n  author = {Slade, Gordon},\n  title = {Self-Avoiding Walk on the Complete Graph},\n  journal = {arXiv preprint arXiv:1904.11149},\n  year = {2019},\n  doi = {10.48550/arXiv.1904.11149}\n}\n\n@article{deng2019,\n  author = {Deng, Youjin and Garoni, Timothy M. and Grimm, Jens and Nasrawi, Abrahim and Zhou, Zongzheng},\n  title = {The Length of Self-Avoiding Walks on the Complete Graph},\n  journal = {Journal of Statistical Mechanics: Theory and Experiment},\n  volume = {2019},\n  pages = {103206},\n  year = {2019},\n  doi = {10.1088/1742-5468/ab3da3}\n}\n\n@book{flajolet2009,\n  author = {Flajolet, Philippe and Sedgewick, Robert},\n  title = {Analytic Combinatorics},\n  publisher = {Cambridge University Press},\n  address = {Cambridge},\n  year = {2009},\n  doi = {10.1017/CBO9780511801655}\n}\n","figures":[{"id":"depth","kind":"chart","data":"{\"type\": \"line\", \"style\": \"pgfplots\", \"xlabel\": \"Depth of request\", \"ylabel\": \"Requests\", \"x\": [0, 1, 2, 3, 4, 5], \"series\": [{\"label\": \"Memory 1\", \"y\": [1, 5, 25, 125, 625, 3125], \"marker\": \"o\"}, {\"label\": \"Memory 3\", \"y\": [1, 5, 20, 60, 180, 540], \"marker\": \"s\"}, {\"label\": \"Full memory\", \"y\": [1, 5, 20, 60, 120, 120], \"marker\": \"^\"}], \"yscale\": \"log\", \"legend\": \"upper left\", \"size\": [5.1, 3.2]}"}],"options":{"citation_style":"numeric"}}