# Given the marginals of a contingency table, what is the maximum observable value for the $\chi^2$ Pearson statistic?

I know that given a $$R\times C$$ contingency table observed on $$N$$ subjects, the maximum value of $$\chi^2$$ statistics is $$N\cdot [\min(R,C)-1]$$. But, this is independent of given margins (namely, row totals and column totals. Is there a closed formula or an easy way for computing such a constrained maximum? For example: in a $$2\times 2$$ contingency table with margins $$[50, 50]$$ and $$[10,90]$$, it is easy to observe that there the table $$\begin{array}{*{20}{c}} 0&{50}\\ 10&{40} \end{array}$$ is the only one having the highest $$\chi^2$$ ($$11.11$$ and not $$100$$) among all the tables with the same marginals. Are there papers or algorithms for searching it in a feasible time also for a generic $$R\times C$$ table given its marginals?

$$R\times C$$ table is a rectangular contingency table where $$R$$ is a given number of rows and $$C$$ a given number of columns, each one greater than 1 and not necessarily the same. The question is: if I know only the marginal frequency distributions (namely, the row and the column totals), what is the maximum value of the $$\chi^2$$ statistics that can be obtained? This value can be obtained via the solution of an optimization problem algebraically or there exist some algorithms? Example with a $$3\times4$$ table: $$\begin{array}{*{20}{c}} {{n_{11}}}&{{n_{12}}}&{{n_{13}}}&{{n_{14}}}&{20}\\ {{n_{21}}}&{{n_{22}}}&{{n_{23}}}&{{n_{24}}}&{100}\\ {{n_{31}}}&{{n_{32}}}&{{n_{33}}}&{{n_{34}}}&{380}\\ {50}&{80}&{170}&{200}&{400} \end{array}$$ what are the $$n_{ij}$$ values that allow for the maximum $$\chi^2$$ Pearson statistics?

• 1. what do you mean by a "generic $R\times C$ table"? Do you mean a random one or something else? 2. Your two questions seem to be quite distinct and should probably be posted separately. Commented Jan 21, 2019 at 3:26
• Not a random table, but image I know only marginal count (or frequency) distribution. For example, I know etnicity count distribution of a municipality and the professional status one. My question is before to compute or observe the joint distribution, can I predict what is the maximum observable $\chi^2$ statistics if I know the marginal distribution only? Commented Jan 21, 2019 at 16:12
• Your example has a zero count but you have the statement "each one greater than 1". Is there a conflict there or am I misreading that?
– JimB
Commented Jan 21, 2019 at 17:52
• I think I see now. You have each row and column total being at least one rather than all individual cells being at least one.
– JimB
Commented Jan 23, 2019 at 3:55
• Your example makes it clear that for any optimum in the general case, every $2\times 2$ subtable will contain at least one zero. This might be both a useful simplification as well as of practical value in generating approximate answers.
– whuber
Commented Jan 23, 2019 at 14:53

I think a general formula for anything but a 2x2 table would be messy at best.

A brute force method would be for a specific set of marginals to generate a million or more tables with those marginals and use the maximum of those simulations as a lower bound for the maximum chi-square value. Here is an R implementation of that:

# Marginals
rowTotals = c(20,100,380)
colTotals = c(50,80,170,200)

nsim = 1000000
chi2max = 0
nrows = length(rowTotals)
ncols = length(colTotals)
observed = matrix(rep(NA,nrows*ncols), nrow=nrows, ncol=ncols, byrow=TRUE)
p = rep(1,ncols)/ncols
for (i in 1:nsim) {
for (j in 1:(nrows-1)) {
observed[j,] = rmultinom(1,rowTotals[j],p)
}
observed[nrows,] = colTotals -
colSums(matrix(observed[c(1:(nrows-1)),], nrow=nrows-1, byrow=TRUE))
if (min(observed[nrows,]) >= 0) {
chi2 = chisq.test(observed,correct=FALSE)$statistic if (chi2 > chi2max) { maxCounts = observed chi2max = chi2 } } } chi2max # X-squared # 629.4737 maxCounts # [,1] [,2] [,3] [,4] #[1,] 20 0 0 0 #[2,] 20 80 0 0 #[3,] 10 0 170 200  (Note that I don't use "<-" for setting values I guess because I'm lazy and stubborn.) I suspect that there will be a substantial number of zeros and rows or columns with a single number associated with the maximum chisquared value. Using Mathematica (because it does algebra way better than I can) the maximum chisquare value given row and column marginals $$r_1$$, $$r_2$$, $$c_1$$, and $$c_2$$ (with $$n=r_1+r_2=c_1+c_2$$) is $$\begin{array}{cc} \{ & \begin{array}{cc} \frac{n c_1 r_1}{c_2 r_2} & c_12 r_1)\land (2 c_1>n\lor n\leq 2 r_1) \\ \frac{n c_1 r_2}{r_1 c_2} & n>2 r_1\land c_1\leq r_1 \\ \frac{n r_1 c_2}{c_1 r_2} & (2 c_1=n\lor (c_1>r_1\land 2 c_12 r_1 \\ \end{array} \\ \end{array}$$ • Thanks for your answer, I understand that a brute-force method could solve the issue, but I wonder if there exists some less expensive algorithm (I suppose that if$R$and$C$grows the algorithm slows, too) or some closed algebraic form for computing such a value. My question is motivated by the fact that, with huge datasets, it is easy to count frequencies for each variable, but one would investigate only those "correlations" that could be potentially high. Commented Jan 23, 2019 at 11:42 • One consequence of brute force methods is that it sometimes spurs one on to be much, much more efficient in the search for an optimal (in this case "maximum") value. I also have to wonder if$R x C$tables might have the maximum value in the form of$n$times a ratio of column and row totals (as it is with a 2 x 2 table). – JimB Commented Jan 23, 2019 at 17:24 • The algorithm mentioned by @antonioirpino in his answer is much more effective than brute force, for two-way tables of any dimension. Now, if you still want to use some brute force algorithm, you might speed it up by initially dividing all marginals by their greatest common divisor (and eventually multiplying the resulting$\chi^2\$ statistic by the gcd). However, if you do that, you'll find out that the algorithm you suggest in your answer crashes in certain situations. Try it with rowTotals = c(2,10,38) and colTotals = c(5,8,17,20) and see what happens. Commented Sep 6, 2023 at 10:35

I found a closed formula for $$2\times 2$$ table, $$Max(\chi^2)=n_{..}\frac{p}{(1-p)}\frac{\left[1-(p+\delta)\right]}{(p+\delta)}\leq n_{..}$$ where $$p$$ and $$1-p$$ are the marginal relative frequencies of the first variable ($$p<.5$$) and $$p+\delta$$ and $$1-p-\delta$$ are the marginal relative frequencies of the second variable ($$0\leq\delta<0.5$$, $$p+\delta\leq 0.5\leq 1-p-\delta$$), and $$n_{..}$$ is the sum of joint frequencies. Equality holds only if $$\delta=0$$.

I wrote an algorithm that does not require a brute force search, but I would prove that the algorithm result if an effective maximum. The algorithm in R is more or less this

    max_possible_chi_2=function(rows,cols){
if (sum(rows)!=sum(cols)){
stop("sum of rows must be equal to the sum of cols")
}
#define frechet bounds
M1=matrix(rows,length(rows),length(cols))
M2=matrix(cols,length(rows),length(cols), byrow = T)
RESU=M1*0
R1=rows
C1=cols
while ((sum(R1)+sum(C1))>1e-16){
TM1=matrix(R1,length(rows),length(cols))
TM2=matrix(C1,length(rows),length(cols), byrow = T)
FB=pmin(TM1,TM2)
els=FB^2/(M1*M2)
WH=which(els == max(els), arr.ind = TRUE)[1,]
RESU[WH[1],WH[2]]=FB[WH[1],WH[2]]
R1[WH[1]]=R1[WH[1]]-FB[WH[1],WH[2]]
C1[WH[2]]=C1[WH[2]]-FB[WH[1],WH[2]]
}
chi=sum(rows)*(sum(RESU^2/(M1*M2))-1)
v=sqrt(chi/(sum(rows)*(min(length(rows),length(cols))-1)))
print(chi)
print(v)
return(RESU)
}