Tails of waiting times and their bounds

Tails of distributions having the form of the geometric convolution are considered. In the case of light-tailed summands, a simple proof of the famous Cramér asymptotic formula is given via the change of probability measure. Some related results are obtained, namely, bounds of the tails of geometric convolutions, expressions for the distribution of the 1st failure time and failure rate in regenerative systems, and others. In the case of heavy-tailed summands, two-sided bounds of the tail of the geometric convolution are given in the cases where the summands have either Pareto or Weibull distributions. The results obtained have the property that the corresponding lower and upper bounds are tailed-equivalent. This revised version was published online in June 2006 with corrections to the Cover Date.     

Solving the Vehicle Routing Problem with Stochastic Demands using the Cross-Entropy Method

An alternate formulation of the classical vehicle routing problem with stochastic demands (VRPSD) is considered. We propose a new heuristic method to solve the problem, based on the Cross-Entropy method. In order to better estimate the objective function at each point in the domain, we incorporate Monte Carlo sampling. This creates many practical issues, especially the decision as to when to draw new samples and how many samples to use. We also develop a framework for obtaining exact solutions and tight lower bounds for the problem under various conditions, which include specific families of demand distributions. This is used to assess the performance of the algorithm. Finally, numerical results are presented for various problem instances to illustrate the ideas.     

Refined exponential rates in Vapnik–Chervonenkis inequalities

Vapnik–Chervonenkis bounds on speeds of convergence of empirical means to their expectations have been continuously improved over the years. The result obtained by M. Talagrand in 1994 [11] seems to provide the final word as far as universal bounds are concerned. However, for fixed families of underlying probability distributions, the exponential rate in the deviation term can be fairly improved by the more adequate Cramér transform, as shown by theorems of large deviations.     

On the lower bounds for mean square error of empirical bayes estimators

The usual empirical Bayes setting is considered with θ being a shift or a scale parameter. A class of empirical Bayes estimators of a function b(θ) is proposed. The properties of the estimates are studied and mean square errors are calculated. The lower bounds are constructed for mean square errors of the empirical Bayes estimators over the class of all empirical Bayes estimators of b(θ). The results are applied to the case b(θ)=θ. The examples of the upper and lower bounds for mean square error are presented for the most popular families of conditional distributions. Added to the English translaion.     

Characterizations of distributions by moment properties of sums of records and successive maxima

We consider the estimation problem for expectations of random variables that are sums of records and successive maxima. The corresponding upper bounds and characterizations of source distributions are obtained in the case where these bounds are attained, Bibliography: 4 titles. Translated from Zapiski Nauchnykh Seminarov; POMI, Vol. 361, 2008, pp. 138–144.     

On the calculation of the bounds of probability of events using infinite random sets

This paper presents an extension of the theory of finite random sets to infinite random sets, that is useful for estimating the bounds of probability of events, when there is both aleatory and epistemic uncertainty in the representation of the basic variables. In particular, the basic variables can be modelled as CDFs, probability boxes, possibility distributions or as families of intervals provided by experts. These four representations are special cases of an infinite random set. The method introduces a new geometrical representation of the space of basic variables, where many of the methods for the estimation of probabilities using Monte Carlo simulation can be employed. This method is an appropriate technique to model the bounds of the probability of failure of structural systems when there is parameter uncertainty in the representation of the basic variables. A benchmark example is used to demonstrate the advantages and differences of the proposed method compared with the finite approach.     

Some results on lower variance bounds useful in reliability modeling and estimation

In the present paper a general theorem that links characterizations of discrete life distributions based on relationship between failure rate and conditional expectations with those in terms of Chernoff-type inequalities is proposed. Exact expression for lower bounds to the variance is calculated for distributions belonging to the modified power series family, Ord family and mixture geometric models. It is shown that the bounds obtained here contain the Cramer–Rao and Chapman–Robbins inequalities as special cases. An application of the results to real data is also provided.     

Bounds for the Multicovering Radii of Reed-Muller Codes with Applications to Stream Ciphers

The multicovering radii of a code are recentgeneralizations of the covering radius of a code. For positivem, the m-covering radius of C is the leastradius t such that everym-tuple of vectors is contained in at least one ball of radiust centered at some codeword. In this paper upper bounds arefound for the multicovering radii of first order Reed-Muller codes. These bounds generalize the well-known Norse bounds for the classicalcovering radii of first order Reed-Muller codes. They are exactin some cases. These bounds are then used to prove the existence of secure families of keystreams against a general class of cryptanalytic attacks. This solves the open question that gave rise to the study ofmulticovering radii of codes.     

The conjugacy vector of ap-group of maximal class

We find the conjugacy vector, i.e., we determine the number of conjugacy classes which compose the sets of the elements with centralizers of equal order, for several general families ofp-groups of maximal class which include those of order up top ⁹. As a consequence, we obtain the number of conjugacy classes,r(G), for the groups in these families. Also, we provide upper and lower bounds forr(G) and characterize when they are attained. Examples are given showing that the bounds are actually attained. This work has been supported by DGICYT grant PB91-0446 and by the University of the Basque Country.     

Perturbed Markov Chains with Damping Component

The paper is devoted to studies of regularly and singularly perturbed Markov chains with damping component. In such models, a matrix of transition probabilities is regularised by adding a special damping matrix multiplied by a small damping (perturbation) parameter ε. We perform a detailed perturbation analysis for such Markov chains, particularly, give effective upper bounds for the rate of approximation for stationary distributions of unperturbed Markov chains by stationary distributions of perturbed Markov chains with regularised matrices of transition probabilities, asymptotic expansions for approximating stationary distributions with respect to damping parameter, explicit coupling type upper bounds for the rate of convergence in ergodic theorems for n-step transition probabilities, as well as ergodic theorems in triangular array mode.

     

The general form of the law of the iterated logarithm for generalized Kolmogorov-Smirnov-Renyi statistics

One result of Smirnov's important paper [Uspehi Mat. Nauk. 10, 179–206, (in Russian)] yields exponential bounds for the large deviations of his one-sided Smirnov statistic and the two-sided Kolmogorov statistic. In the present paper exponential bounds are given for the large deviations of a wide class of Kolmogorov-Smirnov-Renyi type statistics. As a by-product, exponential bounds for the large deviations of the corresponding limit distributions are obtained.     

Some Characteristic Properties of the Fisher Information Matrix via Cacoullos-Type Inequalities

Some lower bounds for the variance of a function g of a random vector X are extended to a wider class of distributions. Using these bounds, some useful inequalities for the Fisher information are obtained for convolutions and linear combinations of random variables. Finally, using these inequalities, simple proofs are given of classical characterizations of the normal distribution, under certain restrictions, including the matrix analogue of the Darmois-Skitovich result.     

A branch-reduce-cut algorithm for the global optimization of probabilistically constrained linear programs

We consider probabilistically constrained linear programs with general distributions for the uncertain parameters. These problems involve non-convex feasible sets. We develop a branch-and-bound algorithm that searches for a global optimal solution to this problem by successively partitioning the non-convex feasible region and by using bounds on the objective function to fathom inferior partition elements. This basic algorithm is enhanced by domain reduction and cutting plane strategies to reduce the size of the partition elements and hence tighten bounds. The proposed branch-reduce-cut algorithm exploits the monotonicity properties inherent in the problem, and requires solving linear programming subproblems. We provide convergence proofs for the algorithm. Some illustrative numerical results involving problems with discrete distributions are presented.     

Continuity theorems for the M/M/1/n queueing system

In this paper continuity theorems are established for the number of losses during a busy period of the M/M/1/n queue. We consider an M/GI/1/n queueing system where the service time probability distribution, slightly different in a certain sense from the exponential distribution, is approximated by that exponential distribution. Continuity theorems are obtained in the form of one or two-sided stochastic inequalities. The paper shows how the bounds of these inequalities are changed if further assumptions, associated with specific properties of the service time distribution (precisely described in the paper), are made. Specifically, some parametric families of service time distributions are discussed, and the paper establishes uniform estimates (given for all possible values of the parameter) and local estimates (where the parameter is fixed and takes only the given value). The analysis of the paper is based on the level crossing approach and some characterization properties of the exponential distribution. Dedicated to Vladimir Mikhailovich Zolotarev, Victor Makarovich Kruglov, and to the memory of Vladimir Vyacheslavovich Kalashnikov.     

An investigation of phase-distribution moment-matching algorithms for use in queueing models

Algorithms for matching moments to phase-type distributions are evaluated on the basis of their performance in their intended application, queueing models. The moment-matching algorithms under consideration match two moments to a hyperexponential distribution with balanced means and three moments to a mixture of two Erlang distributions of common order. These algorithms are used to approximate an interarrival-time distribution for a queueing model, and the accuracy of associated performance-measure approximations is then used to evaluate the moment-matching algorithms. Three performance measures are considered, and attention is focussed on the steady-state mean queue length (number in system) of theGI/M/1 queue. Performance-measure approximations are compared to three-moment bounds and performance-measure values arising from hypothetical approximated distributions.     

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.     

Bounds on the value of information in uncertain decision problems

The cost of obtaining good information regarding the various probability distributions needed for the solution of most stochastic decision problems is considerable. It is important to consider questions such as: (1) what minimal amounts of information are sufficient to determine optimal decision rules; (2) what is the value of obtaining knowledge of the actual realization of the random vectors; and (3) what is the value of obtaining some partial information regarding the actual realization of the random vectors. This paper is primarily concerned with questions two and three when the decision maker has an a priori knowledge of the joint distribution function of the random variables. Some remarks are made regarding results along the lines of question one. Mention is made of assumptions sufficient so that knowledge of means, or of means, variances, co-variances and n-moments are sufficient for the calculation of optimal decision rules. The analysis of the second question leads to the development of bounds on the value of perfect information. For multiperiod problems it is important to consider when the perfect information is available. Jensen's inequality is the key tool of the analysis. The calculation of the bounds requires the solution of nonlinear programs and the numerical evaluation of certain functions. Generally speaking, tighter bounds may be obtained only at the expense of additional information and computational complexity. Hence, one may wish to compute some simple bounds to decide upon the advisability of obtaining more information. For the analysis of the value of partial information it is convenient to introduce the notion of a signal. Each signal represents the receipt of certain information, and these signals are drawn from a given probability distribution. When a signal is received, it alters the decision maker's perception of the probability distributions inherent in his decision problem. The choice between different information structures must then take into account these probability distributions as well as the decision maker's preference function. A hierarchy of bounds may be determined for partial information evaluation utilizing the tools of the multiperiod perfect information case. However, the calculation of these bounds is generally considerably more dicult than the calculation of similar boulids in the perfect information case. Most of the analysis is directed towards problems in which the decision maker has a linear utility function over profits, costs or some other numerical variable. However, some of the bounds generalize to the case when the utility function is strictly increasing and concave.     

A survey of dual-feasible and superadditive functions

Dual-feasible functions are valuable tools that can be used to compute both lower bounds for different combinatorial problems and valid inequalities for integer programs. Several families of functions have been used in the literature. Some of them were defined explicitly, and others not. One of the main objectives of this paper is to survey these functions, and to state results concerning their quality. We clearly identify dominant subsets of functions, i.e. those which may lead to better bounds or stronger cuts. We also describe different frameworks that can be used to create dual-feasible functions. With these frameworks, one can get a dominant function based on other ones. Two new families of dual-feasible functions obtained by applying these methods are proposed in this paper.     

Sharp dilation-type inequalities with a fixed parameter of convexity

Sharp upper bounds for large and small deviations and dilation-type inequalities are considered for probability distributions satisfying convexity conditions of Brunn-Minkowski type. Bibliography: 17 titles. Published in Zapiski Nauchnykh Seminarov POMI, Vol. 351, 2007, pp. 54–78.     

On an inverse problem in mixture failure rates modelling

Mixtures of decreasing failure rate (DFR) distributions are always DFR. It turns out that very often mixtures of increasing failure rate distributions can decrease or show even more complicated patterns of dependence on time. For studying this and other relevant effects two simple models of mixing with additive and multiplicative failure rates are considered. It is shown that for these models an inverse problem can be solved, which means that given an arbitrary shape of the mixture failure rate and a mixing distribution, the failure rate for a governing distribution can be uniquely obtained. Some examples are considered where this operation can be performed explicitly. Possible generalizations are discussed. Copyright © 2001 John Wiley & Sons, Ltd.