{"id":"023f0927-df74-4958-af80-8d6e4fd56d30","arxiv_id":"1908.10024","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A broad review of Poisson binomial distributions that adds new bounds and small-n exact values for approximating rational multiples of binomials by strongly Rayleigh variables.","lead":"This paper surveys the Poisson binomial distribution, the sum of independent coin flips with different probabilities, covering classical approximations and recent links to polynomial roots and optimal transport. It also adds a few new results, including quantifications of how far floor(2X/3) can be from a Poisson binomial, plus small computed cases and an open conjecture.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.4's stated root lower bound rests on an unproved quantitative bridge from Newton-inequality violation to imaginary-part size; without it, the claim is unverified.","rationale":"The reader's weakest_assumption identifies exactly the same gap: Theorem 4.4 is stated with 'one can prove' and the Newton-inequality violation is not shown to imply the quantitative root-location bound. I agree this is the most load-bearing issue. The concern does not overturn the survey portion, which is well-attributed, so the conditional verdict remains appropriate. I additionally note the n=1 domain defect and that the appendix's small-n Acc values also need lower-bound arguments, but those are secondary to Theorem 4.4. The proposed check, either an explicit derivation of the coefficient-to-root transfer lemma or a numerical scan for a counterexample, would decide whether the theorem's constant is correct or whether the statement should be weakened to a conjecture.","tokens_in":19907,"tokens_out":20175,"duration_ms":187144,"concrete_test":"Prove the quantitative contrapositive of Theorem 4.4: for F_n(z)=sum_{k=0}^{2n} a_k z^k with a_{2k}=C(3n+1,3k+1) and a_{2k+1}=C(3n,3k+2), show that if every root satisfies |Im z_i| < sqrt(9n^2-9n-1)/2, then Newton's inequality (4.2) must hold. If this implication is not derivable, or yields a smaller threshold, the theorem's stated constant is unsupported. A numerical root computation for n=2,...,50 would also immediately reveal any counterexample.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 4.4 is the paper's sharpest new mathematical assertion, but its proof is replaced by 'one can prove' and by the observation that the coefficients of the PGF of floor(2X/3) violate Newton's inequality (4.2). That observation is only qualitative: it shows some root is non-real, not that a root has imaginary part at least sqrt(9n^2-9n-1)/2 ~ 3n/2. No argument in the paper connects the displayed coefficient imbalance (between a_{2k}=C(3n+1,3k+1) and a_{2k+1}=C(3n,3k+2)) to a quantitative lower bound on max Im z_i. The missing transfer lemma is the entire substance of the theorem. The statement also needs a domain qualifier: for n=1 the radicand 9n^2-9n-1 is negative, so the right-hand side is not real. Since the paper's motivation for saying floor(2X/3) is 'far away' from strongly Rayleigh depends on this O(n) lower bound, the absent proof, not the survey content, is the load-bearing weak point.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper is an expository survey of the Poisson binomial distribution, covering distributional properties, Poisson/normal/binomial approximations, polynomial and strong-Rayleigh aspects, optimal transport questions around approximating 2X/3, and computational/learning results. The authors compile numerous known theorems with citations and add several new pieces: Theorem 4.4, which asserts a quantitative lower bound on the imaginary parts of the roots of the PGF of floor(2X/3) for X~Bin(3n,1/2); a discussion and open problems around the quantity Acc(2X/3); and exact values of Acc(2X/3) for small n in Appendix A. The survey portions are internally consistent and accurately attribute known results; the new mathematical claims are, however, only sketched.","tokens_in":20004,"tokens_out":10337,"duration_ms":96230,"significance":"If the new claims are correct, the paper would be a useful resource for the Poisson binomial community and for researchers working on strong-Rayleigh properties of discretized sums. The survey of post-2000 results on approximation, learning, and polynomial geometry is valuable and generally accurate, with citations that appear reliable. The paper also has strengths in being self-contained and in connecting diverse literatures. It does not fit free parameters to its conclusions, and its new results are checked against external benchmarks such as binomial tail estimates and Newton's inequality. The sharpest new assertion, Theorem 4.4, and the exact accuracy values in Appendix A are not yet supported by complete proofs, so the contribution as a research paper is conditional on supplying those arguments.","major_comments":[{"comment":"Theorem 4.4 is the paper's most significant new mathematical assertion, but it is not proved. The text says only that 'one can prove' the bound and gives the observation that the coefficients of the PGF of floor(2X/3) violate Newton's inequality (4.2). That observation is qualitative: it implies the polynomial is not real-rooted, i.e. max_i Im(z_i) > 0, but it does not by itself imply the quantitative bound max_i Im(z_i) >= sqrt(9n^2 - 9n - 1)/2. The missing transfer lemma from the coefficient imbalance a_{2k} = binom(3n+1,3k+1), a_{2k+1} = binom(3n,3k+2) to a root-location bound is the entire substance of the theorem. The statement also needs a domain qualifier, since for n=1 the radicand 9n^2 - 9n - 1 is negative. Because the theorem motivates the claim that floor(2X/3) is 'far away' from being strongly Rayleigh and underpins Open Problem 4.6, this missing proof is load-bearing rather than a presentation issue.","section":"Section 4, Theorem 4.4"},{"comment":"The values Acc(2X/3) = 2/3 reported for n=5 and n=6 are presented as exact, but only upper bounds are demonstrated. For n=6, the construction of Y ~ Bin(4,1/2) gives W_infinity(2X/3,Y) <= 2/3, and no argument is supplied to show that every strongly Rayleigh Y on {0,...,2n} satisfies W_infinity(2X/3,Y) >= 2/3. For n=5, the text says that a 'similar argument as in the case n=4' shows W_infinity(2X/3,Y) != 1/3, but the exclusion argument is not written out, and the possibility of values strictly between 1/3 and 2/3 is not addressed. To report these as exact values of Acc, the authors must either give the lower-bound proofs or explicitly state the values as upper bounds.","section":"Appendix A, n=5 and n=6"}],"minor_comments":[{"comment":"In the statements of Theorems 3.5 and 3.6, the displayed definition reads 'mu := sum_{i=1}^n p_n' where it should be 'sum_{i=1}^n p_i'; the same typo appears in Theorem 3.7.","section":"Section 3, Theorems 3.5 and 3.6"},{"comment":"The phrase 'Elm's approach' should be 'Ehm's approach', referring to Ehm [41].","section":"Section 3, around (3.10)"},{"comment":"The parameters written as 'PB(1/4 + sqrt(8), 1/4 - sqrt(8))' are not probabilities in [0,1]; the intended parameters appear to be approximately 1/2 + sqrt(2)/4 and 1/2 - sqrt(2)/4, matching the roots -3 ± sqrt(8) of the displayed PGF.","section":"Appendix A, n=3"},{"comment":"The expression 'PB(1/2 + 2/sqrt(5), 1/2 - 2/sqrt(5))' is again outside [0,1] for the plus sign; the factorized PGF (1 + 10x + 5x^2)/16 has Bernoulli parameters 5/8 + sqrt(5)/8 and 5/8 - sqrt(5)/8, so the displayed parameters should be corrected.","section":"Appendix A, n=4"},{"comment":"The sentence 'the r.h.s of (5.3) is the discrete Fourier transform' should read 'the right-hand side of (5.3)'.","section":"Section 5, (5.3)-(5.4)"}],"recommendation":"major_revision","confidential_remarks":"The survey content is solid and worth publishing as a resource, but the paper's own novelty is concentrated in Section 4 and Appendix A, where the main assertions are not fully supported. If the authors can supply the missing proof of Theorem 4.4 and the lower-bound arguments for the Appendix A accuracy values, the paper would be a clear contribution; otherwise it should be reframed as a survey with conjectures and upper bounds."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Plainly: this is a useful survey with some genuinely new bits, but the new bits are not yet theorems. The survey core is solid and well-cited; the new claims in Section 4 and Appendix A are plausible but under-proved. I'd send it to a qualified referee, with the expectation of major revision.\n\nWhat's good: the paper gives a compact map of the Poisson binomial literature—Hoeffding inequalities, Poisson/normal/binomial approximation, computational methods, and the polynomial-geometry side. The bibliography is broad and the attributions look right. The optimal-transport formulation (4.6) for approximating 2X/3 by strong Rayleigh laws is a fresh angle, and the small-n computations in Appendix A give a concrete starting point. Conjecture 4.8 (fractional parts of a strong Rayleigh variable decompose into sums of bounded independent variables) is a natural question that connects to Liggett's Hurwitz stability result.\n\nThe soft spots are all in the new material. Theorem 4.4 is the sharpest new assertion, but the proof is replaced by 'one can prove' and a qualitative observation that Newton's inequality fails. That observation only shows some roots are non-real; it does not yield the quantitative bound max Im z_i ≥ sqrt(9n^2−9n−1)/2. You need a real transfer lemma connecting coefficient imbalance to root location, and the paper doesn't supply one. Also, for n=1 the radicand is negative, so the statement needs a domain qualifier. Proposition 4.5's proof is a sketch with a garbled definition of C_p (the two cases are given the same expression); the idea seems right, but the write-up is not reliable as is. Appendix A's claims for n=5 and n=6 likewise assert optimality without a lower-bound argument; the 'similar argument' for n=5 is not shown. None of this undermines the survey portions, but it does mean the new results should not be cited as theorems yet.\n\nMy recommendation: give it a serious referee. The survey half is publishable after light editing; the new half needs either proofs or explicit reclassification as conjectures and numerical evidence. If the authors fix Theorem 4.4 (or downgrade it) and clean up Proposition 4.5 and the appendix, this would be a valuable reference.","headline":"Useful survey of Poisson binomial theory with a few new results that are under-proved; Theorem 4.4 needs a real proof or a demotion to conjecture.","tokens_in":20665,"tokens_out":3110,"would_cite":true,"duration_ms":30845,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60E05","60E10","60E15","62E17"],"pacs":[],"model":"deepseek-v4-flash","headline":"For $X \\sim \\mathrm{Bin}(3n,1/2)$, the probability generating function of $\\lfloor 2X/3 \\rfloor$ has a root with imaginary part at least $\\sqrt{9n^2-9n-1}/2$, so naive rational rounding does not preserve the strongly Rayleigh property.","keywords":["Poisson binomial distribution","strongly Rayleigh property","real-rooted polynomials","rational rounding of random variables","optimal transport","distribution learning","Newton's inequality"],"falsifier":"For $n = 10, 20, 40, 80$, compute all roots of the degree-$2n$ polynomial $\\sum_k \\mathbb P(\\lfloor 2X/3 \\rfloor = k) z^k$ with $X \\sim \\mathrm{Bin}(3n,1/2)$ and compare $\\max_i \\Im(z_i)$ with $\\sqrt{9n^2-9n-1}/2$. If any $n$ has observed maximum below the bound, or growth slower than linear, Theorem 4.4 is false; matching growth would validate the missing coefficient-to-root step.","tokens_in":19600,"feed_emoji":"🎲","tokens_out":14744,"duration_ms":135849,"temperature":0.7,"pith_summary":"The paper is an expository survey of the Poisson binomial distribution with a new counterexample at its core. Its unifying thesis is that a distribution on $\\{0,\\dots,n\\}$ is Poisson binomial exactly when its generating polynomial has only real roots, a property called strongly Rayleigh; under this identification, stochastic orderings, Poisson and normal approximation, and distribution learning become chapters of the geometry of polynomials. The new contribution is negative: rounding $X \\sim \\mathrm{Bin}(3n,1/2)$ down to $\\lfloor 2X/3 \\rfloor$ destroys real-rootedness, and the generating polynomial gains a root whose imaginary part is at least $\\sqrt{9n^2-9n-1}/2$, so the naive rational approximation is not strongly Rayleigh for large $n$. This matters because $\\lfloor jX/k \\rfloor$ rounding was proposed as a route to multivariate central limit theorems for strongly Rayleigh variables, and this paper shows that route fails already at $j=2,k=3$. What survives is that the rounded PGF is still Hurwitz stable, and small-$n$ computations indicate the best strongly Rayleigh approximation sits at distance $2/3$ in the infinity-Wasserstein metric.","feed_headline":"Rounding a binomial by 2/3 puts roots far off the real axis","feed_subtitle":"A root lands at least $\\sqrt{9n^2-9n-1}/2$ off the real axis, so a natural CLT route fails.","key_machinery":"The load-bearing object is the probability generating function $f(u)=\\prod_{i=1}^n (p_i u + 1-p_i)$, whose coefficients are the distribution's weights. The paper's organizing idea is that the coefficients form a Poisson binomial distribution if and only if $f$ is real stable, meaning all roots are real and, here, negative; this is the strongly Rayleigh property, and it is what the rounding question tests. To attack $\\lfloor 2X/3 \\rfloor$, the paper uses the coefficient imbalance between even and odd values, which forces a failure of Newton's inequality $a_i^2 \\ge a_{i-1}a_{i+1}(1+1/i)(1+1/(n-i))$, and pairs this with root-location arguments for the lower bound on the imaginary parts. On the positive side, it uses a classical root-interlacing criterion, the Hermite-Biehler theorem, to explain why the same PGF is Hurwitz stable and hence a sum of independent random variables taking values in $\\{0,1,2\\}$. The approximation question is quantified by the infinity-Wasserstein distance $W_\\infty$, which measures the worst-case move needed to push the rounded variable into a strongly Rayleigh distribution.","core_discovery":"The paper's sharpest new assertion is Theorem 4.4: for $X \\sim \\mathrm{Bin}(3n,1/2)$, the roots $z_i$ of the probability generating function of $\\lfloor 2X/3 \\rfloor$ satisfy $\\max_i \\Im(z_i) \\ge \\sqrt{9n^2-9n-1}/2$. Since the right-hand side is linear in $n$, the rounded variable is, for large $n$, far outside the strongly Rayleigh class. The explanation offered is that rounding concentrates probability unevenly on even and odd values, with $\\mathbb P(\\lfloor 2X/3 \\rfloor=2k)$ proportional to $\\binom{3n+1}{3k+1}$ and the odd masses proportional to $\\binom{3n}{3k+2}$, so Newton's inequality fails. The paper also records that the same PGF is Hurwitz stable, formulates the $W_\\infty$-optimal strongly Rayleigh approximation problem $\\mathrm{Acc}(2X/3)$, and computes it for $n\\le 6$, conjecturing that $\\mathrm{Acc}(2X/3)=O(1)$.","pith_inferences":["The coefficient-to-root mechanism behind Theorem 4.4 is generic: any fixed rounding rule $\\lfloor jX/k\\rfloor$ that imbalances coefficient parities should produce PGF roots with imaginary parts growing linearly in $n$, so the strongly Rayleigh class is likely closed only under exact affine maps and under $\\lfloor X/k\\rfloor$.","One can test the $O(1)$ conjecture directly by computing $\\mathrm{Acc}(2X/3)$ for $n$ up to a few dozen with numerical root-finding: if the value plateaus at $2/3$ rather than decaying, the conjecture holds and the plateau value may be exactly $2/3$.","A quantitative lemma connecting Newton-inequality slack to root displacement would turn the paper's counterexample into a general certificate that a log-concave-but-not-PF sequence is far from every strongly Rayleigh distribution in the $W_\\infty$ metric.","The paper's $P_3/Q_3$ examples show that root interlacing does not imply factorization into low-degree positive-coefficient polynomials, so proving Conjecture 4.8 will need something beyond the classical interlacing criterion."],"forward_implications":["For $X\\sim\\mathrm{Bin}(3n,1/2)$, the variable $\\lfloor 2X/3\\rfloor$ is not strongly Rayleigh for large $n$: its PGF has a root with imaginary part at least $\\sqrt{9n^2-9n-1}/2$, so the naive integer-rounding operation leaves the real-rooted class.","No single binomial $\\mathrm{Bin}(2n,p)$ approximates $2X/3$ in $W_\\infty$ better than $C_p n$, so mean-variance matching alone cannot repair the rounding.","The equidistributed choice $p_i=i/(2n+1)$ gives a strictly better but still linear lower bound on $W_\\infty(2X/3,\\mathrm{PB}(p_1,\\dots,p_{2n}))$; it is the best explicit construction the paper discusses.","Although $\\lfloor 2X/3\\rfloor$ is not strongly Rayleigh, it is Hurwitz stable, hence a sum of independent random variables taking values in $\\{0,1,2\\}$; the obstruction is specifically real-rootedness rather than any factorization into low-degree positive-coefficient factors.","The small-$n$ computations give $\\mathrm{Acc}(2X/3)=1/3$ for $n=1,2$ and $2/3$ for $n=3,4,5,6$, supporting the conjecture that $\\mathrm{Acc}(2X/3)=O(1)$."],"supporting_citations":[{"why":"Supplies the classical criterion: a polynomial with nonnegative coefficients has only real roots exactly when its normalized coefficients are the probabilities of a sum of independent Bernoulli trials; Theorem 4.4 tests this criterion.","marker":"[1]"},{"why":"Companion characterization of the same real-rootedness through total nonnegativity of the Toeplitz coefficient matrix, cited with [1] as the foundation of the paper's terminology.","marker":"[2]"},{"why":"Introduces the strongly Rayleigh property and its equivalence to negative dependence, giving the paper the class of distributions whose closure under rounding it studies.","marker":"[21]"},{"why":"Raises the question of approximating $\\lfloor jX/k\\rfloor$ by strongly Rayleigh variables and proves the positive case $j=1$; Theorem 4.4 is the negative answer to the next case.","marker":"[47]"},{"why":"Proves that the PGF of $\\lfloor 2X/3\\rfloor$ is Hurwitz stable, the positive half of the paper's story about the same variable.","marker":"[65]"},{"why":"Introduces ultra-logconcavity and Newton's inequality as negative-dependence conditions; these are the inequalities the coefficients of $\\lfloor 2X/3\\rfloor$ violate.","marker":"[74]"},{"why":"Supplies the infinity-Wasserstein metric $W_\\infty$ used to define the approximation accuracy $\\mathrm{Acc}(2X/3)$ and to state the open problem.","marker":"[103]"}],"fun_headline_variants":["Round a binomial by 2/3, roots leave the real line","2/3-rounded binomial: roots at linear distance from real axis","Binomial rounding by 2/3: Newton fails, roots roam far","For Bin(3n,1/2) rounded by 2/3, roots are ~1.5n away","Why rounding a binomial by 2/3 breaks the natural CLT route"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Theorem 4.4 hinges on a step the paper states but does not prove: that the failure of Newton's inequality for the coefficients of the generating polynomial of $\\lfloor 2X/3 \\rfloor$ forces some root to have imaginary part at least $\\sqrt{9n^2-9n-1}/2$.","fun_headline_variants_meta":{"raw":{"variants":["Round a binomial by 2/3, roots leave the real line","2/3-rounded binomial: roots at linear distance from real axis","Binomial rounding by 2/3: Newton fails, roots roam far","For Bin(3n,1/2) rounded by 2/3, roots are ~1.5n away","Why rounding a binomial by 2/3 breaks the natural CLT route"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000552,"raw_usage":{"total_tokens":2573,"prompt_tokens":829,"completion_tokens":1744,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":445,"completion_tokens_details":{"reasoning_tokens":1637}},"tokens_in":445,"tokens_out":1744,"duration_ms":15562,"temperature":1.0,"reasoning_tokens":1637,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T10:56:08.923054+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For $n = 10, 20, 40, 80$, compute all roots of the degree-$2n$ polynomial $\\sum_k \\mathbb P(\\lfloor 2X/3 \\rfloor = k) z^k$ with $X \\sim \\mathrm{Bin}(3n,1/2)$ and compare $\\max_i \\Im(z_i)$ with $\\sqrt{9n^2-9n-1}/2$. If any $n$ has observed maximum below the bound, or growth slower than linear, Theorem 4.4 is false; matching growth would validate the missing coefficient-to-root step.","supporting_citations":[{"cited_title":"Ghosh, T","cited_arxiv_id":null,"evidence_quote":"Raises the question of approximating $\\lfloor jX/k\\rfloor$ by strongly Rayleigh variables and proves the positive case $j=1$; Theorem 4.4 is the negative answer to the next case."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Proves that the PGF of $\\lfloor 2X/3\\rfloor$ is Hurwitz stable, the positive half of the paper's story about the same variable."},{"cited_title":"Pemantle","cited_arxiv_id":null,"evidence_quote":"Introduces ultra-logconcavity and Newton's inequality as negative-dependence conditions; these are the inequalities the coefficients of $\\lfloor 2X/3\\rfloor$ violate."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the infinity-Wasserstein metric $W_\\infty$ used to define the approximation accuracy $\\mathrm{Acc}(2X/3)$ and to state the open problem."}],"review_version":1}