Markov chain Monte Carlo exact tests for incomplete two-way contingency tables

We consider testing the quasi-independence hypothesis for two-way contingency tables which contain some structural zero cells. For sparse contingency tables where the large sample approximation is not adequate, the Markov chain Monte Carlo exact tests are powerful tools. To construct a connected chain over the two-way contingency tables with fixed sufficient statistics and an arbitrary configuration of structural zero cells, an algebraic algorithm proposed by Diaconis and Sturmfels [Diaconis, P. and Sturmfels, B. (1998). The Annals of statistics, 26, pp. 363–397.] can be used. However, their algorithm does not seem to be a satisfactory answer, because the Markov basis produced by the algorithm often contains many redundant elements and is hard to interpret. We derive an explicit characterization of a minimal Markov basis, prove its uniqueness, and present an algorithm for obtaining the unique minimal basis. A computational example and the discussion on further basis reduction for the case of positive sufficient statistics are also given.     

A hybrid elitist pareto-based coordinate exchange algorithm for constructing multi-criteria optimal experimental designs

This paper presents a new Pareto-based coordinate exchange algorithm for populating or approximating the true Pareto front for multi-criteria optimal experimental design problems that arise naturally in a range of industrial applications. This heuristic combines an elitist-like operator inspired by evolutionary multi-objective optimization algorithms with a coordinate exchange operator that is commonly used to construct optimal designs. Benchmarking results from both a two-dimensional and three-dimensional example demonstrate that the proposed hybrid algorithm can generate highly reliable Pareto fronts with less computational effort than existing procedures in the statistics literature. The proposed algorithm also utilizes a multi-start operator, which makes it readily parallelizable for high performance computing infrastructures.     

An Optimal Reliability and Maintainability Design of a Searching System

In this article, we deal with an optimal reliability and maintainability design problem of a searching system with complex structures. The system availability and life cycle cost are used as optimization criteria and estimated by simulation. We want to determine MTBF (Mean Time between Failures) and MTTR (Mean Time to Repair) for all components and ALDT (Administrative and Logistics Delay Times) of the searching system in order to minimize the life cycle cost and to satisfy the target system availability. A hybrid genetic algorithm with a heuristic method is proposed to find near-optimal solutions and compared with a general genetic algorithm.     

A new metamodel-based method for solving semi-expensive simulation optimization problems

In this article, a new algorithm for rather expensive simulation problems is presented, which consists of two phases. In the first phase, as a model-based algorithm, the simulation output is used directly in the optimization stage. In the second phase, the simulation model is replaced by a valid metamodel. In addition, a new optimization algorithm is presented. To evaluate the performance of the proposed algorithm, it is applied to the (s,S) inventory problem as well as to five test functions. Numerical results show that the proposed algorithm leads to better solutions with less computational time than the corresponding metamodel-based algorithm.     

On capacity evaluation for multi-state weighted k-out-of-n system

ABSTRACT

Weighted k-out-of-n system has been widely used in various engineering areas. Performance of such system is characterized by the total capacity of the components. Therefore, capacity evaluation is of great importance for research on the behavior of the system over time. Capacity evaluation for binary weighted k-out-of-n system has been reported in the literature. In this paper, to shorten computational time, we first develop a multiplication method for capacity evaluation of binary weighted k-out-of-n system. We then generalize capacity evaluation to multi-state weighted k-out-of-n system. Recursive algorithm and multiplication algorithm are developed for capacity evaluation for such system. Comparison is made of the two methods in different aspects. An illustrative example of an oil transmission system is presented to demonstrate the implementation of the proposed methods.     

Optimal Configuration of a Square Array Group Testing Algorithm

We consider the optimal configuration of a square array group testing algorithm (denoted A2) to minimize the expected number of tests per specimen. For prevalence greater than 0.2498, individual testing is shown to be more efficient than A2. For prevalence less than 0.2498, closed form lower and upper bounds on the optimal group sizes for A2 are given. Arrays of dimension 2 × 2, 3 × 3, and 4 × 4 are shown to never be optimal. The results are illustrated by considering the design of a specimen pooling algorithm for detection of recent HIV infections in Malawi.     

Improving Path Trimming in a Network Algorithm for Fisher's Exact Test in Two-way Contingency Tables

This article provides an improvement of the network algorithm for calculating the exact p value of the generalized Fisher's exact test in two-way contingency tables. We give a new exact upper bound and an approximate upper bound for the maximization problems encountered in the network algorithm. The approximate bound has some very desirable computational properties and the meaning is elucidated from a viewpoint of differential geometry. Our proposed procedure performs well regardless of the pattern of marginal totals of data.     

System Reliability Assessment through p Minimal Paths in Stochastic Case with Backup-routing

For a stochastic-flow network in which each arc has several possible capacities, we assess the probability that a given amount of data are sent through p(p ≥ 2) minimal paths simultaneously subject to time threshold. Such a probability is named the system reliability. Without knowing all minimal paths, a solution procedure is first proposed to calculate it. Furthermore, the backup-routing is established in advance to declare the first and the second priority p minimal paths in order to enhance the system reliability. Subsequently, the system reliability according to the backup-routing can be computed easily.     

Reliability evaluation subject to assured accuracy rate and time for stochastic unreliable-node computer networks

In many real-life networks such as computer networks, branches and nodes have multi-state capacity, lead time, and accuracy rate. The network with unreliable nodes is more complex to evaluate the reliability because node failure results in the disabled of adjacent branches. Such a network is named a stochastic unreliable-node computer network (SUNCN). Under the strict assumption that each component (branch and node) has a deterministic capacity, the quickest path (QP) problem is to find a path sending a specific amount of data with minimum transmission time. The accuracy rate is a critical index to measure the performance of a computer network because some packets are damaged or lost due to voltage instability, magnetic field effects, lightning, etc. Subject to both assured accuracy rate and time constraints, this paper extends the QP problem to discuss the system reliability of an SUNCN. An efficient algorithm based on a graphic technique is proposed to find the minimal capacity vector meeting such constraints. System reliability, the probability to send a specific amount of data through multiple minimal paths subject to both assured accuracy rate and time constraints, can subsequently be computed.     

Classification using distance nearest neighbours

This paper proposes a new probabilistic classification algorithm using a Markov random field approach. The joint distribution of class labels is explicitly modelled using the distances between feature vectors. Intuitively, a class label should depend more on class labels which are closer in the feature space, than those which are further away. Our approach builds on previous work by Holmes and Adams (J. R. Stat. Soc. Ser. B 64:295–306, 2002; Biometrika 90:99–112, 2003) and Cucala et al. (J. Am. Stat. Assoc. 104:263–273, 2009). Our work shares many of the advantages of these approaches in providing a probabilistic basis for the statistical inference. In comparison to previous work, we present a more efficient computational algorithm to overcome the intractability of the Markov random field model. The results of our algorithm are encouraging in comparison to the k-nearest neighbour algorithm.     

UPPER BOUNDS FOR THE HARMONIC MEAN, WITH AN APPLICATION TO EXPERIMENTAL DESIGN

For positive-valued random variables, the paper provides a sequence of upper bounds for the harmonic mean, the ith of these bounds being exact if and only if the random variable is essentially i-valued. Sufficient conditions for the convergence of the bounds to the harmonic mean are given. The bounds have a number of applications, particularly in experimental design where they may be used to check how close a given design is to A-optimality     

Distributed inference for two-sample U-statistics in massive data analysis

This paper considers distributed inference for two-sample U-statistics under the massive data setting. In order to reduce the computational complexity, this paper proposes distributed two-sample U-statistics and blockwise linear two-sample U-statistics. The blockwise linear two-sample U-statistic, which requires less communication cost, is more computationally efficient especially when the data are stored in different locations. The asymptotic properties of both types of distributed two-sample U-statistics are established. In addition, this paper proposes bootstrap algorithms to approximate the distributions of distributed two-sample U-statistics and blockwise linear two-sample U-statistics for both nondegenerate and degenerate cases. The distributed weighted bootstrap for the distributed two-sample U-statistic is new in the literature. The proposed bootstrap procedures are computationally efficient and are suitable for distributed computing platforms with theoretical guarantees. Extensive numerical studies illustrate that the proposed distributed approaches are feasible and effective.     

A note on exact calculation of the non central hypergeometric distribution

Direct calculation of the non central hypergeometric (NH) distribution and its moments can present computational issues in both efficiency and accuracy. In response, several methods, both approximate and exact, for calculating the NH mean and variance have appeared in the literature. We add to this body of work, a straight-forward, exact method that is easily programed, efficient, and computationally stable. Specifically, by considering the logs of the values of the NH probability mass function (pmf) and then shifting the exponents so that, prior to normalization, the mode acquires a value of 1, concerns for overflow are eliminated.     

Exact distribution of the MLEs of the parameters and of the quantiles of two-parameter exponential distribution under hybrid censoring

Epstein [Truncated life tests in the exponential case, Ann. Math. Statist. 25 (1954), pp. 555–564] introduced a hybrid censoring scheme (called Type-I hybrid censoring) and Chen and Bhattacharyya [Exact confidence bounds for an exponential parameter under hybrid censoring, Comm. Statist. Theory Methods 17 (1988), pp. 1857–1870] derived the exact distribution of the maximum-likelihood estimator (MLE) of the mean of a scaled exponential distribution based on a Type-I hybrid censored sample. Childs et al. [Exact likelihood inference based on Type-I and Type-II hybrid censored samples from the exponential distribution, Ann. Inst. Statist. Math. 55 (2003), pp. 319–330] provided an alternate simpler expression for this distribution, and also developed analogous results for another hybrid censoring scheme (called Type-II hybrid censoring). The purpose of this paper is to derive the exact bivariate distribution of the MLE of the parameter vector of a two-parameter exponential model based on hybrid censored samples. The marginal distributions are derived and exact confidence bounds for the parameters are obtained. The results are also used to derive the exact distribution of the MLE of the pth quantile, as well as the corresponding confidence bounds. These exact confidence intervals are then compared with parametric bootstrap confidence intervals in terms of coverage probabilities. Finally, we present some numerical examples to illustrate the methods of inference developed here.     

Network reliability for multipath TCP networks with a retransmission mechanism under the time constraint

It is essential to reduce data latency and guarantee quality of service for modern computer networks. The emerging networking protocol, Multipath Transmission Control Protocol, can reduce data latency by transmitting data through multiple minimal paths (MPs) and ensure data integrity by the packets retransmission mechanism. The bandwidth of each edge can be considered as multi-state in computer networks because different situations, such as failures, partial failures and maintenance, exist. We evaluate network reliability for a multi-state retransmission flow network through which the data can be successfully transmitted by means of multiple MPs under the time constraint. By generating all minimal bandwidth patterns, the proposed algorithm can satisfy these requirements to calculate network reliability. An example and a practical case of the Pan-European Research and Education Network are applied to demonstrate the proposed algorithm.     

Computing projection depth and its associated estimators

To facilitate the application of projection depth, an exact algorithm is proposed from the view of cutting a convex polytope with hyperplanes. Based on this algorithm, one can obtain a finite number of optimal direction vectors, which are x-free and therefore enable us (Liu et al., Preprint, 2011) to compute the projection depth and most of its associated estimators of dimension p≥2, including Stahel-Donoho location and scatter estimators, projection trimmed mean, projection depth contours and median, etc. Both real and simulated examples are also provided to illustrate the performance of the proposed algorithm.     

The distribution of cook's d statistic

Cook (1977) proposed a diagnostic to quantify the impact of deleting an observation on the estimated regression coefficients of a General Linear Univariate Model (GLUM). Simulations of models with Gaussian response and predictors demonstrate that his suggestion of comparing the diagnostic to the median of the F for overall regression captures an erratically varying proportion of the values.

We describe the exact distribution of Cook's statistic for a GLUM with Gaussian predictors and response. We also present computational forms, simple approximations, and asymptotic results. A simulation supports the accuracy of the results. The methods allow accurate evaluation of a single value or the maximum value from a regression analysis. The approximations work well for a single value, but less well for the maximum. In contrast, the cut-point suggested by Cook provides widely varying tail probabilities. As with all diagnostics, the data analyst must use scientific judgment in deciding how to treat highlighted observations.     

A fast general extension algorithm of Latin hypercube sampling

A fast general extension algorithm of Latin hypercube sampling (LHS) is proposed, which reduces the time consumption of basic general extension and preserves the most original sampling points. The extension algorithm starts with an original LHS of size m and constructs a new LHS of size m?+?n that remains the original points. This algorithm is the further research of basic general extension, which cost too much time to get the new LHS. During selecting the original sampling points to preserve, time consumption is cut from three aspects. The first measure of the proposed algorithm is to select isolated vertices and divide the adjacent matrix into blocks. Secondly, the relationship of original LHS structure and new LHS structure is discussed. Thirdly, the upper and lower bounds help reduce the time consumption. The proposed algorithm is applied for two functions to demonstrate the effectiveness.     

An efficient algorithm for estimating the parameters of superimposed exponential signals

An efficient computational algorithm is proposed for estimating the parameters of undamped exponential signals, when the parameters are complex valued. Such data arise in several areas of applications including telecommunications, radio location of objects, seismic signal processing and computer assisted medical diagnostics. It is observed that the proposed estimators are consistent and the dispersion matrix of these estimators is asymptotically the same as that of the least squares estimators. Moreover, the asymptotic variances of the proposed estimators attain the Cramer–Rao lower bounds, when the errors are Gaussian.     

Efficient time/space algorithm to compute rectangular probabilities of multinomial, multivariate hypergeometric and multivariate Pólya distributions

The computation of rectangular probabilities of multivariate discrete integer distributions such as the multinomial, multivariate hypergeometric or multivariate Pólya distributions is of great interest both for statistical applications and for probabilistic modeling purpose. All these distributions are members of a broader family of multivariate discrete integer distributions for which computationaly efficient approximate methods have been proposed for the evaluation of such probabilities, but with no control over their accuracy. Recently, exact algorithms have been proposed for computing such probabilities, but they are either dedicated to a specific distribution or to very specific rectangular probabilities. We propose a new algorithm that allows to perform the computation of arbitrary rectangular probabilities in the most general case. Its accuracy matches or even outperforms the accuracy exact algorithms when the rounding errors are taken into account. In the worst case, its computational cost is the same as the most efficient exact method published so far, and is much lower in many situations of interest. It does not need any additional storage than the one for the parameters of the distribution, which allows to deal with large dimension/large counting parameter applications at no extra memory cost and with an acceptable computation time, which is a major difference with respect to the methods published so far.