Search

We study a Markovian agent-based model (MABM) in this paper. Each agent is endowed with a local state that changes over time as the agent interacts with its neighbours. The neighbourhood structure is given by a graph. In a recent paper [Simon et al. 2011], the authors used the automorphisms of the underlying graph to generate a lumpable partition of the joint state space ensuring Markovianness of the lumped process for binary dynamics. However, many large random graphs tend to become asymmetric rendering the automorphism-based lumping approach ineffective as a tool of model reduction. In order to mitigate this problem, we propose a lumping method based on a notion of local symmetry, which compares only local neighbourhoods of vertices. Since local symmetry only ensures approximate lumpability, we quantify the approximation error by means of Kullback-Leibler divergence rate between the original Markov chain and a lifted Markov chain. We prove the approximation error decreases monotonically. The connections to fibrations of graphs are also discussed., Comment: 28 pages, 4 figures

This paper considers two variants of M/G/1 queues with impatient customers, which are denoted by M/G/1+Gw and M/G/1+Gs. In the M/G/1+Gw queue customers have deadlines for their waiting times, and they leave the system immediately if their services do not start before the expiration of their deadlines. On the other hand, in the M/G/1+Gs queue customers have deadlines for their sojourn times, where customers in service also immediately leave the system when their deadlines expire. In this paper we derive comparison results for performance measures of these models. In particular, we show that if the service time distribution is new better than used in expectation, then the loss probability in the M/G/1+Gs queue is greater than that in the M/G/1+Gw queue.

The Ginibre point process (GPP) is one of the main examples of determinantal point processes on the complex plane. It is a recurring distribution of random matrix theory as well as a useful model in applied mathematics. In this paper we briefly overview the usual methods for the simulation of the GPP. Then we introduce a modified version of the GPP which constitutes a determinantal point process more suited for certain applications, and we detail its simulation. This modified GPP has the property of having a fixed number of points and having its support on a compact subset of the plane. See Decreusefond et al. (2013) for an extended version of this paper.

This paper considers risk-sensitive average optimization for denumerable continuous-time Markov decision processes (CTMDPs), in which the transition and cost rates are allowed to be unbounded, and the policies can be randomized history dependent. We first derive the multiplicative dynamic programming principle and some new facts for risk-sensitive finite-horizon CTMDPs. Then, we establish the existence and uniqueness of a solution to the risk-sensitive average optimality equation (RS-AOE) through the results for risk-sensitive finite-horizon CTMDPs developed here, and also prove the existence of an optimal stationary policy via the RS-AOE. Furthermore, for the case of finite actions available at each state, we construct a sequence of models of finite-state CTMDPs with optimal stationary policies which can be obtained by a policy iteration algorithm in a finite number of iterations, and prove that an average optimal policy for the case of infinitely countable states can be approximated by those of the finite-state models. Finally, we illustrate the conditions and the iteration algorithm with an example.

In this paper, we study a large system of $N$ servers each with capacity to process at most $C$ simultaneous jobs and an incoming job is routed to a server if it has the lowest occupancy amongst $d$ (out of N) randomly selected servers. A job that is routed to a server with no vacancy is assumed to be blocked and lost. Such randomized policies are referred to JSQ(d) (Join the Shortest Queue out of $d$) policies. Under the assumption that jobs arrive according to a Poisson process with rate $N\lambda^{(N)}$ where $\lambda^{(N)}=\sigma-\frac{\beta}{\sqrt{N}}$, $\sigma\in\mb{R}_+$ and $\beta\in\mb{R}$, we establish functional central limit theorems (FCLTs) for the fluctuation process in both the transient and stationary regimes when service time distributions are exponential. In particular, we show that the limit is an Ornstein-Uhlenbeck process whose mean and variance depend on the mean-field of the considered model. Using this, we obtain approximations to the blocking probabilities for large $N$, where we can precisely estimate the accuracy of first-order approximations., Comment: 29 pages

In this paper the behaviour of the failure rate and reversed failure rate of an n-component coherent system is studied, where it is assumed that the lifetimes of the components are independent and have a common cumulative distribution function F. Sufficient conditions are provided under which the system failure rate is increasing and the corresponding reversed failure rate is decreasing. We also study the stochastic and ageing properties of doubly truncated random variables for coherent systems.

This paper presents a flexible family which we call the $\alpha$ -mixture of survival functions. This family includes the survival mixture, failure rate mixture, models that are stochastically closer to each of these conventional mixtures, and many other models. The $\alpha$ -mixture is endowed by the stochastic order and uniquely possesses a mathematical property known in economics as the constant elasticity of substitution, which provides an interpretation for $\alpha$ . We study failure rate properties of this family and establish closures under monotone failure rates of the mixture’s components. Examples include potential applications for comparing systems.

The signature of a coherent system has been studied extensively in the recent literature. Signatures are particularly useful in the comparison of coherent or mixed systems under a variety of stochastic orderings. Also, certain signature-based closure and preservation theorems have been established. For example, it is now well known that certain stochastic orderings are preserved from signatures to system lifetimes when components have independent and identical distributions. This applies to the likelihood ratio order, the hazard rate order, and the stochastic order. The point of departure of the present paper is the question of whether or not a similar preservation result will hold for the mean residual life order. A counterexample is provided which shows that the answer is negative. Classes of distributions for the component lifetimes for which the latter implication holds are then derived. Connections to the theory of order statistics are also considered.

In this paper we are concerned with modelling the reliability of a system subject to external shocks. In a run shock model, the system fails when a sequence of shocks above a threshold arrive in succession. Nevertheless, using a single threshold to measure the severity of a shock is too critical in real practice. To this end, we develop a generalized run shock model with two thresholds. We employ a phase-type distribution to model the damage size and the inter-arrival time of shocks, which is highly versatile and may be used to model many quantitative features of random phenomenon. Furthermore, we use the Markovian property to construct a multi-state system which degrades with the arrival of shocks. We also provide a numerical example to illustrate our results.

The mean time to failure (MTTF) function in age replacement is used to evaluate the performance and effectiveness of the age replacement policy. In this paper, based on the MTTF function, we introduce two new nonparametric classes of lifetime distributions with nonmonotonic mean time to failure in age replacement; increasing then decreasing MTTF (IDMTTF) and decreasing then increasing MTTF (DIMTTF). The implications between these classes of distributions and some existing classes of nonmonotonic ageing classes are studied. The characterizations of IDMTTF and DIMTTF in terms of the scaled total time on test transform are also obtained.

In this paper we are concerned with the reliability properties of two coherent systems having shared components. We assume that the components of the systems are two overlapping subsets of a set of n components with lifetimes X1,...,Xn. Further, we assume that the components of the systems fail according to the model of sequential order statistics (which is equivalent, under some mild conditions, to the failure model corresponding to a nonhomogeneous pure-birth process). The joint reliability function of the system lifetimes is expressed as a mixture of the joint reliability functions of the sequential order statistics, where the mixing probabilities are the bivariate signature matrix associated to the structures of systems. We investigate some stochastic orderings and dependency properties of the system lifetimes. We also study conditions under which the joint reliability function of systems with shared components of order m can be equivalently written as the joint reliability function of systems of order n (n>m). In order to illustrate the results, we provide several examples.

For many practical situations in reliability engineering, components in the system are usually dependent since they generally work in a collaborative environment. In this paper we build sufficient conditions for comparing two coherent systems under different random environments in the sense of the usual stochastic, hazard rate, reversed hazard rate, and likelihood ratio orders. Applications and numerical examples are provided to illustrate all the theoretical results established here.

In this paper we study the Robbins–Monro procedure Xn+1 = Xn - an-1Yn with some fixed number a > 0 and establish the moderate deviation principle of the process {Xn}.

Community detection is considered for a stochastic block model graph of n vertices, with K vertices in the planted community, edge probability p for pairs of vertices both in the community, and edge probability q for other pairs of vertices. The main focus of the paper is on weak recovery of the community based on the graph G, with o(K) misclassified vertices on average, in the sublinear regime n1-o(1) ≤ K ≤ o(n). A critical parameter is the effective signal-to-noise ratio λ = K2(p - q)2 / ((n - K)q), with λ = 1 corresponding to the Kesten–Stigum threshold. We show that a belief propagation (BP) algorithm achieves weak recovery if λ > 1 / e, beyond the Kesten–Stigum threshold by a factor of 1 / e. The BP algorithm only needs to run for log*n + O(1) iterations, with the total time complexity O(|E|log*n), where log*n is the iterated logarithm of n. Conversely, if λ ≤ 1 / e, no local algorithm can asymptotically outperform trivial random guessing. Furthermore, a linear message-passing algorithm that corresponds to applying a power iteration to the nonbacktracking matrix of the graph is shown to attain weak recovery if and only if λ > 1. In addition, the BP algorithm can be combined with a linear-time voting procedure to achieve the information limit of exact recovery (correctly classify all vertices with high probability) for all K ≥ (n / logn) (ρBP + o(1)), where ρBP is a function of p / q.

Mao and Hu (2010) left an open problem about the hazard rate order between the largest order statistics from two samples of n geometric random variables. Du et al. (2012) solved this open problem when n = 2, and Wang (2015) solved for 2 ≤ n ≤ 9. In this paper we completely solve this problem for any value of n.

In this paper we prove that a parallel system consisting of Weibull components with different scale parameters ages faster than a parallel system comprising Weibull components with equal scale parameters in the convex transform order when the lifetimes of components of both systems have different shape parameters satisfying some restriction. Moreover, while comparing these two systems, we show that the dispersive and the usual stochastic orders, and the right-spread order and the increasing convex order are equivalent. Further, some of the known results in the literature concerning comparisons of k-out-of-n systems in the exponential model are extended to the Weibull model. We also provide solutions to two open problems mentioned by Balakrishnan and Zhao (2013) and Zhao et al. (2016).

In this paper we investigate the stochastic properties of the number of failed components of a three-state network. We consider a network made up of n components which is designed for a specific purpose according to the performance of its components. The network starts operating at time t = 0 and it is assumed that, at any time t > 0, it can be in one of states up, partial performance, or down. We further suppose that the state of the network is inspected at two time instants t1 and t2 (t1 < t2). Using the notion of the two-dimensional signature, the probability of the number of failed components of the network is calculated, at t1 and t2, under several scenarios about the states of the network. Stochastic and ageing properties of the proposed failure probabilities are studied under different conditions. We present some optimal age replacement policies to show applications of the proposed criteria. Several illustrative examples are also provided.

We study the rare-event behavior of the workload process in a transitory queue, where the arrival epochs (or 'points') of a finite number of jobs are assumed to be the ordered statistics of independent and identically distributed (i.i.d.) random variables. The service times (or 'marks') of the jobs are assumed to be i.i.d. random variables with a general distribution, that are jointly independent of the arrival epochs. Under the assumption that the service times are strictly positive, we derive the large deviations principle (LDP) satisfied by the workload process. The analysis leverages the connection between ordered statistics and self-normalized sums of exponential random variables to establish the LDP. In this paper we present the first analysis of rare events in transitory queueing models, supplementing prior work that has focused on fluid and diffusion approximations.

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.

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.

The sequential stochastic assignment problem (SSAP) allocates distinct workers with deterministic values to sequentially arriving tasks with stochastic parameters to maximize the expected total reward. In this paper we study an extension of the SSAP, in which the worker values are considered to be random variables, taking on new values upon each task arrival. Several SSAP models with different assumptions on the distribution of the worker values and closed-form expressions for optimal assignment policies are presented.

In this paper we estimate quantile sensitivities for dependent sequences via infinitesimal perturbation analysis, and prove asymptotic unbiasedness, weak consistency, and a central limit theorem for the estimators under some mild conditions. Two common cases, the regenerative setting and ϕ-mixing, are analyzed further, and a new batched estimator is constructed based on regenerative cycles for regenerative processes. Two numerical examples, the G/G/1 queue and the Ornstein–Uhlenbeck process, are given to show the effectiveness of the estimator.

We consider a greedy walk on a Poisson process on the real line. It is known that the walk does not visit all points of the process. In this paper we first obtain some useful independence properties associated with this process which enable us to compute the distribution of the sequence of indices of visited points. Given that the walk tends to +∞, we find the distribution of the number of visited points in the negative half-line, as well as the distribution of the time at which the walk achieves its minimum.

De Bruijn's identity relates two important concepts in information theory: Fisher information and differential entropy. Unlike the common practice in the literature, in this paper we consider general additive non-Gaussian noise channels where more realistically, the input signal and additive noise are not independently distributed. It is shown that, for general dependent signal and noise, the first derivative of the differential entropy is directly related to the conditional mean estimate of the input. Then, by using Gaussian and Farlie–Gumbel–Morgenstern copulas, special versions of the result are given in the respective case of additive normally distributed noise. The previous result on independent Gaussian noise channels is included as a special case. Illustrative examples are also provided.

The purpose of this paper is twofold. On the one hand, we provide sufficient conditions for the excess wealth order. These conditions are based on properties of the quantile functions which are useful when the dispersive order does not hold. On the other hand, we study sufficient conditions for the comparison in the increasing convex order of spacings of generalized order statistics. These results will be combined to show how we can provide comparisons of quantities of interest in reliability and insurance.

In this paper we build the increasing convex (concave) order for the scalar product of random vectors with an upper (lower) tail permutation decreasing joint density. As applications, we revisit allocations of portfolio risks in financial engineering and of coverage limits and deductibles in insurance. Some related results in the literature are substantially updated.

Classical Jackson networks are a well-established tool for the analysis of complex systems. In this paper we analyze Jackson networks with the additional features that (i) nodes may have an infinite supply of low priority work and (ii) nodes may be unstable in the sense that the queue length at these nodes grows beyond any bound. We provide the limiting distribution of the queue length distribution at stable nodes, which turns out to be of product form. A key step in establishing this result is the development of a new algorithm based on adjusted traffic equations for detecting unstable nodes. Our results complement the results known in the literature for the subcases of Jackson networks with either infinite supply nodes or unstable nodes by providing an analysis of the significantly more challenging case of networks with both types of nonstandard node present. Building on our product-form results, we provide closed-form solutions for common customer and system oriented performance measures.

In this paper we analyze a tollbooth tandem queueing problem with an infinite number of servers. A customer starts service immediately upon arrival but cannot leave the system before all customers who arrived before him/her have left, i.e. customers depart the system in the same order as they arrive. Distributions of the total number of customers in the system, the number of departure-delayed customers in the system, and the number of customers in service at time t are obtained in closed form. Distributions of the sojourn times and departure delays of customers are also obtained explicitly. Both transient and steady state solutions are derived first for Poisson arrivals, and then extended to cases with batch Poisson and nonstationary Poisson arrival processes. Finally, we report several stochastic ordering results on how system performance measures are affected by arrival and service processes.

We study congestion periods in a finite fluid buffer when the net input rate depends upon a recurrent Markov process; congestion occurs when the buffer content is equal to the buffer capacity. Similarly to O'Reilly and Palmowski (2013), we consider the duration of congestion periods as well as the associated volume of lost information. While these quantities are characterized by their Laplace transforms in that paper, we presently derive their distributions in a typical stationary busy period of the buffer. Our goal is to compute the exact expression of the loss probability in the system, which is usually approximated by the probability that the occupancy of the infinite buffer is greater than the buffer capacity under consideration. Moreover, by using general results of the theory of Markovian arrival processes, we show that the duration of congestion and the volume of lost information have phase-type distributions.

This paper concerns discrete-time Markov decision chains with denumerable state and compact action sets. Besides standard continuity requirements, the main assumption on the model is that it admits a Lyapunov function ℓ. In this context the average reward criterion is analyzed from the sample-path point of view. The main conclusion is that if the expected average reward associated to ℓ2 is finite under any policy then a stationary policy obtained from the optimality equation in the standard way is sample-path average optimal in a strong sense.

This paper is an investigation into the reliability and stochastic properties of three-state networks. We consider a single-step network consisting of n links and we assume that the links are subject to failure. We assume that the network can be in three states, up (K = 2), partial performance (K = 1), and down (K = 0). Using the concept of the two-dimensional signature, we study the residual lifetimes of the networks under different scenarios on the states and the number of failed links of the network. In the process of doing so, we define variants of the concept of the dynamic signature in a bivariate setting. Then, we obtain signature based mixture representations of the reliability of the residual lifetimes of the network states under the condition that the network is in state K = 2 (or K = 1) and exactly k links in the network have failed. We prove preservation theorems showing that stochastic orderings and dependence between the elements of the dynamic signatures (which relies on the network structure) are preserved by the residual lifetimes of the states of the network (which relies on the network ageing). Various illustrative examples are also provided.