In this paper we develop a collection of results associated to the analysis of the sequential Monte Carlo (SMC) samplers algorithm, in the context of high-dimensional independent and identically distributed target probabilities. The SMC samplers algorithm can be designed to sample from a single probability distribution, using Monte Carlo to approximate expectations with respect to this law. Given a target density in d dimensions our results are concerned with d → ∞, while the number of Monte Carlo samples, N, remains fixed. We deduce an explicit bound on the Monte-Carlo error for estimates derived using the SMC sampler and the exact asymptotic relative -error of the estimate of the normalising constant associated to the target. We also establish marginal propagation of chaos properties of the algorithm. These results are deduced when the cost of the algorithm is O(Nd2).

Consider a one-dimensional diffusion process on the diffusion interval I originated in x0 ∈ I. Let a(t) and b(t) be two continuous functions of t, t > t0, with bounded derivatives, a(t) < b(t), and a(t), b(t) ∈ I, for all t > t0. We study the joint distribution of the two random variables Ta and Tb, the first hitting times of the diffusion process through the two boundaries a(t) and b(t), respectively. We express the joint distribution of Ta and Tb in terms of ℙ(Ta < t, Ta < Tb) and ℙ(Tb < t, Ta > Tb), and we determine a system of integral equations verified by these last probabilities. We propose a numerical algorithm to solve this system and we prove its convergence properties. Examples and modeling motivation for this study are also discussed.

We consider an investment problem where observing and trading are only possible at random times. In addition, we introduce drawdown constraints which require that the investor's wealth does not fall under a prior fixed percentage of its running maximum. The financial market consists of a riskless bond and a stock which is driven by a Lévy process. Moreover, a general utility function is assumed. In this setting we solve the investment problem using a related limsup Markov decision process. We show that the value function can be characterized as the unique fixed point of the Bellman equation and verify the existence of an optimal stationary policy. Under some mild assumptions the value function can be approximated by the value function of a contracting Markov decision process. We are able to use Howard's policy improvement algorithm for computing the value function as well as an optimal policy. These results are illustrated in a numerical example.

In this paper, bounded variation control of one-dimensional diffusion processes is considered. We assume that the agent is allowed to control the diffusion only at the jump times of an observable, independent Poisson process. The agent's objective is to maximize the expected present value of the cumulative payoff generated by the controlled diffusion over its lifetime. We propose a relatively weak set of assumptions on the underlying diffusion and the instantaneous payoff structure, under which we solve the problem in closed form. Moreover, we illustrate the main results with an explicit example.

We study the conditions for positive recurrence and transience of multi-dimensional birth-and-death processes describing the evolution of a large class of stochastic systems, a typical example being the randomly varying number of flow-level transfers in a telecommunication wire-line or wireless network. First, using an associated deterministic dynamical system, we provide a generic method to construct a Lyapunov function when the drift is a smooth function on ℝN. This approach gives an elementary and direct proof of ergodicity. We also provide instability conditions. Our main contribution consists of showing how discontinuous drifts change the nature of the stability conditions and of providing generic sufficient stability conditions having a simple geometric interpretation. These conditions turn out to be necessary (outside a negligible set of the parameter space) for piecewise constant drifts in dimension two.

We derive explicit lower and upper bounds for the probability generating functional of a stationary locally stable Gibbs point process, which can be applied to summary statistics such as the F function. For pairwise interaction processes we obtain further estimates for the G and K functions, the intensity, and higher-order correlation functions. The proof of the main result is based on Stein's method for Poisson point process approximation.

In this article we study the parabolic system of equations which is closely related to a multitype branching Brownian motion. Particular attention is paid to the monotone traveling wave solutions of this system. Provided with some moment conditions, we show the existence, uniqueness, and asymptotic behaviors of such waves with speed greater than or equal to a critical value c̲ and nonexistence of such waves with speed smaller than c̲.

We consider a broad class of fair leader election algorithms, and study the duration of contestants (the number of rounds a randomly selected contestant stays in the competition) and the overall cost of the algorithm. We give sufficient conditions for the duration to have a geometric limit distribution (a perpetuity built from Bernoulli random variables), and for the limiting distribution of the total cost (after suitable normalization) to be a perpetuity. For the duration, the proof is established via convergence (to 0) of the first-order Wasserstein distance from the geometric limit. For the normalized overall cost, the method of proof is also convergence of the first-order Wasserstein distance, augmented with an argument based on a contraction mapping in the first-order Wasserstein metric space to show that the limit approaches a unique fixed-point solution of a perpetuity distributional equation. The use of these two steps is commonly referred to as the contraction method.

We study an interacting random walk system on ℤ where at time 0 there is an active particle at 0 and one inactive particle on each site n ≥ 1. Particles become active when hit by another active particle. Once activated, the particle starting at n performs an asymmetric, translation invariant, nearest neighbor random walk with left-jump probability ln. We give conditions for global survival, local survival, and infinite activation both in the case where all particles are immortal and in the case where particles have geometrically distributed lifespan (with parameter depending on the starting location of the particle). More precisely, once activated, the particle at n survives at each step with probability pn ∈ [0, 1]. In particular, in the immortal case, we prove a 0-1 law for the probability of local survival when all particles drift to the right. Besides that, we give sufficient conditions for local survival or local extinction when all particles drift to the left. In the mortal case, we provide sufficient conditions for global survival, local survival, and local extinction (which apply to the immortal case with mixed drifts as well). Analysis of explicit examples is provided: we describe completely the phase diagram in the cases ½ - ln ~ ± 1 / nα, pn = 1 and ½ - ln ~ ± 1 / nα, 1 - pn ~ 1 / nβ (where α, β > 0).

We consider a class of infinite time horizon optimal stopping problems for spectrally negative Lévy processes. Focusing on strategies of threshold type, we write explicit expressions for the corresponding expected payoff via the scale function, and further pursue optimal candidate threshold levels. We obtain and show the equivalence of the continuous/smooth fit condition and the first-order condition for maximization over threshold levels. As examples of its applications, we give a short proof of the McKean optimal stopping problem (perpetual American put option) and solve an extension to Egami and Yamazaki (2013).

In this paper, we propose a new comparison tool for spatial homogeneity of point processes, based on the joint examination of void probabilities and factorial moment measures. We prove that determinantal and permanental processes, as well as, more generally, negatively and positively associated point processes are comparable in this sense to the Poisson point process of the same mean measure. We provide some motivating results on percolation and coverage processes, and preview further ones on other stochastic geometric models, such as minimal spanning forests, Lilypond growth models, and random simplicial complexes, showing that the new tool is relevant for a systemic approach to the study of macroscopic properties of non-Poisson point processes. This new comparison is also implied by the directionally convex ordering of point processes, which has already been shown to be relevant to the comparison of the spatial homogeneity of point processes. For this latter ordering, using a notion of lattice perturbation, we provide a large monotone spectrum of comparable point processes, ranging from periodic grids to Cox processes, and encompassing Poisson point processes as well. They are intended to serve as a platform for further theoretical and numerical studies of clustering, as well as simple models of random point patterns to be used in applications where neither complete regularity nor the total independence property are realistic assumptions.

We study the endemic behaviour of a homogeneously mixing SIS epidemic in a population of size N with a general infectious period, Q, by introducing a novel subcritical branching process with immigration approximation. This provides a simple but useful approximation of the quasistationary distribution of the SIS epidemic for finite N and the asymptotic Gaussian limit for the endemic equilibrium as N → ∞. A surprising observation is that the quasistationary distribution of the SIS epidemic model depends on Q only through

In this article we study a number of collisions concerning a simple occupancy problem with unequal probabilities. Using combinatorial arguments and negative associations of random variables, we have several limit theorems, namely, a weak law of large numbers and a Poisson law of small numbers including the Chen-Stein estimate.

In the present paper, we study the evolution of an overloaded cyclic polling model that starts empty. Exploiting a connection with multitype branching processes, we derive fluid asymptotics for the joint queue length process. Under passage to the fluid dynamics, the server switches between the queues infinitely many times in any finite time interval causing frequent oscillatory behavior of the fluid limit in the neighborhood of zero. Moreover, the fluid limit is random. In addition, we suggest a method that establishes finiteness of moments of the busy period in an M/G/1 queue.

Both small-world models of random networks with occasional long-range connections and gossip processes with occasional long-range transmission of information have similar characteristic behaviour. The long-range elements appreciably reduce the effective distances, measured in space or in time, between pairs of typical points. In this paper we show that their common behaviour can be interpreted as a product of the locally branching nature of the models. In particular, it is shown that both typical distances between points and the proportion of space that can be reached within a given distance or time can be approximated by formulae involving the limit random variable of the branching process.

As a version of the secretary problem, Ferguson, Hardwick and Tamaki (1992) considered an optimal stopping problem called the duration problem. The basic duration problem is the classical duration problem, in which the objective is to maximize the time of possession of a relatively best object when a known number of rankable objects appear in random order. In this paper we generalize this classical problem in two directions by allowing the number N (of available objects) to be a random variable with a known upper bound n and also allowing the objects to appear in accordance with Bernoulli trials. Two models can be considered for our random horizon duration problem according to whether the planning horizon is N or n. Since the form of the optimal rule is in general complicated, our main concern is to give to each model a sufficient condition for the optimal rule to be simple. For N having a uniform, generalized uniform, or curtailed geometric distribution, the optimal rule is shown to be simple in the so-called secretary case. The asymptotic results, as n → ∞, will also be given for these priors.

A probabilistic cellular automaton (PCA) can be viewed as a Markov chain. The cells are updated synchronously and independently, according to a distribution depending on a finite neighborhood. We investigate the ergodicity of this Markov chain. A classical cellular automaton is a particular case of PCA. For a one-dimensional cellular automaton, we prove that ergodicity is equivalent to nilpotency, and is therefore undecidable. We then propose an efficient perfect sampling algorithm for the invariant measure of an ergodic PCA. Our algorithm does not assume any monotonicity property of the local rule. It is based on a bounding process which is shown to also be a PCA. Last, we focus on the PCA majority, whose asymptotic behavior is unknown, and perform numerical experiments using the perfect sampling procedure.