We study a model for the destruction of a random network by fire. Suppose that we are given a multigraph of minimum degree at least 2 having real-valued edge lengths. We pick a uniform point from along the length and set it alight; the edges of the multigraph burn at speed 1. If the fire reaches a vertex of degree 2, the fire gets directly passed on to the neighbouring edge; a vertex of degree at least 3, however, passes the fire either to all of its neighbours or none, each with probability ${\textstyle{1 \over 2}}$. If the fire goes out before the whole network is burnt, we again set fire to a uniform point. We are interested in the number of fires which must be set in order to burn the whole network, and the number of points which are burnt from two different directions. We analyse these quantities for a random multigraph having n vertices of degree 3 and α(n) vertices of degree 4, where α(n)/n → 0 as n → ∞, with independent and identically distributed standard exponential edge lengths. Depending on whether $\alpha(n) \gg \sqrt{n}$ or $\alpha(n)=O(\sqrt{n})$, we prove that, as n → ∞, these quantities converge jointly in distribution when suitably rescaled to either a pair of constants or to (complicated) functionals of Brownian motion. We use our analysis of this model to make progress towards a conjecture of Aronson, Frieze and Pittel (1998) concerning the number of vertices which remain unmatched when we use the Karp–Sipser algorithm to find a matching on the Erdős–Rényi random graph.

In this paper we treat a two-stage grouping procedure of building a k-out-of-n system from several clusters of components. We use a static framework in which the component reliabilities are fixed. Under such a framework, we address the impact of the selecting strategies, the sampling probabilities, and the component reliabilities on the constructed system’s reliability. An interesting finding is that the level of component reliabilities could be identified as a decisive factor in determining how the selecting strategies and the component reliabilities affect the system reliability. The new results generalize and extend those established earlier in the literature such as Di Crescenzo and Pellerey (2011), Hazra and Nanda (2014), Navarro, Pellerey, and Di Crescenzo (2015), and Hazra, Finkelstein, and Cha (2017). Several Monte Carlo simulation experiments are provided to illustrate the theoretical results.

In this paper, we introduce a new large family of Lévy-driven point processes with (and without) contagion, by generalising the classical self-exciting Hawkes process and doubly stochastic Poisson processes with non-Gaussian Lévy-driven Ornstein–Uhlenbeck-type intensities. The resulting framework may possess many desirable features such as skewness, leptokurtosis, mean-reverting dynamics, and more importantly, the ‘contagion’ or feedback effects, which could be very useful for modelling event arrivals in finance, economics, insurance, and many other fields. We characterise the distributional properties of this new class of point processes and develop an efficient sampling method for generating sample paths exactly. Our simulation scheme is mainly based on the distributional decomposition of the point process and its intensity process. Extensive numerical implementations and tests are reported to demonstrate the accuracy and effectiveness of our scheme. Moreover, we use portfolio risk management as an example to show the applicability and flexibility of our algorithms.

We consider de Finetti’s problem for spectrally one-sided Lévy risk models with control strategies that are absolutely continuous with respect to the Lebesgue measure. Furthermore, we consider the version with a constraint on the time of ruin. To characterize the solution to the aforementioned models, we first solve the optimal dividend problem with a terminal value at ruin and show the optimality of threshold strategies. Next, we introduce the dual Lagrangian problem and show that the complementary slackness conditions are satisfied, characterizing the optimal Lagrange multiplier. Finally, we illustrate our findings with a series of numerical examples.

In large storage systems, files are often coded across several servers to improve reliability and retrieval speed. We study load balancing under the batch sampling routeing scheme for a network of n servers storing a set of files using the maximum distance separable (MDS) code (cf. Li (2016)). Specifically, each file is stored in equally sized pieces across L servers such that any k pieces can reconstruct the original file. When a request for a file is received, the dispatcher routes the job into the k-shortest queues among the L for which the corresponding server contains a piece of the file being requested. We establish a law of large numbers and a central limit theorem as the system becomes large (i.e. n → ∞), for the setting where all interarrival and service times are exponentially distributed. For the central limit theorem, the limit process take values in ℓ2, the space of square summable sequences. Due to the large size of such systems, a direct analysis of the n-server system is frequently intractable. The law of large numbers and diffusion approximations established in this work provide practical tools with which to perform such analysis. The power-of-d routeing scheme, also known as the supermarket model, is a special case of the model considered here.

In this paper we introduce the multivariate Brownian semistationary (BSS) process and study the joint asymptotic behaviour of its realised covariation using in-fill asymptotics. First, we present a central limit theorem for general multivariate Gaussian processes with stationary increments, which are not necessarily semimartingales. Then, we show weak laws of large numbers, central limit theorems, and feasible results for BSS processes. An explicit example based on the so-called gamma kernels is also provided.

We consider a random graph model that was recently proposed as a model for complex networks by Krioukov et al. (2010). In this model, nodes are chosen randomly inside a disk in the hyperbolic plane and two nodes are connected if they are at most a certain hyperbolic distance from each other. It has previously been shown that this model has various properties associated with complex networks, including a power-law degree distribution and a strictly positive clustering coefficient. The model is specified using three parameters: the number of nodes N, which we think of as going to infinity, and $\alpha, \nu > 0$, which we think of as constant. Roughly speaking, $\alpha$ controls the power-law exponent of the degree sequence and $\nu$ the average degree. Earlier work of Kiwi and Mitsche (2015) has shown that, when $\alpha \lt 1$ (which corresponds to the exponent of the power law degree sequence being $\lt 3$), the diameter of the largest component is asymptotically almost surely (a.a.s.) at most polylogarithmic in N. Friedrich and Krohmer (2015) showed it was a.a.s. $\Omega(\log N)$ and improved the exponent of the polynomial in $\log N$ in the upper bound. Here we show the maximum diameter over all components is a.a.s. $O(\log N),$ thus giving a bound that is tight up to a multiplicative constant.

We exhibit an exact simulation algorithm for the supremum of a stable process over a finite time interval using dominated coupling from the past (DCFTP). We establish a novel perpetuity equation for the supremum (via the representation of the concave majorants of Lévy processes [27]) and use it to construct a Markov chain in the DCFTP algorithm. We prove that the number of steps taken backwards in time before the coalescence is detected is finite. We analyse the performance of the algorithm numerically (the code, written in Julia 1.0, is available on GitHub).

We analyse the jigsaw percolation process, which may be seen as a measure of whether two graphs on the same vertex set are ‘jointly connected’. Bollobás, Riordan, Slivken, and Smith (2017) proved that, when the two graphs are independent binomial random graphs, whether the jigsaw process percolates undergoes a phase transition when the product of the two probabilities is $\Theta({1}/{(n\ln n)})$. We show that this threshold is sharp, and that it lies at ${1}/{(4n\ln n)}$.

In the literature on optimal stopping, the problem of maximizing the expected discounted reward over all stopping times has been explicitly solved for some special reward functions (including (x+)ν, (ex − K)+, (K − e− x)+, x ∈ ℝ, ν ∈ (0, ∞), and K > 0) under general random walks in discrete time and Lévy processes in continuous time (subject to mild integrability conditions). All such reward functions are continuous, increasing, and logconcave while the corresponding optimal stopping times are of threshold type (i.e. the solutions are one-sided). In this paper we show that all optimal stopping problems with increasing, logconcave, and right-continuous reward functions admit one-sided solutions for general random walks and Lévy processes, thereby generalizing the aforementioned results. We also investigate in detail the principle of smooth fit for Lévy processes when the reward function is increasing and logconcave.

There are two ways of speeding up Markov chain Monte Carlo algorithms: (a) construct more complex samplers that use gradient and higher-order information about the target and (b) design a control variate to reduce the asymptotic variance. While the efficiency of (a) as a function of dimension has been studied extensively, this paper provides the first results linking the efficiency of (b) with dimension. Specifically, we construct a control variate for a d-dimensional random walk Metropolis chain with an independent, identically distributed target using the solution of the Poisson equation for the scaling limit in [30]. We prove that the asymptotic variance of the corresponding estimator is bounded above by a multiple of $\log(d)/d$ over the spectral gap of the chain. The proof hinges on large deviations theory, optimal Young’s inequality and Berry–Esseen-type bounds. Extensions of the result to non-product targets are discussed.

We consider the nearest-neighbour simple exclusion process on the one-dimensional discrete torus $\mathbb{T}_N=\mathbb{Z}/N\mathbb{Z}$ , with random rates $c_N=\{c_{x,N}\colon x \in \mathbb{T}_N\}$ defined in terms of a homogeneous Poisson process on $\mathbb{R}$ with intensity $\lambda$ . Given a realization of the Poisson process, the jump rate along the edge $\{x,x+1\}$ is 1 if there is not any Poisson mark in $ (x,x+1) $ ; otherwise, it is $\lambda/N,\, \lambda \in( 0,1]$ . The density profile of this process with initial measure associated to an initial profile $\rho_0\colon \mathbb{R} \rightarrow [0,1]$ , evolves as the solution of a bounded diffusion random equation. This result follows from an appropriate quenched hydrodynamic limit. If $\lambda=1$ then $\rho$ is discontinuous at each Poisson mark with passage through the slow bonds, otherwise the conductance at the slow bonds decreases meaning no passage through the slow bonds in the continuum. The main results are concerned with upper and lower quenched and annealed bounds of $T_j$ , where $T_j$ is the first displacement time of a tagged particle in a stochastic cluster of size j (the cluster is defined via specific macroscopic density profiles). It is possible to observe that when time t grows, then $\mathbb{P}\{T_j \geq t\}$ decays quadratically in both the upper and lower bounds, and falls as slow as the presence of more Poisson marks neighbouring the tagged particle, as expected.

In this paper we develop the theory of the W and Z scale functions for right-continuous (upwards skip-free) discrete-time, discrete-space random walks, along the lines of the analogous theory for spectrally negative Lévy processes. Notably, we introduce for the first time in this context the one- and two-parameter scale functions Z, which appear for example in the joint deficit at ruin and time of ruin problems of actuarial science. Comparisons are made between the various theories of scale functions as one makes time and/or space continuous.

In Weil (2001) formulae were proved for stationary Boolean models Z in ℝd with convex or polyconvex grains, which express the densities (specific mean values) of mixed volumes of Z in terms of related mean values of the underlying Poisson particle process X. These formulae were then used to show that in dimensions 2 and 3 the densities of mixed volumes of Z determine the intensity γ of X. For d = 4, a corresponding result was also stated, but the proof given was incomplete, since in the formula for the density of the Euler characteristic V̅0(Z) of Z a term $\overline V^{(0)}_{2,2}(X,X)$ was missing. This was pointed out in Goodey and Weil (2002), where it was also explained that a new decomposition result for mixed volumes and mixed translative functionals would be needed to complete the proof. Such a general decomposition result has recently been proved by Hug, Rataj, and Weil (2013), (2018) and is based on flag measures of the convex bodies involved. Here, we show that such flag representations not only lead to a correct derivation of the four-dimensional result, but even yield a corresponding uniqueness theorem in all dimensions. In the proof of the latter we make use of Alesker’s representation theorem for translation invariant valuations. We also discuss which shape information can be obtained in this way and comment on the situation in the nonstationary case.

We propose an asymptotically optimal heuristic, which we term randomized assignment control (RAC) for a restless multi-armed bandit problem with discrete-time and finite states. It is constructed using a linear programming relaxation of the original stochastic control formulation. In contrast to most of the existing literature, we consider a finite-horizon problem with multiple actions and time-dependent (i.e. nonstationary) upper bound on the number of bandits that can be activated at each time period; indeed, our analysis can also be applied in the setting with nonstationary transition matrix and nonstationary cost function. The asymptotic setting is obtained by letting the number of bandits and other related parameters grow to infinity. Our main contribution is that the asymptotic optimality of RAC in this general setting does not require indexability properties or the usual stability conditions of the underlying Markov chain (e.g. unichain) or fluid approximation (e.g. global stable attractor). Moreover, our multi-action setting is not restricted to the usual dominant action concept. Finally, we show that RAC is also asymptotically optimal for a dynamic population, where bandits can randomly arrive and depart the system.

In this paper, we study a large multi-server loss model under the SQ(d) routeing scheme when the service time distributions are general with finite mean. Previous works have addressed the exponential service time case when the number of servers goes to infinity, giving rise to a mean field model. The fixed point of the limiting mean field equations (MFEs) was seen to be insensitive to the service time distribution in simulations, but no proof was available. While insensitivity is well known for loss systems, the models, even with state-dependent inputs, belong to the class of linear Markov models. In the context of SQ(d) routeing, the resulting model belongs to the class of nonlinear Markov processes (processes whose generator itself depends on the distribution) for which traditional arguments do not directly apply. Showing insensitivity to the general service time distributions has thus remained an open problem. Obtaining the MFEs in this case poses a challenge due to the resulting Markov description of the system being in positive orthant as opposed to a finite chain in the exponential case. In this paper, we first obtain the MFEs and then show that the MFEs have a unique fixed point that coincides with the fixed point in the exponential case, thus establishing insensitivity. The approach is via a measure-valued Markov process representation and the martingale problem to establish the mean field limit.

We consider discrete-time Markov chains with Polish state space. The large deviations principle for empirical measures of a Markov chain can equivalently be stated in Laplace principle form, which builds on the convex dual pair of relative entropy (or Kullback– Leibler divergence) and cumulant generating functional f ↦ ln ʃ exp (f). Following the approach by Lacker (2016) in the independent and identically distributed case, we generalize the Laplace principle to a greater class of convex dual pairs. We present in depth one application arising from this extension, which includes large deviation results and a weak law of large numbers for certain robust Markov chains—similar to Markov set chains—where we model robustness via the first Wasserstein distance. The setting and proof of the extended Laplace principle are based on the weak convergence approach to large deviations by Dupuis and Ellis (2011).

In this paper we study continuous-time two-player zero-sum optimal switching games on a finite horizon. Using the theory of doubly reflected backward stochastic differential equations with interconnected barriers, we show that this game has a value and an equilibrium in the players’ switching controls.

We study an urn process with two urns, initialized with a ball each. Balls are added sequentially, the urn being chosen independently with probability proportional to the $\alpha$th power $(\alpha >1)$ of the existing number of balls. We study the (rare) event that the urn compositions are balanced after the addition of $2n-2$ new balls. We derive precise asymptotics of the probability of this event by embedding the process in continuous time. Quite surprisingly, fine control of this probability may be leveraged to derive a lower-tail large deviation principle (LDP) for $L = \sum_{i=1}^{n} ({S_i^2}/{i^2})$, where $\{S_n \colon n \geq 0\}$ is a simple symmetric random walk started at zero. We provide an alternative proof of the LDP via coupling to Brownian motion, and subsequent derivation of the LDP for a continuous-time analog of L. Finally, we turn our attention back to the urn process conditioned to be balanced, and provide a functional limit law describing the trajectory of the urn process.

We consider random rectangles in $\mathbb{R}^2$ that are distributed according to a Poisson random measure, i.e. independently and uniformly scattered in the plane. The distributions of the length and the width of the rectangles are heavy tailed with different parameters. We investigate the scaling behaviour of the related random fields as the intensity of the random measure grows to infinity while the mean edge lengths tend to zero. We characterise the arising scaling regimes, identify the limiting random fields, and give statistical properties of these limits.