Connecting Tables with Allowing Negative Cell Counts

Conducting the goodness of fit test for discrete exponential family models with sparse contingency tables is a challenging task since we cannot use asymptotic methods, especially when we have large tables. To do so, one applies sampling procedures, such as Markov Chain Monte Carlo (MCMC) procedures, from the state space [BC89, CDHL05, DE85, GT92].

Even though Besag and Clifford argued that irreducibility of a Markov chain is not essential in [BC89], that view is not conventional since it is very difficult to understand a chain over sparse tables in high dimensions. To understand the irreducibility of a Markov chain over the set of all possible contingency tables with given constraints, Diaconis and Sturmfels introduced a notion of a Markov basis [DS98]. Diaconis and Sturmfels showed that a Markov basis, a generating set of a toric ideal associated with the design matrix for a discrete exponential family model, is the set of moves which guarantee to connect all tables for the given model [DS98]. The most significant benefit in computing a Markov basis for a discrete exponential family model is that if we have a Markov basis for the model, we do not have to re-compute it since moves in a Markov basis connect all tables for any observed tables under the model. However, it is computationally expensive to compute a Markov basis in terms of the dimension of a table. In fact, [DO05] showed that the number of elements in a Markov basis for the no-three-way interaction model can be arbitrarily large. This means that it is not feasible to compute a Markov basis for large tables under the no-three-way interaction model. Then, Hara et al. conducted study of employing MCMC with a lattice basis which is much easier to compute than a Markov basis [HAT11]. However, with a lattice basis, we cannot guarantee that a chain is connected so that the estimated distribution of statistics might be biased.

To try to circumvent the difficulty of computing a Markov basis which may be large, [CDDH05, BB00] studied computing a smaller set of moves, such as a lattice basis, by allowing cell counts of the contingency table to be negative one ($-1$). Motivated by their work, in this paper, we consider cases when we can connect a Markov chain if we allow cell counts to be $-1$ including some cases on the no-three-way interaction model with the basic moves.

A basic move of a $2\times 2\times 2$ minor for the no-three-way interaction model is a $I\times J\times K$ contingency table with $\{0,\pm 1\}$ entries such that for distinct $i,i^{\prime}\in\{1,\ldots,I\}$, distinct $j,j^{\prime}\in\{1,\ldots,J\}$, and distinct $k,k^{\prime}\in\{1,\ldots,K\}$,

and all zeros otherwise. In 2018, Lee showed that if $I=3$, $J=3$, and $K\geq 2$, then basic moves connect all tables if we allow cell counts $X_{ijk}$ to be $-1$ when we run a Markov chain. For $I>3$, $J>3$, and $K\geq 2$, it is still an open problem that basic moves connect all tables if we allow cell counts $X_{ijk}$ to be $-1$ when we run a Markov chain.

The contribution of this paper is the following:

• •

  We show that under a fixed model, if a set of moves $M$ connects all tables in a sample space, the set of all tables with fixed margins, which contains a table with all cell counts equal to $1$, then $M$ connects all tables in a sample space with any fixed margins if we allow cell counts to be $-1$.

• •

  We show that under the no-three-way interaction model, the set of basic moves of $2\times 2\times 2$ minors connects tables in a sample space with a fixed margins if we allow cell counts to be $-1$ in the case of $I=2$. Then we also show that the set of basic moves connects all tables in the sample space with any fixed margins if we allow cell counts to be $-1$ for $I=3$ and $J=4$.

• •

  We apply our result to the Navy personnel dataset obtained from U.S. NAVY DEMOGRAPHIC DATA, 2022.

This paper is organized as follows: In Section 2, we set up basics for our results in this paper. Then, in Section 3, we show some theoretical conditions allowing us to connect all tables in the given fiber with a subset of a Markov basis if we allow cell counts to be $-1$. Additionally, we show cases of the three way contingency tables under the no-three-way interaction model that we can connect tables in the fiber by a set of all basic moves while allowing cell counts to be $-1$. Then we apply our hybrid scheme, that is, a Markov chain with a set of basic moves by allowing cell counts to be negative one combined with SA to an empirical data on U.S. Navy (USN) personnel in Section 5. We end with discussion and open problems.

In this section we set up some basic notation and definitions for our results in this paper.

Let $A\in\mathbb{Z}^{m\times d}$ and $b\in\mathbb{Z}^{m}$. We define $b-$fiber of $A$ is

For a finite $\mathcal{M}\subset\ker A\cap\mathbb{Z}^{n}$, we define the fiber graph $\mathcal{G}(\mathcal{F}_{A,b},\mathcal{M})$ of $A$ as graph having the $b$-fiber as its vertex set and the set

as its edge set.

In this paper, we focus on assessing interaction between three discrete random variables $X,\,Y,\,Z$ with finite levels, where $X\in\{1,\ldots,I\}$, $Y\in\{1,\ldots,J\}$, and $Z\in\{1,\ldots,K\}$ for $I,\,J,\,K\in\mathbb{N}$. In order to conduct statistical analysis on such interactions, a commonly used model is called a log linear model. A log linear model is a generalized linear model and it forms a class of discrete exponential family.

Applying the notation of the log-linear model notation to the three-way contingency table, we have the parameterization $n_{ijk}\sim Pois(\mu_{ijk})$, the Poisson distribution with the parameter $\mu_{ijk}$, such that:

If we assume there is no interaction between three categorical variables, namely,

for all $i=1,\ldots,I$, $j=1,\ldots,J$, and $k=1,\ldots,K$, then we call this model the no-three-way interaction model.

In this section, we show the main result for the connectivity of a Markov chain if we allow cell counts to drop to $-1$.

Note that we cannot apply Proposition 7 to the set of all basic moves since the set of basic moves does not connect tables in the fiber which contains a table with all ones. As an example, we consider the case of $I=J=K=3$. Suppose we have a $3\times 3\times 3$ table such that

Then note that the set of basic moves does not connect this table to any other tables with the same margins. However, we can show that if we allow cell counts to be $-1$, then we can connect this table to other tables in the fiber $\mathcal{F}_{A,b}$ [Lee06]. Therefore, in the next section, we consider some cases which we can connect three-way contingency tables under the no-three-way interaction model with the set of basic moves by allowing cell counts to be $-1$.

In this section, we consider three-way $I\times J\times K$ tables under the no-three-way interaction model with the set of basic moves.

Note that, by Lemma 12.2 in [Stu96], for some positive integer $t$, if we allow $X_{ijk}\geq-t$, then all moves in $M$ connect all tables in $\mathcal{F}_{A,b}$ for a three way $I\times J\times K$ contingency table $X_{ijk}$ under the no-three way interaction model.

Dinwoodie et al. discussed connecting tables via allowing cell counts to be negative one and they discussed a condition for a set of moves so that it connects tables in the fiber by allowing cell counts to be negative one (Proposition 0.2.1 [CDY09a]). However, for the no-three-way interaction model, the ideal generated by binomials with exponents for the positive part and negative part of all possible basic moves for $3\times 3\times 4$ is not radical. Therefore, we cannot use Proposition 0.2.1 for the connectivity of tables with allowing cell counts to be $-1$. However, using a known Markov basis for $3\times 3\times K$, for $K\geq 2$, by Aoki and Takemura in [AT03a], we can show that basic moves of all $2\times 2\times 2$ minors can connect tables for $3\times 3\times 4$ case.

In general we do not know that a set of basic moves of $2\times 2\times 2$ minors connects all tables in $\mathcal{F}_{A,b}$ under the no-three-way interaction model for any $b\in\mathbb{Z}^{m}_{\geq 0}$ if we allow cell counts to be $-1$. Thus, it is still an open problem to prove that moves of $2\times 2\times 2$ minors connects all $I\times J\times K$ tables in the fiber for $I>3,\,J>3,\,K>3$ under the no-three-way interaction model if we allow cell counts to be negative one.

We now examine the performance of the algorithms using an empirical data set from [NAV22]. The data set consists of the USN officer and enlisted population as of January 20, 2021. The data is organized into a three way contingency table stratified by race, rank, and gender. The rank category consists of 19 levels. The values are displayed in Tables 1, 2, 3, and 4. By Theorem 13, we know that the set of all basic moves connects tables in the fiber if we allow cell counts to be $-1$. Thus we apply our MCMC scheme to this contingency table.

Of note, the table consists of a wide range of cell counts. In general, cell counts decrease as rank increases which is expected as there are fewer billets for higher ranks thus reflecting the USN’s “up or out” promotion structure. Further, we note that there are considerably fewer females than males across all ranks and races. For this reason, several sub-categories were combined to ensure that the chain runs smoothly.

In this computation, we consider the following hypotheses:

In this study, as the first experiment, we only look at ranks which include Admirals, officers (O-1 through O-6) and W-4, W-3, and W-2. The race category consists of six levels and gender is binary. This results in a $10\times 6\times 2$ contingency table. The $\chi^{2}$ test statistics of the observed table is $90.23$. Therefore an estimate p-value using the $\chi^{2}$ distribution with $(10-1)\cdot(6-1)\cdot(2-1)$ is $0.00002$.

For the second experiment, we look at all 19 ranks. The race category consists of six levels and gender is binary. This results in a $19\times 6\times 2$ contingency table. The $\chi^{2}$ test statistics of the observed table is $2775.15$. Therefore an estimate p-value using the $\chi^{2}$ distribution with $(19-1)\cdot(6-1)\cdot(2-1)$ is very close to $0$.

In this paper we conduct MCMC with basic moves by allowing cell counts to be negative one. Experimental results imply that for the case of the three-way $I\times J\times K$ tables under the no-three-way interaction model, our MCMC algorithm provides an estimated distribution of $\chi^{2}$ statistics closer to the asymptotic distribution, $\chi^{2}$ distribution with the degrees of freedom $(I-1)(J-1)(K-1)$.

RY and DB are partially funded by NSF Division of Mathematical Sciences: Statistics Program DMS 1916037.