In their recent paper Velleman and Warrington (2013) analyzed the expected values of some of the parameters in a memory game; namely, the length of the game, the waiting time for the first match, and the number of lucky moves. In this paper we continue this direction of investigation and obtain the limiting distributions of those parameters. More specifically, we prove that when suitably normalized, these quantities converge in distribution to a normal, Rayleigh, and Poisson random variable, respectively. We also make a connection between the memory game and one of the models of preferential attachment graphs. In particular, as a by-product of our methods, we obtain the joint asymptotic normality of the degree counts in the preferential attachment graphs. Furthermore, we obtain simpler proofs (although without rate of convergence) of some of the results of Peköz et al. (2014) on the joint limiting distributions of the degrees of the first few vertices in preferential attachment graphs. In order to prove that the length of the game is asymptotically normal, our main technical tool is a limit result for the joint distribution of the number of balls in a multitype generalized Pólya urn model.

This paper is concerned with the standard bivariate death process as well as with some Markovian modifications and extensions of the process that are of interest especially in epidemic modeling. A new and powerful approach is developed that allows us to obtain the exact distribution of the population state at any point in time, and to highlight the actual nature of the solution. Firstly, using a martingale technique, a central system of relations with two indices for the temporal state distribution will be derived. A remarkable property is that for all the models under consideration, these relations exhibit a similar algebraic structure. Then, this structure will be exploited by having recourse to a theory of Abel-Gontcharoff pseudopolynomials with two indices. This theory generalizes the univariate case examined in a preceding paper and is briefly introduced in the Appendix.

In a fork-join network each incoming job is split into K tasks and the K tasks are simultaneously assigned to K parallel service stations for processing. For the distributions of response times and queue lengths of fork-join networks, no explicit formulae are available. Existing methods provide only analytic approximations for the response time and the queue length distributions. The accuracy of such approximations may be difficult to justify for some complicated fork-join networks. In this paper we propose a perfect simulation method based on coupling from the past to generate exact realisations from the equilibrium of fork-join networks. Using the simulated realisations, Monte Carlo estimates for the distributions of response times and queue lengths of fork-join networks are obtained. Comparisons of Monte Carlo estimates and theoretical approximations are also provided. The efficiency of the sampling algorithm is shown theoretically and via simulation.

In the so-called lightbulb process, on days r = 1,…,n, out of n lightbulbs, all initially off, exactly r bulbs, selected uniformly and independent of the past, have their status changed from off to on, or vice versa. With X the number of bulbs on at the terminal time n, an even integer, and μ = n/2, σ2 = var(X), we have supz ∈ R | P((X - μ)/σ ≤ z) - P(Z ≤ z) | ≤ nΔ̅0/2σ2 + 1.64n/σ3 + 2/σ, where Z is a standard normal random variable and Δ̅0 = 1/2√n + 1/2n + e−n/2/3 for n ≥ 6, yielding a bound of order O(n−1/2) as n → ∞. A similar, though slightly larger bound, holds for odd n. The results are shown using a version of Stein's method for bounded, monotone size bias couplings. The argument for even n depends on the construction of a variable Xs on the same space as X that has the X-size bias distribution, that is, which satisfies E[Xg(X)] = μE[g(Xs)] for all bounded continuous g, and for which there exists a B ≥ 0, in this case B = 2, such that X ≤ Xs ≤ X + B almost surely. The argument for odd n is similar to that for even n, but one first couples X closely to V, a symmetrized version of X, for which a size bias coupling of V to Vs can proceed as in the even case. In both the even and odd cases, the crucial calculation of the variance of a conditional expectation requires detailed information on the spectral decomposition of the lightbulb chain.

We introduce a new approach to simulating rare events for Markov random walks with heavy-tailed increments. This approach involves sequential importance sampling and resampling, and uses a martingale representation of the corresponding estimate of the rare-event probability to show that it is unbiased and to bound its variance. By choosing the importance measures and resampling weights suitably, it is shown how this approach can yield asymptotically efficient Monte Carlo estimates.

We study the integrated telegraph process $X_t$ under the assumption of general distribution for the random times between consecutive reversals of direction. Specifically, $X_t$ represents the position, at time t, of a particle moving U time units upwards with velocity c and D time units downwards with velocity $-c$ . The latter motions are repeated cyclically, according to independent alternating renewals. Explicit expressions for the probability law of $X_t$ are given in the following cases: (i) (U, D) gamma-distributed; (ii) U exponentially distributed and D gamma-distributed. For certain values of the parameters involved, the probability law of $X_t$ is provided in a closed form. Some expressions for the moment generating function of $X_t$ and its Laplace transform are also obtained. The latter allows us to prove the existence of a Kac-type condition under which the probability density function of the integrated telegraph process, with identically distributed gamma intertimes, converges to that of the standard Brownian motion.

Finally, we consider the square of $X_t$ and disclose its distribution function, specifying the expression for some choices of the distribution of (U, D).

The main result of this paper is the solution to the optimal stopping problem of maximizing the variance of a geometric Lévy process. We call this problem the variance problem. We show that, for some geometric Lévy processes, we achieve higher variances by allowing randomized stopping. Furthermore, for some geometric Lévy processes, the problem has a solution only if randomized stopping is allowed. When randomized stopping is allowed, we give a solution to the variance problem. We identify the Lévy processes for which the allowance of randomized stopping times increases the maximum variance. When it does, we also solve the variance problem without randomized stopping.

In this paper we study absorbing continuous-time Markov decision processes in Polish state spaces with unbounded transition and cost rates, and history-dependent policies. The performance measure is the expected total undiscounted costs. For the unconstrained problem, we show the existence of a deterministic stationary optimal policy, whereas, for the constrained problems with N constraints, we show the existence of a mixed stationary optimal policy, where the mixture is over no more than N+1 deterministic stationary policies. Furthermore, the strong duality result is obtained for the associated linear programs.

We consider an interacting particle system on a graph which, from a macroscopic point of view, looks like ℤd and, at a microscopic level, is a complete graph of degree N (called a patch). There are two birth rates: an inter-patch birth rate λ and an intra-patch birth rate ϕ. Once a site is occupied, there is no breeding from outside the patch and the probability c(i) of success of an intra-patch breeding decreases with the size i of the population in the site. We prove the existence of a critical value λc(ϕ, c, N) and a critical value ϕc(λ, c, N). We consider a sequence of processes generated by the families of control functions {cn}n∈ℕ and degrees {Nn}n∈ℕ; we prove, under mild assumptions, the existence of a critical value nc(λ, ϕ, c). Roughly speaking, we show that, in the limit, these processes behave as the branching random walk on ℤd with inter-neighbor birth rate λ and on-site birth rate ϕ. Some examples of models that can be seen as particular cases are given.

This paper is concerned with the behaviour of a Lévy process when it crosses over a positive level, u, starting from 0, both as u becomes large and as u becomes small. Our main focus is on the time, τu, it takes the process to transit above the level, and in particular, on the stability of this passage time; thus, essentially, whether or not τu behaves linearly as u ↓ 0 or u → ∞. We also consider the conditional stability of τu when the process drifts to -∞ almost surely. This provides information relevant to quantities associated with the ruin of an insurance risk process, which we analyse under a Cramér condition.

We study the distributions of component and system lifetimes under the time-homogeneous load-sharing model, where the multivariate conditional hazard rates of working components depend only on the set of failed components, and not on their failure moments or the time elapsed from the start of system operation. Then we analyze its time-heterogeneous extension, in which the distributions of consecutive failure times, single component lifetimes, and system lifetimes coincide with mixtures of distributions of generalized order statistics. Finally we focus on some specific forms of the time-nonhomogeneous load-sharing model.

In this paper, we consider a financial or insurance system with a finite number of individual risks described by real-valued random variables. We focus on two kinds of risk measures, referred to as the tail moment (TM) and the tail central moment (TCM), which are defined as the conditional moment and conditional central moment of some individual risk in the event of system crisis. The first-order TM and the second-order TCM coincide with the popular risk measures called the marginal expected shortfall and the tail variance, respectively. We derive asymptotic expressions for the TM and TCM with any positive integer orders, when the individual risks are pairwise asymptotically independent and have distributions from certain classes that contain both light-tailed and heavy-tailed distributions. The formulas obtained possess concise forms unrelated to dependence structures, and hence enable us to estimate the TM and TCM efficiently. To demonstrate the wide application of our results, we revisit some issues related to premium principles and optimal capital allocation from the asymptotic point of view. We also give a numerical study on the relative errors of the asymptotic results obtained, under some specific scenarios when there are two individual risks in the system. The corresponding asymptotic properties of the degenerate univariate versions of the TM and TCM are discussed separately in an appendix at the end of the paper.

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.

Relations of a Markov chain describing the repeated splitting of polygons to processes known from queueing theory are pointed out.

We consider a stochastic fluid queue served by a constant rate server and driven by a process which is the local time of a reflected Lévy process. Such a stochastic system can be used as a model in a priority service system, especially when the time scales involved are fast. The input (local time) in our model is typically (but not necessarily) singular with respect to the Lebesgue measure, a situation which, in view of the nonsmooth or bursty nature of several types of Internet traffic, is nowadays quite realistic. We first discuss how to rigorously construct the (necessarily) unique stationary version of the system under some natural stability conditions. We then consider the distribution of performance steady-state characteristics, namely, the buffer content, the idle period, and the busy period. These derivations are much based on the fact that the inverse of the local time of a Markov process is a Lévy process (a subordinator), hence making the theory of Lévy processes applicable. Another important ingredient in our approach is the use of Palm calculus for stationary random point processes and measures.

In this paper we generalize a bounded Markov process, described by Stoyanov and Pacheco-González for a class of transition probability functions. A recursive integral equation for the probability density of these bounded Markov processes is derived and the stationary probability density is obtained by solving an equivalent differential equation. Examples of stationary densities for different transition probability functions are given and an application for designing a robotic coverage algorithm with specific emphasis on particular regions is discussed.

In this paper, we study the stationary distributions for reflected diffusions with jumps in the positive orthant. Under the assumption that the stationary distribution possesses a density in R+n that satisfies certain finiteness conditions, we characterize the Fokker-Planck equation. We then provide necessary and sufficient conditions for the existence of a product-form distribution for diffusions with oblique boundary reflections and jumps. To do so, we exploit a recent characterization of the boundary properties of such reflected processes. In particular, we show that the conditions generalize those for semimartingale reflecting Brownian motions and reflected Lévy processes. We provide explicit results for some models of interest.

We study a multiclass Markovian queueing network with switchover across a set of many-server stations. New arrivals to each station follow a nonstationary Poisson process. Each job waiting in queue may, after some exponentially distributed patience time, switch over to another station or leave the network following a probabilistic and state-dependent mechanism. We analyze the performance of such networks under the many-server heavy-traffic limiting regimes, including the critically loaded quality-and-efficiency-driven (QED) regime, and the overloaded efficiency-driven (ED) regime. We also study the limits corresponding to mixing the underloaded quality-driven (QD) regime with the QED and ED regimes. We establish fluid and diffusion limits of the queue-length processes in all regimes. The fluid limits are characterized by ordinary differential equations. The diffusion limits are characterized by stochastic differential equations, with a piecewise-linear drift term and a constant (QED) or time-varying (ED) covariance matrix. We investigate the load balancing effect of switchover in the mixed regimes, demonstrating the migration of workload from overloaded stations to underloaded stations and quantifying the load balancing impact of switchover probabilities.

An extension of the class of strict sense stationary processes is studied. The extended class represents the strict sense analogy of an extension of wide sense stationary processes considered in an earlier paper [9]. The relations between the various types of processes defined are investigated in the general and in the Gaussian case, and some examples are given. It is shown that associated with a process belonging to the extended class there is a strict sense stationary process. The associated strict sense stationary process is unique iff the original process is ergodic.