A general class of scale-shape mixtures of skew-normal distributions: properties and estimation

This paper introduces the scale-shape mixtures of skew-normal (SSMSN) distributions which provide alternative candidates for modeling asymmetric data in a wide variety of settings. We obtain the moments and study some characterizations of the SSMSN distributions. Instead of resorting to numerical optimization procedures, two variants of EM algorithms are developed for carrying out maximum likelihood estimation. Our algorithms are analytically simple because closed-form expressions of conditional expectations in the E-step as well as the updating estimators in the M-step can be explicitly obtained. The observed information matrix is derived for approximating the asymptotic covariance matrix of parameter estimates. A simulation study is conducted to examine the finite sample properties of ML estimators. The utility of the proposed methodology is illustrated by analyzing a real example.     

Almost optimal solution of initial-value problems by randomized and quantum algorithms

We establish essentially optimal bounds on the complexity of initial-value problems in the randomized and quantum settings. For this purpose we define a sequence of new algorithms whose error/cost properties improve from step to step. These algorithms yield new upper complexity bounds, which differ from known lower bounds by only an arbitrarily small positive parameter in the exponent, and a logarithmic factor. In both the randomized and quantum settings, initial-value problems turn out to be essentially as difficult as scalar integration.     

Tabu Guided Generalized Hill Climbing Algorithms

This paper formulates tabu search strategies that guide generalized hill climbing (GHC) algorithms for addressing NP-hard discrete optimization problems. The resulting framework, termed tabu guided generalized hill climbing (TG²HC) algorithms, uses a tabu release parameter that probabilistically accepts solutions currently on the tabu list. TG²HC algorithms are modeled as a set of stationary Markov chains, where the tabu list is fixed for each outer loop iteration. This framework provides practitioners with guidelines for developing tabu search strategies to use in conjunction with GHC algorithms that preserve some of the algorithms known performance properties. In particular, sufficient conditions are obtained that indicate how to design iterations of problem-specific tabu search strategies, where the stationary distributions associated with each of these iterations converge to the distribution with zero weight on all non-optimal solutions.     

Randomized algorithms for total least squares problems

Motivated by the recently popular probabilistic methods for low‐rank approximations and randomized algorithms for the least squares problems, we develop randomized algorithms for the total least squares problem with a single right‐hand side. We present the Nyström method for the medium‐sized problems. For the large‐scale and ill‐conditioned cases, we introduce the randomized truncated total least squares with the known or estimated rank as the regularization parameter. We analyze the accuracy of the algorithm randomized truncated total least squares and perform numerical experiments to demonstrate the efficiency of our randomized algorithms. The randomized algorithms can greatly reduce the computational time and still maintain good accuracy with very high probability.     

Normal/Independent Distributions and Their Applications in Robust Regression

Abstract

Maximum likelihood estimation with nonnormal error distributions provides one method of robust regression. Certain families of normal/independent distributions are particularly attractive for adaptive, robust regression. This article reviews the properties of normal/independent distributions and presents several new results. A major virtue of these distributions is that they lend themselves to EM algorithms for maximum likelihood estimation. EM algorithms are discussed for least L_p regression and for adaptive, robust regression based on the t, slash, and contaminated normal families. Four concrete examples illustrate the performance of the different methods on real data.     

A randomized maximum cross-section method to simulate random structure systems with distributed transitions

In this paper, random structure systems with distributed transitions are considered. A theorem on the form of conditional structure distributions is proved. To simulate these distributions, a statistical algorithm using a randomized method of maximum cross-section is constructed. Also, a modified version of this algorithm using simulation with a single random number is constructed. The algorithms are used to simulate the numerical solution of random structure systems with distributed transitions. A theorem on weak convergence of a numerical solution obtained by the algorithms is proved.     

Folding characterization in conservative chaotic fluid flows

We study transport of passive scalar fields in a bidimensional incompressible chaotic fluid flow. For a spatially smooth velocity field with impulsive perturbations, the model is described by a randomized standard mapping. We numerically investigate passive scalar field transport for given initial concentration distributions and their dependence on the nonlinearity and noise amplitude. We show that space and time concentration histograms are determined by the underlying mechanism of stretching and folding. Moreover, to characterize this process we introduce a parameter, the average derivative of a tracer line length, which shows interesting scale properties.     

Bayesian Inversion of Piecewise Affine Operators in a Gaussian Framework

Piecewise affine inverse problems form a general class of nonlinear inverse problems. In particular inverse problems obeying certain variational structures, such as Fermat's principle in travel time tomography, are of this type. In a piecewise affine inverse problem a parameter is to be reconstructed when its mapping through a piecewise affine operator is observed, possibly with errors. A piecewise affine operator is defined by partitioning the parameter space and assigning a specific affine operator to each part. A Bayesian approach with a Gaussian random field prior on the parameter space is used. Both problems with a discrete finite partition and a continuous partition of the parameter space are considered.

The main result is that the posterior distribution is decomposed into a mixture of truncated Gaussian distributions, and the expression for the mixing distribution is partially analytically tractable. The general framework has, to the authors' knowledge, not previously been published, although the result for the finite partition is generally known.

Inverse problems are currently of large interest in many fields. The Bayesian approach is popular and most often highly computer intensive. The posterior distribution is frequently concentrated close to high-dimensional nonlinear spaces, resulting in slow mixing for generic sampling algorithms. Inverse problems are, however, often highly structured. In order to develop efficient sampling algorithms for a problem at hand, the problem structure must be exploited.

The decomposition of the posterior distribution that is derived in the current work can be used to develop specialized sampling algorithms. The article contains examples of such sampling algorithms. The proposed algorithms are applicable also for problems with exact observations. This is a case for which generic sampling algorithms tend to fail.     

Precomputing strategy for Hamiltonian Monte Carlo method based on regularity in parameter space

Markov Chain Monte Carlo (MCMC) algorithms play an important role in statistical inference problems dealing with intractable probability distributions. Recently, many MCMC algorithms such as Hamiltonian Monte Carlo (HMC) and Riemannian Manifold HMC have been proposed to provide distant proposals with high acceptance rate. These algorithms, however, tend to be computationally intensive which could limit their usefulness, especially for big data problems due to repetitive evaluations of functions and statistical quantities that depend on the data. This issue occurs in many statistic computing problems. In this paper, we propose a novel strategy that exploits smoothness (regularity) in parameter space to improve computational efficiency of MCMC algorithms. When evaluation of functions or statistical quantities are needed at a point in parameter space, interpolation from precomputed values or previous computed values is used. More specifically, we focus on HMC algorithms that use geometric information for faster exploration of probability distributions. Our proposed method is based on precomputing the required geometric information on a set of grids before running sampling algorithm and approximating the geometric information for the current location of the sampler using the precomputed information at nearby grids at each iteration of HMC. Sparse grid interpolation method is used for high dimensional problems. Tests on computational examples are shown to illustrate the advantages of our method.     

加速寿命试验Bayes估计算法的改进

本文就指数分布场合恒定应力加速寿命试验及Weibull分布场合序进应力加速寿命试验中参数的Bayes估计的显式表示提出了一种有效的改进算法,从而达到了减少计算误差和节省计算时间及内存资源的目的。     

Triple I algorithms based on Schweizer–Sklar operators in fuzzy reasoning

In this paper, we focus on the flexible inference method with parameters, that is the parametric triple I method by the combination of Schweizer–Sklar operators and triple I principles for fuzzy reasoning. Because the Schweizer–Sklar parameter m reflects the interaction between propositions in reasoning processes, the new parameterized triple I algorithms are closer to human reasoning in daily life. Also some properties of the new algorithms such as the reductivity, continuity and approximation are discussed. It is shown that some existing results are special cases of the new algorithms given here and in view of the variability of the parameter m the new algorithms have excellent flexibility in reasoning processes.     

High order Parzen windows and randomized sampling

In this paper high order Parzen windows stated by means of basic window functions are studied for understanding some algorithms in learning theory and randomized sampling in multivariate approximation. Learning rates are derived for the least-square regression and density estimation on bounded domains under some decay conditions on the marginal distributions near the boundary. These rates can be almost optimal when the marginal distributions decay fast and the order of the Parzen windows is large enough. For randomized sampling in shift-invariant spaces, we consider the situation when the sampling points are neither i.i.d. nor regular, but are noised from regular grids by probability density functions. The approximation orders are estimated by means of the regularity of the approximated function and the density function and the order of the Parzen windows.     

MIRHA: multi-start biased randomization of heuristics with adaptive local search for solving non-smooth routing problems

This paper discusses the use of probabilistic or randomized algorithms for solving vehicle routing problems with non-smooth objective functions. Our approach employs non-uniform probability distributions to add a biased random behavior to the well-known savings heuristic. By doing so, a large set of alternative good solutions can be quickly obtained in a natural way and without complex configuration processes. Since the solution-generation process is based on the criterion of maximizing the savings, it does not need to assume any particular property of the objective function. Therefore, the procedure can be especially useful in problems where properties such as non-smoothness or non-convexity lead to a highly irregular solution space, for which the traditional optimization methods—both of exact and approximate nature—may fail to reach their full potential. The results obtained so far are promising enough to suggest that the idea of using biased probability distributions to randomize classical heuristics is a powerful one that can be successfully applied in a variety of cases.     

Approximating Probability Distributions Using Small Sample Spaces

We formulate the notion of a "good approximation" to a probability distribution over a finite abelian group ?. The quality of the approximating distribution is characterized by a parameter ɛ which is a bound on the difference between corresponding Fourier coefficients of the two distributions. It is also required that the sample space of the approximating distribution be of size polynomial in and 1/ɛ. Such approximations are useful in reducing or eliminating the use of randomness in certain randomized algorithms. We demonstrate the existence of such good approximations to arbitrary distributions. In the case of n random variables distributed uniformly and independently over the range , we provide an efficient construction of a good approximation. The approximation constructed has the property that any linear combination of the random variables (modulo d) has essentially the same behavior under the approximating distribution as it does under the uniform distribution over . Our analysis is based on Weil's character sum estimates. We apply this result to the construction of a non-binary linear code where the alphabet symbols appear almost uniformly in each non-zero code-word. Received: September 22, 1990/Revised: First revision November 11, 1990; last revision November 10, 1997     

Preservation of transform orders under a semiparametric model and its mixture

In this paper, sufficient conditions for preservation of several transform orders under a typical family of semiparametric distributions are made. The preservation properties are developed to compare mixture semiparametric distributions. Possible applications of the achieved results to compare scale family of distributions and also compare coherent systems with dependent but identical components and series and parallel systems with randomized number of components are provided.     

Optimal Scaling of Random Walk Metropolis Algorithms with Non-Gaussian Proposals

The asymptotic optimal scaling of random walk Metropolis (RWM) algorithms with Gaussian proposal distributions is well understood for certain specific classes of target distributions. These asymptotic results easily extend to any light tailed proposal distribution with finite fourth moment. However, heavy tailed proposal distributions such as the Cauchy distribution are known to have a number of desirable properties, and in many situations are preferable to light tailed proposal distributions. Therefore we consider the question of scaling for Cauchy distributed proposals for a wide range of independent and identically distributed (iid) product densities. The results are somewhat surprising as to when and when not Cauchy distributed proposals are preferable to Gaussian proposal distributions. This provides motivation for finding proposal distributions which improve on both Gaussian and Cauchy proposals, both for finite dimensional target distributions and asymptotically as the dimension of the target density, d → ∞. Throughout we seek the scaling of the proposal distribution which maximizes the expected squared jumping distance (ESJD).     

Efficient computation of sparse structures

Basic graph structures such as maximal independent sets (MIS's) have spurred much theoretical research in randomized and distributed algorithms, and have several applications in networking and distributed computing as well. However, the extant (distributed) algorithms for these problems do not necessarily guarantee fault‐tolerance or load‐balance properties. We propose and study “low‐average degree” or “sparse” versions of such structures. Interestingly, in sharp contrast to, say, MIS's, it can be shown that checking whether a structure is sparse, will take substantial time. Nevertheless, we are able to develop good sequential/distributed (randomized) algorithms for such sparse versions. We also complement our algorithms with several lower bounds. Randomization plays a key role in our upper and lower bound results. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 322–344, 2016     

两多维样本模型中位置参数相等性的M-检验

本文给出了基于投影寻踪方法检验两多维样本位置参数相等的M 统计量和t 统计量,分别用PP型自助M 统计量和PP型自助t 统计量给出了上述两统计量的近似分布, 并给出了检验的算法,进行一些模拟.     

Approximations and Randomization to Boost CSP Techniques

In recent years we have seen an increasing interest in combining constraint satisfaction problem (CSP) formulations and linear programming (LP) based techniques for solving hard computational problems. While considerable progress has been made in the integration of these techniques for solving problems that exhibit a mixture of linear and combinatorial constraints, it has been surprisingly difficult to successfully integrate LP-based and CSP-based methods in a purely combinatorial setting. Our approach draws on recent results on approximation algorithms based on LP relaxations and randomized rounding techniques, with theoretical guarantees, as well on results that provide evidence that the runtime distributions of combinatorial search methods are often heavy-tailed. We propose a complete randomized backtrack search method for combinatorial problems that tightly couples CSP propagation techniques with randomized LP-based approximations. We present experimental results that show that our hybrid CSP/LP backtrack search method outperforms the pure CSP and pure LP strategies on instances of a hard combinatorial problem.     

On the characterization of fisher information and stability of the least favorable lattice distributions

The paper is concerned with the stability properties of the least favorable distributions minimizing the Fisher information in a given class of distributions. The derivation of a least favorable distribution (the solution of a variational problem) is a necessary stage of the Huber minimax approach in robust estimation of a location parameter. Generally, the solutions of variational problems essentially depend on the regularity restrictions of a functional class. The stability of these optimal solutions to violations of the smoothness restrictions is studied under the lattice distribution classes. The discrete analogues of Fisher information are obtained in these cases. They have the form of the Hellinger metrics with the estimation of a real continuous location parameter and the form of the X² metrics with the estimation of an integer discrete location parameter. The analytical expressions for the corresponding least favorable discrete distributions are derived in some classes of lattice distributions by means of generating functions and Bellman's recursive functional equations of dynamic programming. These classes include the class of nondegenerate distributions with a restriction on the value of the density in the center of symmetry, the class of finite distributions, and the class of contaminated distributions. The obtained least favorable lattice distributions preserve the structure of their prototypes in the continuous case. These results show the stability of robust minimax solutions under different types of transitions from the continuous distribution to the discrete one. Proceedings of the Seminar on Stability Problems for Stochastic Models, Hajduszoboszló, Hungary, 1997, Part II.