3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Glen_b Jan 21 at 3:26
  • 1
    $\begingroup$ 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? $\endgroup$ – antonio irpino Jan 21 at 16:12
  • $\begingroup$ 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? $\endgroup$ – JimB Jan 21 at 17:52
  • $\begingroup$ 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. $\endgroup$ – JimB Jan 23 at 3:55
  • $\begingroup$ 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. $\endgroup$ – whuber Jan 23 at 14:53
1
$\begingroup$

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_1<n\land (r_1<n\lor n>2 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_1<n))\land n>2 r_1 \\ \end{array} \\ \end{array}$$

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – antonio irpino Jan 23 at 11:42
  • $\begingroup$ 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). $\endgroup$ – JimB Jan 23 at 17:24
0
$\begingroup$

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)
    }
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.