Functions of elementary random variables and their application to system reliability

Summary LetX ₁,...,X _n be elementary random variables, i.e. random variables taking only finitely many values in . Then for an arbitray functionf(X ₁,...,X _n ) inX ₁,...,X _n a unique polynomial representation with the aid of Lagrange polynomials is given. This easily yields the moments as well as the distribution off(X ₁,...,X _n ) by terms of finitely many moments of the variablesX ₁,...,X _n . For n=1 a necessary and sufficient condition results thatm numbers are the firstm moments of a random variable takingm+1 different values. As an application of random functionsf(X ₁,...,X _n ) the reliability of technical systems with three states is treated.

---

Zusammenfassung X ₁, ...,X _n seien elementare Zufallsvariable, d. h., Zufallsvariable, die nur endlich viele reelle Werte annehmen. Mit Hilfe von Lagrangepolynomen wird für eine beliebige Funktionf(X₁,...,X _n ) eine eindeutige polynomiale Darstellung angegeben. Daraus ergeben sich leicht die Momente wie auch die Verteilung von f(X₁,...,X _n ), ausgedrückt durch die Momente der VariablenX ₁,...,X _n . Fürn=1 erhält man eine notwendige und hinreichende Bedingung, daßm Zahlen die erstenm Momente einer Zufallsvariablen sind, diem+1 verschiedene Werte annimmt. Als Anwendung wird die Zuverlässigkeit eines technischen Systems mit drei Zuständen behandelt.

     

Inequalities for sums of independent geometrical random variables

Summary We give a survey of known results regarding Schur-convexity of probability distribution functions. Then we prove that the functionF(p ₁,...,p_n;t)=P(X₁+...+X_n≤t) is Schur-concave with respect to (p ₁,...,p_n) for every realt, whereX _i are independent geometric random variables with parametersp _i. A generalization to negative binomial random variables is also presented.     

Complexity of the Frobenius problem

Consider the Frobenius Problem: Given positive integersa ₁,...,a _n witha _i 2 and such that their greatest common divisor is one, find the largest natural number that is not expressible as a non-negative integer combination ofa ₁,...,a _n. In this paper we prove that the Frobenius problem is NP-hard, under Turing reductions.     

Total Variation Distance for Poisson Subset Numbers

Let n be an integer and A₀,..., A_k random subsets of {1,..., n} of fixed sizes a₀,..., a_k, respectively chosen independently and uniformly. We provide an explicit and easily computable total variation bound between the distance from the random variable , the size of the intersection of the random sets, to a Poisson random variable Z with intensity λ = EW. In particular, the bound tends to zero when λ converges and for all j = 0,..., k, showing that W has an asymptotic Poisson distribution in this regime. Received February 24, 2005     

Partition conditions and vertex-connectivity of graphs

It was proved ([5], [6]) that ifG is ann-vertex-connected graph then for any vertex sequencev ₁, ...,v _n ≠V(G) and for any sequence of positive integersk ₁, ...,k _n such thatk ₁+...+k _n =|V(G)|, there exists ann-partition ofV(G) such that this partition separates the verticesv ₁, ...,v(n), and the class of the partition containingv _i induces a connected subgraph consisting ofk _i vertices, fori=1, 2, ...,n. Now fix the integersk ₁, ...,k _n . In this paper we study what can we say about the vertex-connectivity ofG if there exists such a partition ofV(G) for any sequence of verticesv ₁, ...,v _n ≠V(G). We find some interesting cases when the existence of such partitions implies then-vertex-connectivity ofG, in the other cases we give sharp lower bounds for the vertex-connectivity ofG.     

Distributions of Random Partitions and Their Applications

Assume that a random sample of size m is selected from a population containing a countable number of classes (subpopulations) of elements (individuals). A partition of the set of sample elements into (unordered) subsets, with each subset containing the elements that belong to same class, induces a random partition of the sample size m, with part sizes {Z ₁,Z ₂,...,Z _N } being positive integer-valued random variables. Alternatively, if N _j is the number of different classes that are represented in the sample by j elements, for j=1,2,...,m, then (N ₁,N ₂,...,N _m ) represents the same random partition. The joint and the marginal distributions of (N ₁,N ₂,...,N _m ), as well as the distribution of are of particular interest in statistical inference. From the inference point of view, it is desirable that all the information about the population is contained in (N ₁,N ₂,...,N _m ). This requires that no physical, genetical or other kind of significance is attached to the actual labels of the population classes. In the present paper, combinatorial, probabilistic and compound sampling models are reviewed. Also, sampling models with population classes of random weights (proportions), and in particular the Ewens and Pitman sampling models, on which many publications are devoted, are extensively presented.      

The Typical Growth of the kth Excess in a Random Integer Partition

 For a partition , of a positive integer n chosen uniformly at random from the set of all such partitions, the kth excess is defined by if . We prove a bivariate local limit theorem for as . The whole range of possible values of k is studied. It turns out that ρ and η _k are asymptotically independent and both follow the doubly exponential (extreme value) probability law in a suitable neighbourhood of . Received February 6, 2001; in revised form February 25, 2002 Published online August 5, 2002     

Asymptotics for the Euclidean TSP with power weighted edges

Summary LetU ₁,...,U_n denote i.i.d. random variables with the uniform distribution on [0, 1]², and letT ²T²(U₁,...,U_n) denote the shortest tour throughU ₁,...,U_n with square-weighted edges. By drawing on the quasi-additive structure ofT ² and the boundary rooted dual process, it is shown that lim _n E T ²(U ₁,...,U_n)= for some finite constant .This work was supported in part by NSF Grant DMS-9200656, Swiss National Foundation Grant 21-298333.90, and the US Army Research Office through the Mathematical Sciences Institute of Cornell University, whose assistance is gratefully acknowledged     

A dimension theorem for division rings

LetD be a division algebra over a fieldk, letn be an arbitrary positive integer, and letk(x ₁,...,x _n) denote the rational function field inn variables overk. In this note we complete previous work by proving that the following three conditions are equivalent: (i) there exists an integerj such that the matrix ringM _j(D) contains a commutative subfield which has transcendence degreen overk; (ii) K dim (D⊗_k k(x ₁,...,x _n )) =n; (iii) gl. dim (D⊗_k k(x ₁,...,x _n )) =n. The crucial tool in the proof of this theorem is the Nullstellensatz forD[x ₁,...,x _n] which was obtained by Amitsur and Small.     

On sets of integers with prescribed gaps

For a fixed setI of positive integers we consider the set of paths (p _o,...,p _k ) of arbitrary length satisfyingp _l –p _l–1I forl=2,...,k andp ₀=1,p _k =n. Equipping it with the uniform distribution, the random path lengthT _n is studied. Asymptotic expansions of the moments ofT _n are derived and its asymptotic normality is proved. The step lengthsp _l –p _l–1 are seen to follow asymptotically a restricted geometrical distribution. Analogous results are given for the free boundary case in which the values ofp ₀ andp _k are not specified. In the special caseI={m+1,m+2,...} (for some fixed m) we derive the exact distribution of a random m-gap subset of {1,...,n} and exhibit some connections to the theory of representations of natural numbers. A simple mechanism for generating a randomm-gap subset is also presented.     

Local invariance principles and their application to density estimation

Summary Letx ₁,...,x _n be independent random variables with uniform distribution over [0, 1] ^d , andX( ⁿ ) be the centered and normalized empirical process associated tox ₁,...,x _n . Given a Vapnik-Chervonenkis classL of bounded functions from [0, 1] ^d intoR of bounded variation, we apply the one-dimensional dyadic scheme of Komlós, Major and Tusnády to get the best possible rate in Dudley's uniform central limit theorem for the empirical process {E ⁽ⁿ⁾(h):hL}. WhenL fulfills some extra condition, we prove there exists some sequenceB _n of Brownian bridges indexed byL such that whereK (L) denotes the maximal variation of the elements ofL. This result is then applied to maximal deviations distributions for kernel density estimators under minimal assumptions on the sequence of bandwith parameters. We also derive some results concerning strong approximations for empirical processes indexed by classes of sets with uniformly small perimeter. For example, it follows from Beck's paper that the above result is optimal, up to a possible factor , whenL is the class of Euclidean balls with radius less thanr.     

A strong approximation for logarithmic averages of partial sums of random variables

LetS _n be the partial sums of -mixing stationary random variables and letf(x) be a real function. In this note we give sufficient conditions under which the logarithmic average off(S _n / _n ) converges almost surely to _– f(x)d(x). We also obtain strong approximation forH(n)= _k=1 ⁿ k ^–1 f(S _k /k)=logn _– f(x)d(x) which will imply the asymptotic normality ofH(n)/log^1/2 n. But for partial sums of i.i.d. random variables our results will be proved under weaker moment condition than assumed for -mixing random variables.     

Homology classes that can be represented by embedded spheres in rational surfaces

The problem of embedding spheres in rational surfaces CP~2#nCP~2 is studied.For homology classes u=(b_1+k, b_2,…, b_n) with positive self-intersection numbers, anecessary and sufficient condition to detect its representability is given when k≤5.     

On the equationx(x +d 1)…(x + (k - 1)d 1) =y(y +d 2)…(y + (mk - 1)d 2)

For given positive integersm ≥ 2,d ₁ andd ₂, we consider the equation of the title in positive integersx, y andk ≥ 2. We show that the equation implies thatk is bounded. For a fixedk, we give conditions under which the equation implies that max(x, y) is bounded. Dedicated to the memory of Professor K G Ramanathan     

Ramsey partitions of integers and pair divisions

Ifk ₁ andk ₂ are positive integers, the partitionP = (₁,₂,..., _n ) ofk ₁+k ₂ is said to be a Ramsey partition for the pairk ₁,k ₂ if for any sublistL ofP, either there is a sublist ofL which sums tok ₁ or a sublist ofP –L which sums tok ₂. Properties of Ramsey partitions are discussed. In particular it is shown that there is a unique Ramsey partition fork ₁,k ₂ having the smallest numbern of terms, and in this casen is one more than the sum of the quotients in the Euclidean algorithm fork ₁ andk ₂.An application of Ramsey partitions to the following fair division problem is also discussed: Suppose two persons are to divide a cake fairly in the ratiok ₁k ₂. This can be done trivially usingk ₁+k ₂-1 cuts. However, every Ramsey partition ofk ₁+k ₂ also yields a fair division algorithm. This method yields fewer cuts except whenk ₁=1 andk ₂=1, 2 or 4.     

A sufficient condition for graphs to be weaklyk-linked

We consider graphs, which are finite, undirected, without loops and in which multiple edges are possible. For each natural numberk letg(k) be the smallest natural numbern, so that the following holds:LetG be ann-edge-connected graph and lets ₁,...,s _k,t ₁,...,t _k be vertices ofG. Then for everyi {1,..., k} there existsa pathP _i froms _i tot _i, so thatP ₁,...,P _k are pairwise edge-disjoint. We prove      

Lower bounds for the distribution function of a k-dimensionaln-extensible exchangeable process

A lower bound for the distribution function of a k-dimensional, n-extensible exchangeable process is provided when the marginals are uniform on the unit segment. The result is obtained by means of standard linear programming techniques. The lower bound for infinitely extendible exchangeable processes is the distribution of independent random variables.     

Random orders

Letk andn be positive integers and fix a setS of cardinalityn; letP _k (n) be the (partial) order onS given by the intersection ofk randomly and independently chosen linear orders onS. We begin study of the basic parameters ofP _k (n) (e.g., height, width, number of extremal elements) for fixedk and largen. Our object is to illustrate some techniques for dealing with these random orders and to lay the groundwork for future research, hoping that they will be found to have useful properties not obtainable by known constructions.Supported by NSF grant MCS 84-02054.     

Quasi‐randomness of graph balanced cut properties

Quasi‐random graphs can be informally described as graphs whose edge distribution closely resembles that of a truly random graph of the same edge density. Recently, Shapira and Yuster proved the following result on quasi‐randomness of graphs. Let k ≥ 2 be a fixed integer, α₁,…,α_k be positive reals satisfying \begin{align*}\sum_{i} \alpha_i = 1\end{align*} and (α₁,…,α_k)≠(1/k,…,1/k), and G be a graph on n vertices. If for every partition of the vertices of G into sets V ₁,…,V _k of size α₁n,…,α_kn, the number of complete graphs on k vertices which have exactly one vertex in each of these sets is similar to what we would expect in a random graph, then the graph is quasi‐random. However, the method of quasi‐random hypergraphs they used did not provide enough information to resolve the case (1/k,…,1/k) for graphs. In their work, Shapira and Yuster asked whether this case also forces the graph to be quasi‐random. Janson also posed the same question in his study of quasi‐randomness under the framework of graph limits. In this paper, we positively answer their question. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

A Moment Matrix Approach to Multivariable Cubature

We develop an approach to multivariable cubature based on positivity, extension, and completion properties of moment matrices. We obtain a matrix-based lower bound on the size of a cubature rule of degree 2n + 1; for a planar measure , the bound is based on estimating where C:=C^# [ ] is a positive matrix naturally associated with the moments of . We use this estimate to construct various minimal or near-minimal cubature rules for planar measures. In the case when C = diag(c₁,...,c_n) (including the case when is planar measure on the unit disk), (C) is at least as large as the number of gaps c_k >c_k+1.