{"id":"5b8c2bd1-a18c-49fe-b745-f2e680251017","arxiv_id":"2507.10019","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A binomial approximation to the sample overlap likelihood yields a simple estimator for Jaccard containment, but several of the paper's error bounds and sample size formulas are not rigorously supported.","lead":"This paper develops a statistical model for estimating how much two sets overlap when you only have small random samples from each set, rather than the full sets. It may matter for large database systems where computing exact overlap is too expensive, if the model's error bounds hold.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The claimed posterior MSE upper bound in Section 5 is invalid because Ihat_b is not the posterior mean; the variance simplification is also in the wrong direction in the sparse regime, so the sample-size guarantees built on it do not follow.","rationale":"The reader's formal weakest assumption is the independence approximation underlying the binomial model. I do not make that the primary concern: in the stated sparse regime the true x is a sum of I nearly independent indicators with success probability alpha1*alpha2, and the binomial P-by-Q model has the same mean and matching leading-order variance; the paper's own experiments support this. The load-bearing defect is instead the posterior-MSE argument, which the reader's rationale already lists as a backwards inequality but does not elevate to the weakest assumption. Since the central claim advertises tight posterior error bounds and explicit sample-size requirements, and since Section 5's inequalities are false in both directions, the advertised quantitative guarantees are not supported as stated. The point estimator remains unbiased, so the empirical contribution survives; the appropriate response is a conditional acceptance requiring corrected bounds and consistency between Sections 5 and 6, which is exactly the reader's verdict. Hence verdict_should_be is UNCHANGED.","tokens_in":12615,"tokens_out":28316,"duration_ms":288729,"concrete_test":"Numerically evaluate the exact posterior in a valid sparse case: N1=N2=1e5, I=5000, M1=M2=1e4 (n=1e8, alpha=0.1), observed x=50. Normalize p(I|x) proportional to I^50 * (1 - I/1e10)^99999950 on [0,1e5]; compute E[I|x], Var(I|x), and MSE_p(Ihat_b) with Ihat_b = x*1e10/1e8 = 5000. The Section 5 claim predicts MSE < Var_B ≈ 500,000. Exact integration gives E[I|x] ≈ 5100, Var(I|x) ≈ 510,000, and MSE ≈ 520,000, exceeding the claimed bound. If a precise computation instead yields MSE < 500,000, the concern is refuted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Section 5 the paper asserts MSE_p(I)(Ihat_b) < Var_B[I] < C^2 * x(n-x)/(n^2(n+1)), with C=N1N2 and n=M1M2. Both inequalities fail for the regime the paper targets. For any posterior, MSE_p(Ihat_b) = Var(I|x) + (Ihat_b - E[I|x])^2. Under the stated uniform prior and binomial likelihood, the Beta posterior mean is approximately C(x+1)/(n+2), while Ihat_b = Cx/n; the squared gap is [C(n-2x)/(n(n+2))]^2, positive unless n=2x, so the strict inequality MSE < Var is impossible. Moreover, the exact Beta variance is C^2*(x+1)(n-x+1)/((n+2)^2(n+3)); in the sparse small-x regime this is larger, not smaller, than C^2*x(n-x)/(n^2(n+1)), so the simplification is a lower bound. Consequently the containment MSE bounds, the sufficiency condition alpha1*alpha2^2 >= 1/(N1*delta^2), and the sample-size guidance in Section 6 are unsupported; Section 6 also uses alpha=0.001 after stating alpha>=0.01 for its own example. The unconditional estimator Ihat_b remains unbiased, so the point estimate survives, but the advertised tight posterior error bounds and explicit sample size requirements are not established.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies estimation of Jaccard containment φ = |A∩B|/|A| and Jaccard similarity J = |A∩B|/|A∪B| from uniform random samples P ⊆ A and Q ⊆ B, assuming the set sizes N1, N2 and sample sizes M1, M2 are known. The author derives an exact combinatorial likelihood for the observed overlap x = |P∩Q|, proposes a binomial approximation Pb(x|I) based on treating the M1M2 pairs in P×Q as independent matches with probability I/(N1N2), and compares this approximation with a union-based likelihood from prior work. The paper then derives an estimator Îb = x N1N2/(M1M2), claims posterior MSE bounds and sample-size requirements under a uniform prior, extends the estimator to Jaccard similarity, and proposes batch-MinHash schemes for sampled data. The paper includes empirical validation on synthetic data and a GitHub repository with code.","tokens_in":12930,"tokens_out":9222,"duration_ms":93486,"significance":"If the central claims were sound, the paper would offer a practically relevant framework for containment and similarity estimation in settings where only samples of large sets are available and set sizes are known. The unconditional estimator Îb is unbiased, the exact likelihood derivation in Section 3.3 is a useful reference, and the empirical comparison against the union-based model is informative. The paper is clearly written and ships reproducible code. However, the posterior MSE analysis in Section 5 is directionally incorrect: the claimed inequality MSE < posterior variance is impossible for an estimator that is not the posterior mean, and the variance simplification is in the wrong direction in the sparse regime. Because Sections 6 and 7 build directly on these bounds, the advertised error guarantees and sample-size recommendations are not established.","major_comments":[{"comment":"The displayed chain 'MSE_p(I)(Îb) < Var_B[I] < (N1N2)^2 · x(M1M2−x)/((M1M2)^2(M1M2+1))' is wrong in both inequalities. For any posterior, MSE equals posterior variance plus squared bias of the estimator relative to the posterior mean. Under the stated uniform prior and binomial likelihood, the approximate posterior mean of I is C(x+1)/(n+2) with C = N1N2 and n = M1M2, whereas Îb = Cx/n, giving a squared bias of C^2(n−2x)^2/(n^2(n+2)^2), which is positive unless n = 2x. Thus MSE is strictly greater than the posterior variance, not less. Additionally, the exact Beta variance with parameters (x+1, n−x+1) is (x+1)(n−x+1)/((n+2)^2(n+3)), which in the sparse small-x regime is larger than the paper's expression x(n−x)/(n^2(n+1)); for example at x = 1, n = 100 the exact variance is approximately 1.87×10^-4 while the paper's expression is approximately 9.80×10^-5. Hence the simplification is a lower bound, not an upper bound. The subsequent bound MSE_p(I)(Îb) < x(N1N2)^2/(M1M2)^2 and all sample-size conditions derived from it are therefore unsupported.","section":"Section 5, 'Bounding Posterior MSE'"},{"comment":"The numerical example is internally inconsistent. The paper states that for δ = 0.01 and N1 = 10^8 the accuracy condition requires α ≥ 1/(δ√N1) = 0.01, and the validity condition gives α ≥ 0.000403, so the binding constraint is α ≥ 0.01. The example then says 'we use α = 0.001' and reports M1 = 10^5, M2 = 5×10^5. This value of α is ten times smaller than the paper's own required minimum, so the example does not demonstrate feasibility under the stated conditions. The sample-size guidance in this section needs to be recomputed consistently after correcting the error bounds.","section":"Section 6, 'Practicality in Real-World Regimes'"},{"comment":"The fractional-error bound for the Jaccard estimator depends on the Section 5 bound MSE_p(I)(Îb) < x(N1N2)^2/(M1M2)^2 and therefore inherits the failure of that bound. In addition, the propagation step writes 1 + I/(N1+N2−I) ≈ 1 + N1/N2, which requires I ≈ N1, i.e., containment near 1; this condition is not stated or justified. Consequently the claimed O(1/√x) fractional-error guarantee for J is not established for the general parameter range the paper targets.","section":"Section 7, 'Posterior Error Bounds'"},{"comment":"The empirical validation of the binomial approximation against the exact distribution is performed at a single parameter configuration (N1 = 10^6, N2 = 2×10^6, I = 5×10^5, M1 = 3×10^4, M2 = 4×10^4). The paper does not report experiments that vary the sampling rate ratio M1M2/(N1N2) or approach the boundary of the sparse regime, even though the abstract and conclusion claim accuracy 'when sample sizes are small compared to the original sets.' Since the theoretical posterior-MSE support is flawed, this single-point validation is insufficient to substantiate the central claim of practical accuracy across the stated regime.","section":"Section 4, 'Experimental Setup' and 'Distributional Comparison'"}],"minor_comments":[{"comment":"The phrase 'a special subset of size I ⊆ F' is notational misuse: I is an integer, not a set. It should read 'a special subset S ⊆ F with |S| = I' or similar.","section":"Section 3.1"},{"comment":"The displayed Chernoff-bound condition for α1α2 appears garbled due to the layout; the formula 'α1α2 ≥ ln(1/ε)/N1 · (2+φ)/(1−φ) / (1−φ)' should be rewritten unambiguously, and the numeric example (760/N1) should be checked against the corrected formula.","section":"Section 5, 'Estimator Validity'"},{"comment":"The phrase 'with an arbitarily high confidence' contains a typo ('arbitarily' should be 'arbitrarily').","section":"Section 7"},{"comment":"The sentence 'Forturnately, it's easy to do' contains a typo ('Forturnately' should be 'Fortunately').","section":"Section 8.4"},{"comment":"The phrase 'emperical distribution' contains a typo ('emperical' should be 'empirical').","section":"Section 9.2"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is clearly written, addresses a relevant practical problem, and provides reproducible code, but the statistical-inference core in Sections 5–7 contains a directionally incorrect inequality that propagates into the main guarantees. The point estimator Îb is unbiased and may survive a corrected analysis, so I do not recommend rejection; however, the posterior error bounds, sample-size conditions, and Jaccard error claims need to be reworked or substantially qualified. The empirical validation is also too thin to carry the paper's generality claims on its own."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe useful part of this paper is the core idea: model the observed sample overlap x as binomial with parameter I/(N1N2), then estimate I by Ihat = x N1N2/(M1M2). The estimator is simple, unbiased, and works fine in the sparse regime M1M2 << N1N2. The exact combinatorial likelihood in Section 3.3 is genuinely new and a nice reference; the 5-tuple decomposition with the nested sum looks correct. The empirical comparison against the union-based likelihood is convincing: the union model is indeed the wrong distribution for x.\n\nThe trouble is that all the theoretical guarantees built on the posterior analysis are broken. Section 5 claims MSE_p(I)(Ihat) < Var_B[I] < ... . The first inequality is backwards. Ihat is not the posterior mean. Under the paper's own Beta approximation, the posterior mean is about N1N2(x+1)/(M1M2+2), not N1N2 x/(M1M2). The squared difference is positive unless M1M2 = 2x, so MSE = Var + bias^2 > Var. The Beta variance simplification also goes the wrong direction: the exact scaled variance is larger than the simplification in the small-x regime. So the MSE upper bounds, the sufficiency condition on alpha, and the sample-size guidance in Section 6 do not follow. Section 6 also uses alpha = 0.001 after stating alpha >= 0.01 for its own example. The MinHash error propagation in Section 9.1 has a derivative that does not match the chain rule.\n\nThe point estimator survives; it is unbiased and the binomial model is reasonable. But the advertised tight error bounds and explicit sample size requirements are not established until the posterior analysis is corrected. The paper also never compares against Henzinger's small-sample intersection estimator, which is the closest prior work and should be cited and contrasted.\n\nWho is this for? Someone working on set similarity estimation in databases might use the exact likelihood and the estimation idea, but only after the error guarantees are fixed. I would not cite the quantitative claims as they stand. It deserves a serious referee, but the referee should be told to verify the posterior MSE section carefully; it will need major revision.\n\nRecommendation: send back for major revision, not desk reject. The core model is sound; the guarantees are not.","headline":"A useful estimator and a genuinely new exact likelihood, but the posterior MSE bounds and sample-size formulas are wrong as stated; the paper needs correction before the guarantees can be trusted.","tokens_in":13397,"tokens_out":5968,"would_cite":false,"duration_ms":59184,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62D05","62F15","62G05"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that a binomial model for the overlap of two random samples yields a low-bias estimator of Jaccard containment with explicit error bounds and sample-size requirements.","keywords":["Jaccard containment","Jaccard similarity","random sampling without replacement","binomial approximation","intersection estimation","posterior error bounds","sample complexity","MinHash"],"falsifier":"Simulate two sets of known sizes and intersection, draw samples at a rate where $M_1M_2$ is not negligible relative to $N_1N_2$ (for example $\\alpha_1=\\alpha_2=0.2$), and compare the empirical distribution of $x$ with the binomial $P_b(x\\mid I)$; if the observed mean or variance deviates from binomial predictions by more than the paper's posterior MSE bound, or if $\\hat{I}_b$ shows bias exceeding the stated bound, the independence approximation fails in that regime.","tokens_in":12390,"feed_emoji":"📊","tokens_out":7907,"duration_ms":80739,"temperature":0.7,"pith_summary":"The paper tries to establish that, when the full sizes of two sets are known but only small uniform samples of each are available, the overlap between the samples is well described by a binomial distribution. It proposes estimating the true intersection size by taking the observed sample overlap and scaling it up by the ratio of the set sizes to the sample sizes. The paper argues that this estimator has low bias and variance in the sparse-sampling regime, provides upper bounds on its posterior mean squared error, and translates those bounds into explicit sample-size requirements for a desired accuracy and confidence. It also extends the same model to Jaccard similarity and to batched MinHash sketches, giving error bounds that scale with the inverse square root of the observed overlap. A sympathetic reader would care because these are the conditions faced in large database systems that can access only partial data and need containment or similarity estimates without full sketches.","feed_headline":"Binomial formula estimates set overlap from two random samples","feed_subtitle":"Backed by explicit error bounds and sample-size rules for huge sets where only portions are reachable.","key_machinery":"The load-bearing object is the Cartesian product $A\\times B$ with its $I$ diagonal matching pairs, and the assumption that the sampled subgrid $P\\times Q$ sees each such pair independently with probability $I/(N_1N_2)$. This turns the observed overlap $x$ into a binomial count, which is tractable enough to derive an estimator, a Beta posterior, Chernoff-based validity conditions, and sample-complexity formulas. The exact likelihood derived by summing over a five-tuple decomposition is used only as ground truth because its nested sums are intractable for large sets.","core_discovery":"The central claim is that the likelihood for the observed number $x$ of matching elements in two uniform samples is, in the sparse regime, $P_b(x\\mid I)=\\binom{M_1M_2}{x}\\left(\\frac{I}{N_1N_2}\\right)^x\\left(1-\\frac{I}{N_1N_2}\\right)^{M_1M_2-x}$, where $M_1,M_2$ are the sample sizes and $N_1,N_2$ the set sizes. This leads to the estimator $\\hat{I}_b = x\\frac{N_1N_2}{M_1M_2}$ for the intersection size and $\\hat{\\phi}=x\\frac{N_2}{M_1M_2}$ for the containment $\\phi=I/N_1$. The paper reports that this binomial likelihood matches the exact sampling distribution closely in experiments, while a union-based likelihood from earlier work overestimates the overlap dramatically. Under a uniform prior on $I$, the posterior is Beta-like and yields the MSE bound $\\mathrm{MSE} < x(N_1N_2)^2/(M_1M_2)^2$; enforcing estimator validity tightens this to $N_2/(M_1M_2)$, and combining the two conditions gives the sampling-rate requirement $\\alpha_1\\alpha_2 \\ge \\max\\{1/(\\delta^2 N_1),\\, 2\\ln(1/\\epsilon)/((1-\\phi)^2 N_1)\\}$ for containment error below $\\delta$ with confidence at least $1-\\epsilon$.","pith_inferences":["If the binomial approximation holds, the same product-of-samples logic could extend to weighted or duplicate-rich collections, but the without-replacement correction would need to be quantified before trusting the bounds.","The paper's sample-complexity formulas imply an allocation rule for asymmetric set sizes: when $N_2\\gg N_1$, symmetric sampling forces $M_2$ to scale with $N_2/N_1$, so a practitioner should instead choose $M_2$ based on the desired observed overlap rather than a fixed fraction of $N_2$.","The small negative bias noted in the batch MinHash experiments, left unexplained in the paper, may come from a second-order without-replacement effect or from the Jensen-type gap in converting sampled Jaccard estimates; a bias-correction study would be a direct test.","Because the Jaccard fractional-error bound decreases as $1/\\sqrt{x}$, a system could keep drawing samples until the observed overlap crosses the threshold $c=4/\\delta^2$, which the paper's lower-tail bound directly addresses."],"forward_implications":["With known $N_1,N_2$ and sparse sampling, containment can be estimated as $\\hat{\\phi}=x N_2/(M_1M_2)$, and the paper's bounds say this estimate has MSE below $xN_2^2/(M_1M_2)^2$, tightening to $N_2/(M_1M_2)$ when the estimator is valid.","To guarantee containment RMSE below $\\delta$ with probability at least $1-\\epsilon$, sampling rates must satisfy $\\alpha_1\\alpha_2 \\ge \\max\\{1/(\\delta^2 N_1),\\, 2\\ln(1/\\epsilon)/((1-\\phi)^2 N_1)\\}$; symmetric sampling needs $M_1\\ge \\sqrt{N_1}/\\delta$.","For Jaccard similarity, the fractional error of $\\hat{J}$ scales as $O(1/\\sqrt{x})$, so the required product of sample sizes grows like $1/(\\delta^2 I)$ rather than $1/(\\delta^2 N_1)$.","Batched MinHash over sampled subsets yields a containment estimate whose RMSE is bounded by $\\sqrt{2M N_2/(k M_1M_2)}$ (or $(N_2/M_2)\\sqrt{(m_1+m_2)/(kM_1)}$ for unequal batches), and stratified batching restores the independence the binomial model assumes."],"supporting_citations":[{"why":"Supplies the union-based likelihood model that the binomial approximation is compared against and shown to outperform for direct sample intersection counts.","marker":"[4]"},{"why":"Defines resemblance and containment and establishes the MinHash setting being adapted to sampled subsets.","marker":"[5]"},{"why":"Provides the Chernoff concentration bound used to turn estimator validity and accuracy requirements into sample-size conditions.","marker":"[8]"},{"why":"Supplies the Beta distribution variance identity backing the posterior MSE upper bound.","marker":"[9]"},{"why":"Second source for the Beta variance formula used in the posterior error analysis.","marker":"[10]"},{"why":"Gives the Chernoff tail bound used for lower-tail probability guarantees on the observed overlap $x$.","marker":"[11]"}],"fun_headline_variants":["Binomial model gives exact overlap odds from two samples","New binomial estimator beats union bound for set overlap","Intersection size from random samples: binomial formula wins","Small-sample overlap estimator with explicit error bounds","Binomial likelihood leads to simple containment estimate"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The estimator and all error bounds rest on treating the $M_1M_2$ sampled pairs as independent matching events with common probability $I/(N_1N_2)$, ignoring that the samples are drawn without replacement; the paper assumes the sparse regime $M_1M_2 \\ll N_1N_2$ makes this dependence negligible.","fun_headline_variants_meta":{"raw":{"variants":["Binomial model gives exact overlap odds from two samples","New binomial estimator beats union bound for set overlap","Intersection size from random samples: binomial formula wins","Small-sample overlap estimator with explicit error bounds","Binomial likelihood leads to simple containment estimate"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000832,"raw_usage":{"total_tokens":3651,"prompt_tokens":981,"completion_tokens":2670,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":597,"completion_tokens_details":{"reasoning_tokens":2601}},"tokens_in":597,"tokens_out":2670,"duration_ms":21061,"temperature":1.0,"reasoning_tokens":2601,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:42:57.742302+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate two sets of known sizes and intersection, draw samples at a rate where $M_1M_2$ is not negligible relative to $N_1N_2$ (for example $\\alpha_1=\\alpha_2=0.2$), and compare the empirical distribution of $x$ with the binomial $P_b(x\\mid I)$; if the observed mean or variance deviates from binomial predictions by more than the paper's posterior MSE bound, or if $\\hat{I}_b$ shows bias exceeding the stated bound, the independence approximation fails in that regime.","supporting_citations":[{"cited_title":"Henzinger","cited_arxiv_id":null,"evidence_quote":"Supplies the union-based likelihood model that the binomial approximation is compared against and shown to outperform for direct sample intersection counts."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines resemblance and containment and establishes the MinHash setting being adapted to sampled subsets."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the Beta distribution variance identity backing the posterior MSE upper bound."},{"cited_title":"Casella and R","cited_arxiv_id":null,"evidence_quote":"Second source for the Beta variance formula used in the posterior error analysis."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the Chernoff tail bound used for lower-tail probability guarantees on the observed overlap $x$."}],"review_version":1}