Upper bounds for the risk in the α — t utility function

Fishburn's α — t model is an important example of a utility function involving a target for a random variable. Simple upper bounds for the risk function in this model are proposed for cases in which the probability distribution is either unknown, or produces complicated or intractable statements of the model.     

Some new results on waiting time and busy time in M/G/1 queue

This paper considers an M/G/1 queue with Poisson rate λ > 0 and service time distribution G(t) which is supposed to have finite mean 1/μ. The following questions are first studied: (a) The closed bounds of the probability that waiting time is more than a fixed value; (b)The total busy time of the server, which including the distribution, probability that are more than a fixed value during a given time interval (0, t], and the expected value. Some new and important results are obtained by theories of the classes of life distributions and renewal process.     

Simple random walk on long range percolation clusters I: heat kernel bounds

In this paper, we derive upper bounds for the heat kernel of the simple random walk on the infinite cluster of a supercritical long range percolation process. For any d ?? 1 and for any exponent ${s \in (d, (d+2) \wedge 2d)}$ giving the rate of decay of the percolation process, we show that the return probability decays like ${t^{-{d}/_{s-d}}}$ up to logarithmic corrections, where t denotes the time the walk is run. Our methods also yield generalized bounds on the spectral gap of the dynamics and on the diameter of the largest component in a box. The bounds and accompanying understanding of the geometry of the cluster play a crucial role in the companion paper (Crawford and Sly in Simple randomwalk on long range percolation clusters II: scaling limit, 2010) where we establish the scaling limit of the random walk to be ??-stable Lévy motion.     

Resolution Complexity of Random Constraint Satisfaction Problems: Another Half of the Story

Let C_n,cn^2,k,t be a random constraint satisfaction problem(CSP) of n binary variables, where c > 0 is a fixed constant and the cn constraints are selected uniformly and independently from all the possible k-ary constraints each of which contains exactly t tuples of the values as its restrictions. We establish upper bounds for the tightness threshold for C_n,cn^2,k,t to have an exponential resolution complexity. The upper bounds partly answers the open problems regarding the CSP resolution complexity with the tightness between the existing upper and lower bound [1].     

Random point fields with Markovian refinements and the geometry of fractally disordered media

We give a general construction of the probability measure for describing stochastic fractals that model fractally disordered media. For these stochastic fractals, we introduce the notion of a metrically homogeneous fractal Hansdorff-Karathéodory measure of a nonrandom type. We select a classF[q] of random point fields with Markovian refinements for which we explicitly construct the probability distribution. We prove that under rather weak conditions, the fractal dimension D for random fields of this class is a self-averaging quantity and a fractal measure of a nonrandom type (the Hausdorff D-measure) can be defined on these fractals with probability 1. Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 124, No. 3, pp. 490–505, September, 2000.     

Conditional Monte Carlo method for dynamic systems with random properties

A method is developed for calculating moments and other properties of states X(t) of dynamic systems with random coefficients depending on semi-Markov processes ξ(t) and subjected to Gaussian white noise. Random vibration theory is used to find probability laws of conditional processes X(t)∣ξ(·). Unconditional properties of X(t) are estimated by averaging conditional statistics of this process corresponding to samples of ξ(t). The method is particularly efficient for linear systems since X(t)∣ξ(·) is Gaussian during periods of constant values of ξ(t), so that and its probability law is completely defined by the process mean and covariance functions that can be obtained simply from equations of linear random vibration. The method is applied to find statistics of an Ornstein-Uhlenbeck process X(t) whose decay parameter is a semi-Markov process ξ(t). Numerical results show that X(t) is not Gaussian and that the law of this process depends essentially on features of ξ(t). A version of the method is used to calculate the failure probability for an oscillator with degrading stiffness subjected to Gaussian white noise.     

Simple bounds for recovering low-complexity models

This note presents a unified analysis of the recovery of simple objects from random linear measurements. When the linear functionals are Gaussian, we show that an s-sparse vector in ${\mathbb{R}^n}$ can be efficiently recovered from 2s log n measurements with high probability and a rank r, n × n matrix can be efficiently recovered from r(6n ? 5r) measurements with high probability. For sparse vectors, this is within an additive factor of the best known nonasymptotic bounds. For low-rank matrices, this matches the best known bounds. We present a parallel analysis for block-sparse vectors obtaining similarly tight bounds. In the case of sparse and block-sparse signals, we additionally demonstrate that our bounds are only slightly weakened when the measurement map is a random sign matrix. Our results are based on analyzing a particular dual point which certifies optimality conditions of the respective convex programming problem. Our calculations rely only on standard large deviation inequalities and our analysis is self-contained.     

The optional stopping theorem for quantum martingales

In classical probability theory, a random time T is a stopping time in a filtration (Ft)_t?0 if and only if the optional sampling holds at T for all bounded martingales. Furthermore, if a process (Xt)_t?0 is progressively measurable with respect to (Ft)_t?0, then XT is FT-measurable. Unfortunately, this is not the case in noncommutative probability with the definition of stopped process used until now. It is shown in this article that we can define the stopping of noncommutative processes in Fock space in such a way that all the bounded martingales can be stopped at any stopping time T, are adapted to the filtration of the past before T and satisfy the optional stopping theorem.     

A note on multitype branching process with bounded immigration in random environment

In this paper, we study the total number of progeny, W, before regenerating of multitype branching process with immigration in random environment. We show that the tail probability of |W| is of order t-κ as t→∞, with κ some constant. As an application, we prove a stable law for (L-1) random walk in random environment, generalizing the stable law for the nearest random walk in random environment (see "Kesten, Kozlov, Spitzer: A limit law for random walk in a random environment. Compositio Math., 30, 145-168 (1975)").     

On the service system MX/G/∞

In the present paper we consider the service system M^X/G/∞ characterized by an infinite number of servers anda general service time distribution. The customers arrive at the system in groups of size X, which is a random variable, the time between group arrivals being exponentially distributed. Using simple probability arguments, we obtain probability generating functions (p.g.f.'s) of the number of busy servers at time t and the number that depart by time t. Several other properties of these random variables are also discussed.     

Gauss inequalities on ordered linear spaces

Markov inequalities on ordered linear spaces are tightened through the α-unimodality of the corresponding measures. Modality indices are studied for various induced measures, including the singular values of a random matrix and the periodogram of a time series. These tools support a detailed study of linear inference and the ordering of random matrices, to include fixed and random designs and probability bounds on their comparative efficiencies. Other applications include probability bounds on quadratic forms and of order statistics on Rⁿ, on periodograms in the analysis of time series, and on run-length distributions in multivariate statistical process control. Connections to other topics in applied probability and statistics are noted.     

On the Beck‐Fiala conjecture for random set systems

Motivated by the Beck‐Fiala conjecture, we study discrepancy bounds for random sparse set systems. Concretely, these are set systems (X,Σ), where each element x ∈ X lies in t randomly selected sets of Σ, where t is an integer parameter. We provide new bounds in two regimes of parameters. We show that when |Σ| ≥ |X| the hereditary discrepancy of (X,Σ) is with high probability ; and when |X| ? |Σ|^t the hereditary discrepancy of (X,Σ) is with high probability O(1). The first bound combines the Lovász Local Lemma with a new argument based on partial matchings; the second follows from an analysis of the lattice spanned by sparse vectors.     

Bounds and constructions of <Emphasis Type="Italic">t</Emphasis>-spontaneous emission error designs

The combinatorial aspects of quantum codes were demonstrated in the study of decay processes of certain quantum systems used in the newly emerging field of quantum computing. Among them, the configuration of t-spontaneous emission error design (t-SEED) was proposed to correct errors caused by quantum jumps. The number of designs (dimension) in a t-SEED corresponds to the number of orthogonal basis states in a quantum jump code. In this paper the upper and lower bounds on the dimensions of 3-\((v,\,4;\,m)\) SEEDs are studied and the necessary and sufficient conditions for 3-SEEDs attaining the upper bounds are described. Several new combinatorial constructions are presented for general t-SEEDs and lots of t-SEEDs of new parameters with \(t\ge 3\) are shown to exist.     

On the Lipschitz constant of the RSK correspondence

We view the RSK correspondence as associating to each permutation π∈Sn a Young diagram λ=λ(π), i.e. a partition of n. Suppose now that π is left-multiplied by t transpositions, what is the largest number of cells in λ that can change as a result? It is natural refer to this question as the search for the Lipschitz constant of the RSK correspondence.We show upper bounds on this Lipschitz constant as a function of t. For t=1, we give a construction of permutations that achieve this bound exactly. For larger t we construct permutations which come close to matching the upper bound that we prove.     

Approximation and estimation of very small probabilities of multivariate extreme events

This article discusses modelling of the tail of a multivariate distribution function by means of a large deviation principle (LDP), and its application to the estimation of the probability p _n of a multivariate extreme event from a sample of n iid random vectors, with \(p_{n}\in [n^{-\tau _{2}},n^{-\tau _{1}}]\) for some t ₁>1 and t ₂>t ₁. One way to view the classical tail limits is as limits of probability ratios. In contrast, the tail LDP provides asymptotic bounds or limits for log-probability ratios. After standardising the marginals to standard exponential, tail dependence is represented by a homogeneous rate function I. Furthermore, the tail LDP can be extended to represent both dependence and marginals, the latter implying marginal log-Generalised Weibull tail limits. A connection is established between the tail LDP and residual tail dependence (or hidden regular variation) and a recent extension of it. Under a smoothness assumption, they are implied by the tail LDP. Based on the tail LDP, a simple estimator for very small probabilities of extreme events is formulated. It avoids estimation of I by making use of its homogeneity. Strong consistency in the sense of convergence of log-probability ratios is proven. Simulations and an application illustrate the difference between the classical approach and the LDP-based approach.     

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.     

On lower bounds on the size of designs in compact symmetric spaces of rank 1

The concept of t-designs in compact symmetric spaces of rank 1 is a generalization of the theory of classical t-designs. In this paper we obtain new lower bounds on the cardinality of designs in projective compact symmetric spaces of rank 1. With one exception our bounds are the first improvements of the classical bounds by more than one. We use the linear programming technique and follow the approach we have proposed for spherical codes and designs. Some examples are shown and compared with the classical bounds.     

DIMENSION RESULTS FOR ORNSTEIN-UHLENBECK TYPE MARKOV PROCESS

Let {X_t, t ≥ 0} be an Ornstein-Uhlenbeck type Markov process with Levy process A_t, the authors consider the fractal properties of its ranges, give the upper and lower bounds of the Hausdorff dimensions of the ranges and the estimate of the dimensions of the level sets for the process. The existence of local times and occuption times of X_t are considered in some special situations.     

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].