The expectation and variance of the joint linear complexity of random periodic multisequences

The linear complexity of sequences is one of the important security measures for stream cipher systems. Recently, in the study of vectorized stream cipher systems, the joint linear complexity of multisequences has been investigated. By using the generalized discrete Fourier transform for multisequences, Meidl and Niederreiter determined the expectation of the joint linear complexity of random N-periodic multisequences explicitly. In this paper, we study the expectation and variance of the joint linear complexity of random periodic multisequences. Several new lower bounds on the expectation of the joint linear complexity of random periodic multisequences are given. These new lower bounds improve on the previously known lower bounds on the expectation of the joint linear complexity of random periodic multisequences. By further developing the method of Meidl and Niederreiter, we derive a general formula and a general upper bound for the variance of the joint linear complexity of random N-periodic multisequences. These results generalize the formula and upper bound of Dai and Yang for the variance of the linear complexity of random periodic sequences. Moreover, we determine the variance of the joint linear complexity of random periodic multisequences with certain periods.     

Almost Sure Hausdorff Dimension of Graphs of Random Wavelet Series

In this contribution, we consider the problem of computing the Hausdorff dimension of the graph of a continuous random field obtained as an infinite series of smooth deterministic functions with independent random weights. The particular case of random wavelet series is addressed and almost sure lower bounds of their Hausdorff dimension are obtained. Sub-classes are exhibited for which these lower bounds coincide with almost sure upper bounds based on particular smoothness indices of the series. A direct application of these results provides new insights concerning the Hausdorff dimension as opposed to classical smoothness indices.     

Comonotonic bounds on the survival probabilities in the Lee–Carter model for mortality projection

In the Lee–Carter framework, future survival probabilities are random variables with an intricate distribution function. In large homogeneous portfolios of life annuities, value-at-risk or conditional tail expectation of the total yearly payout of the company are approximately equal to the corresponding quantities involving random survival probabilities. This paper aims to derive some bounds in the increasing convex (or stop-loss) sense on these random survival probabilities. These bounds are obtained with the help of comonotonic upper and lower bounds on sums of correlated random variables.     

Computation of sharp bounds on the distribution of a function of dependent risks

We propose a new algorithm to compute numerically sharp lower and upper bounds on the distribution of a function of d dependent random variables having fixed marginal distributions. Compared to the existing literature, the bounds are widely applicable, more accurate and more easily obtained.     

Bounds for the price of discrete arithmetic Asian options

In this paper the pricing of European-style discrete arithmetic Asian options with fixed and floating strike is studied by deriving analytical lower and upper bounds. In our approach we use a general technique for deriving upper (and lower) bounds for stop-loss premiums of sums of dependent random variables, as explained in Kaas et al. (Ins. Math. Econom. 27 (2000) 151–168), and additionally, the ideas of Rogers and Shi (J. Appl. Probab. 32 (1995) 1077–1088) and of Nielsen and Sandmann (J. Financial Quant. Anal. 38(2) (2003) 449–473). We are able to create a unifying framework for European-style discrete arithmetic Asian options through these bounds, that generalizes several approaches in the literature as well as improves the existing results. We obtain analytical and easily computable bounds. The aim of the paper is to formulate an advice of the appropriate choice of the bounds given the parameters, investigate the effect of different conditioning variables and compare their efficiency numerically. Several sets of numerical results are included. We also discuss hedging using these bounds. Moreover, our methods are applicable to a wide range of (pricing) problems involving a sum of dependent random variables.     

Random hypergraph coloring algorithms and the weak chromatic number

We present a hypergraph coloring algorithm and analyze its performance in spaces of random hypergrpahs. In these spaces the number of colors used by our algorithm is almost surely within a small constant factor (less than 2) of the weak chromatic number of the hypergraph. This also establishes new upper and lower bounds for the weak chromatic number of uniform hypergraphs.     

A Fourier formulation of the Frostman criterion for random graphs and its applications to wavelet series

In the paper by F. Roueff “Almost sure Hausdorff dimensions of graphs of random wavelet series” [J. Fourier Anal. Appl., to appear] lower bounds of the Hausdorff dimension of the graphs of random wavelet series (RWS) have been obtained essentially under the hypothesis that the wavelet coefficients have a bounded probability density function (p.d.f.) with respect to the Lebesgue measure. In this article we extend these lower bounds to classes of RWS that do not satisfy this hypothesis.     

Convex relaxations of chance constrained optimization problems

In this paper we develop convex relaxations of chance constrained optimization problems in order to obtain lower bounds on the optimal value. Unlike existing statistical lower bounding techniques, our approach is designed to provide deterministic lower bounds. We show that a version of the proposed scheme leads to a tractable convex relaxation when the chance constraint function is affine with respect to the underlying random vector and the random vector has independent components. We also propose an iterative improvement scheme for refining the bounds.     

Randomized Simplex Algorithms on Klee-Minty Cubes

The analysis of two most natural randomized pivot rules on the Klee-Minty cubes leads to (nearly) quadratic lower bounds for the complexity of linear programming with random pivots. Thus we disprove two bounds (for the expected running time of the random-edge simplex algorithm on Klee-Minty cubes) conjectured in the literature. At the same time, we establish quadratic upper bounds for the expected length of a path for a simplex algorithm with random pivots on the classes of linear programs under investigation. In contrast to this, we find that the average length of an increasing path in a Klee-Minty cube is exponential when all paths are taken with equal probability. Received: September 2, 1996     

Laplace eigenvalues and bandwidth-type invariants of graphs

For (weighted) graphs several labeling properties and their relation to the eigenvalues of the Laplacian matrix of a graph are considered. Several upper and lower bounds on the bandwidth and other min-sum problems are derived. Most of these bounds depend on Laplace eigenvalues of the graphs. The results are applied in the study of bandwidth and the min-sums of random graphs, random regular graphs, and Kneser graphs. © John Wiley & Sons, Inc.     

Improved Analytical Bounds for Gambler’s Ruin Probabilities

Given integer-valued wagers Feller (1968) has established upper and lower bounds on the probability of ruin, which often turn out to be very close to each other. However, the exact calculation of these bounds depends on the unique non-trivial positive root of the equation () = 1, where is the probability generating function for the wager. In the situation of incomplete information about the distribution of the wager, one is interested in bounds depending only on the first few moments of the wager. Ethier and Khoshnevisan (2002) derive bounds depending explicitly on the first four moments. However, these bounds do not make the best possible use of the available information. Based on the theory of s-convex extremal random variables among arithmetic and real random variables, a substantial improvement can be given. By fixed first four moments of the wager, the obtained new bounds are nearly perfect analytical approximations to the exact bounds of Feller.AMS 2000 Subject Classification: 60E15, 60G40, 91A60     

Some upper and lower bounds on PSD-rank

Positive semidefinite rank (PSD-rank) is a relatively new complexity measure on matrices, with applications to combinatorial optimization and communication complexity. We first study several basic properties of PSD-rank, and then develop new techniques for showing lower bounds on the PSD-rank. All of these bounds are based on viewing a positive semidefinite factorization of a matrix M as a quantum communication protocol. These lower bounds depend on the entries of the matrix and not only on its support (the zero/nonzero pattern), overcoming a limitation of some previous techniques. We compare these new lower bounds with known bounds, and give examples where the new ones are better. As an application we determine the PSD-rank of (approximations of) some common matrices.     

Lyapunov Exponents for the Random Product of Two Shears

We give lower and upper bounds on both the Lyapunov exponent and generalised Lyapunov exponents for the random product of positive and negative shear matrices. These types of random products arise in applications such as fluid stirring devices. The bounds, obtained by considering invariant cones in tangent space, give excellent accuracy compared to standard and general bounds, and are increasingly accurate with increasing shear. Bounds on generalised exponents are useful for testing numerical methods, since these exponents are difficult to compute in practice.

     

Tight lower bound on the probability of a binomial exceeding its expectation

We give the proof of a tight lower bound on the probability that a binomial random variable exceeds its expected value. The inequality plays an important role in a variety of contexts, including the analysis of relative deviation bounds in learning theory and generalization bounds for unbounded loss functions.     

Tail bounds for the joint distribution of the surplus prior to and at ruin

For the classical risk model with Poisson arrivals, we study the (bivariate) tail of the joint distribution of the surplus prior to and at ruin. We obtain some exact expressions and new bounds for this tail, and we suggest three numerical methods that may yield upper and lower bounds for it. As a by-product of the analysis, we obtain new upper and lower bounds for the probability and severity of ruin. Many of the bounds in the present paper improve and generalise corresponding bounds that have appeared earlier. For the numerical bounds, their performance is also compared against bounds available in the literature.     

Bounds for Asian basket options

In this paper we propose pricing bounds for European-style discrete arithmetic Asian basket options in a Black and Scholes framework. We start from methods used for basket options and Asian options. First, we use the general approach for deriving upper and lower bounds for stop-loss premia of sums of non-independent random variables as in Kaas et al. [Upper and lower bounds for sums of random variables, Insurance Math. Econom. 27 (2000) 151–168] or Dhaene et al. [The concept of comonotonicity in actuarial science and finance: theory, Insurance Math. Econom. 31(1) (2002) 3–33]. We generalize the methods in Deelstra et al. [Pricing of arithmetic basket options by conditioning, Insurance Math. Econom. 34 (2004) 55–57] and Vanmaele et al. [Bounds for the price of discrete sampled arithmetic Asian options, J. Comput. Appl. Math. 185(1) (2006) 51–90]. Afterwards we show how to derive an analytical closed-form expression for a lower bound in the non-comonotonic case. Finally, we derive upper bounds for Asian basket options by applying techniques as in Thompson [Fast narrow bounds on the value of Asian options, Working Paper, University of Cambridge, 1999] and Lord [Partially exact and bounded approximations for arithmetic Asian options, J. Comput. Finance 10 (2) (2006) 1–52]. Numerical results are included and on the basis of our numerical tests, we explain which method we recommend depending on moneyness and time-to-maturity.     

Estimates for the inverse elements of tridiagonal matrices

In this work, new upper and lower bounds for the inverse entries of the tridiagonal matrices are presented. The bounds improve the bounds in D. Kershaw [Inequalities on the elements of the inverse of a certain tridiagonal matrix, Math. Comput. 24 (1970) 155–158], P.N. Shivakumar, C.X. Ji [Upper and lower bounds for inverse elements of finite and infinite tridiagonal matrices, Linear Algebr. Appl. 247 (1996) 297–316], R. Nabben [Two-sided bounds on the inverse of diagonally dominant tridiagonal matrices, Linear Algebr. Appl. 287 (1999) 289–305] and R. Peluso, T. Politi [Some improvements for two-sided bounds on the inverse of diagonally dominant tridiagonal matrices, Linear. Algebr. Appl. 330 (2001) 1–14].     

On the smallest eigenvalue of the Stokes operator in a domain with fine-grained random boundary

This article deals with a problem arising in localization of the principal eigenvalue (PE) of the Stokes operator under the Dirichlet condition on the fine-grained random boundary of a domain contained in a cube of size t ? 1. The random microstructure is assumed identically distributed in distinct unit cubic cells and, in essence, independent. In this setting, the asymptotic behavior of the PE as t → ∞ is deterministic: it proves possible to find nonrandom upper and lower bounds on the PE which apply with probability that converges to 1. It was proved earlier that in two dimensions the nonrandom unilateral bounds on the PE can be chosen asymptotically equivalent, which implies the convergence in probability to a nonrandom limit of the appropriately normalized PE. The present article extends this result to higher dimensions.     

New lower bounds for the three-dimensional finite bin packing problem

The three-dimensional finite bin packing problem (3BP) consists of determining the minimum number of large identical three-dimensional rectangular boxes, bins, that are required for allocating without overlapping a given set of three-dimensional rectangular items. The items are allocated into a bin with their edges always parallel or orthogonal to the bin edges. The problem is strongly NP-hard and finds many practical applications. We propose new lower bounds for the problem where the items have a fixed orientation and then we extend these bounds to the more general problem where for each item the subset of rotations by 90° allowed is specified. The proposed lower bounds have been evaluated on different test problems derived from the literature. Computational results show the effectiveness of the new lower bounds.     

Quantifying the error of convex order bounds for truncated first moments

The concepts of convex order and comonotonicity have become quite popular in risk theory, essentially since Kaas et al. [Kaas, R., Dhaene, J., Goovaerts, M.J., 2000. Upper and lower bounds for sums of random variables. Insurance: Math. Econ. 27, 151-168] constructed bounds in the convex order sense for a sum S of random variables without imposing any dependence structure upon it. Those bounds are especially helpful, if the distribution of S cannot be calculated explicitly or is too cumbersome to work with. This will be the case for sums of lognormally distributed random variables, which frequently appear in the context of insurance and finance.In this article we quantify the maximal error in terms of truncated first moments, when S is approximated by a lower or an upper convex order bound to it. We make use of geometrical arguments; from the unknown distribution of S only its variance is involved in the computation of the error bounds. The results are illustrated by pricing an Asian option. It is shown that under certain circumstances our error bounds outperform other known error bounds, e.g. the bound proposed by Nielsen and Sandmann [Nielsen, J.A., Sandmann, K., 2003. Pricing bounds on Asian options. J. Financ. Quant. Anal. 38, 449-473].