Search

We study two adaptive importance sampling schemes for estimating the probability of a rare event in the high-dimensional regime $d \to \infty$ with $d$ the dimension. The first scheme, motivated by recent results, seeks to use as auxiliary distribution a projection of the optimal auxiliary distribution (optimal among Gaussian distributions, and in the sense of the Kullback--Leibler divergence); the second scheme is the prominent cross-entropy method. In these schemes, two samples are used: the first one to learn the auxiliary distribution and the second one, drawn according to the learnt distribution, to perform the final probability estimation. Contrary to the common belief that the sample size needs to grow exponentially in the dimension to make the estimator consistent and avoid the weight degeneracy phenomenon, we find that a polynomial sample size in the first learning step is enough. We prove this result assuming that the sought probability is bounded away from $0$. For the first scheme, we show that the sample size only needs to grow like $rd$ with $r$ the effective dimension of the projection, while for cross-entropy, the polynomial growth rate remains implicit although insight on its value is provided. In addition to proving consistency, we also prove that in the regimes studied, the importance sampling weights do not degenerate.

In this paper we propose a dimension-reduction strategy in order to improve the performance of importance sampling in high dimension. The idea is to estimate variance terms in a small number of suitably chosen directions. We first prove that the optimal directions, i.e., the ones that minimize the Kullback--Leibler divergence with the optimal auxiliary density, are the eigenvectors associated to extreme (small or large) eigenvalues of the optimal covariance matrix. We then perform extensive numerical experiments that show that as dimension increases, these directions give estimations which are very close to optimal. Moreover, we show that the estimation remains accurate even when a simple empirical estimator of the covariance matrix is used to estimate these directions. These theoretical and numerical results open the way for different generalizations, in particular the incorporation of such ideas in adaptive importance sampling schemes.

This paper belongs to a series of papers aiming to investigate scaling limits of Crump-Mode-Jagers (CMJ) trees. In the previous two papers we identified general conditions under which CMJ trees belong to the universality class of Galton-Watson and Bellman-Harris processes. In this paper we identify general conditions for CMJ trees to belong to the universality class of binary, homogeneous CMJ trees. These conditions state that the offspring process should 'look like' a renewal process, and also that it should not accumulate too many atoms near the origin. We show in particular that any renewal process satisfies these conditions.

Rare event probability estimation is an important topic in reliability analysis. Stochastic methods, such as importance sampling, have been developed to estimate such probabilities but they often fail in high dimension. In this paper, we propose a new cross-entropy-based importance sampling algorithm to improve rare event probability estimation in high dimension. We focus on the cross-entropy method with Gaussian auxiliary distributions and we suggest to update the Gaussian covariance matrix only in a one-dimensional subspace. For that purpose, the main idea is to consider the projection in the one-dimensional subspace spanned by the sample mean vector, which gives an influential direction for the variance estimation. This approach does not require any additional simulation budget compared to the basic cross-entropy algorithm and we show on different numerical test cases that it greatly improves its performance in high dimension.

In reliability-based design, the estimation of the failure probability is a crucial objective. However, focusing only on the occurrence of the failure event may be insufficient to entirely characterize the reliability of the considered system. This paper provides a common estimation scheme of two complementary moment independent sensitivity measures, allowing to improve the understanding of the system's reliability. Numerical applications are performed in order to show the effectiveness of the proposed estimation procedure., Comment: New version with a comparison to ROSA Sobol indices

We study a model of wireless networks where users move at speed s, which has the original feature of being defined through a fixed-point equation. Namely, we start from a two-class Processor-Sharing queue to model one representative cell of this network: class 1 users are not impatient (non-moving) and class 2 users are impatient (moving). This model has five parameters, and we study the case where one of these parameters is set as a function of the other four through a fixed-point equation. This fixed-point equation captures the fact that the considered cell is in balance with the rest of the network. This modeling approach allows us to alleviate some drawbacks of earlier models of mobile networks. Our main and surprising finding is that for this model, mobility drastically improves the heavy traffic behavior, going from the usual 1/(1-rho) scaling without mobility (i.e., when s=0) to a logarithmic scaling -log(1-rho) as soon as s>0. In the high load regime, this confirms that the performance of mobile system takes benefit from the spatial mobility of users. Other model extensions and complementary methodological approaches to this heavy traffic analysis are finally discussed.

We examine a queue-based random-access algorithm where activation and deactivation rates are adapted as functions of queue lengths. We establish its heavy traffic behavior on a complete interference graph, which turns out to be highly nonstandard in two respects: (1) the scaling depends on some parameter of the algorithm and is not the $N/N^2$ scaling usually found in functional central limit theorems; (2) the heavy traffic limit is deterministic. We discuss how this nonstandard behavior arises from the idleness induced by the distributed nature of the algorithm. In order to prove our main result, we developed a new method for obtaining a fully coupled stochastic averaging principle., Comment: 40 pages

Crump-Mode-Jagers (CMJ) trees generalize Galton-Watson trees by allowing individuals to live for an arbitrary duration and give birth at arbitrary times during their life-time. In this paper, we are interested in the height and contour processes encoding a general CMJ tree. We show that the one-dimensional distribution of the height process can be expressed in terms of a random transformation of the ladder height process associated with the underlying Lukasiewicz path. As an application of this result, when edges of the tree are "short" we show that, asymptotically, (1) the height process is obtained by stretching by a constant factor the height process of the associated genealogical Galton-Watson tree, (2) the contour process is obtained from the height process by a constant time change and (3) the CMJ trees converge in the sense of finite-dimensional distributions., Comment: introduction of the spine process, generalizing to the chronological setting the classical discrete exploration process

We establish a sufficient condition for the tightness of a sequence of stochastic processes. Our condition makes it possible to study processes with accumulations of fixed times of discontinuity. Our motivation comes from the study of processes in varying or random environment. We demonstrate the usefulness of our condition on two examples: Galton Watson branching processes in varying environment and logistic branching processes with catastrophes., Comment: Result of first version generalized and proof simplified

We consider the following Markovian dynamic on point processes: at constant rate and with equal probability, either the rightmost atom of the current configuration is removed, or a new atom is added at a random distance from the rightmost atom. Interpreting atoms as limit buy orders, this process was introduced by Lakner et al. to model a one-sided limit order book. We consider this model in the regime where the total number of orders converges to a reflected Brownian motion, and complement the results of Lakner et al. by showing that, in the case where the mean displacement at which a new order is added is positive, the measure-valued process describing the whole limit order book converges to a simple functional of this reflected Brownian motion. Our results make it possible to derive useful and explicit approximations on various quantities of interest such as the depth or the total value of the book. Our approach leverages an unexpected connection with L\'evy trees. More precisely, the cornerstone of our approach is the regenerative characterization of L\'evy trees due to Weill, which provides an elegant proof strategy which we unfold., Comment: Accepted for publication in stochastic systems

We study a multistage epidemic model which generalizes the SIR model and where infected individuals go through K>0 stages of the epidemic before being removed. An infected individual in stage k=1,...,K may infect a susceptible individual, who directly goes to stage k of the epidemic; or it may go to the next stage k+1 of the epidemic. For this model, we identify the critical regime in which we establish diffusion approximations. Surprisingly, the limiting diffusion exhibits an unusual form of state space collapse which we analyze in detail., Comment: The exposition of the results has been significantly changed

Recent advances have resulted in queue-based algorithms for medium access control which operate in a distributed fashion, and yet achieve the optimal throughput performance of centralized scheduling algorithms. However, fundamental performance bounds reveal that the "cautious" activation rules involved in establishing throughput optimality tend to produce extremely large delays, typically growing exponentially in 1/(1-r), with r the load of the system, in contrast to the usual linear growth. Motivated by that issue, we explore to what extent more "aggressive" schemes can improve the delay performance. Our main finding is that aggressive activation rules induce a lingering effect, where individual nodes retain possession of a shared resource for excessive lengths of time even while a majority of other nodes idle. Using central limit theorem type arguments, we prove that the idleness induced by the lingering effect may cause the delays to grow with 1/(1-r) at a quadratic rate. To the best of our knowledge, these are the first mathematical results illuminating the lingering effect and quantifying the performance impact. In addition extensive simulation experiments are conducted to illustrate and validate the various analytical results.

We consider a model for a one-sided limit order book proposed by Lakner et al. We show that it can be coupled with a branching random walk and use this coupling to answer a non-trivial question about the long-term behavior of the price. The coupling relies on a classical idea of enriching the state-space by artificially creating a filiation, in this context between orders of the book, that we believe has the potential of being useful for a broader class of models., Comment: Minor error in the proof of Theorem 1 corrected. Final version accepted for publication to Journal of Applied Probability

Consider compound Poisson processes with negative drift and no negative jumps, which converge to some spectrally positive L\'evy process with non-zero L\'evy measure. In this paper we study the asymptotic behavior of the local time process, in the spatial variable, of these processes killed at two different random times: either at the time of the first visit of the L\'evy process to 0, in which case we prove results at the excursion level under suitable conditionings; or at the time when the local time at 0 exceeds some fixed level. We prove that finite-dimensional distributions converge under general assumptions, even if the limiting process is not c\`adl\`ag. Making an assumption on the distribution of the jumps of the compound Poisson processes, we strengthen this to get weak convergence. Our assumption allows for the limiting process to be a stable L\'evy process with drift. These results have implications on branching processes and in queueing theory, namely, on the scaling limit of binary, homogeneous Crump-Mode-Jagers processes and on the scaling limit of the Processor-Sharing queue length process., Comment: Final version accepted for publication in Journal of Theoretical Probability

We consider regenerative processes with values in some Polish space. We define their \epsilon-big excursions as excursions e such that f(e)>\epsilon, where f is some given functional on the space of excursions which can be thought of as, e.g., the length or the height of e. We establish a general condition that guarantees the convergence of a sequence of regenerative processes involving the convergence of \epsilon-big excursions and of their endpoints, for all \epsilon in a countable set whose closure contains 0. Finally, we provide various sufficient conditions on the excursion measures of this sequence for this general condition to hold and discuss possible generalizations of our approach to processes that can be written as the concatenation of i.i.d. paths., Comment: Final version accepted for publication in Annales de l'Institut Henri Poincar\'e

We consider a stochastic network with mobile users in a heavy-traffic regime. We derive the scaling limit of the multi-dimensional queue length process and prove a form of spatial state space collapse. The proof exploits a recent result by Lambert and Simatos which provides a general principle to establish scaling limits of regenerative processes based on the convergence of their excursions. We also prove weak convergence of the sequences of stationary joint queue length distributions and stationary sojourn times., Comment: Final version accepted for publication in Queueing Systems, Theory and Applications

We establish a general sufficient condition for a sequence of Galton Watson branching processes in varying environment to converge weakly. This condition extends previous results by allowing offspring distributions to have infinite variance, which leads to a new and subtle phenomena when the process goes through a bottleneck and also in terms of time scales. Our assumptions are stated in terms of pointwise convergence of a triplet of two real-valued functions and a measure. The limiting process is characterized by a backwards ordinary differential equation satisfied by its Laplace exponent, which generalizes the branching equation satisfied by continuous state branching processes. Several examples are discussed, namely branching processes in random environment, Feller diffusion in varying environment and branching processes with catastrophes., Comment: Tightness is now proved in a separate paper (arXiv 1409.5215)

We study the convergence of the $M/G/1$ processor-sharing, queue length process in the heavy traffic regime, in the finite variance case. To do so, we combine results pertaining to L\'{e}vy processes, branching processes and queuing theory. These results yield the convergence of long excursions of the queue length processes, toward excursions obtained from those of some reflected Brownian motion with drift, after taking the image of their local time process by the Lamperti transformation. We also show, via excursion theoretic arguments, that this entails the convergence of the entire processes to some (other) reflected Brownian motion with drift. Along the way, we prove various invariance principles for homogeneous, binary Crump-Mode-Jagers processes. In the last section we discuss potential implications of the state space collapse property, well known in the queuing literature, to branching processes., Comment: Published in at http://dx.doi.org/10.1214/12-AAP904 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Dynamic Spectrum Access systems exploit temporarily available spectrum (`white spaces') and can spread transmissions over a number of non-contiguous sub-channels. Such methods are highly beneficial in terms of spectrum utilization. However, excessive fragmentation degrades performance and hence off-sets the benefits. Thus, there is a need to study these processes so as to determine how to ensure acceptable levels of fragmentation. Hence, we present experimental and analytical results derived from a mathematical model. We model a system operating at capacity serving requests for bandwidth by assigning a collection of gaps (sub-channels) with no limitations on the fragment size. Our main theoretical result shows that even if fragments can be arbitrarily small, the system does not degrade with time. Namely, the average total number of fragments remains bounded. Within the very difficult class of dynamic fragmentation models (including models of storage fragmentation), this result appears to be the first of its kind. Extensive experimental results describe behavior, at times unexpected, of fragmentation under different algorithms. Our model also applies to dynamic linked-list storage allocation, and provides a novel analysis in that domain. We prove that, interestingly, the 50% rule of the classical (non-fragmented) allocation model carries over to our model. Overall, the paper provides insights into the potential behavior of practical fragmentation algorithms.

File-sharing networks are distributed systems used to disseminate files among nodes of a communication network. The general simple principle of these systems is that once a node has retrieved a file, it may become a server for this file. In this paper, the capacity of these networks is analyzed with a stochastic model when there is a constant flow of incoming requests for a given file. It is shown that the problem can be solved by analyzing the asymptotic behavior of a class of interacting branching processes. Several results of independent interest concerning these branching processes are derived and then used to study the file-sharing systems.

An occupancy problem with an infinite number of bins and a random probability vector for the locations of the balls is considered. The respective sizes of bins are related to the split times of a Yule process. The asymptotic behavior of the landscape of first empty bins, i.e., the set of corresponding indices represented by point processes, is analyzed and convergences in distribution to mixed Poisson processes are established. Additionally, the influence of the random environment, the random probability vector, is analyzed. It is represented by two main components: an i.i.d. sequence and a fixed random variable. Each of these components has a specific impact on the qualitative behavior of the stochastic model. It is shown in particular that for some values of the parameters, some rare events, which are identified, play an important role on average values of the number of empty bins in some regions.

A stochastic model for a mobile network is studied. Users enter the network, and then perform independent Markovian routes between nodes where they receive service according to the Processor-Sharing policy. Once their service requirement is satisfied, they leave the system. The stability region is identified via a fluid limit approach, and strongly relies on a "spatial homogenization" property: at the fluid level, customers are instantaneously distributed across the network according to the stationary distribution of their Markovian dynamics and stay distributed as such as long as the network is not empty. In the unstable regime, spatial homogenization almost surely holds asymptotically as time goes to infinity (on the normal scale), telling how the system fills up. One of the technical achievements of the paper is the construction of a family of martingales associated to the multidimensional process of interest, which makes it possible to get crucial estimates for certain exit times., Comment: Published in at http://dx.doi.org/10.1214/09-AAP613 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

We investigate in this paper the performance of a simple file sharing principle. For this purpose, we consider a system composed of N peers becoming active at exponential random times; the system is initiated with only one server offering the desired file and the other peers after becoming active try to download it. Once the file has been downloaded by a peer, this one immediately becomes a server. To investigate the transient behavior of this file sharing system, we study the instant when the system shifts from a congested state where all servers available are saturated by incoming demands to a state where a growing number of servers are idle. In spite of its apparent simplicity, this queueing model (with a random number of servers) turns out to be quite difficult to analyze. A formulation in terms of an urn and ball model is proposed and corresponding scaling results are derived. These asymptotic results are then compared against simulations.

The Recoil Growth algorithm, proposed in 1999 by Consta et al., is one of the most efficient algorithm available in the literature to sample from a multi-polymer system. Such problems are closely related to the generation of self-avoiding paths. In this paper, we study a variant of the original Recoil Growth algorithm, where we constrain the generation of a new polymer to take place on a specific class of graphs. This makes it possible to make a fine trade-off between computational cost and success rate. We moreover give a simple proof for a lower bound on the irreducibility of this new algorithm, which applies to the original algorithm as well., Comment: Title changed