数理解析研究所講究録 1437 巻 2005 年 122-127

122

TORIC IDEALS AND CONTINGENCY TABLESHIDEFUMI OHSUGI (RIKKYO UNIVERSITY)
TAKAYUKI HIBI (OSAKA UNIVERSITY)

ABSTRACT. Fundamental questions on semigroup rings and toric ideals arisingfrom contingency tables will be studied. In addition to discussing recent developments on such the topic, the algebraic background of contingency tables, including
the algebraic aspects of Markov chains will be also explained.

1. ALGEBRAIC BACKGROUND OF CONTINGENCY TABLES
In commutative algebra, a Markov chain can be regarded as a system of binomial
generators of the toric ideal arising from a contingency table.
An n-way contingency table is an dimensional matrix whose entries are nonnegative integers. For example, the following 2-way contingency table is given in [6,Table 2].
$n$

Example 1.1, Looking at the below 2-way contingency table T, we want to knowwhether “Eye color” and “Hair color” are correlated.

Eye$\mathrm{c}\mathrm{o}\mathrm{l}\mathrm{o}\mathrm{r}\backslash \mathrm{H}\mathrm{a}\mathrm{i}\mathrm{r}$

Brown
Blue
Hazel

Green
Total

color Black Brunette Red Blonde Total
220
68
26
7
119
215
20
94
84
17
14
93
10
15
54
64
14
16
5
29
71
127
592
286
108

In general, when an n-way contingency table is given, we are interested in factor
interaction. For the sake of simpleness, we explain the case $n=2$ here. (See [1] fordetails.) We consider the following I
contingency table :
$n$

$J$

$\mathrm{x}$$X$$\backslash$$Y$$X_{1}$$X_{2}$.
$.\cdot$$X_{I}$

Total$Y_{1}$$Y_{2}$$n_{11}$$n_{12}$$n_{22}$$n_{21}$.

$T_{0}$...

$Y_{J}$

Total$\ldots$$n_{1J}$$n_{1+}$$\ldots$$n_{2J}$$n_{2+}$.
.

.
.

$\cdot$$.\cdot$$n_{I1}$$n_{I2}$$\ldots$$n_{+1}$$n_{+2}$$\ldots$

Then we suppose the null hypothesis
and try to test it$H_{0}$.

$\cdot$$.\cdot$$n_{IJ}$$n_{I+}$$n_{+J}$$N$“there is no association between $X$ and$\mathrm{Y}$

”

123

One of the popular methods which test the association of $X$ andstatistic
test, we compute theIn the$Y$

is the$\chi^{2}$

test.

$\chi^{2}$$\chi^{2}$$\chi^{2}(T_{0})=\sum_{i=1}^{I}\sum_{j=1}^{J}\frac{(n_{ij}-\frac{n_{\mathrm{i}+}n_{+j}}{N})^{2}}{\frac{n_{i+^{n}+j}}{N}}$.

distributions withstatistic has asymptotic
is true, thenIf the hypothesisofwith the value
degrees of freedom $(I-1)$ $(J-1)$ . Thus we compare, then we conclude
distribution. If}
the right-hand side 5% point of$X$
and are independent.
is true, andthatis sparse, that is, there are a lot of cells with
However, it is known that, if
test is not good forapproximation is bad. Hence$n_{i+}n_{+j}/N<5$ , then thecontingency tables such that $N/IJ$ is small.
denoteFor such sparse contingency tables, we use the Fisher’s exact test Let
Exampleexample,inthe set of tables with the same marginal distribution as To. For$(108
2\mathrm{S}671127)$
is
rows
four
of
sum
the
such
that
matrix4
1.1,
is the set of all
and the sum of four columns is the transpose of (2202159364). We now assume
follows the multiple hypergeometric distribution. Hereis true and thatthat
the multiple hypergeometric distribution is defined by$\chi^{2}$$\chi^{2}$$H_{0}$$\chi^{2}(T_{0})$$\chi^{2}(T_{0}$$\chi^{2}$$\mathrm{a}\mathrm{o},05$$<\alpha_{0.05}$$Y$$H_{0}$$T_{0}$$\chi^{2}$$\chi^{2}$$\mathcal{F}_{T_{0}}$$\mathrm{x}$$\mathcal{F}_{T}$$H_{0}$$4$$\mathcal{F}_{T_{0}}$$P(T)= \frac{(\prod_{i=1}^{I}n_{i+}!)(\prod_{j_{-}^{-}1}^{J}n_{+j}!)}{N!\prod_{i,j}n_{ij}!}$for eachand P-value$T\in \mathcal{F}_{T_{0}}$. For the Fisher’s exact test, we compute$\chi^{2}(T)$for all$T\in \mathcal{F}_{T_{0}}$$P= \sum_{T\in F\tau_{0},\chi^{2}(T)\geq\chi^{2}(T_{0})}P(T)$is true, and $X$ and are independent.
. If $P>0.05_{7}$ then we conclude that
Unfortunately, the Fisher’s exact test also has a problem. In general, it is very
consists. For example, in Example 1.1,
difficult to enumerate all elements ofof $1_{7}225,914,276,76\mathrm{S},514$ elements. In such a case, it is almost impossible to compute

of

$Y$

$H_{0}$$T_{0}$$\mathcal{F}_{T}$$\mathcal{F}_{T_{0}}$value of exactly.
Here we are in the position to introduce Markov Chain Monte Carlo method (called
MCMC method for short). For the computation of $P$-value, we give up above exact.
calculation and make use of the Markov chain to do the sampling fromI
integer$T’$ belong toan$T-T’$
is, thenandNote that, if bothmatrix such that the sum of all entries of each rows and each columns is zero. Let
matrices which satisfies that the sum of all
denote the set of all integer I
entries of each rows and each columns is zero. Then a Markov basis is a finite subset,,, there exist
satisfying that, for any ,with $\Xi_{k}=\pm 1$ such that$P$

$T_{0}$$\mathcal{F}_{T_{0}}$$\mathrm{x}$$T$$\mathrm{x}$$\mathcal{M}_{I\mathrm{x}J}$$\{T_{1}, \ldots, T_{\ell}\}\subseteq \mathcal{M}_{I\mathrm{x}J}$$J$$\mathcal{F}_{T_{0}}$

$J$

$T$

$T’\in \mathcal{F}_{T_{0}}$$T’=T+ \sum_{k=1}^{A}\epsilon_{k}T_{i_{k}}$,$T_{i_{1}}$$\ldots$$T_{i_{A}}$124$T+ \sum_{k=1}^{a}\epsilon_{k}T_{i_{\mathrm{k}}}\in \mathcal{F}_{T_{0}}$for a1J $1\leq a\leq A$ .
If a Markov basis
the following algorithm:$\{T_{1}, \ldots, T_{\ell}\}$is given, then we can construct a Markov chain by

Metropolis-Hastings algorithm
0. Chooseat random and set $t=T$ ;1. Repeat the following:;
1.1. Select from the uniform distribution on$-1\}$ (independent of );1.2. Select from the uniform distribution on
1.3. If $t+sTi$ is a nonnegative matrix, then set $t=t+\epsilon T_{i}$ with probability$T\in \mathcal{F}_{T_{0}}$$\{T_{1}, \ldots, T_{\ell}\}$$T_{\dot{\mathrm{t}}}$$\{1,$$\epsilon$$\min\{\frac{P(t+\epsilon T_{i})}{P(t)}$$\mathrm{i}$, $1\}$ .

Let $B=\{T_{1}, \ldots, T_{\ell}\}$ be a Markov basis and let
denote the graph with thevertex set
where
and
are joined by an edge if $m-m’\in \mathcal{B}\cup-B$ .
The most important point is that, the graphmust be connected. Otherwise,
there exists an unreachable element ofin Metropolis-Hastings algorithm. The
infinite set
is regarded as the set of all integer solutions of some system of.
linear equations, and hence we can associatewith the “toric ideal”.
A configuration in
is a finite set $A=$ 1,,
which is containedin a hyperplane inwithout the origin. Let
denote the Laurant polynomial ring in variables over a field $K$ . We associate aconfiguration $A$,
with the semigroup ring $K[A]$”$=K[x_{1}$ , . . . ,
where
if a
. Let
denote thepolynomial ring in variables over $K$ . The toric idealof $A$ is the kernel of thesurjective homomorphism:
fordefined by setting. A polynomialof the form $u-v$ , where and are monomials,
is called a binomial It is known [14] that the toric ideal
is generated by thebinomials $u-v$ with $\pi(u)=\pi(v)$ .
A configuration $A$ is called unimodular if the initial ideal ofis generated bysquarefree monomials with respect to any monomial order. A configuration $A$ iscalled compressed if the initial ideal ofis generated by squarefree monomials
with respect to any reverse lexicographic order. We are interested in the following
conditions:$G_{B,T_{0}}$$m\in \mathcal{F}_{T_{0}}$$\mathcal{F}_{T_{0}}$$m’\in \mathcal{F}_{T_{0}}$$G_{B,T_{0}}$$\mathcal{F}_{T_{0}}$$\mathcal{M}_{I\mathrm{x}J}$$\mathcal{M}_{I\mathrm{x}J}$$I_{A_{r_{1}}}$$r_{n}$$\mathbb{R}^{d}$$\{$$\mathbb{R}^{d}$$\mathrm{a}_{n}\}\subseteq \mathbb{Z}^{d}$$\ldots$$K[\mathrm{t}_{7}\mathrm{t}^{-1}]=K[t_{1}, t_{1}^{-1}, \ldots, t_{d}, t_{d}^{-1}]$$d$$\subseteq \mathbb{Z}^{d}$$\mathrm{t}^{\mathrm{a}}=?$$\ldots t_{d}^{a_{d}}$$=K[\mathrm{a}_{1}, \ldots, \mathrm{a}_{n}]\subset K[\mathrm{t}, \mathrm{t}^{-1}]$$=$$(a_{1}, \ldots, a_{d})$$\pi$$1\leq \mathrm{i}\leq n$$x_{n}]$$K[\mathrm{x}]$$I_{A}$$n$$\mathrm{K}[\mathrm{x}]arrow K[A]$$f\in K[\mathrm{x}]$$\pi(x_{i})=\mathrm{t}^{\mathrm{a}_{t}}$

$u$

$v$

$I_{A}$$I_{A}$$I_{A}$(i) $A$ is unimodular;(ii) $A$ is compressed;(iii) there exists a monomial order such that the initial ideal ofis generated by squarefree monomials;
$<$

to

$<$

(iv) $K[A]$ is normal$I_{A}$

with respect125

holds and each of the converse of them is false
Then (i)[8],to[9] and [10] for further information.
readerin general We refer theis called indispensable ([15] andOn the other hand, a binomial belonging toof binomial generators of , either or $-f$[10] if, for an arbitrary systemappears in . If is indispensable, then $-f$ is indispensable. Hence the set ofindispensable binomials is of the form $F\cup-F$ , where $F\cap-F=\emptyset$ . In abuse ofterminology, such a set $F$ will .called the set of indispensable binomials of .
In the present paper, we study the configuration arising from abe the set of vectors
contingency table, where $r_{1}\geq r_{2}\geq\cdots\geq r_{n}\geq 2$ . Let$\Rightarrow(\mathrm{i}\mathrm{i})\Rightarrow(\mathrm{i}\mathrm{i}\mathrm{i})\Rightarrow(\mathrm{i}\mathrm{v})$$f$$I_{A}$$)$$f$$I_{A}$$\mathcal{F}$$f$$\mathcal{F}$$I_{A}$$r_{1}\mathrm{x}$$\cdots$$r_{2}\mathrm{x}$$\mathrm{x}$$r_{n}$$A_{r_{1}r_{2}\cdots r_{n}}$$\mathrm{e}_{i_{2}i_{3}\cdots i_{n}}^{(1)}\oplus \mathrm{e}_{i_{1}i_{3}\cdots i_{n}}^{(2)}\oplus\cdot$

where each
vector ofphism:$\oplus \mathrm{e}_{i_{1}\dot{x}_{2}\cdots i_{n-1}}^{(n)}$,is a unit coordinate
belongs to $[r_{k}]=\{1,2, \ldots, r_{k}\}$ andis the kernel of the homomor. The toric ideal$\mathrm{e}_{j_{1}j_{2}\cdots j_{n-1}}^{(k)}$$\mathrm{i}_{k}$$\mathbb{Z}^{r_{1}\cross\cdots r_{k-1}\mathrm{x}r_{k+1}\cdots \mathrm{x}r_{n}}$

$\pi$

..

$I_{A_{r_{1^{f}2}}..r_{n}}$$K[\{x_{\mathrm{z}_{1}\iota_{2}\cdots i_{n}} ; \mathrm{i}_{k}\in[r_{k}]\}]arrow K[\{t_{i_{1}\cdots i_{k-1}i_{k+1}\cdots i_{n}}^{(k)} ; k\in[n], \mathrm{i}_{k}\in[r_{k}]\}]$

defined by$\pi(x_{i_{1}i_{2}\cdots \mathrm{i}_{n}})=t_{i_{2}i_{3}\cdots i_{n}}^{(1)}t_{i_{1}i_{3}\cdots i_{n}}^{(2)}\cdots$$t_{i_{1}i_{2}\cdots i_{n-1}}^{(n)}$.

Proposition 1.2. Work with the same notation as above. Thena Markov basis for an arbitrary if and only if the toric ideal.
withby the binomials$T$isis generated$B\subseteq \mathcal{M}_{r_{1}\mathrm{X}\cdots \mathrm{X}r_{n}}$$I_{A_{\tau_{1}}}r_{\hslash}$$\beta^{+}-\beta^{-}\in B$$\mathrm{x}^{\beta^{+}}-\mathrm{x}^{\beta^{-}}\in K[\mathrm{x}]$2. RECENT DEVELOPMENTS
In the present section, we discuss the recent developments ([12]) on semigrouprings and toric ideals arising from contingency tables. First, using the formula in.
[13, p. 162], we can compute the dimension of$K[A_{r_{1}},\ldots,r_{n}]$Proposition 2.1. The dimension of$K[A_{r_{1},\ldots,r_{n}}]$is equal to$+ \sum_{k=1}^{n-1}(-1)^{n-k-1}\sum_{i_{1}<\cdots<i_{k}}r_{i_{1}}\cdots r_{i_{k}}$$(-\mathrm{l})^{}$

Indispensable binomials have been completely determined for the following threeclasses of. .
(1) $n=2$ (unimodular, Segre product of polynomial rings),(Lawrence lifting)(2) $n\geq 3$ and(computed by Aoki-Takemura [2], [3]).
,(3)
In particular, for all of (1) (3), a minimal set of binomial generators 1s umque.
$I_{A,r12}$$r_{n}$$r_{1}\mathrm{x}$$r_{1}\mathrm{x}$$3\mathrm{x}$$3$$r_{1}\mathrm{x}$$r_{2}\mathrm{x}$$4\mathrm{x}$$2\mathrm{x}\cdots \mathrm{x}$$3,4\mathrm{x}$$4\mathrm{x}$

$2$

$4$

–

Conjecture 2.2. The toric ideal of the configuration
dispensable binomials.

$A_{\tau_{1}r_{2}\cdots r_{n}}$is generated by in-

On the other hand, Boffi-Rossi [5] computed a lexicographic Grobner basis of thewhose initial ideal is generated by squarefree monomials. We now
toric ideal.
discuss the following two properties of the toric ideal of the configuration$I_{A_{r_{1^{33}}}}$$A_{333}$

128

coincides with the set of indisTheorem 2.3. No reduced Grobner basis of.
pensable binomials ( the minimal set of binomial generators) of$I_{A_{333}}$$I_{A_{333}}$$=$

Theorem 2.4. The configuration A333 is compressed.
for which there exists a monomial
We characterize the configurations
order $<such$ that the reduced Gr\"obner basis of... with respect to is the.
set of indispensable binomials of$A_{\tau_{1}r_{2}\cdots r_{n}}$$<$$I_{A_{r_{1^{r}2}}}$$r_{n}$$I_{A_{r_{1^{r}2}}}r_{n}$:Theorem 2.5. Let $n\leq 3$ . Then the following conditions are equivalent(i) either $n=2$ or $r_{3}=2$ ;(ii)
is unimodular ;such that the reduced Gr\"obner basis of(iii) there exists a monomial order;with respect
the set of indispensable binomials of
Gr\"obner
basis
such that the reduced(iv) there exists a monomial orderof.
a minimal set of binomial generators ofwith respect$forA_{r_{1}r_{2}\cdots r_{n}}$$A_{\tau_{1}r_{2}\cdots r_{n}}$$<$$to<\mathrm{i}s$$I_{A\tau_{1}r_{2}\cdot\cdot\tau_{n}}$$I_{Ar_{1^{r}2}}\mathit{7}\eta$$<$$to<\mathrm{i}s$$I_{A_{r_{1^{f}2}}}r_{n}$$I_{A_{r_{1}r_{2}}}r_{n}$We study normality of semigroup rings arising from contingency tables. We clasexcept for $K$ [A553], $K[A_{543}]$ and $K[A_{443}]$ .
sify all normal semigroup rings$K[A_{r_{1}r_{2}\cdots r_{n}}]$Theorem 2.6. Work with the same notation as above. Then toe have$r_{1}$

5$\mathrm{x}$$\mathrm{x}$

$5$

or

$r_{2}$$\mathrm{x}$$3$$r_{1}$$\cross r_{2}$$r_{1}$$\mathrm{x}$or 5$\mathrm{x}$

$3$

$2$

$\mathrm{x}$$\mathrm{x}$$\mathrm{x}\cdots$$\mathrm{x}$

$2$

$3$

$4\cross 3$

or 4$\mathrm{x}$$4$$\mathrm{x}$$3$otherwise, . ,$i$$n\geq 4$

andunimodular
normalUNKNOWN if normal or not$e.$

not normaf$r_{3}\geq 3$$n=3$ and $r_{3}\geq 4$$n=3$ , $r_{3}=3$ , $r_{1}\geq 6$ and $r_{2}\geq 4$

is given in [3], it seems
Even though a unique minimal set of generators of$K[A_{443}]$$K[A_{543}]$
to be difficult to know if
andare normal. On the other hand, we
do not know if
withare compressed.
$I_{A_{r_{1}43}}$$A_{r_{1}33}$$r_{1}\geq 4$

Question 2.7, Are $K[A_{553}]_{f}K[A_{543}]$ and $K[A_{443}]$ normal?

Question 2.8. Is$A_{r_{1}33}$

compressed for$r_{1}\geq 4$?

REFERENCES[1] A. Agresti, “Categorical Data Analysis,” John Wiley & Sons, 2002.
[2] S. Aoki and A. Takemura, Minimal basis for connected Markov chain over 3 x3x K contingency
tables with fixed two dimensional marginals, Australian and New Zealand Journal of Statistics,
45 (2003), 229 249.
[3] S. Aoki and A. Takemura, The list of indispensable moves of the unique minimal Markov basis
for 3 x4x K and 4 x 4x 4 contingency tables with fixed two-dimensional marginals, METR
Technical Report, 03-38.
[4] G. Boffi and F. Rossi, Grobner bases related to 3-dimensional transportation problems,
Quaderni matematici Univ. Trieste, II, 482 (2000)-

127[5] G. Boffi and F. Rossi, A stability property of certain Gr\"obner bases, preprint, Feb. 2003.
[6] P. Diaconis and B. Sturmfels, Algebraic algorithms for sampling from conditional distributions,Annals of Statistics 26 (1998), 363- 397.
[7] H. Ohsugi, J. Herzog and T. Hibi, Combinatorial pure subrings, Osaka J. Math., 37 (2000),745-757.

[8] H. Ohsugi and T. Hibi, A normal $(0,1)$ -polytope none of whose regular triangulations is
unimodular, Discrete Compt. Geom. 21 (1999), 201 204.
[9] H. Ohsugi and T. Hibi, Compressed polytopes, initial ideals and complete multipartite graphs,
Illinois J. Math., 44 (2000), 391 406.
[10] H. Ohsugi and T. Hibi, Convex polytopes all of whose reverse lexicographic initial ideals are
squarefree, Proc. Amer. Math. Soc, 129 (2001), Num ber 9, 2541 2546.
[11] H. Ohsugi and T. Hibi, Indispensable binomials of finite graphs, J. Algebra and its applications,
to appear.
[12] H. Ohsugi and T. Hibi, Toric ideals arising from contingency tables, preprint, 2004.
[13] F. Santos and B. Sturmfels, Higher Lawrence conflguraions, J. Combinatorial Theory, Ser. A,
103 (2003), 151 164.
[14] B. Sturemfels, “Grobner bases and convex polytopes,” Amer. Math. Soc, Providence, RI,
–

-

–

–

1995.

[15] A. Takemura and S. Aoki, Some characterizations of minimal Markov basis for sampling fromdiscrete conditional distributions, Annals of the Institute of Statistical Mathematics, (2003),
to appear.

Hidefumi Ohsugi
Department of Mathematics
Rikkyo University
Toshima, Tokyo 171-8501, Japan$\mathrm{E}$-mail:ohsugi@rkmath.rikkyo.ac,jP

Takayuki Hibi
Department of Pure and Applied Mathematics
Graduate School of Information Science and Technology
Osaka University
Toyonaka, Osaka 560-0043, Japan-mail:hibi@math. sci.osaka-u. ac.jp$\mathrm{E}$