On upper bounds for the tail distribution of geometric sums of subexponential random variables

The approach used by Kalashnikov and Tsitsiashvili for constructing upper bounds for the tail distribution of a geometric sum with subexponential summands is reconsidered. By expressing the problem in a more probabilistic light, several improvements and one correction are made, which enables the constructed bound to be significantly tighter. Several examples are given, showing how to implement the theoretical result.     

On upper bounds for the variance of functions of random variables

The upper bounds for the variance of a function g of a random variable X obtained in Cacoullos (1982) (for short CP) are improved in the case μ = E(X) ≠ 0. A main feature of these bounds is that they involve the second moment of the derivative or the difference of g. A multivariate extension for functions of independent random variables is also given.     

Stochastic equivalence of ordered random variables with applications in reliability theory

This paper presents some conditions for stochastic equality of (univariate or multivariate) random variables under various stochastic orderings. The main results provide generalizations of several known results. Applications to stochastic equivalence and characterization problems associated with multivariate NBU (NBUE) distributions are also included.     

Polynomial area bounds for MST embeddings of trees

In their seminal paper on geometric minimum spanning trees, Monma and Suri (1992) [31] showed how to embed any tree of maximum degree 5 as a minimum spanning tree in the Euclidean plane. The embeddings provided by their algorithm require area O(n²²)×O(n²²) and the authors conjectured that an improvement below cn×cn is not possible, for some constant c>0. In this paper, we show how to construct MST embeddings of arbitrary trees of maximum degree 3 and 4 within polynomial area.     

Practical sequential bounds for approximating two-terminal reliability

With increasing emphases on better and more reliable services, network systems have incorporated reliability analysis as an integral part in their planning, design and operation. This article first presents a simple exact decomposition algorithm for computing the NP-hard two-terminal reliability, which measures the probability of successful communication from specified source node to sink node in the network. Then a practical bounding algorithm, which is indispensable for large networks, is presented by modifying the exact algorithm for obtaining sequential lower and upper bounds on two-terminal reliability. Based on randomly generated large networks, computational experiments are conducted to compare the proposed algorithm to the well-known and widely used edge-packing approximation model and to explore the performance of the proposed bounding algorithm. Computational results reveal that the proposed bounding algorithm is superior to the edge-packing model, and the trade-off of accuracy for execution time ensures that an exact difference between upper and lower bounds on two-terminal reliability can be obtained within an acceptable time.     

Exact inequalities for sums of asymmetric random variables, with applications

Let be independent identically distributed random variables each having the standardized Bernoulli distribution with parameter . Let if and . Let . Let f be such a function that f and f′′ are nondecreasing and convex. Then it is proved that for all nonnegative numbers one has the inequality where . The lower bound on m is exact for each . Moreover, is Schur-concave in . A number of corollaries are obtained, including upper bounds on generalized moments and tail probabilities of (super)martingales with differences of bounded asymmetry, and also upper bounds on the maximal function of such (super)martingales. Applications to generalized self-normalized sums and t-statistics are given.      

A central limit theorem for random sums of random variables

Anscombe (1952) (also see Chung (1974)) has developed a central limit theoremof random sums of independent and identically distributed random variables. Applicability of this theorem in practice, however, is limited since the normalization requires random factors. In this paper we establish sufficient conditions under which the central limit theorem holds when such random factors are replaced by the underlying asymptotic mean and standard ddeviation. An application of this result in the context of shock models is also given.     

Prophet inequalities for dependent random variables

A prophet inequality with constant a satisfying K-log K=2 is obtained for a class dependent random variables in the full information case, under the same assumptions the prophet constant 4 is obtained in the partial information case. Applications to sums of independent random variables are given     

Fast computation of bounds for two-terminal network reliability

In this paper, an algorithm for the fast computation of network reliability bounds is proposed. The evaluation of the network reliability is an intractable problem for very large networks, and hence approximate solutions based on reliability bounds have assumed importance. The proposed bounds computation algorithm is based on an efficient BDD representation of the reliability graph model and a novel search technique to find important minpaths/mincuts to quickly reduce the gap between the reliability upper and lower bounds. Furthermore, our algorithm allows the control of the gap between the two bounds by controlling the overall execution time. Therefore, a trade-off between prediction accuracy and computational resources can be easily made in our approach. The numerical results are presented for large real example reliability graphs to show the efficacy of our approach.     

General scheme of maxima of sums of independent random variables and its applications

A general scheme of maxima of sums of independent random variables is introduced. We prove a theorem on the convergence of the maxima in probability. We study its applications to large jumps in random walks and to extrema of shot-noise fields in the case of regularly varying tails. Nondegenerate limiting laws are obtained.Translated from Matematicheskie Zametki, vol. 77, no. 4, 2005, pp. 544–550.Original Russian Text Copyright © 2005 by A. V. Lebedev.This revised version was published online in April 2005 with a corrected issue number.     

Multidimensional dual-feasible functions and fast lower bounds for the vector packing problem

In this paper, we address the 2-dimensional vector packing problem where an optimal layout for a set of items with two independent dimensions has to be found within the boundaries of a rectangle. Many practical applications in areas such as the telecommunications, transportation and production planning lead to this combinatorial problem. Here, we focus on the computation of fast lower bounds using original approaches based on the concept of dual-feasible functions.     

Large deviations for product of sums of random variables

In this paper, we obtain sample path and scalar large deviation principles for the product of sums of positive random variables. We study the case when the positive random variables are independent and identically distributed and bounded away from zero or the left tail decays to zero sufficiently fast. The explicit formula for the rate function of a scalar large deviation principle is given in the case when random variables are exponentially distributed.     

Coefficient bounds for a subclass of starlike functions of complex order

In the present work, we determine coefficient bounds for functions in certain subclass of starlike functions of complex order b, which are introduced here by means of a multiplier differential operator. Several corollaries and consequences of the main results are also considered.     

A characterization of discrete unimodality with applications to variance upper bounds

Bertin and Theodorescu (1984,Statist. Probab. Lett.,2, 23–30) developed a characterization of discrete unimodality based on convexity properties of a discretization of distribution functions. We offer a new characterization of discrete unimodality based on convexity properties of a piecewise linear extension of distribution functions. This reliance on functional convexity, as in Khintchine's classic definition, leads to variance dilations and upper bounds on variance for a large class of discrete unimodal distributions. These bounds are compared to existing inequalities due to Muilwijk (1966,Sankhy, Ser. B,28, p. 183), Moors and Muilwijk (1971,Sankhy, Ser. B,33, 385–388), and Rayner (1975,Sankhy, Ser. B,37, 135–138), and are found to be generally tighter, thus illustrating the power of unimodality assumptions.     

独立情形下自正则和的精确渐近性

研究均值为零非退化的独立同分布的随机变量序列正则和收敛性,在适当条件下,获得了自正则和精确渐近性的一般结果.     

Gap functions and error bounds for weak vector variational inequalities

In this article, by using the image space analysis, a gap function for weak vector variational inequalities is obtained. Its lower semicontinuity is also discussed. Then, these results are applied to obtain the error bounds for weak vector variational inequalities. These bounds provide effective estimated distances between a feasible point and the solution set of the weak vector variational inequalities.     

Upper comonotonicity and convex upper bounds for sums of random variables

It is well-known that if a random vector with given marginal distributions is comonotonic, it has the largest sum with respect to convex order. However, replacing the (unknown) copula by the comonotonic copula will in most cases not reflect reality well. For instance, in an insurance context we may have partial information about the dependence structure of different risks in the lower tail. In this paper, we extend the aforementioned result, using the concept of upper comonotonicity, to the case where the dependence structure of a random vector in the lower tail is already known. Since upper comonotonic random vectors have comonotonic behavior in the upper tail, we are able to extend several well-known results of comonotonicity to upper comonotonicity. As an application, we construct different increasing convex upper bounds for sums of random variables and compare these bounds in terms of increasing convex order.     

Merit functions for general variational inequalities

In this paper, we consider some classes of merit functions for general variational inequalities. Using these functions, we obtain error bounds for the solution of general variational inequalities under some mild conditions. Since the general variational inequalities include variational inequalities, quasivariational inequalities and complementarity problems as special cases, results proved in this paper hold for these problems. In this respect, results obtained in this paper represent a refinement of previously known results for classical variational inequalities.