Computing p-values in conditional independence models for a contingency table

We present a Markov chain Monte Carlo (MCMC) method for generating Markov chains using Markov bases for conditional independence models for a four-way contingency table. We then describe a Markov basis characterized by Markov properties associated with a given conditional independence model and show how to use the Markov basis to generate random tables of a Markov chain. The estimates of exact p-values can be obtained from random tables generated by the MCMC method. Numerical experiments examine the performance of the proposed MCMC method in comparison with the χ ² approximation using large sparse contingency tables.     

Markov bases and subbases for bounded contingency tables

In this paper we study the computation of Markov bases for contingency tables whose cell entries have an upper bound. It is known that in this case one has to compute universal Gröbner bases, and this is often infeasible also in small- and medium-sized problems. Here we focus on bounded two-way contingency tables under independence model. We show that when these bounds on cells are positive the set of basic moves of all 2 × 2 minors connects all tables with given margins. We also give some results about bounded incomplete table and we conclude with an open problem on the necessary and sufficient condition on the set of structural zeros so that the set of basic moves of all 2 × 2 minors connects all incomplete contingency tables with given positive margins.     

Dynamic Markov Bases

This article presents a computational approach for generating Markov bases for multiway contingency tables whose cell counts might be constrained by fixed marginals and by lower and upper bounds. Our framework includes tables with structural zeros as a particular case. Instead of computing the entire Markov bases in an initial step, our framework finds sets of local moves that connect each table in the reference set with a set of neighbor tables. We construct a Markov chain on the reference set of tables that requires only a set of local moves at each iteration. The union of these sets of local moves forms a dynamic Markov basis. We illustrate the practicality of our algorithms in the estimation of exact p-values for a three-way table with structural zeros and a sparse eight-way table. This article has online supplementary materials.     

Minimal invariant Markov basis for sampling contingency tables with fixed marginals

In this paper we define an invariant Markov basis for a connected Markov chain over the set of contingency tables with fixed marginals and derive some characterizations of minimality of the invariant basis. We also give a necessary and sufficient condition for uniqueness of minimal invariant Markov bases. By considering the invariance, Markov bases can be presented very concisely. As an example, we present minimal invariant Markov bases for all 2 × 2 × 2 × 2 hierarchical models. The invariance here refers to permutation of indices of each axis of the contingency tables. If the categories of each axis do not have any order relations among them, it is natural to consider the action of the symmetric group on each axis of the contingency table. A general algebraic algorithm for obtaining a Markov basis was given by Diaconis and Sturmfels (The Annals of Statistics, 26, 363–397, 1998). Their algorithm is based on computing Gröbner basis of a well-specified polynomial ideal. However, the reduced Gröbner basis depends on the particular term order and is not symmetric. Therefore, it is of interest to consider the properties of invariant Markov basis.     

Lower Bounds on the Graver Complexity of <Emphasis Type="Italic">M</Emphasis>-Fold Matrices

In this paper, we present a construction that turns certain relations on Graver basis elements of an M-fold matrix \({{A^{(M)}}}\) into relations on Graver basis elements of an \({(M+1)}\)-fold matrix \({{A^{(M+1)}}}\). In doing so, we strengthen the bound on the Graver complexity of the M-fold matrix \({{A_{3\times{M}}}}\) from \({{g(A_{3\times{M}}) \geq 17\cdot2^{M-3}-7}}\) (Berstein and Onn) to \({{g(A_{3\times{M}}) \geq 24\cdot2^{M-3}-21}}\), for \({M \geq 4}\). Moreover, we give a lower bound on the Graver complexity \({{g(A^{(M)})}}\) of general \({M}\)-fold matrices \({{A^{(M)}}}\) and we prove that the bound for \({g(A_{3\times{M}})}\) is not tight.     

The quadratic Graver cone, quadratic integer minimization, and extensions

It has been shown in a number of recent papers that Graver bases methods enable to solve linear and nonlinear integer programming problems in variable dimension in polynomial time, resulting in a variety of applications in operations research and statistics. In this article we continue this line of investigation and show that Graver bases also enable to minimize quadratic and higher degree polynomial functions which lie in suitable cones. These cones always include all separable convex polynomials and typically more.     

On the Gröbner complexity of matrices

In this paper we show that if for an integer matrix A the universal Gröbner basis of the associated toric ideal I_A coincides with the Graver basis of A, then the Gröbner complexity u(A) and the Graver complexity g(A) of its higher Lawrence liftings agree, too. In fact, if the universal Gröbner basis of I_A coincides with the Graver basis of A, then also the more general complexities u(A,B) and g(A,B) agree for arbitrary B. We conclude that for the matrices A_3×3 and A_3×4, defining the 3×3 and 3×4 transportation problems, we have u(A_3×3)=g(A_3×3)=9 and u(A_3×4)=g(A_3×4)≥27. Moreover, we prove that u(A_a,b)=g(A_a,b)=2(a+b)/gcd(a,b) for positive integers a,b and .     

Instanton approximation, periodic ASD connections, and mean dimension

We study a moduli space of ASD connections over S³×R. We consider not only finite energy ASD connections but also infinite energy ones. So the moduli space is infinite dimensional in general. We study the (local) mean dimension of this infinite dimensional moduli space. We show the upper bound on the mean dimension by using a “Runge-approximation” for ASD connections, and we prove its lower bound by constructing an infinite dimensional deformation theory of periodic ASD connections.     

A markov chain sampler for contingency table exact inference

Summary  In the inference of contingency table, when the cell counts are not large enough for asymptotic approximation, conditioning exact method is used and often computationally impractical for large tables. Instead, various sampling methods can be used. Based on permutation, the Monte Carlo sampling may become again impractical for large tables. For this, existing the Markov chain method is to sample a few elements of the table at each iteration and is inefficient. Here we consider a Markov chain, in which a sub-table of user specified size is updated at each iteration, and it achieves high sampling efficiency. Some theoretical properties of the chain and its applications to some commonly used tables are discussed. As an illustration, this method is applied to the exact test of the Hardy-Weinberg equilibrium in the population genetics context.     

Variation of cost functions in integer programming

We study the problem of minimizingc · x subject toA · x =b. x ≥ 0 andx integral, for a fixed matrixA. Two cost functionsc andc′ are considered equivalent if they give the same optimal solutions for eachb. We construct a polytopeSt(A) whose normal cones are the equivalence classes. Explicit inequality presentations of these cones are given by the reduced Gröbner bases associated withA. The union of the reduced Gröbner bases asc varies (called the universal Gröbner basis) consists precisely of the edge directions ofSt(A). We present geometric algorithms for computingSt(A), the Graver basis, and the universal Gröbner basis.     

A bound on the dimension of interval orders

We make use of the partially ordered set (I(0, n), <) consisting of all closed intervals of real numbers with integer endpoints (including the degenerate intervals with the same right- and left-hand endpoints), ordered by [a, b] < [c, d] if b < c, to show that there is no bound on the order dimension of interval orders. We then turn to the problem of computing the dimension of I(0, n), showing that I(0, 10) has dimension 3 but I(0, 11) has dimension 4. We use these results as initial conditions in obtaining an upper bound on the dimension of I(0, n) as a logarithmic function of n. It is our belief that this example is a “canonical” example for interval orders, so that the computation of its dimension should have significant impact on the problem of computing the dimension of interval orders in general.     

Subspaces of matrices with special rank properties

Let K be a field and let M_m×n(K) denote the space of m×n matrices over K. We investigate properties of a subspace M of M_m×n(K) of dimension n(m-r+1) in which each non-zero element of M has rank at least r and enumerate the number of elements of a given rank in M when K is finite. We also provide an upper bound for the dimension of a constant rank r subspace of M_m×n(K) when K is finite and give non-trivial examples to show that our bound is optimal in some cases. We include a similar a bound for the maximum dimension of a constant rank subspace of skew-symmetric matrices over a finite field.     

Markov chain mixing time on cycles

Mixing time quantifies the convergence speed of a Markov chain to the stationary distribution. It is an important quantity related to the performance of MCMC sampling. It is known that the mixing time of a reversible chain can be significantly improved by lifting, resulting in an irreversible chain, while changing the topology of the chain. We supplement this result by showing that if the connectivity graph of a Markov chain is a cycle, then there is an Ω(n²) lower bound for the mixing time. This is the same order of magnitude that is known for reversible chains on the cycle.     

The Graver Complexity of Integer Programming

In this article we establish an exponential lower bound on the Graver complexity of integer programs. This provides new type of evidence supporting the presumable intractability of integer programming. Specifically, we show that the Graver complexity of the incidence matrix of the complete bipartite graph K ₃,m satisfies g(m) = Ω(2 ^m ), with g(m) ≥ 17·2 ^m−3 –7 for every m > 3.     

On approximately simultaneously diagonalizable matrices

A collection A₁, A₂, …, A_k of n × n matrices over the complex numbers C has the ASD property if the matrices can be perturbed by an arbitrarily small amount so that they become simultaneously diagonalizable. Such a collection must perforce be commuting. We show by a direct matrix proof that the ASD property holds for three commuting matrices when one of them is 2-regular (dimension of eigenspaces is at most 2). Corollaries include results of Gerstenhaber and Neubauer-Sethuraman on bounds for the dimension of the algebra generated by A₁, A₂, …, A_k. Even when the ASD property fails, our techniques can produce a good bound on the dimension of this subalgebra. For example, we establish for commuting matrices A₁, …, A_k when one of them is 2-regular. This bound is sharp. One offshoot of our work is the introduction of a new canonical form, the H-form, for matrices over an algebraically closed field. The H-form of a matrix is a sparse “Jordan like” upper triangular matrix which allows us to assume that any commuting matrices are also upper triangular. (The Jordan form itself does not accommodate this.)     

Permutation polytopes and indecomposable elements in permutation groups

Each group G of n×n permutation matrices has a corresponding permutation polytope, P(G):=conv(G)⊂Rn×n. We relate the structure of P(G) to the transitivity of G. In particular, we show that if G has t nontrivial orbits, then min{2t,⌊n/2⌋} is a sharp upper bound on the diameter of the graph of P(G). We also show that P(G) achieves its maximal dimension of ²(n−1) precisely when G is 2-transitive. We then extend the results of Pak [I. Pak, Four questions on Birkhoff polytope, Ann. Comb. 4 (1) (2000) 83-90] on mixing times for a random walk on P(G). Our work depends on a new result for permutation groups involving writing permutations as products of indecomposable permutations.     

Generating uniformly distributed random latin squares

By simulating an ergodic Markov chain whose stationary distribution is uniform over the space of n × n Latin squares, we can obtain squares that are (approximately) uniformly distributed; we offer two such chains. The central issue is the construction of “moves” that connect the squares. Our first approach uses the fact that an n × n Latin square is equivalent to an n × n × n contingency table in which each line sum equals 1. We relax the nonnegativity condition on the table's cells, allowing “improper” tables that have a single—1-cell. A simple set of moves connects this expanded space of tables [the diameter of the associated graph is bounded by 2(n − 1)³], and suggests a Markov chain whose subchain of proper tables has the desired uniform stationary distribution (with an average of approximately n steps between proper tables). By grouping these moves appropriately, we derive a class of moves that stay within the space of proper Latin squares [with graph diameter bounded by 4(n − 1)²]; these may also be used to form a suitable Markov chain. © 1996 John Wiley & Sons, Inc.     

A polynomial oracle-time algorithm for convex integer minimization

In this paper we consider the solution of certain convex integer minimization problems via greedy augmentation procedures. We show that a greedy augmentation procedure that employs only directions from certain Graver bases needs only polynomially many augmentation steps to solve the given problem. We extend these results to convex N-fold integer minimization problems and to convex 2-stage stochastic integer minimization problems. Finally, we present some applications of convex N-fold integer minimization problems for which our approach provides polynomial time solution algorithms.     

The tangential end fibration of an aspherical Poincaré complex

We construct a sphere fibration over a finite aspherical Poincaré complex X, which we call the tangential end fibration, under the condition that the universal cover of X is forward tame and simply connected at infinity. We show that it is tangent to X if the formal dimension of X is even or, when the formal dimension is odd, if the diagonal X→X×X admits a Poincaré embedding structure.     

Bounds on the global dimension of certain piecewise hereditary categories

We give bounds on the global dimension of a finite length, piecewise hereditary category in terms of quantitative connectivity properties of its graph of indecomposables.We use this to show that the global dimension of a finite-dimensional, piecewise hereditary algebra A cannot exceed 3 if A is an incidence algebra of a finite poset or more generally, a sincere algebra. This bound is tight.