Uniform laws of large numbers for set-valued mappings and subdifferentials of random functions

We derive a uniform (strong) Law of Large Numbers (LLN) for random set-valued mappings. The result can be viewed as an extension of both, a uniform LLN for random functions and LLN for random sets. We apply the established results to a consistency analysis of stationary points of sample average approximations of nonsmooth stochastic programs.     

Random capacities and their distributions

Summary We formalize the notion of an increasing and outer continuous random process, indexed by a class of compact sets, that maps the empty set on zero. Existence and convergence theorems for distributions of such processes are proved. These results generalize or are similar to those known in the special cases of random measures, random (closed) sets and random (upper) semicontinuous functions. For the latter processes infinite divisibility under the maximum is introduced and characterized. Our result generalizes known characterizations of infinite divisibility for random sets and max-infinite divisibility for random vectors. Also discussed is the convergence in distribution of the row-vise maxima of a null-array of random semicontinuous functions.Research supported by the Swedish Natural Science Research Council     

Polar sets for anisotropic Gaussian random fields

This paper studies polar sets for anisotropic Gaussian random fields, i.e. sets which a Gaussian random field does not hit almost surely. The main assumptions are that the eigenvalues of the covariance matrix are bounded from below and that the canonical metric associated with the Gaussian random field is dominated by an anisotropic metric. We deduce an upper bound for the hitting probabilities and conclude that sets with small Hausdorff dimension are polar. Moreover, the results allow for a translation of the Gaussian random field by a random field, that is independent of the Gaussian random field and whose sample functions are of bounded Hölder norm.     

Zero distribution of random polynomials

We study global distribution of zeros for a wide range of ensembles of random polynomials. Two main directions are related to almost sure limits of the zero counting measures and to quantitative results on the expected number of zeros in various sets. In the simplest case of Kac polynomials, given by the linear combinations of monomials with i.i.d. random coefficients, it is well known that under mild assumptions on the coefficients, their zeros are asymptotically uniformly distributed near the unit circumference. We give estimates of the expected discrepancy between the zero counting measure and the normalized arclength on the unit circle. Similar results are established for polynomials with random coefficients spanned by different bases, e.g., by orthogonal polynomials. We show almost sure convergence of the zero counting measures to the corresponding equilibrium measures for associated sets in the plane and quantify this convergence. In our results, random coefficients may be dependent and need not have identical distributions.     

An update algorithm for restricted random walk clustering for dynamic data sets

In this article, we present a randomized dynamic cluster algorithm for large data sets. It is based on the restricted random walk cluster algorithm by Schöll and Schöll-Paschinger that has given good results in past studies. We discuss different approaches for the clustering of dynamic data sets. In contrast to most of these methods, dynamic restricted random walk clustering is also efficient for a small percentage of changes in the data set and has the additional advantage that the updates asymptotically produce the same clusters as a reclustering with the static variant; there is thus no need for any reclustering ever. In addition, the method has a relatively low computational complexity which enables it to cluster large data sets.     

On a Class of Random Variational Inequalities on Random Sets

We study a class of random variational inequalities on random sets and give measurability, existence, and uniqueness results in a Hilbert space setting. In the special case where the random and the deterministic variables are separated, we present a discretization technique based on averaging and truncation, prove a Mosco convergence result for the feasible random set, and establish norm convergence of the approximation procedure.     

A Multivalued Strong Law of Large Numbers

We prove a strong law of large numbers for random closed sets in a separable Banach space. It improves upon and unifies the laws of large numbers with convergence in the Wijsman, Mosco and slice topologies, without requiring extra assumptions on either the properties of the space or the kind of sets that can be taken on by the random set as values.     

Laws of Large Numbers for Exchangeable Random Sets in Kuratowski-Mosco Sense

Abstract

Most of the results for laws of large numbers based on Banach space valued random sets assume that the sets are independent and identically distributed (IID) and compact, in which Rådström embedding or the refined method for collection of compact and convex subsets of a Banach space plays an important role. In this paper, exchangeability among random sets as a dependency, instead of IID, is assumed in obtaining strong laws of large numbers, since some kind of dependency of random variables may be often required for many statistical analyses. Also, the Hausdorff convergence usually used is replaced by another topology, Kuratowski-Mosco convergence. Thus, we prove strong laws of large numbers for exchangeable random sets in Kuratowski-Mosco convergence, without assuming the sets are compact, which is weaker than Hausdorff sense.     

Large deviations for sums of i.i.d. random compact sets

We prove a large deviation principle for Minkowski sums of i.i.d. random compact sets in a Banach space, that is, the analog of Cramér theorem for random compact sets.

     

FRACTAL PROPERTIES OF POLAR SETS OF RANDOM STRING PROCESSES

This paper studies fractal properties of polar sets for random string processes. We give upper and lower bounds of the hitting probabilities on compact sets and prove some sufficient conditions and necessary conditions for compact sets to be polar for the random string process. Moreover, we also determine the smallest Hausdorff dimensions of non-polar sets by constructing a Cantor-type set to connect its Hausdorff dimension and capacity.     

Robust portfolio selection based on asymmetric measures of variability of stock returns

This paper addresses a new uncertainty set—interval random uncertainty set for robust optimization. The form of interval random uncertainty set makes it suitable for capturing the downside and upside deviations of real-world data. These deviation measures capture distributional asymmetry and lead to better optimization results. We also apply our interval random chance-constrained programming to robust mean-variance portfolio selection under interval random uncertainty sets in the elements of mean vector and covariance matrix. Numerical experiments with real market data indicate that our approach results in better portfolio performance.     

Countable Random Sets: Uniqueness in Law and Constructiveness

The first part of this article deals with theorems on uniqueness in law for σ-finite and constructive countable random sets, which in contrast to the usual assumptions may have points of accumulation. We discuss and compare two approaches on uniqueness theorems: first, the study of generators for σ-fields used in this context and, secondly, the analysis of hitting functions. The last section of this paper deals with the notion of constructiveness. We prove a measurable selection theorem and a decomposition theorem for constructive countable random sets, and study constructive countable random sets with independent increments.     

On Induced Subgraphs with All Degrees Odd

 Gallai proved that the vertex set of any graph can be partitioned into two sets, each inducing a subgraph with all degrees even. We prove that every connected graph of even order has a vertex partition into sets inducing subgraphs with all degrees odd, and give bounds for the number of sets of this type required for vertex partitions and vertex covers. We also give results on the partitioning and covering problems for random graphs. Received: October 5, 1998?Final version received: October 20, 2000     

Characterizations and embedding properties in exchangeability

Summary Our key result is the characterization of exchangeable sequences as being strongly stationary, i.e. invariant in distribution under stopping time shifts. From this we prove homogeneity characterizations of pure and mixed Markov chains. These results carry over to continuous time processes and random sets, and on a whole, our theory provides a unified approach to exchangeability. The key result above is closely related to Dacunha-Castelle's embedding characterization of exchangeability, which is partially extended here to processes on [0, 1]. In the other direction, we prove that a previsible sample from a finite or infinite exchangeable sequence X may be embedded into a copy of X. We finally establish some uniqueness results for exponentially and uniformly killed exchangeable random sets.     

Jensen's inequality for random elements in metric spaces and some applications

Jensen's inequality is extended to metric spaces endowed with a convex combination operation. Applications include a dominated convergence theorem for both random elements and random sets, a monotone convergence theorem for random sets, and other results on set-valued expectations in metric spaces and on random probability measures.     

Estimated stochastic programs with chance constraints

We will consider a non-parametric estimation procedure for chance-constrained stochastic programs where the random parameters appear on the right-hand side of linear constraints for the decision variable. The assumed independence of the components of the random right-hand side data results in stochastic programs with a separability structure in the constraints. We estimate the unknown probability distribution of the random right-hand side data via isotonic regression estimates of increasing hazard rates. Our choice of the estimates was motivated by the relationship between logarithmic concave measures and increasing hazard rate distributions. We establish large deviation results for optimal values and optimal solution sets of the estimated programs. Finally, we discuss the numerical treatment of the estimated chance-constrained programs and report on a test run.     

Some mathematical tools for linguistic probabilities

We propose and develop, in this paper, some concepts and techniques useful for the theory of linguistic probabilisies introduced by L.A. Zadeh. These probabilities are expressed in linguistic rather than numerical terms. The mathematical framework for this study is based upon the possibility theory.We formulate first the problem of optimization under elastic constraints which is not only important for mathematical programming but will be served to justify the extension of possibility measure to linguistic variables. Next, in connection with translation rules in natural languages we study some transformations of fuzzy sets using a relation between random sets and fuzzy sets. Finally, we point out some differences between random variables and fuzzy variables, and present the mathematical notion of possibility, in the setting of set-functions, as a special case of Choquet capacities.     

Qualitative inequalities for squared partial correlations of a Gaussian random vector

We describe various sets of conditional independence relationships, sufficient for qualitatively comparing non-vanishing squared partial correlations of a Gaussian random vector. These sufficient conditions are satisfied by several graphical Markov models. Rules for comparing degree of association among the vertices of such Gaussian graphical models are also developed. We apply these rules to compare conditional dependencies on Gaussian trees. In particular for trees, we show that such dependence can be completely characterised by the length of the paths joining the dependent vertices to each other and to the vertices conditioned on. We also apply our results to postulate rules for model selection for polytree models. Our rules apply to mutual information of Gaussian random vectors as well.     

Large deviations for heavy-tailed random elements in convex cones

We prove large deviation results for sums of heavy-tailed random elements in rather general convex cones being semigroups equipped with a rescaling operation by positive real numbers. In difference to previous results for the cone of convex sets, our technique does not use the embedding of cones in linear spaces. Examples include the cone of convex sets with the Minkowski addition, positive half-line with maximum operation and the family of square integrable functions with arithmetic addition and argument rescaling.