The vertices of the kth power of a directed path with n vertices are exposed one by one to a selector in some random order. At any time the selector can see the graph induced by the vertices that have already appeared. The selector's aim is to choose online the maximal vertex (i.e. the vertex with no outgoing edges). We give upper and lower bounds for the asymptotic behaviour of pn,kn1/(k+1), where pn,k is the probability of success under the optimal algorithm. In order to derive the upper bound, we consider a model in which the selector obtains some extra information about the edges that have already appeared. We give the exact asymptotics of the probability of success under the optimal algorithm in this case. In order to derive the lower bound, we analyse a site percolation process on a sequence of the kth powers of a directed path with n vertices.

In the present work, some new maximal inequalities for nonnegative N-demi(super)martingales are first developed. As an application, new bounds for the cumulative distribution function of the waiting time for the first occurrence of a scan statistic in a sequence of independent and identically distributed (i.i.d.) binary trials are obtained. A numerical study is also carried out for investigating the behavior of the new bounds.

Recently, Rao et al. (2004) introduced an alternative measure of uncertainty known as the cumulative residual entropy (CRE). It is based on the survival (reliability) function F̅ instead of the probability density function f used in classical Shannon entropy. In reliability based system design, the performance characteristics of the coherent systems are of great importance. Accordingly, in this paper, we study the CRE for coherent and mixed systems when the component lifetimes are identically distributed. Bounds for the CRE of the system lifetime are obtained. We use these results to propose a measure to study if a system is close to series and parallel systems of the same size. Our results suggest that the CRE can be viewed as an alternative entropy (dispersion) measure to classical Shannon entropy.

We study the measure of a typical cell in a Voronoi tessellation defined by n independent random points X1, . . ., Xn drawn from an absolutely continuous probability measure μ with density f in ℝd. We prove that the asymptotic distribution of the measure – with respect to dμ = f(x)dx – of the cell containing X1 given X1 = x is independent of x and the density f. We determine all moments of the asymptotic distribution and show that the distribution becomes more concentrated as d becomes large. In particular, we show that the variance converges to 0 exponentially fast in d. We also obtain a bound independent of the density for the rate of convergence of the diameter of a typical Voronoi cell.

Batch service has a wide application in manufacturing, communication networks, and cloud computing. In batch service queues with limited resources, one critical issue is to properly schedule the service so as to ensure the quality of service. In this paper we consider an M/G[a,b]/1/N batch service queue with bulking threshold a, max service capacity b, and buffer capacity N, where N can be finite or infinite. Through renewal theory, busy period analysis and decomposition techniques, we demonstrate explicitly how the bulking threshold influences the system performance such as the mean waiting time and time-averaged number of loss customers in batch service queues. We then establish a necessary and sufficient condition on the optimal bulking threshold that minimizes the expected waiting time. Enabled by this condition, we propose a simple algorithm which guarantees to find the optimal threshold in polynomial time. The performance of the algorithm is also demonstrated by numerical examples.

We present an analysis of convergence of a quasi-regression Monte Carlo method proposed by Glasserman and Yu (2004). We show that the method surely converges to the true price of an American option even under multiple underlyings via polynomial chaos expansion and weaker conditions than those used in Glasserman and Yu (2004). Further, we show the number of simulation paths grows exponentially in the number of basis functions to obtain convergence in implementing the method. Finally, we propose a rate of convergence considering regularity of value functions.

We prove a second-order limit law for additive functionals of a d-dimensional fractional Brownian motion with Hurst index H = 1 / d, using the method of moments and extending the Kallianpur–Robbins law, and then give a functional version of this result. That is, we generalize it to the convergence of the finite-dimensional distributions for corresponding stochastic processes.

Lester Dubins and Leonard Savage posed the question as to what extent the optimal reward function U of a leavable gambling problem varies continuously in the gambling house Γ, which specifies the stochastic processes available to a player, and the utility function u, which determines the payoff for each process. Here a distance is defined for measurable houses with a Borel state space and a bounded Borel measurable utility. A trivial example shows that the mapping Γ ↦ U is not always continuous for fixed u. However, it is lower semicontinuous in the sense that, if Γn converges to Γ, then lim inf Un ≥ U. The mapping u ↦ U is continuous in the supnorm topology for fixed Γ, but is not always continuous in the topology of uniform convergence on compact sets. Dubins and Savage observed that a failure of continuity occurs when a sequence of superfair casinos converges to a fair casino, and queried whether this is the only source of discontinuity for the special gambling problems called casinos. For the distance used here, an example shows that there can be discontinuity even when all the casinos are subfair.

Using a new approach, for spectrally negative Lévy processes we find joint Laplace transforms involving the last exit time (from a semiinfinite interval), the value of the process at the last exit time, and the associated occupation time, which generalize some previous results.

Importance sampling has become an important tool for the computation of extreme quantiles and tail-based risk measures. For estimation of such nonlinear functionals of the underlying distribution, the standard efficiency analysis is not necessarily applicable. In this paper we therefore study importance sampling algorithms by considering moderate deviations of the associated weighted empirical processes. Using a delta method for large deviations, combined with classical large deviation techniques, the moderate deviation principle is obtained for importance sampling estimators of two of the most common risk measures: value at risk and expected shortfall.

In this paper we consider a diffusive stochastic predator–prey model with a nonlinear functional response and the randomness is assumed to be of Gaussian nature. A large deviation principle is established for solution processes of the considered model by implementing the weak convergence technique.

We study the evolution of cooperation in an interacting particle system with two types. The model we investigate is an extension of a two-type biased voter model. One type (called defector) has a (positive) bias α with respect to the other type (called cooperator). However, a cooperator helps a neighbor (either defector or cooperator) to reproduce at rate γ. We prove that the one-dimensional nearest-neighbor interacting dynamical system exhibits a phase transition at α = γ. A special choice of interaction kernels yield that for α > γ cooperators always die out, but if γ > α, cooperation is the winning strategy.

The infinite-bin model, introduced by Foss and Konstantopoulos (2003), describes the Markovian evolution of configurations of balls placed inside bins, obeying certain transition rules. We prove that we can couple the behaviour of any finite number of balls, provided at least two different transition rules are allowed. This coupling makes it possible to define the regeneration events needed by Foss and Zachary (2013) to prove convergence results for the distribution of the balls.

We introduce extensions to an infinite-allele branching process that allows for multiple types to exist alongside labels. We consider a Markov branching process and general branching process under different assumptions, and show asymptotic results about the growth of the labels as well as the frequency spectrum. These results are motivated by two separate models. The Markov binary splitting results are motivated by a model of clonal evolution in cancer that considers the effect of both driver and passenger mutations on tumor growth. The general process has applications in viral reproduction and dynamics.

We consider a class of Sevastyanov branching processes with nonhomogeneous Poisson immigration. These processes relax the assumption required by the Bellman–Harris process which imposes the lifespan and offspring of each individual to be independent. They find applications in studies of the dynamics of cell populations. In this paper we focus on the subcritical case and examine asymptotic properties of the process. We establish limit theorems, which generalize classical results due to Sevastyanov and others. Our key findings include a novel law of large numbers and a central limit theorem which emerge from the nonhomogeneity of the immigration process.

A critical branching process {Zk, k = 0, 1, 2, ...} in a random environment is considered. A conditional functional limit theorem for the properly scaled process {log Zpu, 0 ≤ u < ∞} is established under the assumptions that Zn > 0 and p ≪ n. It is shown that the limiting process is a Lévy process conditioned to stay nonnegative. The proof of this result is based on a limit theorem describing the distribution of the initial part of the trajectories of a driftless random walk conditioned to stay nonnegative.

Drawdown (respectively, drawup) of a stochastic process, also referred as the reflected process at its supremum (respectively, infimum), has wide applications in many areas including financial risk management, actuarial mathematics, and statistics. In this paper, for general time-homogeneous Markov processes, we study the joint law of the first passage time of the drawdown (respectively, drawup) process, its overshoot, and the maximum of the underlying process at this first passage time. By using short-time pathwise analysis, under some mild regularity conditions, the joint law of the three drawdown quantities is shown to be the unique solution to an integral equation which is expressed in terms of fundamental two-sided exit quantities of the underlying process. Explicit forms for this joint law are found when the Markov process has only one-sided jumps or is a Lévy process (possibly with two-sided jumps). The proposed methodology provides a unified approach to study various drawdown quantities for the general class of time-homogeneous Markov processes.

By adding a vorticity matrix to the reversible transition probability matrix, we show that the commute time and average hitting time are smaller than that of the original reversible one. In particular, we give an affirmative answer to a conjecture of Aldous and Fill (2002). Further quantitive properties are also studied for the nonreversible finite Markov chains.

We describe the ergodic properties of some Metropolis–Hastings algorithms for heavy-tailed target distributions. The results of these algorithms are usually analyzed under a subgeometric ergodic framework, but we prove that the mixed preconditioned Crank–Nicolson (MpCN) algorithm has geometric ergodicity even for heavy-tailed target distributions. This useful property comes from the fact that, under a suitable transformation, the MpCN algorithm becomes a random-walk Metropolis algorithm.