Unbiased estimates for gradients of stochastic network performance measures

Three classes of stochastic networks and their performance measures are considered. These performance measures are defined as the expected value of some random variables and cannot normally be obtained analytically as functions of network parameters in a closed form. We give similar representations for the random variables to provide a useful way of analytical study of these functions and their gradients. The representations are used to obtain sufficient conditions for the gradient estimates to be unbiased. The conditions are rather general and usually met in simulation study of the stochastic networks. Applications of the results are discussed and some practical algorithms of calculating unbiased estimates of the gradients are also presented.     

Particle filters with random resampling times

Particle filters are numerical methods for approximating the solution of the filtering problem which use systems of weighted particles that (typically) evolve according to the law of the signal process. These methods involve a corrective/resampling procedure which eliminates the particles that become redundant and multiplies the ones that contribute most to the resulting approximation. The correction is applied at instances in time called resampling/correction times. Practitioners normally use certain overall characteristics of the approximating system of particles (such as the effective sample size of the system) to determine when to correct the system. As a result, the resampling times are random. However, in the continuous time framework, all existing convergence results apply only to particle filters with deterministic correction times. In this paper, we analyse (continuous time) particle filters where resampling takes place at times that form a sequence of (predictable) stopping times. We prove that, under very general conditions imposed on the sequence of resampling times, the corresponding particle filters converge. The conditions are verified when the resampling times are chosen in accordance to the effective sample size of the system of particles, the coefficient of variation of the particles’ weights and, respectively, the (soft) maximum of the particles’ weights. We also deduce central-limit theorem type results for the approximating particle system with random resampling times.     

Complete convergence and Cesàro summation for i.i.d. random variables

Summary Various results generalizing summation methods for divergent series of real numbers to analogous results for independent, identically distributed random variables have appeared during the last two decades. The main result of this paper provides necessary and sufficient conditions for the complete convergence of the Cesàro means of i.i.d random variables.     

Zariski closure and the dimension of the Gaussian low of the product of random matrices. I

Summary We prove the Central Limit Theorem for products of i.i.d. random matrices. The main aim is to find the dimension of the corresponding Gaussian law. It turns out that ifG is the Zariski closure of a group generated by the support of the distribution of our matrices, and ifG is semi-simple, then the dimension of the Gaussian law is equal to the dimension of the diagonal part of Cartan decomposition ofG.In this article we present a detailed exposition of results announced in [GGu]. For reasons explained in the introduction, this part is devoted to the case ofSL(m, ) group. The general semi-simple Lie group will be considered in the second part of the work.The central limit theorem for products of independent random matrices is our main topic, and the results obtained complete to a large extent the general picture of the subject.The proofs rely on methods from two theories. One is the theory of asymptotic behaviour of products of random matrices itself. As usual, the existence of distinct Lyapunov exponents is the most important fact here. The other is the theory of algebraic groups. We want to point out that algebraic language and methods play a very important role in this paper.In fact, this mixture of methods has already been used for the study of Lyapunov exponents in [GM1, GM2, GR3]. We believe that it is impossible to avoid the algebraic approach if one aims to obtain complete and effective answers to natural problems arising in the theory of products of random matrices.In order also to present the general picture of the subject we describe several results which are well known. Some of these can be proven for stationary sequences of matrices, others are true also for infinite dimensional operators (see e.g. [BL, O, GM2, L, R]). But our main concern is with independent matrices, in which case very precise and constructive statements can be obtained.     

On the Bahadur representation of sample quantiles for sequences of φ-mixing random variables

The object of the present investigation is to show that the elegant asymptotic almost-sure representation of a sample quantile for independent and identically distributed random variables, established by Bahadur [1] holds for a stationary sequence of φ-mixing random variables. Two different orders of the remainder term, under different φ-mixing conditions, are obtained and used for proving two functional central limit theorems for sample quantiles. It is also shown that the law of iterated logarithm holds for quantiles in stationary φ-mixing processes.     

A Central Limit Theorem for linear random fields

A Central Limit Theorem is proved for linear random fields when sums are taken over union of finitely many disjoint rectangles. The approach does not rely upon the use of Beveridge-Nelson decomposition and the conditions needed are similar in nature to those given by Ibragimov for linear processes. When specializing this result to the case when sums are being taken over rectangles, a complete analogue of the Ibragimov result is obtained for random fields with a lot of uniformity.     

Conditional distribution of heavy tailed random variables on large deviations of their sum

It is known that large deviations of sums of subexponential random variables are most likely realised by deviations of a single random variable. In this article we give a detailed picture of how subexponential random variables are distributed when a large deviation of the sum is observed.     

Scaling limits of coupled continuous time random walks and residual order statistics through marked point processes

A continuous time random walk (CTRW) is a random walk in which both spatial changes represented by jumps and waiting times between the jumps are random. The CTRW is coupled if a jump and its preceding or following waiting time are dependent random variables (r.v.), respectively. The aim of this paper is to explain the occurrence of different limit processes for CTRWs with forward- or backward-coupling in Straka and Henry (2011) [37] using marked point processes. We also establish a series representation for the different limits. The methods used also allow us to solve an open problem concerning residual order statistics by LePage (1981) [20].     

Computable de Finetti measures

We prove a computable version of the de Finetti theorem on exchangeable sequences of real random variables. As a consequence, exchangeable stochastic processes expressed in probabilistic functional programming languages can be automatically rewritten as procedures that do not modify non-local state. Along the way, we prove that a distribution on the unit interval is computable if and only if its moments are uniformly computable.     

Quenched invariance principle for simple random walk on discrete point processes

We consider the simple random walk on random graphs generated by discrete point processes. This random walk moves on graphs whose vertex set is a random subset of a cubic lattice and whose edges are lines between any consecutive vertices on lines parallel to each coordinate axis. Under the assumption that the discrete point processes are finitely dependent and stationary, we prove that the quenched invariance principle holds, i.e., for almost every configuration of the point process, the path distribution of the walk converges weakly to that of a Brownian motion.     

The hyper-Dirichlet process and its discrete approximations: The butterfly model

The aim of this paper is the study of some random probability distributions, called hyper-Dirichlet processes. In the simplest situation considered in the paper these distributions charge the product of three sample spaces, with the property that the first and the last component are independent conditional to the middle one. The law of the marginals on the first two and on the last two components are specified to be Dirichlet processes with the same marginal parameter measure on the common second component. The joint law is then obtained as the hyper-Markov combination, introduced in [A.P. Dawid, S.L. Lauritzen, Hyper-Markov laws in the statistical analysis of decomposable graphical models, Ann. Statist. 21 (3) (1993) 1272-1317], of these two Dirichlet processes. The processes constructed in this way in fact are in fact generalizations of the hyper-Dirichlet laws on contingency tables considered in the above paper. Our main result is the convergence to the hyper-Dirichlet process of the sequence of hyper-Dirichlet laws associated to finer and finer “discretizations” of the two parameter measures, which is proved by means of a suitable coupling construction.     

Limiting behavior of a diffusion in an asymptotically stable environment

Let V be a two sided random walk and let X denote a real valued diffusion process with generator . This process is the continuous equivalent of the one-dimensional random walk in random environment with potential V. Hu and Shi (1997) described the Lévy classes of X in the case where V behaves approximately like a Brownian motion. In this paper, based on some fine results on the fluctuations of random walks and stable processes, we obtain an accurate image of the almost sure limiting behavior of X when V behaves asymptotically like a stable process. These results also apply for the corresponding random walk in random environment.     

Effect of truncation on large deviations for heavy-tailed random vectors

This paper studies the effect of truncation on the large deviations behavior of the partial sum of a triangular array coming from a truncated power law model. Each row of the triangular array consists of i.i.d. random vectors, whose distribution matches a power law on a ball of radius going to infinity, and outside that it has a light-tailed modification. The random vectors are assumed to be R^d-valued. It turns out that there are two regimes depending on the growth rate of the truncating threshold, so that in one regime, much of the heavy tailedness is retained, while in the other regime, the same is lost.     

一类独立随机场的强定律的收敛率

§ 1　IntroductionDefinition1 .[1 ] A field{ Xi,i∈Nd} is called negatively associated(NA) if for every pair ofdisjoint subsets T1 ,T2 of Nd,Cov(f1 (Xi,i∈ T1 ) ,f2 (Xj,j∈ T2 ) )≤ 0 ,whenever f1 and f2 are coordinatewise increasing.Definition2 .[1 ] A field{ Xi,i∈Nd} is calledρ* -mixing ifρ* (s) =sup{ (ρ(S,T) ;S,T N,dist(S,T)≥ s}→ 0 (s→∞ ) ,whereρ(S,T) =sup{ |E(f -Ef) (g -Eg) |/‖ f -Ef‖2 ‖ g -Eg‖2 ,f∈ L2 (σ(S) ) ,g∈ L2 (σ(T) ) } .Definition 3.[1 ] A field { Xi…     

On Pearson-Kotz Dirichlet distributions

In this paper, we discuss some basic distributional and asymptotic properties of the Pearson-Kotz Dirichlet multivariate distributions. These distributions, which appear as the limit of conditional Dirichlet random vectors, possess many appealing properties and are interesting from theoretical as well as applied points of view. We illustrate an application concerning the approximation of the joint conditional excess distribution of elliptically symmetric random vectors.     

Intrinsic volumes of the maximal polytope process in higher dimensional STIT tessellations

Stationary and isotropic iteration stable random tessellations are considered, which are constructed by a random process of iterative cell division. The collection of maximal polytopes at a fixed time t within a convex window W⊂R^d is regarded and formulas for mean values, variances and a characterization of certain covariance measures are proved. The focus is on the case d≥3, which is different from the planar one, treated separately in Schreiber and Thäle (2010) [12]. Moreover, a limit theorem for suitably rescaled intrinsic volumes is established, leading — in sharp contrast to the situation in the plane — to a non-Gaussian limit.     

Effort associated with a class of random optimization methods

When differentiability is not assumed random procedures can be successfully used to estimate the extreme values of a given function. For a class of such algorithms we treat the problem of estimating the mean effort.Research partially supported by CNPq-Brazil.     

Zeno's walk: A random walk with refinements

Summary. A self-modifying random walk on is derived from an ordinary random walk on the integers by interpolating a new vertex into each edge as it is crossed. This process converges almost surely to a random variable which is totally singular with respect to Lebesgue measure, and which is supported on a subset of having Hausdorff dimension less than , which we calculate by a theorem of Billingsley. By generating function techniques we then calculate the exponential rate of convergence of the process to its limit point, which may be taken as a bound for the convergence of the measure in the Wasserstein metric. We describe how the process may viewed as a random walk on the space of monotone piecewise linear functions, where moves are taken by successive compositions with a randomly chosen such function. Received: 20 November 1995 / In revised form: 14 May 1996     

Convergence rates in the strong laws of asymptotically negatively associated random fields

In this paper, a notion of negative side p-mixing (p -mixing) which can be regardedas asymptotic negative association is defined, and some Rosenthal type inequalities for p -mix-ing random fields are established. The complete convergence and almost sure summability onthe convergence rates with respect to the strong law of large numbers are also discussed for p--mixing random fields. The results obtained extend those for negatively associated sequences andp“ -mixing random fields.     

Stein’s method for invariant measures of diffusions via Malliavin calculus

Given a random variable F$F$ regular enough in the sense of the Malliavin calculus, we are able to measure the distance between its law and any probability measure with a density function which is continuous, bounded, strictly positive on an interval in the real line and admits finite variance. The bounds are given in terms of the Malliavin derivative of F$F$. Our approach is based on the theory of Itô diffusions and the stochastic calculus of variations. Several examples are considered in order to illustrate our general results.