Pith. sign in

REVIEW 5 major objections 3 minor 21 references

On the number of contingency tables and the independence heuristic

T0 review · 5 major / 3 minor · reviewed 2026-08-27 · deepseek-v4-flash

Pith's one-line read Sharp asymptotics for two-tier contingency tables reveal a second-order phase transition at $B_c=1+\sqrt{1+1/C}$, where the independence heuristic starts to undercount by an exponential factor.

desk verdict The phase transition at Bc is real and the proof works away from the critical point, but the endpoint B=Bc is not actually proved, and two display errors in Lemma 4.1 and equation (4.1) need fixing. read the letter →

arxiv 2009.10810 v1 pith:EZ2ZMBHQ submitted 2020-09-22 math.CO math.PRmath.STstat.TH

classification math.COmath.PRmath.STstat.TH MSC 05A1605A1560C05
keywords contingencytablesindependenceheuristicphasetransitiontypicaltabletransportationpolytopeasymptoticenumerationBarvinokmarginscorrelationratio
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper counts $n\times n$ contingency tables in which the first $n^\delta$ rows and columns have margin $BCn$ and the remaining $n$ have margin $Cn$. It proves that the logarithm of the true count has a second-order phase transition at $B_c=1+\sqrt{1+1/C}$: below $B_c$ the second-order term varies with $B$, while above $B_c$ it stays frozen at its critical value. The paper then compares the true count with the classical independence heuristic, which replaces the table count by a product of row- and column-margin binomial factors. The comparison shows the heuristic matches the true count to order $n^{1+\delta}$ for $B\le B_c$, but undercounts by an exponential factor $\exp(\Theta(n^{1+\delta}))$ for $B>B_c$. The result matters because it locates precisely where a widely used approximation breaks down and ties the failure to a phase transition in the structure of random tables.

What carries the argument

The mechanism is the typical table: the unique maximizer $Z$ of the concave function $g(X)=\sum_{i,j} f(x_{ij})$ over the transportation polytope, with $f(x)=(x+1)\log(x+1)-x\log x$. A theorem of Barvinok bounds $\log T$ between $g(Z)$ and $g(Z)-O(n\log n)$, so the counting problem reduces to locating $Z$. A quoted lemma gives sharp asymptotics for the three structurally relevant entries of $Z$: the corner entry $z_{11}$, the off-diagonal block entry $z_{1,n+1}$, and the diagonal block entry $z_{n+1,n+1}$. Feeding these entry asymptotics into a Taylor expansion of $g$ yields the coefficient formulas in Proposition 3.4, from which both theorems follow.

What would settle it

Numerically solve the concave maximization defining the typical table for $C=1$, increasing $n$, at $B=B_c=1+\sqrt{2}$; if $z_{11}$ does not diverge on the scale predicted by the lemma's $B<B_c$ formula or switch to the $B>B_c$ scaling, the claimed transition point or exponent is wrong. Equivalently, compute $\frac{1}{n^{1+\delta}}\log(T_{n,\delta}(B,C)/G_{n,\delta}(B,C))$ for $B$ slightly above $B_c$ by exact enumeration for small $n$ and check it approaches the positive formula rather than zero.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is Theorem 2.2: for the two-tier margins, the correlation ratio satisfies $$\lim_{n\to\infty}\frac{1}{$n^{{1+\delta}}$}\log\frac{T_{n,\delta}(B,C)}{G_{n,\delta}(B,C)}=0\quad(B\le B_c),$$ and equals $C(B-B_c)\log(1+1/C)-2(f(BC)-f(B_c C))>0$ for $B>B_c$, where $f(x)=(x+1)\log(x+1)-x\log x$. Equivalently, the row-margin and column-margin events in a uniformly random table are asymptotically independent below $B_c$ and positively correlated above it. Theorem 2.1 gives the matching sharp expansion for $\log T_{n,\delta}(B,C)$: up to the $n^{1+\delta}$ term it agrees with the independence heuristic for all $B$, but above $B_c$ the coefficient of $n^{1+\delta}$ stops changing with $B$, so the heuristic's predicted decrease is an artifact. The phase transition is of second order because the limiting exponent is continuous with continuous first derivative, but its second derivative jumps at $B_c$.

Load-bearing premise

The proof rests on the quoted asymptotic for the typical table's corner entry, a bound whose denominator vanishes at $B=B_c$; if that entry does not behave as stated at the critical point, both the zero limit for $B\le B_c$ and the positive exponent above $B_c$ collapse.

Editorial extensions

If this is right

  • For $B\le B_c$, $\log T_{n,\delta}(B,C)=\log G_{n,\delta}(B,C)+o(n^{1+\delta})$, so the independence heuristic is correct to leading exponential order in this regime.
  • For $B>B_c$, the true count exceeds the heuristic by a factor $e^{\Theta(n^{1+\delta})}$; the heuristic mispredicts the count's dependence on $B$.
  • The coefficient of $n^{1+\delta}$ in $\log T$ is largest at $B_c$ and constant for all $B>B_c$, so increasing the large margin beyond the threshold does not change the second-order count.
  • Row and column margin events become positively correlated exactly above $B_c$; the correlation exponent's second derivative jumps, giving a thermodynamic-style second-order phase transition.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • One can test whether the same threshold $B_c=1+\sqrt{1+1/C}$ governs other margin shapes, such as three-tier margins or random margins, since the mechanism is driven by the corner entry of the typical table rather than by the exact two-tier structure.
  • The heuristic's failure mode suggests practical samplers or estimators that assume row-column independence in two-way tables should be calibrated against this threshold when margins are highly skewed; below $B_c$ the approximation is safer.
  • At $B=B_c$ the paper's formulas leave an open gap because the quoted lemma degenerates; a natural extension is to determine whether a logarithmic correction or a different scaling appears exactly at the critical point.
Share X Bluesky LinkedIn Reddit HN

Formalized claims in Lean

  1. Claim #1: On the paper's own terms, the central discovery is Theorem 2.2: for the two-tier margins, the correlation ratio satisfies $$\lim_{n\to\infty}\frac{1}{$n^{{1+\delta}}$}\log\frac{T_{n,\delta}(B,C)}{G_{n,\delta}(B,C)}=0\quad(B\le B_c),$$ and equals $C(B-B_c)\log(1+1/C)-2(f(BC)-f(B_c C))>0$ for $B>B_c$, where $f(x)=(x+1)\log(x+1)-x\log x$. Equivalently, the row-margin and column-margin events in a uni

Signed reviews

No signed human review yet.

Request a human review

A listed scientist reviews the paper for a fee and the review publishes here regardless of verdict. See the reviewers or get listed.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

5 major / 3 minor

Summary. The paper studies n×n contingency tables with Barvinok margins: n^δ rows and columns have row/column sum BCn and the remaining n have sum Cn. For fixed B, C and 0<δ<1 it claims an asymptotic expansion of log T_{n,δ}(B,C) (Theorem 2.1) with a phase transition at Bc=1+sqrt(1+1/C), and a corollary (Theorem 2.2) saying that the ratio to the independence-heuristic estimate G satisfies (1/n^{1+δ}) log(T/G) → 0 for B≤Bc and a positive constant for B>Bc. The proof combines Barvinok's upper and lower bounds for T in terms of the entropy maximizer g(Z) with a typical-table lemma quoted from [DLP], then computes g(Z) and log G by Taylor expansion.

Significance. If correct, the result is significant: it gives sharp asymptotics for a nontrivial intermediate margin regime and shows that the classical independence heuristic can fail by an exponential factor after a critical value, despite behaving smoothly through the transition. The overall strategy is natural, the constants are explicit, and no parameters are fitted to the target quantity. Away from the critical point the main computation appears sound, and the B>Bc positivity statement relies on a positive gap B−Bc and is robust. However, several technical issues, most importantly the unproved endpoint B=Bc and an inconsistency in the quoted Lemma 3.3, prevent the theorems as stated from being fully established.

major comments (5)
  1. [§2 and §3 (Theorems 2.1–2.2, Lemma 3.3, Proposition 3.4)] The endpoint B=Bc is not proved. Lemma 3.3(i) is stated for B≤Bc but has denominators Bc−B, and the quantity z*_11=B^2C(C+1)/((Bc−B)(Bc+B−2)) is undefined at B=Bc. Proposition 3.4(i) is stated only for B<Bc, while its proof says “suppose B≤Bc”; Theorem 2.1(i) nevertheless asserts a finite D n^{2δ} term for B≤Bc. This cannot be obtained by continuity: at B=Bc one has K=((1+C)(BC)^2)/(C(BC+1)^2)=1 and E→∞, so D=f(E)+E log K−B^2C/(2(C+1)) tends to infinity. A separate treatment of the critical case, or a reformulation that excludes B=Bc, is therefore required.
  2. [§3, Lemma 3.3(ii)] The displayed second and third bounds in Lemma 3.3(ii) are mutually inconsistent with the row-sum identity. For B>Bc, if |z_{1,n+1}−BC|≤o(1) and n^{δ−1}z_{11}→C(B−Bc)>0, then n^{δ−1}z_{11}+z_{1,n+1}→C(2B−Bc), not BC, contradicting the identity (⌊n^δ⌋/n)z_{11}+z_{1,n+1}=BC used in the proof of Proposition 3.4. The later proof correctly uses z_{1,n+1}→BcC, so the lemma as quoted appears to have BC in place of BcC in the second bound.
  3. [§4, Lemma 4.1] The displayed n^{1+δ} coefficient in Lemma 4.1 is [f(BC)−BC log(1+1/C)], whereas equation (4.1) and Theorem 2.1 use [2f(BC)−BC log(1+1/C)]. If Lemma 4.1 were taken literally, the subtraction in the proof of Theorem 2.2 would leave a nonvanishing f(BC)n^{1+δ} term for B<Bc. The computation in §5 suggests the factor 2 was lost in the displayed formula; it must be corrected.
  4. [§4, Eq. (4.1)] The error in equation (4.1) is written O(n^{3δ}+n log n), while Lemma 4.1 has O(n^{3δ−1}+n log n). Taken literally, for δ>1/2 the term n^{3δ} is larger than n^{1+δ}, so the passage to the limit in Theorem 2.2 is unjustified. The exponent should be n^{3δ−1}.
  5. [§3, Proposition 3.4(ii) and Theorem 2.1(ii)] For B>Bc, Lemma 3.3(ii) gives z_{11}=C(B−Bc)n^{1−δ}+O(1), so f(z_{11})=(1−δ)log n+O(1), and the corner block contributes n^{2δ}f(z_{11})=(1−δ)n^{2δ}log n+O(n^{2δ}). This log n term is not O(n^{2δ}) for δ>1/2, so the error O(n^{2δ}+n log n) in Theorem 2.1(ii) is too small. The expansion should include O(n^{2δ}log n+n log n), or the log n term should be made explicit. This does not affect the n^{1+δ} coefficient or the limit in Theorem 2.2, but it is a mathematical error in the stated sharp asymptotics.
minor comments (3)
  1. [§2.3] The displayed formula N=⌊Cn⌋·n+2⌊BCn⌋·⌊n^δ⌋ double-counts the large margins; the correct total sum is Cn^2+BCn^{1+δ}+O(n), as used in §5.
  2. [§5] In the Taylor expansion of log(Cn^2+BCn^{1+δ}), the n^{δ−1} term should carry a factor 1/C and the n^{2δ−2} term a factor 1/C^2; as printed, the displayed expansion does not match the subsequent algebra.
  3. [§3, Proposition 3.4] The statement of Proposition 3.4 says 0≤δ<1 and part (i) says B<Bc, but the proof says “suppose B≤Bc”; the ranges should be made consistent with Theorem 2.1.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the counting asymptotics are derived from Barvinok's independent bounds and a self-contained typical-entry estimate, not from the table counts themselves.

full rationale

The derivation chain is not circular. Theorem 2.1 for log T_{n,delta}(B,C) is obtained by combining Barvinok's Theorem 3.2, which bounds log T by g(Z) up to O(n log n), with Proposition 3.4, which computes g(Z) for the typical table Z. Proposition 3.4 in turn uses only Lemma 3.3 from [DLP] to approximate the three corner entries z_{11}, z_{1,n+1}, z_{n+1,n+1} of the typical table. Lemma 3.3 is a self-citation, but it is not circular: it concerns the entries of the typical table under fixed Barvinok margins, and its stated assumptions do not include the number T_{n,delta}(B,C) or the independence heuristic G_{n,delta}(B,C). It is therefore independent evidence rather than a fit to the target quantity. Theorem 2.2 then takes the difference between Theorem 2.1 and Lemma 4.1, where Lemma 4.1 computes log G_{n,delta}(B,C) directly from the combinatorial definition (1.3) by Stirling expansions. No parameter is fitted to either log T or log G; the constant D and the auxiliary value E in Theorem 2.1 are explicit functions of B, C, and the limiting entry value z*_{11}, not fitted coefficients. The critical value B_c = 1 + sqrt(1+1/C) arises from the entry estimates in Lemma 3.3, not from the counting formula. There is a real proof gap: Theorem 2.1 and Theorem 2.2 state results at B = B_c, while Proposition 3.4(i) and the B <= B_c case of Lemma 3.3 have denominators (B_c - B) and are only established for B < B_c. There is also an apparent coefficient typo between Lemma 4.1 and line (4.1). These are correctness or consistency issues, not circularity. The central derivation remains independent of its conclusions, so no circular step is exhibited.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No new entities are introduced, and no parameters are fitted to data. The parameters B, C, and delta describe the margins themselves. The main inputs are Barvinok's theorem and the typical-table lemma from [DLP].

assumptions (4)
  • standard math Barvinok's two-sided bound: g(Z) - gamma(m+n)log N <= log T <= g(Z), where Z is the typical table (Theorem 3.2 from [B1]).
    External theorem invoked without proof; it is not specific to this paper and is standard in asymptotic enumeration.
  • domain assumption Typical-table entry asymptotics for Barvinok margins (Lemma 3.3 from [DLP]).
    Load-bearing input from the authors' own prior paper. The current paper does not prove this lemma, and the displayed bound contains (Bc-B)^(-1), so it is degenerate at B = Bc.
  • standard math Stirling approximation and Taylor expansion of f(x) are valid with controlled error for fixed B and C.
    Routine analytic estimates used in Proposition 3.4 and Section 5; they hold for fixed B < Bc and B > Bc, but not uniformly near B = Bc.
  • ad hoc to paper Lemma 3.3 extends to the critical case B = Bc.
    The paper states Theorem 2.1(i) for B <= Bc, but the proof of Proposition 3.4 explicitly treats only B < Bc, and the displayed constants have denominators (Bc-B) that vanish at Bc. No separate critical-case argument is provided.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the number of contingency tables and the independence heuristic." pith.science (2026). https://pith.science/paper/EZ2ZMBHQ

@misc{pith2026200910810,
  author       = {Pith},
  title        = {Pith review of: On the number of contingency tables and the independence heuristic},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EZ2ZMBHQ}},
  note         = {Machine review of arXiv:2009.10810}
}
abstract

We obtain sharp asymptotic estimates on the number of $n \times n$ contingency tables with two linear margins $Cn$ and $BCn$. The results imply a second order phase transition on the number of such contingency tables, with a critical value at \ts $B_{c}:=1 + \sqrt{1+1/C}$. As a consequence, for \ts $B>B_{c}$, we prove that the classical \emph{independence heuristic} leads to a large undercounting.

Figures

Figures reproduced from arXiv: 2009.10810 by the authors.

Figure 1
Figure 1. Plot of the critical correlation coefficient in uniform contingency tables with Barvi￾nok’s margins with parameters n, δ, B and C. For each 0 < δ < 1 and C > 0, there exists a second-order phase transition of the critical correlation coefficient in B at critical value Bc = 1 + p 1 + 1/C. Below Bc the rows and columns are asymptotically independent, but above Bc, they are asymptotically positively correlated. 3. Proo… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

  1. [1]

    Barvinok, Asymptotic estimates for the number of contingency tables, integer flows, and volumes of transportation polytopes, Internat.\ Math.\ Res.\ Notices 2009 (2009), 348--385

    A. Barvinok, Asymptotic estimates for the number of contingency tables, integer flows, and volumes of transportation polytopes, Internat.\ Math.\ Res.\ Notices 2009 (2009), 348--385

  2. [2]

    Barvinok, On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries, Adv.\ Math

    A. Barvinok, On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries, Adv.\ Math. 224 (2010), 316--339

  3. [3]

    Barvinok, What does a random contingency table look like?, Comb.\ Probab.\ Comp

    A. Barvinok, What does a random contingency table look like?, Comb.\ Probab.\ Comp. 19 (2010), 517--539

  4. [4]

    Barvinok and J

    A. Barvinok and J. A. Hartigan, An asymptotic formula for the number of non-negative integer matrices with prescribed row and column sums, Trans.\ AMS 364 (2012), 4323--4368

  5. [5]

    B\' e k\' e ssy, P

    A. B\' e k\' e ssy, P. B\' e k\' e ssy and J. Koml\' o s, Asymptotic enumeration of regular matrices, Studia Sci.\ Math.\ Hungar. 7 (1972), 343--353

  6. [6]

    Lower bounds for contingency tables via Lorentzian polynomials

    P. Br\"and\'en, J. Leake and I. Pak, Lower bounds for contingency tables via Lorentzian polynomials, preprint (2020), 28 pp.; arXiv:2008.05907

  7. [7]

    E. R. Canfield and B. D. McKay, Asymptotic enumeration of integer matrices with large equal row and column sums, Combinatorica 30 (2010), 655--680

  8. [8]

    J. A. De Loera, Counting and Estimating Lattice Points: Tools from Algebra, Analysis, Convexity, and Probability, Optima 81 (2009), 1--9; available at http://www.mathopt.org/Optima-Issues/optima81.pdf

Show all 21 references
  1. [9]

    J. A. De Loera, Details on experiments (counting and estimating lattice points), an appendix to DL1 , ibid., 17-22; available at http://www.mathopt.org/Optima-Issues/optima81-app.pdf

  2. [10]

    Diaconis and B

    P. Diaconis and B. Efron, Testing for independence in a two-way table: new interpretations of the chi-square statistic, Ann.\ Stat. 13 (1985), 845--913

  3. [11]

    Diaconis and A

    P. Diaconis and A. Gangolli, Rectangular arrays with fixed margins, Disc.\ Prob.\ Alg. 72 (1995), 15--41

  4. [12]

    Dittmer, H

    S. Dittmer, H. Lyu and I. Pak, Phase transition in random contingency tables with non-uniform margins, to appear in Trans.\ AMS; arXiv:1903.08743

  5. [13]

    I. J. Good, Probability and the Weighing of Evidence, Hafner, New York, 1950, 119 pp

  6. [14]

    I. J. Good, On the application of symmetric Dirichlet distributions and their mixtures to contingency tables, Annals Math.\ Stat. 34 (1963), 911--934

  7. [15]

    I. J. Good, Maximum entropy for hypothesis formulation, especially for multidimensional contingency tables, Annals.\ Stat. 4 (1976), 1159--1189

  8. [16]

    I. J. Good and J. F. Crook, The enumeration of arrays and a generalization related to contingency tables, Discrete Math. 19 (1977), 23--45

  9. [17]

    Greenhill and B

    C. Greenhill and B. D. McKay, Asymptotic enumeration of sparse nonnegative integer matrices with specified row and column sums, Adv.\ Appl.\ Math. 41 (2008), 459--481

  10. [18]

    Liebenau and N

    A. Liebenau and N. Wormald, Asymptotic enumeration of digraphs and bipartite graphs by degree sequence, preprint (2020), 25 pp.; arXiv:2006.15797

  11. [19]

    Shapiro, Bounds on the number of integer points in a polytope via concentration estimates, preprint (2010), 23 pp.; arXiv:1011.6252

    A. Shapiro, Bounds on the number of integer points in a polytope via concentration estimates, preprint (2010), 23 pp.; arXiv:1011.6252

  12. [20]

    Wormald, Asymptotic enumeration of graphs with given degree sequence, in Proc.\ ICM Rio de Janeiro, Vol

    N. Wormald, Asymptotic enumeration of graphs with given degree sequence, in Proc.\ ICM Rio de Janeiro, Vol. 3, 2018, 3229--3248

  13. [21]

    Da Wu, On limiting distribution of a certain class of random binary contingency tables, preprint (2020), 11 pp.; arXiv:2002.12559

Pith tools

Reviewed August 27, 2026 · model on record in the stance chip above.