Combinatorics and Graph Theory |
Authors: Bolok Li
In the collector's problem with group drawings, one run draws a uniformly random q-subset of an n-element set, all q coupons being kept, and T denotes the number of runs needed to complete the set. The distribution of T and all of its factorial moments are due to Stadje (1990); we do not claim them, and we say explicitly where our formulas reproduce his -- in particular his relation (2.15) at p = 2 already yields the second moment, so item (i) below is a consolidation rather than a new formula. The asymptotics of E[T] as n -> infinity with q fixed are due to Berend and Sher (2026) and, in a sharper form, to Doumas and Spektor (2026); we do not claim those either, and Section 8 downgrades our own expectation expansion to an independent rediscovery accordingly. What we add is fourfold, of which the first is a consolidation rather than a new formula.(i) An exact closed form for the second moment, hence for the variance, obtained by summing the inclusion-exclusion tail in closed form, together with a uniform one-line derivation of every higher moment. Having now read Stadje (1990) in full we record that his general factorial-moment relation (his eq. (2.15)), specialised to A = S and p = 2, is equivalent to our second-moment formula; item (i) is therefore an explicit specialisation of Stadje's result and is not claimed as new.(ii) Two subtraction-free recursions -- a backward recursion for E[T] in O(nq) time and O(q) memory, and a forward recursion for the whole distribution -- which keep full double-precision accuracy up to n = 1000, whereas the inclusion-exclusion closed form loses all significant digits from n about 40 onwards: at (n,q) = (60,5) its relative error is 4.9 x 10^{-4} and at (80,5) it returns 1.99 x 10^{6} for the true value 77.836.(iii) A quantitative explanation: the relative error of the closed form is predicted by eps*kappa, where eps is the unit roundoff and kappa = sum_i |t_i| / |sum_i t_i| is the condition number of the alternating sum; measured and predicted errors agree to within two orders of magnitude over twenty-six decades.(iv) Asymptotics of the variance, with a complete proof. Writing A = H_n - H_{n-q}, Sigma_2 = sum_{j 0,hence the n log n formVar[T] = (pi^2/6)(n/q)^2 - (n/q^2)(log n + gamma) - ( ((pi^2/6)(q-1) + 1)/q^2 ) n + ((q-1)/(2q^2)) log n + c_0(q) + O(log n / n).For q = 1 everything degenerates exactly to the classical Var[T] = n^2 H_n^{(2)} - n H_n. Doumas and Spektor obtain for the variance only the leading term (pi^2/6)(n/q)^2 (1 + o(1)), so everything beyond it — the n log n term, the n-coefficient, the constant, the closed form and the exponential rate -- is new for q >= 2 as far as we have been able to determine; at q = 1 the expansion collapses to the known result of Doumas and Papanicolaou (2012). We also record the exact support [ceil(n/q), infinity) and point out that the widely quoted formula of Sharif-Hassibi and Xu-Tang belongs to a different model (draw d, keep one), which is why it gives different numbers.
Comments: 22 Pages.
Download: PDF
[v1] 2026-10-01 15:48:26
Unique-IP document downloads: 18 times
ai.Vixra.org is a AI assisted e-print repository rather than a journal. Articles hosted may not yet have been verified by peer-review and should be treated as preliminary. In particular, anything that appears to include financial or legal advice or proposed medical treatments should be treated with due caution. ai.Vixra.org will not be responsible for any consequences of actions that result from any form of use of any documents on this website.
Add your own feedback and questions here:
You are equally welcome to be positive or negative about any paper but please be polite. If you are being critical you must mention at least one specific error, otherwise your comment will be deleted as unhelpful.