1 Introduction
Log-linear models are the general way of studying contingency tables. To measure how well a log-linear model fits to the data in a contingency table, we use asymp- totic tests based on large sample approximations such as chi-squared approximations.
覧Springer
For large and sparse contingency tables, exact tests evaluating statistical significance using p -values are preferable to asymptotic tests; however, the computation of an exact p -value for testing a log-linear model may be infeasible due to the enumeration of all contingency tables with fixed marginals specified by the log-linear model. To study such tables, Markov chain Monte Carlo (MCMC) is a popular technique for generating contingency tables with fixed marginals. Diaconis and Sturmfels ( 1998 ) suggested the computation of a Markov basis by finding Gröbner bases, thus allowing the construc- tion of a Markov chain that connects all contingency tables with fixed marginals. Graphical models are statistical models for interpreting conditional independence relationships among a number of variables and are a subclass of the general class of hierarchical log-linear models, as described in Lauritzen ( 1996 ). Decomposable graphical models, a subclass of graphical models, are important in applied graphical modeling, because numerous theoretical and computational aspects are more use- ful and tractable with decomposable graphical models than with general graphical models. Moreover, an attractive feature of decomposable models is their ease of inter- pretation. Dobra ( 2003 ) gave explicit formulae of Markov bases for decomposable log-linear models and described the algorithm for generating Markov bases. Geiger et al. ( 2006 ) analyzed the algebraic properties of decomposable graphical models and provided various characterizations of the models. Hara et al. ( 2010 ) clarified struc- tures of Markov bases for decomposable models and gave a complete description of minimal and minimal invariant Markov bases for the models. In this paper, we give a new explicit formula that identifies a Markov basis on the junction tree for a decomposable log-linear model and show MCMC using the Markov basis for computing the p -value for a decomposable log-linear model. In Sect. 2 , we define decomposable log-linear models and the junction trees constructed by the graphs of decomposable log-linear models. In Sect. 3 , we give a description of a Markov basis characterized by the global Markov properties of Lauritzen ( 1996 ) on the graph of a decomposable log-linear model. In Sect. 4 , we show how to employ the Markov basis for generating contingency tables of a Markov chain; then we provide an algorithm for drawing contingency tables by using the Markov basis. We also compare the proposed and Dobra's algorithms for generating tables. Section 5 gives MCMC using the Markov basis for generating random tables. The estimates of exact p -values can be calculated from the random tables. In Sect. 6, we present numerical experiments for examining the performance of the proposed MCMC using real datasets and simulation studies. Section 7 gives some concluding remarks.
2 Decomposable log-linear models and junction trees
Let X = (X 1 , . . . , X K ) be a vector of discrete random variables and V = {1, . . . , K } denote the index set associated with X 1 , . . . , X K . Each variable X k takes a finite number of values x k ∈ I k = {1, 2, . . . , I k } for k ∈ V . Let n(x) be the entry for cell x ∈ I = Π k ∈ V I k . Then a table of counts n = { n(x)} x ∈ T is a K -dimensional array of non-negative integer numbers. For a subset C ⊂ V , we write X C for {X k} k ∈ C and IC = Π k ∈ C I k . Then the marginal n C of n is the contingency table with marginal cells xc ∈ Ic and entries given by
where ( xc , x ) ∈ I . Consider a hierarchical log-linear model specified by a generating class C = {Ci}1<!<M which is a class of variable sets in minimal sufficient statistics. The log- linear model is graphical if C is the set of cliques of an independence graph. More- over, the log-linear model is decomposable if the independence graph induced by C is a hypergraph G = (V, C) , where V is the set of vertices and C is the set of cliques, i.e., the generating class. Detail discussions of decomposable log-linear models can be found in Lauritzen ( 1996 ). It is known that all the cliques in C of G can be ordered to satisfy the running intersection property : For all 1 < j ≤ M , there exists an i < j such that
By employing the maximum cardinality search algorithm described in Hájek et al. ( 1992 ), the ordered clique set C can be obtained. When the cliques in C have the running intersection property, it is possible to construct a junction tree T (C) with C as its node set, see Jensen and Jensen ( 1994 ). We define a clique separator S i for C i  ∈ C as for i  = 2, . . . , M , and denote the set of separators by S  = { S i } 2<i<M . Then a separator S ∈ S is associated with the edge between a pair of adjacent cliques in T ( C ). For T ( C ), the following lemma is immediately obtained: Lemma 1  For any two cliques C i , C j  (i  <  j) in C  of T (C), there exists a unique path from C i to C j that is the sequence C i = C j , C j , . . . , C j − 1 , C j = C j of distinct cliques. We can then characterize the conditional independence relationship between any two cliques C i , C j on T (C) as follows: Theorem 1  Assume that there exists a path from C i to C j (i < j) such that C i = C'o, C'i, . . . , C'i_1, C'i = Cj. We set Aj, Aj and B as
where S ′ i = C i ∩ C ′ 1 ∈ S. Then X A is conditionally independent of X A , given X B , i.e., XAj L XAj | XB Proof The global Markov property defined by Lauritzen ( 1996 ) leads to the above口conditional independence relationship. Theorem 1 plays an important role for generating Markov bases in Sect. 3 .
👍 Springer
Example 2.1 Let n be a seven-way contingency table of a vector of discrete random variables X = (X 1 , . . . , X 7 ) and V = {1, . . . , 7} be the index set of X . Consider the decomposable log-linear model with generating class C that is the set of ordered cliques such that C 1 = {1, 2, 4}, C 2 = {2, 4, 5}, C 3 = {2, 3, 5}, C 4 = {4, 5, 6} and C 5 = {5, 6, 7}. The marginal tables n C 1 , . . . , n C 5 are also the minimal sufficient statistics for the log-linear model. For the hypergraph G = (V, E) of the log-linear model, the separators in S are given by S 2 = {2, 4}, S 3 = {2, 5}, S 4 = {4, 5} and S 5 = {5, 6}. The junction tree T (C) defined by C is illustrated in Fig. 1 . For example, the path from C 3 to C 5 in T ( C ) is the sequence C 3 , C 2 , C 4 , C 5 . Then we have A 3 = C 3 \ S 3 = {3}, A 5 = C 5 \ S 5 = {7} and B = V\(A2 U A5) = {1,2,4,5,6}, so that we can obtain XA3  L XA<|XB, or X3 L X7|{X1, X2, X4, X5, X6}.
3 Markov bases for decomposable models
Let Γ ( C ) denote the set of all K -way contingency tables of non-negative integer entries with fixed marginals n C 1 , . . . , n C M . To generate a table n ′ ∈ Γ(C) from an original table n ∈ Γ(C) , we can use the data swapping technique of Dalenius and Reiss ( 1982 ) such that cell entries are moved from one cell to the other while the fixed marginals are left unchanged. Since some of the cell entries are increased and other cells are decreased in the swapping, a data swap associated with n is an array f = {f(x)}xeI with integer entries f ( x ) ∈ {0, ±1, ±2, . . .}. Thus n ′ created by adding f to n has to be consistent with fixed marginals. Definition 1 A move f for C is a data swap that preserves fixed marginals nC 1 , . . . , n C M specified by C . Then we have n + f ∈ Γ(C) if and only if n(x) + f(x) ≥ 0 for all x ∈ I . From the marginal constraints associated with clique C ∈ C , we have
The move with entries of zero everywhere except four cells that contain two entries of 1 and two entries of −1 is called a primitive move . Definition 2  A Markov basis M is a finite collection of moves that preserve fixed marginals n C 1 , . . . , n C M . For any two tables n , n ′ ∈ Γ(C) , there exists a sequence of moves f ( 1 ) , . . , f ( R ) ∈ M such that
for 1 ≤ R ′ ≤ R . From the result of Diaconis and Sturmfels ( 1998 ), there exists a Markov basis for any Γ(C). The Markov basis allows the construction of an irreducible Markov chain on Γ( C ). Diaconis and Sturmfels ( 1998 ) also described a Markov basis of primitive moves for the independence model for a two-way contingency table that is the simplest decomposable log-linear model. We extend their idea for generating primitive moves for the independence model for a two-way table to the case of an arbitrary decomposable log-linear model of a multi- way table. Let C = {C 1 , . . . , C M } be the set of ordered cliques of a decomposable graph G or a generating class of a decomposable log-linear model. We describe a Markov basis for Γ ( C i ,  C j ) that is the set of all contingency tables with fixed marginals n C i and n C i . For any two cliques C i , C j (i < j) in C , the decomposable log-linear model has the conditional independence structure X A i  ⊥  X A i | X B from Eq. ( 1 ). We break up n into slices corresponding to each value of X B and obtain x B -slice of the table, {n XBEIB, where n XBEIN , xBEIN , xIAj , where n xBEIN , xAj ) EIN , xIAj , is cross- classified by X A i and X A j for fixed x B ∈ I B . Note that {n * i ∪ A j x B ∈ I B preserves fixed marginals nc 1 , . . . , nc M and thus {n A i UA j } x B ∈ I B  ∈  Γ(C) . For some indices x λ ,̸≠ x λ , ∈ ¯ z λ , x λ ,̸≠ x λ , ∈ ¯ z λ , we define a primitive move associated with n XB
Then
is a Markov basis for n × B
页Springer
The following theorem shows a Markov basis for Γ( C i , C j ). Theorem 2  Let C i and C j be any two clique in C. Then
is a Markov basis for Γ(C i , C j ). Proof  Let f ∈ F ( C i , C i ). We have
Thus n + f ∈ Γ(C i , C j ). Next we prove that F(C i , C j ) is a Markov basis for Γ(C i , C j ). From Theorem 1 , we have X A i  L  X A i l X B . We recast X A i , X A i and X B by new variables Y i , Y 2 and Y 3 with I 1 = Π k ∈ A , I k , I 2 = Π k ∈ A , I k and I 3 = Π k ∈ B I k categories defined by I 1 , I 2 and I 3 , respectively. We then have Y 1 ⊥ Y 2 | Y 3 . Thus it is sufficient to give a Markov basis for the log-linear model with the generating class { C 1 , C 2 } such that C 1 = {1, 3} and C 2 = {2, 3}. Let n be cell counts of the I 1 × I 2 × I 3 table. By considering the reverse lexicographic order of the cell indices in I 1 × I 2 × I 3 , n can be transformed into a linear list of counts (i.e. vector) ñ. Given a log-linear model, the sufficient statistics b = (ñ C 1 , ñ C 2 ) with the reverse lexicographic order of the cell indices can be written as Añ = b, where A is a some integer matrix and called a configuration of the model. For the log-linear model with {C 1 , C 2 } = {{1, 3}, {2, 3}}, A is given by
where E 1 is the I × I identity matrix, 1 t is the column vector of ones length I , and & denotes the Kronecker product. After permuting rows of A , we have
where e k is the k -th row of E l 3 . By denoting
页Springer A' is written by the block diagonal matrix
where A I 1 I 2 is the ( I 1 + I 2 ) × I 1 I 2 matrix given by and 0 I 1 I 2 is the ( I 1 + I 2 ) × I 1 I 2 matrix of all zero elements. Note that A I 1 I 2 is the same form of the configuration of the independence model for a two-way contingency table. Because A ′ is the block diagonal matrix, we can compute independently the Gröbner basis for the toric ideal associated with A k and then obtain a Markov basis f k of Eq. (2). Therefore, F ( C 1 , C 2 ) of Eq. ( 3 ) given by the linear combination
of Markov bases {f k }k ∈ I 3 is indeed a Markov basis for Γ(C 1 , C 2 ).
In "Appendix", we give A' of the conditional independence model of a three-way contingency table. Using Eq. ( 3 ), we define a Markov basis on the junction tree for a decomposable log-linear model as follows: Definition 3  Let C = {C 1 , . . . , C M } be the set of ordered cliques of a decomposable graph G and let T ( C ) be the junction tree with C as its node set. Then the set of primitive moves associated with the junction tree T ( C ) is defined by
where F(C i , C j ) is given by Eq. ( 3 ). We provide the following theorem for a Markov basis for Γ ( C ). Theorem 3  Let T (C) be the junction tree with C = {C 1 , . . . , C M } as its node set. Then the set of primitive moves F(T(C)) = F(C1, . . . , CM) defined by Eq. (4) is a set of moves for Γ(C). Furthermore F(T(C)) is a Markov basis for Γ(C). Proof  By Definition 3 , we have from Theorem 2 that F ( T ( C )) is a Markov basis for Γ( C ). Thus the result can be obtained immediately.口
页Springer
4 Generating Markov bases on junction trees 4.1 Algorithm for generating random tables We propose an algorithm for generating a random table in Γ(C) . Assume that the junction tree T ( C ) of the ordered clique set C can be constructed. We calculate weight w ij representing the number of moves for F ( C i , C j ) by where I Ai = Π k ∈ Ai Ik, I Aj = Π k ∈ Aj Ik and IB = Π k ∈ B Ik, and normalize wij by p(wij) = wij / ∑ 1<s<1<M Wst Given a contingency table n , the following algorithm generates a candidate table ñ by using F(T(C)): [Algorithm 1: Random table generation] Step 1:  Randomly select two cliques C i , C j (i < j) in C with probability p (w ij). Obtain A i , A j and B by
Step 2:  Uniformly choose a move f ∈ F ( C i , C j ). Step 3:  Generate ñ by ñ = n + f. Then Random table generation produces ñ that 4 I B cell entries in n are changed. Example 4.1 We illustrate Random table generation by using the junction tree intro- duced in Example 2.1 . Assume that C 3 and C 5 are selected with probability p ( w 35 ) in Step 1. From Eq. ( 1 ), we have A 3 = {3}, A 5 = {7} and B = {1, 2, 4, 5, 6}, i.e., XA, = X3, XA, = X7 and XB = (X1, X2, X4, X5, X6). Step 2 uniformly selects a move f ∈ F ( C 3 , C 5 ). To pick f , the following steps are repeated for every x B ∈ I B :
We compute f = ∑ x B ∈ I B  ε f × B 3 generates ñ by ñ = n + f.页Springer 4.2 Comparison of the proposed and Dobra's algorithms for generating random tables Dobra ( 2003 ) defined a Markov basis that is the set of primitive moves and is char- acterized by the star property of Blair and Barry ( 1993 ), which decomposes G into the triplet of disjoint subsets (V 1 , S , V 2 ) such that X V 1  L  X V 2 | X S , where S  E  S . When T ( C ) has the star property such that S separates V 1 from V 2 in G , it is possible to construct T ({V 1 U S, V 2 U S}). When decomposing G using the global Markov property in Theorem 1 , we have T ( { A i ∪ B , A i ∪ B }). For a given table n , Dobra's random table generation algorithm based on the star property produces a candidate table ñ that 4 cell entries in n are changed. We can see that the number of cells changed by Random table generation is IB times of that by Dobra's algorithm, and thus Random table generation produces a variety of contingency tables in the set of contingency tables with fixed marginals. Example 4.2 We show the number of cell entries that are changed by using both algorithms. We assume that Random table generation selects C 2 and C 4 on the junction tree introduced in Example 2.1 . Then we have A 2 = {2}, A 4 = {6} and B = {1, 3, 4, 5, 7} by the decomposition of the global Markov property. For given ( A 2 ,  A 4 ,  B ), we break up n into { n { 2 , 6 } x B ∈ I B . In the case of all variables of X being binary, we have 32 x B -slices of the 2 × 2 table of X 2 and X 6 . We denote XB = (X1, X3, X4, X5, X7) = (1, 1, 1, 1) = 1, XB = (1, 1, 1, 1, 2) = 2, . . ., X B = (2, 2, 2, 2) = 32. Then {n {2,6} } x B ∈{1,...,32} is displayed as follows:
For each x B , Random table generation produces ñ × B + n × B + ε (2,6), where f (2,6) ∈ {−1, 1}. Thus Random table generation enables changing all 128(= 4 × 32) cell entries in ñ whereas only 4 cell entries in ñ are changed by using Dobra's algorithm.
5 Computing p -values using MCMC with Markov bases
We provide MCMC using F(T(C)) for generating contingency tables of a Markov chain on Γ( C ). Then the Metropolis–Hastings (M–H) algorithm of Hastings ( 1970 ) can be used to generate the Markov chain. Diaconis and Sturmfels ( 1998 ) proved that
页Springer
the Markov chain generated by the M–H algorithm is an irreducible, aperiodic Markov chain on Γ( C ) with a stationary distribution π . 5.1 Generating Markov chains in MCMC We assume that n has a multinomial distribution. The exact conditional distribution of n given the set of marginal constraints determined by X A i  ⊥ X A i | X B has the product hypergeometric distribution with the following probability function:
Equation (5) indicates that there exists mutual independence between tables {n * B ∈ I B conditional on the fixed marginal table n B . To generate random tables of a Markov chain on Γ( C ), the M–H algorithm iterates through the following steps: [Algorithm 2: M-H algorithm for generating a Markov chain] Step 0:  Initialize the iteration counter r = 1 and set n (0) as the initial contingency table. Step 1:  Generate a candidate table ñ = {ñ x , ∪ A , } x , ∈ I , by using Random table gen- eration. Step 2:  For every xB ∈ IB , proceed as follows: – If all cell entries of ñ A , UA , are non-negative integers, accept ñ , UA , as the next
Step 3:  Increment counter r and return to Step 1. 5.2 MCMC computation of p -values and their standard errors The M–H algorithm draws {n ( r )}o<r<Ro+R ∈ Γ(C ) for a specified clique set C . Then, after discarding the first R 0 tables as a burn-in, the p -value via MCMC (MCMC p-value) can be obtained by
where χ 2 (n, m) is the Pearson chi-squared statistic given by
and m = {m(x)}x∈I is the set of expected values conditional on marginal constrains of C. To evaluate the accuracy of the MCMC estimates, we compute the standard error of ˆ ρ using the batch means method of Geyer ( 1992 ), which works as follows: Dividing random tables {n(r)}Ro+1<r<Ro+R1R2 into R1 batches of size R2 each, the MCMC p-value for the kth batch is then calculated by
The variance estimate of  ĝ can be obtained from
and the batch means estimate of the Monte Carlo standard error is calculated from √ Var / R 1 . Then the batch size R 1 should be large enough so that ˆ β k s are approximately independent. Jones et al. ( 2006 ) recommended to use R 1 = [√R] and R 2 = [R/R] J.
6 Numerical experiments
In this section, we illustrate the performance of the proposed MCMC in comparison with that of asymptotic chi-squared approximation and Dobra's MCMC by using real datasets, and evaluate MCMC for testing decomposable log-linear models via simulation studies.
6.1  MCMC for computing p -values
In the first experiment, we compute the MCMC p -values for testing decompos- able log-linear models for sparse contingency tables. The M–H algorithm generates 1,000,000 (= R) random tables with 10,000 (= R 0 ) tables as a burn-in. We also set R 1 = √ R = 1, 000 and R 2 = R/R 1 = 1, 000 for estimating the standard errors of the MCMC p values. The efficiency of the M–H algorithm is measured by the inefficiency factor defined by Var/σ 2 , where Var is computed from Eq. ( 8 ) and σ 2 is the variance of p -values obtained from hypothetical independent samples. The inefficiency factor is related 841
🔥 Springer

to the number of generating samples required to achieve a given degree of numerical accuracy. Thus the algorithms have higher inefficiency factors when they find p -values with larger standard errors. Experiment 1. Table 1 summarizes the data from a study of nonmetastatic osteosarcoma by Goorin et al. ( 1987 ) in which the response is whether the subject achieved a three- year disease-free interval. This table is a sparse table with some cells having zero entries. For the contingency table, we consider the decomposable log-linear models with the junction trees specified by clique sets C 1 to C 8 given in the first column in Table 2. Table 2 lists the results of the experiments. We can find large discrepancies between the asymptotic p -values obtained using the chi-squared distribution and the MCMC p -values. They indicate that the asymptotic chi-squared approximation is unreliable for sparse contingency tables. Figure 2 shows the autocorrelation plots for the chain values { χ 2 (n(r), m)}1<r<Ro of the burn-in generated by the M–H algorithm using Random table generation (the proposed M–H algorithm) and the M–H algorithm using Dobra's random table gen- eration algorithm (Dobra's M–H algorithm). We can see from Fig. 2 that the Markov chain generated by the proposed M–H algorithm converges to a stationary state faster than that generated by Dobra's M–H algorithm, because no appreciable dependence exists after lag 20–30 in the Markov chain from the proposed M–H algorithm. We can obtain the same results for the rest models with C 5 to C 8 . We compare the efficiency of two algorithms using the inefficiency factor. Because σ 2 for the two algorithms is the same for each model, we compare their standard errors. For all models, the standard errors of the MCMC p -values by the proposed M–H algorithm are about a half of those of Dobra's M–H algorithm. We conclude that the proposed M–H algorithm is more efficient than Dobra's M–H algorithm for the experiments. Experiment 2. The second data shown in Table 3 are from the Avadex data given in Innes et al. ( 1969 ). We consider the decomposable log-linear models with the junction trees specified by clique sets C 1 to C 6 given in the first column in Table 4 .
The values of the fourth and fifth columns in Table 4 indicate that the MCMC p-values obtained by the proposed M–H algorithm are very close to those by Dobra's M–H algorithm. The standard errors of the MCMC p -values obtained by the proposed M–H algorithm are two times smaller than those by Dobra's M–H algorithm, and thus the proposed M–H algorithm is two times efficient than Dobra's M–H algorithm in terms of the inefficiency factor. Experiment 3. The third data shown in Table 5 are from a study of the presence or absence of torus mandibularis in three Aleutian populations from Muller and May- hall ( 1971 ). For the table, we consider the decomposable log-linear models with the junction trees specified by clique sets C 1 to C 6 given in the first column in Table 6 . We see from the fourth and fifth columns in Table 6 that the standard errors found by the proposed M–H algorithm are 1.3–1.6 and 2.4 times smaller than those by Dobra's algorithm except the result for C 4 . These results show that the proposed M–H algorithm efficiently generates random tables more than Dobra's M–H algorithm. The asymptotic chi-squared approximation seems to work well as it returns asymptotic p-values in agreement with the MCMC p-values.
6.2 MCMC for testing decomposable log-linear models
In the experiment, we focus on the simulation studies of MCMC for testing decom- posable log-linear models. The simulation design is as follows: We draw n from the multinomial distribution with sample size of 50 and cell probabilities conditional on C as given in Table 7 . We compute the asymptotic and MCMC p -values for testing decomposable log-linear models with the junction trees specified by the clique sets
given in Table 7 . Here the proposed M–H algorithm generates 1,000 random tables and the MCMC p -values are obtained from Eq. ( 7 ). The above procedure is replicated 1,000 times. Then the Type I error rate is computed from the proportion of the number of the p -values that are smaller than the probability of Type I error α . Table 8 shows results for tests at α = 0.01, 0.05 and 0.10. We find that, for all models, the Type I error rates obtained from the MCMC p -values are very close to α even when they are calculated from 1,000 random tables, while the rates from the asymptotic p -values greatly differ from each α . As expected, the asymptotic χ 2 test is not reliable for such sparse tables. Figure 3 shows the plots of the MCMC and asymptotic p -values for each of the decomposable log-linear models. We can see that the MCMC p -values are almost identical to α , because they are arranged very close to or on the bisecting line. These results show that the proposed M–H algorithm for testing decomposable log-linear
models is a valuable alternative to the asymptotic chi-squared test for sparse contin- gency tables.
7 Concluding remarks
In this study, we showed that a Markov basis on the junction tree for a decomposable log-linear model can be expressed as the union of Markov bases characterized by
Table 8 Type I error rates at α = 0.01, 0.05 and 0.10
global Markov properties. We provided an explicit form of the Markov basis given in Definition 3 and then described Random table generation for generating Markov bases. We also presented the M–H algorithm with a Markov basis for generating contingency tables of a Markov chain. The M–H algorithm using Random table gen- eration allows the production of contingency tables globally in the set of contingency tables with fixed marginals. In the numerical experiments, we demonstrated that, for decomposable log-linear models for sparse contingency tables, the M–H algorithm using Random table gener- ation enables finding more reliable p -values than the asymptotic chi-squared approx- imation and generates random tables more efficiently than Dobra's M–H algorithm in terms of the inefficiency factor.
覧Springer
Moreover, we found that the proposed M–H algorithm works well to test decom- posable log-linear models for sparse contingency tables. Acknowledgments The authors would like to thank the editor and referees whose valuable comments and kind suggestions that led to an improvement of this paper. This research is supported by the Japan Society for the Promotion of Science (JSPS), Grant-in-Aid for Scientific Research (C), No. 20500263.
Appendix: Configuration A of the conditional independence model for a three-
way contingency table
We consider a 2 × 2 × 3 table cross-classified by X = (X 1 , X 2 , X 3 ). For the table, we assume the conditional independence that X 1 ⊥ X 2 | X 3 . When we consider the reverse lexicographic order of the cell indices in {1, 2} × {1, 2} × {1, 2, 3}, that is, (1, 1, 1), (2, 1, 1), . . . , (2, 2, 3), A for the conditional independence model is given by l 0 1 0 0 0 0 0
0
0
0 0 1 0 0 0 0 0 0 1 0 0
0 0 0 0 1 0 0 0 0 0 0 0 1 1
0 By permuting rows of A, we have the block diagonal matrix