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 →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
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.
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
- 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.
Formalized claims in Lean
-
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
/-- @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 -/ def central_claim : Prop :=
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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)
- [§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.
- [§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.
- [§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, 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}.
- [§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)
- [§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.
- [§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, 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
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
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]).
- domain assumption Typical-table entry asymptotics for Barvinok margins (Lemma 3.3 from [DLP]).
- standard math Stirling approximation and Taylor expansion of f(x) are valid with controlled error for fixed B and C.
- ad hoc to paper Lemma 3.3 extends to the critical case B = Bc.
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
Reference graph
Works this paper leans on
-
[1]
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
work page 2009
-
[2]
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
work page 2010
-
[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
work page 2010
-
[4]
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
work page 2012
-
[5]
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
work page 1972
-
[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
work page Pith review arXiv 2020
-
[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
work page 2010
-
[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
work page 2009
Show all 21 references
-
[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
-
[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
1985
-
[11]
Diaconis and A
P. Diaconis and A. Gangolli, Rectangular arrays with fixed margins, Disc.\ Prob.\ Alg. 72 (1995), 15--41
1995
-
[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
1903 arXiv
-
[13]
I. J. Good, Probability and the Weighing of Evidence, Hafner, New York, 1950, 119 pp
1950
-
[14]
I. J. Good, On the application of symmetric Dirichlet distributions and their mixtures to contingency tables, Annals Math.\ Stat. 34 (1963), 911--934
1963
-
[15]
I. J. Good, Maximum entropy for hypothesis formulation, especially for multidimensional contingency tables, Annals.\ Stat. 4 (1976), 1159--1189
1976
-
[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
1977
-
[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
2008
-
[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
2020 arXiv
-
[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
2010 arXiv
-
[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
2018
-
[21]
Da Wu, On limiting distribution of a certain class of random binary contingency tables, preprint (2020), 11 pp.; arXiv:2002.12559
2020 arXiv
Reviewed August 27, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.