Characterizing optimal sampling of binary contingency tables via the configuration model

A binary contingency table is an m × n array of binary entries with row sums r = (r₁, …, r_m) and column sums c = (c₁, …, c_n). The configuration model generates a contingency table by considering r_i tokens of type 1 for each row i and c_j tokens of type 2 for each column j, and then taking a uniformly random pairing between type‐1 and type‐2 tokens. We give a necessary and sufficient condition so that the probability that the configuration model outputs a binary contingency table remains bounded away from 0 as \begin{align*}N=\sum_{i=1}^m r_i=\sum_{j=1}^n c_j\end{align*} goes to ∞. Our finding shows surprising differences from recent results for binary symmetric contingency tables. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Polynomial time perfect sampling algorithm for two‐rowed contingency tables

This paper proposes a polynomial time perfect (exact) sampling algorithm for 2 × n contingency tables. The algorithm is based on monotone coupling from the past (monotone CFTP) algorithm. The expected running time is bounded by O(n³ lnN) where n is the number of columns and N is the total sum of all entries. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

An approximation algorithm for counting contingency tables

We present a randomized approximation algorithm for counting contingency tables, m × n non‐negative integer matrices with given row sums R = (r₁,…,r_m) and column sums C = (c₁,…,c_n). We define smooth margins (R,C) in terms of the typical table and prove that for such margins the algorithm has quasi‐polynomial N^{O(ln N)} complexity, where N = r₁ + … + r_m = c₁ + … + c_n. Various classes of margins are smooth, e.g., when m = O(n), n = O(m) and the ratios between the largest and the smallest row sums as well as between the largest and the smallest column sums are strictly smaller than the golden ratio (1 + )/2 ≈? 1.618. The algorithm builds on Monte Carlo integration and sampling algorithms for log‐concave densities, the matrix scaling algorithm, the permanent approximation algorithm, and an integral representation for the number of contingency tables. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Estimation and testing in large binary contingency tables

Very sparse contingency tables with a multiplicative structure are studied. The number of unspecified parameters and the number of cells are growing with the number of observations. Consistency and asymptotic normality of natural estimators are established. Also uniform convergence of the estimators to the parameters is investigated, and an application to the construction of confidence intervals is presented. Further, a family of goodness-of-fit tests is proposed for testing multiplicativity. It is shown that the test statistics are asymptotically normal. The results can be applied in such different fields as production testing or psychometrics.     

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.     

Brunn-Minkowski inequalities for contingency tables and integer flows

We establish approximate log-concavity for a wide family of combinatorially defined integer-valued functions. Examples include the number of non-negative integer matrices (contingency tables) with prescribed row and column sums (margins), as a function of the margins and the number of integer feasible flows in a network, as a function of the excesses at the vertices. As a corollary, we obtain approximate log-concavity for the Kostant partition function of type A. We also present an indirect evidence that at least some of the considered functions might be genuinely log-concave.     

Quasi-diagonal exponent symmetry model for square contingency tables with ordered categories

For square contingency tables, we propose a quasi-symmetry model with an exponential form along subdiagonal and give the theorem that Tomizawa’s (1992) diagonal exponent symmetry model holds if and only if the proposed model and marginal means equality model hold with the orthogonality of test statistics.     

Automated Factor Slice Sampling

Markov chain Monte Carlo (MCMC) algorithms offer a very general approach for sampling from arbitrary distributions. However, designing and tuning MCMC algorithms for each new distribution can be challenging and time consuming. It is particularly difficult to create an efficient sampler when there is strong dependence among the variables in a multivariate distribution. We describe a two-pronged approach for constructing efficient, automated MCMC algorithms: (1) we propose the “factor slice sampler,” a generalization of the univariate slice sampler where we treat the selection of a coordinate basis (factors) as an additional tuning parameter, and (2) we develop an approach for automatically selecting tuning parameters to construct an efficient factor slice sampler. In addition to automating the factor slice sampler, our tuning approach also applies to the standard univariate slice samplers. We demonstrate the efficiency and general applicability of our automated MCMC algorithm with a number of illustrative examples. This article has online supplementary materials.     

Ordinary and penalized minimum power-divergence estimators in two-way contingency tables

Basu and Basu (Statistica Sinica 8:841–860, 1998) have proposed an empty cell penalty for the minimum power-divergence estimators which can lead to improvements in the small sample properties of these estimators. In this paper, we study the small and moderate sample performances of the ordinary and penalized minimum power-divergence estimators in terms of efficiency and robustness for the log-linear models in two-way contingency tables under the assumptions of multinomial sampling. Calculations made by enumerating all possible sample combinations show that the penalized estimators are competitive with the ordinary estimators for the moderate samples and definitely better for the smallest sample considered for both efficiency and robustness under the considered models. The results also reveal that the bigger the main effects the more need for penalization.     

具有可变抽样区间的Poisson EWMA控制图

传统的EWMA控制图通常都是针对计量型质量特性值的,而对于计数型质量特征值少有研究.设计了单位缺陷数服从Poisson分布的EWMA控制图,并对Poisson EWMA控制图进行了可变抽样区间设计,利用Markov chain方法计算了其平均报警时间,计算结果表明,所设计的动态Poisson EWMA控制图较Shewhart c-图和固定抽样区间的Poissin EWMA控制图能更好的监控过程的变化.     

Honest Importance Sampling With Multiple Markov Chains

Importance sampling is a classical Monte Carlo technique in which a random sample from one probability density, π₁, is used to estimate an expectation with respect to another, π. The importance sampling estimator is strongly consistent and, as long as two simple moment conditions are satisfied, it obeys a central limit theorem (CLT). Moreover, there is a simple consistent estimator for the asymptotic variance in the CLT, which makes for routine computation of standard errors. Importance sampling can also be used in the Markov chain Monte Carlo (MCMC) context. Indeed, if the random sample from π₁ is replaced by a Harris ergodic Markov chain with invariant density π₁, then the resulting estimator remains strongly consistent. There is a price to be paid, however, as the computation of standard errors becomes more complicated. First, the two simple moment conditions that guarantee a CLT in the iid case are not enough in the MCMC context. Second, even when a CLT does hold, the asymptotic variance has a complex form and is difficult to estimate consistently. In this article, we explain how to use regenerative simulation to overcome these problems. Actually, we consider a more general setup, where we assume that Markov chain samples from several probability densities, π₁, …, π_k, are available. We construct multiple-chain importance sampling estimators for which we obtain a CLT based on regeneration. We show that if the Markov chains converge to their respective target distributions at a geometric rate, then under moment conditions similar to those required in the iid case, the MCMC-based importance sampling estimator obeys a CLT. Furthermore, because the CLT is based on a regenerative process, there is a simple consistent estimator of the asymptotic variance. We illustrate the method with two applications in Bayesian sensitivity analysis. The first concerns one-way random effect models under different priors. The second involves Bayesian variable selection in linear regression, and for this application, importance sampling based on multiple chains enables an empirical Bayes approach to variable selection.     

Computational Bayesian Analysis of Hidden Markov Models

Abstract

Versions of the Gibbs Sampler are derived for the analysis of data from hidden Markov chains and hidden Markov random fields. The principal new development is to use the pseudolikelihood function associated with the underlying Markov process in place of the likelihood, which is intractable in the case of a Markov random field, in the simulation step for the parameters in the Markov process. Theoretical aspects are discussed and a numerical study is reported.     

THE CONSTRUCTION OF MULTITYPE CANONICAL MARKOV BRANCHING CHAINS IN RANDOM ENVIRONMENTS

The investigation for branching processes has a long history by their strong physics background, but only a few authors have investigated the branching processes in random environments. First of all, the author introduces the concepts of the multitype canonical Markov branching chain in random environment (CMBCRE) and multitype Markov branching chain in random environment (MBCRE) and proved that CMBCRE must be MBCRE, and any MBCRE must be equivalent to another CMBCRE in distribution. The main results of this article are the construction of CMBCRE and some of its probability properties.     

可变抽样区间的二项EWMA控制图

在制造过程中,对产品的不合格品数进行监控时,通常选用计数性控制图-np图,它是基于过程服从二项分布建立的,一般对于过程中出现的较大波动效果明显。为了提高控制图对不合格品数较小波动的监控效果,本文设计了产品不合格品数服从二项分布的EWMA控制图。提出可变抽样区间的二项EWMA控制图,并采用马可夫链法计算其平均报警时间。对固定抽样区间以及可变抽样区间二项EWMA控制图对比研究,表明当过程失控时,可变抽样区间二项EWMA控制图具有较小的失控平均报警时间,能够迅速监测出过程中的异常波动,明显优于固定抽样区间的二项EWMA控制图。     

Reparameterized and Marginalized Posterior and Predictive Sampling for Complex Bayesian Geostatistical Models

This article proposes a four-pronged approach to efficient Bayesian estimation and prediction for complex Bayesian hierarchical Gaussian models for spatial and spatiotemporal data. The method involves reparameterizing the covariance structure of the model, reformulating the means structure, marginalizing the joint posterior distribution, and applying a simplex-based slice sampling algorithm. The approach permits fusion of point-source data and areal data measured at different resolutions and accommodates nonspatial correlation and variance heterogeneity as well as spatial and/or temporal correlation. The method produces Markov chain Monte Carlo samplers with low autocorrelation in the output, so that fewer iterations are needed for Bayesian inference than would be the case with other sampling algorithms. Supplemental materials are available online.     

Relational models for contingency tables

The paper considers general multiplicative models for complete and incomplete contingency tables that generalize log-linear and several other models and are entirely coordinate free. Sufficient conditions for the existence of maximum likelihood estimates under these models are given, and it is shown that the usual equivalence between multinomial and Poisson likelihoods holds if and only if an overall effect is present in the model. If such an effect is not assumed, the model becomes a curved exponential family and a related mixed parameterization is given that relies on non-homogeneous odds ratios. Several examples are presented to illustrate the properties and use of such models.     

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.     

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.     

Interruptible Exact Sampling in the Passive Case

We establish, for various scenarios, whether or not interruptible exact stationary sampling is possible when a finite-state Markov chain can only be viewed passively. In particular, we prove that such sampling is not possible using a single copy of the chain. Such sampling is possible when enough copies of the chain are available, and we provide an algorithm that terminates with probability one.     

多元对应分析在抽样调查分析中的应用

本文应用多元对应分析、聚类分析等数理统计方法 ,对抽样调查问卷进行分析 ,从而得出各类读者群的特征及它们之间的差异