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.     

A finiteness theorem for Markov bases of hierarchical models

We show that the complexity of the Markov bases of multidimensional tables stabilizes eventually if a single table dimension is allowed to vary. In particular, if this table dimension is greater than a computable bound, the Markov bases consist of elements from Markov bases of smaller tables. We give an explicit formula for this bound in terms of Graver bases. We also compute these Markov and Graver complexities for all K×2×2×2 tables.     

Conditional Inference on Tables With Structural Zeros

We develop a set of sequential importance sampling (SIS) strategies for sampling nearly uniformly from two-way zero-one or contingency tables with fixed marginal sums and a given set of structural zeros. The SIS procedure samples tables column by column or cell by cell by using appropriate proposal distributions, and enables us to approximate closely the null distributions of a number of test statistics involved in such tables. When structural zeros are on the diagonal or follow certain patterns, more efficient SIS algorithms are developed which guarantee that every generated table is valid. Examples show that our methods can be applied to make conditional inference on zero-one and contingency tables, and are more efficient than other existing Monte Carlo algorithms.     

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.     

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.     

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 of Binary Graph Models

This paper is concerned with the topological invariant of a graph given by the maximum degree of a Markov basis element for the corresponding graph model for binary contingency tables. We describe a degree four Markov basis for the model when the underlying graph is a cycle and generalize this result to the complete bipartite graph K_2,n. We also give a combinatorial classification of degree two and three Markov basis moves as well as a Buchberger-free algorithm to compute moves of arbitrary given degree. Finally, we compute the algebraic degree of the model when the underlying graph is a forest.AMS Subject Classification: 05C99, 13P10, 62Q05.     

Multiplicative Decompositions and Frequency of Vanishing of Nonnegative Submartingales

In this paper, we establish a multiplicative decomposition formula for nonnegative local martingales and use it to characterize the set of continuous local submartingales Y of the form Y = N + A, where the measure dA is carried by the set of zeros of Y. In particular, we shall see that in the set of all local submartingales with the same martingale part in the multiplicative decomposition, these submartingales are the smallest ones. We also study some integrability questions in the multiplicative decomposition and interpret the notion of saturated sets in the light of our results.      

Markov bases for two-way subtable sum problems

It is well known that for two-way contingency tables with fixed row sums and column sums the set of square-free moves of degree two forms a Markov basis. However when we impose an additional constraint that the sum of cell counts in a subtable is also fixed, then these moves do not necessarily form a Markov basis. Thus, in this paper, we show a necessary and sufficient condition on a subtable so that the set of square-free moves of degree two forms a Markov basis.     

Optimal scale selection for multi-scale decision tables

Human beings often observe objects or deal with data hierarchically structured at different levels of granulations. In this paper, we study optimal scale selection in multi-scale decision tables from the perspective of granular computation. A multi-scale information table is an attribute-value system in which each object under each attribute is represented by different scales at different levels of granulations having a granular information transformation from a finer to a coarser labelled value. The concept of multi-scale information tables in the context of rough sets is introduced. Lower and upper approximations with reference to different levels of granulations in multi-scale information tables are defined and their properties are examined. Optimal scale selection with various requirements in multi-scale decision tables with the standard rough set model and a dual probabilistic rough set model are discussed respectively. Relationships among different notions of optimal scales in multi-scale decision tables are further analyzed.     

Expectation-Stock Dynamics in Multi-Agent Fisheries

In this paper we consider a game-theoretic dynamic model describing the exploitation of a renewable resource. Our model is based on a Cournot oligopoly game where n profit-maximizing players harvest fish and sell their catch on m markets. We assume that the players do not know the law governing the reproduction of the resource. Instead they use an adaptive updating scheme to forecast the future fish stock. We analyze the resulting dynamical system which describes how the fish population and the forecasts (expectations) of the players evolve over time. We provide results on the existence and local stability of steady states. We consider the set of initial conditions which give non-negative trajectories converging to an equilibrium and illustrate how this set can be characterized. We show how such sets may change as some structural parameters of our model are varied and how these changes can be explained. This paper extends existing results in the literature by showing that they also hold in our two-dimensional framework. Moreover, by using analytical and numerical methods, we provide some new results on global dynamics which show that such sets of initial conditions can have complicated topological structures, a situation which may be particularly troublesome for policymakers.     

Nonparametric Bayesian Modeling for Multivariate Ordinal Data

This article proposes a probability model for k-dimensional ordinal outcomes, that is, it considers inference for data recorded in k-dimensional contingency tables with ordinal factors. The proposed approach is based on full posterior inference, assuming a flexible underlying prior probability model for the contingency table cell probabilities. We use a variation of the traditional multivariate probit model, with latent scores that determine the observed data. In our model, a mixture of normals prior replaces the usual single multivariate normal model for the latent variables. By augmenting the prior model to a mixture of normals we generalize inference in two important ways. First, we allow for varying local dependence structure across the contingency table. Second, inference in ordinal multivariate probit models is plagued by problems related to the choice and resampling of cutoffs defined for these latent variables. We show how the proposed mixture model approach entirely removes these problems. We illustrate the methodology with two examples, one simulated dataset and one dataset of interrater agreement.     

A Markov chain Monte Carlo Algorithm for Approximating Exact Conditional Probabilities

Conditional inference eliminates nuisance parameters by conditioning on their sufficient statistics. For contingency tables conditional inference entails enumerating all tables with the same sufficient statistics as the observed data. For moderately sized tables and/or complex models, the computing time to enumerate these tables is often prohibitive. Monte Carlo approximations offer a viable alternative provided it is possible to obtain samples from the correct conditional distribution. This article presents an MCMC extension of the importance sampling algorithm, using a rounded normal candidate to update randomly chosen cells while leaving the remainder of the table fixed. This local approximation can greatly increase the efficiency of the rounded normal candidate. By choosing the number of cells to be updated at random, a balance is struck between dependency in the Markov chain and accuracy of the candidate.     

How to construct totally disconnected Markov sets?

We deduce a polynomial estimate on a compact planar set from a polynomial estimate on its circular projection, which enables us to prove Markov and Bernstein-Walsh type inequalities for certain sets. We construct

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.     

Rough sets for pattern classification using pairwise-comparison-based tables

Rough set theory is a useful mathematical tool to deal with vagueness and uncertainty in available information. The results of a rough set approach are usually presented in the form of a set of decision rules derived from a decision table. Because using the original decision table is not the only way to implement a rough set approach, it could be interesting to investigate possible improvement in classification performance by replacing the original table with an alternative table obtained by pairwise comparisons among patterns. In this paper, a decision table based on pairwise comparisons is generated using the preference relation as in the Preference Ranking Organization Methods for Enrichment Evaluations (PROMETHEE) methods, to gauges the intensity of preference for one pattern over another pattern on each criterion before classification. The rough-set-based rule classifier (RSRC) provided by the well-known library for the Rough Set Exploration System (RSES) running under Windows as been successfully used to generate decision rules by using the pairwise-comparisons-based tables. Specifically, parameters related to the preference function on each criterion have been determined using a genetic-algorithm-based approach. Computer simulations involving several real-world data sets have revealed that of the proposed classification method performs well compared to other well-known classification methods and to RSRC using the original tables.     

Extracting Sunbeams From Cucumbers

In this article we survey the display formats used in the Journal of Computational and Graphical Statistics during the period 2005–2010 and discover that the most dominant format was the table. We then examine the actual tables used and find that most could have been made more comprehensible had they utilized one or more of three simple rules for table construction. We illustrate these rules on tables drawn from the Journal and elsewhere.     

An algorithm for decomposing a polynomial system into normal ascending sets

We present an algorithm to decompose a polynomial system into a finite set of normal ascending sets such that the set of the zeros of the polynomial system is the union of the sets of the regular zeros of the normal ascending sets.If the polynomial system is zero dimensional,the set of the zeros of the polynomials is the union of the sets of the zeros of the normal ascending sets.     

Rough set based rule induction from two decision tables

We study rule induction from two decision tables as a basis of rough set analysis of more than one decision tables. We regard the rule induction process as enumerating minimal conditions satisfied with positive examples but unsatisfied with negative examples and/or with negative decision rules. From this point of view, we show that seven kinds of rule induction are conceivable for a single decision table. We point out that the set of all decision rules from two decision tables can be split in two levels: a first level decision rule is positively supported by a decision table and does not have any conflict with the other decision table and a second level decision rule is positively supported by both decision tables. To each level, we propose rule induction methods based on decision matrices. Through the discussions, we demonstrate that many kinds of rule induction are conceivable.     

Zero distribution of random polynomials

We study global distribution of zeros for a wide range of ensembles of random polynomials. Two main directions are related to almost sure limits of the zero counting measures and to quantitative results on the expected number of zeros in various sets. In the simplest case of Kac polynomials, given by the linear combinations of monomials with i.i.d. random coefficients, it is well known that under mild assumptions on the coefficients, their zeros are asymptotically uniformly distributed near the unit circumference. We give estimates of the expected discrepancy between the zero counting measure and the normalized arclength on the unit circle. Similar results are established for polynomials with random coefficients spanned by different bases, e.g., by orthogonal polynomials. We show almost sure convergence of the zero counting measures to the corresponding equilibrium measures for associated sets in the plane and quantify this convergence. In our results, random coefficients may be dependent and need not have identical distributions.