A computational study of graph partitioning

LetG = (N, E) be an edge-weighted undirected graph. The graph partitioning problem is the problem of partitioning the node setN intok disjoint subsets of specified sizes so as to minimize the total weight of the edges connecting nodes in distinct subsets of the partition. We present a numerical study on the use of eigenvalue-based techniques to find upper and lower bounds for this problem. Results for bisecting graphs with up to several thousand nodes are given, and for small graphs some trisection results are presented. We show that the techniques are very robust and consistently produce upper and lower bounds having a relative gap of typically a few percentage points.Corresponding author.     

混合Weibull分布参数估计的ECM算法

混合威布尔分布是寿命数据分析中一个重要的统计模型.但是利用传统的统计方法,如矩估计、极大似然估计等估计模型的参数比较困难.应用ECM算法详细研究了混合威布尔分布在正常工作条件下,完全数据场合、Ⅰ-型截尾和Ⅱ-截尾场合的参数估计问题.数据模拟表明利用ECM算法来估计混合威布尔分布是一种有效的方法.     

Rank-Score Tests in Factorial Designs with Repeated Measures

Nonparametric factorial designs for multivariate observations are considered under the framework of general rank-score statistics. Unlike most of the literature, we do not assume the continuity of the underlying distribution functions. The models studied include general repeated measures designs, compound symmetry designs, and designs for longitudinal data. In particular, designs for ordered categorical data are included. The vectors of the multivariate observations may have different lengths. Moreover, our general framework includes missing values and singular covariance matrices which occur quite frequently in practical data analysis problems. The asymptotic properties of the proposed statistics are studied under general nonparametric hypotheses as well as under a sequence of nonparametric contiguous alternatives. L₂-consistent estimators for the unknown covariance matrices are given and two types of quadratic forms are considered for testing the nonparametric hypotheses. The results are applied to a two-way mixed model assuming compound symmetry and to a factorial design for longitudinal data. The main idea of the proofs is based on some moment inequalities for empirical distribution functions in mixed models. The details are provided in the Appendix.     

Diversification-consistent data envelopment analysis with general deviation measures

We propose new efficiency tests which are based on traditional DEA models and take into account portfolio diversification. The goal is to identify the investment opportunities that perform well without specifying our attitude to risk. We use general deviation measures as the inputs and return measures as the outputs. We discuss the choice of the set of investment opportunities including portfolios with limited number of assets. We compare the optimal values (efficiency scores) of all proposed tests leading to the relations between the sets of efficient opportunities. Strength of the tests is then discussed. We test the efficiency of 25 world financial indices using new DEA models with CVaR deviation measures.     

Mediated digraphs and quantum nonlocality

A digraph D=(V,A) is mediated if for each pair x,y of distinct vertices of D, either xyA or yxA or there is a vertex z such that both xz,yzA. For a digraph D, Δ^-(D) is the maximum in-degree of a vertex in D. The nth mediation number μ(n) is the minimum of Δ^-(D) over all mediated digraphs on n vertices. Mediated digraphs and μ(n) are of interest in the study of quantum nonlocality.We obtain a lower bound f(n) for μ(n) and determine infinite sequences of values of n for which μ(n)=f(n) and μ(n)>f(n), respectively. We derive upper bounds for μ(n) and prove that μ(n)=f(n)(1+o(1)). We conjecture that there is a constant c such that μ(n)f(n)+c. Methods and results of design theory and number theory are used.     

A Two-Dimensional Ellipse–Rectangle Intersection Test

We present an efficient algorithm for testing whether or not a filled rectangle and a filled ellipse intersect. The algorithm requires at most two evaluations of the quadratic polynomial that defines the ellipse and the execution of a few simple arithmetic expressions. The convexity and monotonicity properties of this polynomial are the main tools for the design of the algorithm.     

Formulae and Recursions for the Joint Distribution of Success Runs of Several Lengths

Consider a sequence of n independent Bernoulli trials with the j-th trial having probability pj of success, 1 j n. Let M(n,K) and N(n, K) denote, respectively, the r-dimensional random variables (M(n, k1),..., M(n,kr) and (N(n,k1), ..., N(n, kr)), where K = (k1, k2, ..., kr) and M(n, s) [N(n, s)] represents the number of overlapping [non-overlapping] success runs of length s. We obtain exact formulae and recursions for the probability distributions of M(n, K) and N(n, K). The techniques of proof employed include the inclusion-exclusion principle and generating function methodology. Our results have potential applications to statistical tests for randomness.     

Testing the tail–dependence based on the radial component

Throughout this article we assume that the df H of a random vector (X,Y) is in the max-domain of attraction of an extreme value distribution function (df) G with reverse exponential margins. Therefore, the asymptotic dependence structure of H can be represented by a Pickands dependence function D with D = 1 representing the case of asymptotic independence. One of our aims is to test the null hypothesis of tail-dependence against the alternative of tail-independence. Thus we want to prove the validity of the model where D = 1. The test is based on the radial component X + Y. Under a certain spectral expansion it is verified that the df of X + Y, conditioned on X + Y > c, converges to F(t) = t, as c ↑0, if D ≠ 1 and, respectively, to F(t) = t ^1 + ρ , if D = 1, where ρ > 0 determines the rate at which independence is attained. Based on the limiting dfs we find a uniformly most powerful test procedure for testing tail-dependence against rates of tail-independence. In addition, an estimator of the parameter ρ is proposed. The relationship of ρ to another dependence measure, given in the literature, is indicated.      

Asymptotic Null Distributions of Stationarity and Nonstationarity Tests Under Local-to-finite Variance Errors

The purpose of this paper is to investigate the asymptotic null distribution of stationarity and nonstationarity tests when the distribution of the error term belongs to the normal domain of attraction of a stable law in any finite sample but the error term is an i.i.d. process with finite variance as . This local-to-finite variance setup is helpful to highlight the behavior of test statistics under the null hypothesis in the borderline or near borderline cases between finite and infinite variance and to assess the robustness of these test statistics to small departures from the standard finite variance context. From an empirical point of view, our analysis can be useful in settings where the (non)-existence of the (second) moments is not clear-cut, such as, for example, in the analysis of financial time series. A Monte Carlo simulation study is performed to improve our understanding of the practical implications of the limi theory we develop. The main purpose of the simulation experiment is to assess the size distortion of the unit root and stationarity tests under investigation.     

The advantage of decomposing elaborate hypotheses on covariance matrices into conditionally independent hypotheses in building near-exact distributions for the test statistics

The aim of this paper is to show how the decomposition of elaborate hypotheses on the structure of covariance matrices into conditionally independent simpler hypotheses, by inducing the factorization of the overall test statistic into a product of several independent simpler test statistics, may be used to obtain near-exact distributions for the overall test statistics, even in situations where asymptotic distributions are not available in the literature and adequately fit ones are not easy to obtain.