Sampling contingency tables

We give polynomial time algorithms for random sampling from a set of contingency tables, which is the set of m×n matrices with given row and column sums, provided the row and column sums are sufficiently large with respect to m, n. We use this to approximately count the number of such matrices. These problems are of interest in Statistics and Combinatorics. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 10 , 487–506, 1997     

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     

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     

Perfect simulation of processes with long memory: A “coupling into and from the past” algorithm

We describe a new algorithm for the perfect simulation of variable length Markov chains and random systems with perfect connections. This algorithm, which generalizes Propp and Wilson's simulation scheme, is based on the idea of coupling into and from the past. It improves on existing algorithms by relaxing the conditions on the kernel and by accelerating convergence, even in the simple case of finite order Markov chains. Although chains of variable or infinite order have been widely investigated for decades, their use in applied probability, from information theory to bio‐informatics and linguistics, has recently led to considerable renewed interest. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 46, 300–319, 2015     

A perfect sampling method for exponential family random graph models

Generation of deviates from random graph models with nontrivial edge dependence is an increasingly important problem. Here, we introduce a method which allows perfect sampling from random graph models in exponential family form (“exponential family random graph” models), using a variant of Coupling From The Past. We illustrate the use of the method via an application to the Markov graphs, a family that has been the subject of considerable research. We also show how the method can be applied to a variant of the biased net models, which are not exponentially parameterized.     

Speeding up the FMMR perfect sampling algorithm: A case study revisited

In a previous paper by the second author, two Markov chain Monte Carlo perfect sampling algorithms—one called coupling from the past (CFTP) and the other (FMMR) based on rejection sampling—are compared using as a case study the move‐to‐front (MTF) self‐organizing list chain. Here we revisit that case study and, in particular, exploit the dependence of FMMR on the user‐chosen initial state. We give a stochastic monotonicity result for the running time of FMMR applied to MTF and thus identify the initial state that gives the stochastically smallest running time; by contrast, the initial state used in the previous study gives the stochastically largest running time. By changing from worst choice to best choice of initial state we achieve remarkable speedup of FMMR for MTF; for example, we reduce the running time (as measured in Markov chain steps) from exponential in the length n of the list nearly down to n when the items in the list are requested according to a geometric distribution. For this same example, the running time for CFTP grows exponentially in n. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2003     

Perfect simulation with exponential tails on the running time

Monte Carlo algorithms typically need to generate random variates from a probability distribution described by an unnormalized density or probability mass function. Perfect simulation algorithms generate random variates exactly from these distributions, but have a running time T that is itself an unbounded random variable. This article shows that commonly used protocols for creating perfect simulation algorithms, such as Coupling From the Past can be used in such a fashion that the running time is unlikely to be very much larger than the expected running time. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

One-Shot CFTP; Application to a Class of Truncated Gaussian Densities

In this paper, we introduce a new method for perfect simulation of multivariate densities. We use One-Shot CFTP (G. Roberts and J. Rosenthal, “One-shot coupling for certain stochastic recursive sequences,” Stochastic Processes and their Applications vol. 99 pp. 195–208, 2002) together with a monotone coupler for the Gibbs sampler, and implement the algorithm within the Read-Once CFTP protocol (D. B. Wilson, “How to couple form the past using a read-once source of randomness,” Random Structures and Algorithms vol. 16(1) pp. 85–113, 2000b). We illustrate our method by simulating efficiently from high-dimensional truncated normal distributions using the Gibbs sampler. AMS 2000 Subject Classification Primary 65C40; Secondary 65C60     

A new system of skip‐lot sampling plans having a provision for reducing normal inspection

The skip‐lot sampling program can be used for reducing the amount of inspection on a product that has excellent quality history. Thus skip‐lot sampling plans are designed to reduce inspection costs. Moreover, the skip‐lot concept is sound and useful and is economically advantageous to use in the design of sampling plans. Hence, a new system of skip‐lot sampling plans designated as the SkSP‐V plan is developed in this paper. The proposed plan requires a return to normal inspection whenever a lot is rejected during sampling inspection, but has a provision for a reduced normal inspection upon demonstration of superior product quality. A Markov chain formulation and derivation of performance measures for this new plan are presented. The properties of SkSP‐V plan are studied with single sampling plan as the reference plan. Advantages of this new plan are also discussed. Finally, certain cost models are given for the economic design of the SkSP‐V plan. Copyright © 2010 John Wiley & Sons, Ltd.     

Space‐time spectral method for two‐dimensional semilinear parabolic equations

In this paper, a high‐order accurate numerical method for two‐dimensional semilinear parabolic equations is presented. We apply a Galerkin–Legendre spectral method for discretizing spatial derivatives and a spectral collocation method for the time integration of the resulting nonlinear system of ordinary differential equations. Our formulation can be made arbitrarily high‐order accurate in both space and time. Optimal a priori error bound is derived in the L²‐norm for the semidiscrete formulation. Extensive numerical results are presented to demonstrate the convergence property of the method, show our formulation have spectrally accurate in both space and time. John Wiley & Sons, Ltd.     

Decay in time for a one‐dimensional two‐component plasma

The motion of a collisionless plasma is described by the Vlasov–Poisson (VP) system, or in the presence of large velocities, the relativistic VP system. Both systems are considered in one space and one momentum dimension, with two species of oppositely charged particles. A new identity is derived for both systems and is used to study the behavior of solutions for large times. Copyright © 2008 John Wiley & Sons, Ltd.     

On mixing times for stratified walks on the d‐cube

Using the electric and coupling approaches, we derive a series of results concerning the mixing times for the stratified random walk on the d‐cube, inspired in the results of Chung and Graham (1997) [Random Struct. Alg., 11, 199–122]. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 20: 540–552, 2002     

A practical two‐term acceleration algorithm for linear systems

In this paper, a practical two‐term acceleration algorithm is proposed, the interval of the parameter which guarantees the convergence of the acceleration algorithm is analyzed in detail. Further, the acceleration ratio of the new acceleration algorithm is obtained in advance. The new acceleration algorithm is less sensitive to the parameter than the Chebyshev semi‐iterative method. Finally, some numerical examples show that the accelerated algorithm is effective. Copyright © 2011 John Wiley & Sons, Ltd.     

A new two‐stage algorithm for solving power flow tracing

This article proposed a new hybrid algorithm for solving power flow tracing (PFT) through the comparison by other techniques. This proposed hybrid strategy in detail discuses over the achieved results. Both methods use the active and reactive power balance equations at each bus to solve the tracing problem, where the first method considers the proportional sharing assumption and the second one considers the circuit laws to find the relationship between power inflows and outflows through each line, generator, and load connected to each bus of the network. Both algorithms are able to handle loop flow and loss issues in tracing the problem. A mathematical formulation is also introduced to find the share of each unit in provision of each load. These algorithms are employed to find the producer and consumer's shares on the cost of transmission for each line in different case studies. As the results of these studies show, both algorithms can effectively solve the PFT problem. © 2014 Wiley Periodicals, Inc. Complexity 21: 187–194, 2015     

Perfect simulation and inference for point processes given noisy observations

Summary  The paper is concerned with the exact simulation of an unobserved true point process conditional on a noisy observation. We use dominated coupling from the past (CFTP) on an augmented state space to produce perfect samples of the target marked point process. An optimized coupling of the target chains makes the algorithm considerable faster than with the standard coupling used in dominated CFTP for point processes. The perfect simulations are used for inference and the results are compared to an ordinary Metropolis-Hastings sampler.     

A decoupling two‐grid algorithm for the mixed Stokes‐Darcy model with the Beavers‐Joseph interface condition

In this article, a decoupling scheme based on two‐grid finite element for the mixed Stokes‐Darcy problem with the Beavers‐Joseph interface condition is proposed and investigated. With a restriction of a physical parameter α, we derive the numerical stability and error estimates for the scheme. Numerical experiments indicate that such two‐grid based decoupling finite element schemes are feasible and efficient. © 2014 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 30: 1066–1082, 2014     

The linear sampling method for the inverse electromagnetic scattering by a partially coated bi‐periodic structure

In this paper, we consider the inverse problem of recovering a doubly periodic Lipschitz structure through the measurement of the scattered field above the structure produced by point sources lying above the structure. The medium above the structure is assumed to be homogeneous and lossless with a positive dielectric coefficient. Below the structure is a perfect conductor partially coated with a dielectric. A periodic version of the linear sampling method is developed to reconstruct the doubly periodic structure using the near field data. In this case, the far field equation defined on the unit ball of ?³ is replaced by the near field equation which is a linear integral equation of the first kind defined on a plane above the periodic surface. Copyright © 2010 John Wiley & Sons, Ltd.     

Asymptotic finite‐time ruin probabilities for a class of path‐dependent heavy‐tailed claim amounts using Poisson spacings

In the compound Poisson risk model, several strong hypotheses may be found too restrictive to describe accurately the evolution of the reserves of an insurance company. This is especially true for a company that faces natural disaster risks like earthquake or flooding. For such risks, claim amounts are often inter‐dependent and they may also depend on the history of the natural phenomenon. The present paper is concerned with a situation of this kind, where each claim amount depends on the previous claim inter‐arrival time, or on past claim inter‐arrival times in a more complex way. Our main purpose is to evaluate, for large initial reserves, the asymptotic finite‐time ruin probabilities of the company when the claim sizes have a heavy‐tailed distribution. The approach is based more particularly on the analysis of spacings in a conditioned Poisson process. Copyright © 2010 John Wiley & Sons, Ltd.