Joint availability of systems modelled by finite semi–markov processes

Consider a repairable system at the time instants t and t + x, where t, x ≥0. The joint availability of the system at these time instants is defined as the probability of the system being functional in both t and t + x. A set of integral equations is derived for the joint availability of a system modelled by a finite semi–Markov process. The result is applied to the semi–Markov model of a two–unit system with sequential preventive maintenance. The method used for the numerical solution of the resulting system of integral equations is a two–point trapezoidal rule. The system of implementation is the matrix computation package MATLAB on the Apple Macintosh SE/30. The numerical results obtained by this method are shown to be in good agreement with those from simulation.     

Analysis of a Discrete-Time Finite-Capacity Single-Server Queue with Markovian-Arrival Process and Random-Bulk-Service: D-MAP/G Y /1/M

In this article, we consider a single-server, finite-capacity queue with random bulk service rule where customers arrive according to a discrete-time Markovian arrival process (D-MAP). The model is denoted by D-MAP/G ^Y /1/M where server capacity (bulk size for service) is determined by a random variable Y at the starting point of services. A simple analysis of this model is given using the embedded Markov chain technique and the concept of the mean sojourn time of the phase of underlying Markov chain of D-MAP. A complete solution to the distribution of the number of customers in the D-MAP/G ^Y /1/M queue, some computational results, and performance measures such as the average number of customers in the queue and the loss probability are presented.     

NBUE分布类应力-强度模型的概率上界

研究应力-强度模型的结构的可靠性分析,当元件应力变量分布属于NBUE类,强度变量服从指数分布,给出了应力-强度模型中概率的上界,由此讨论了n个元件组成系统的应力-强度模型概率上界.     

Estimation of system reliability in Brownian stress-strength models based on sample paths

Reliability of many stochastic systems depends on uncertain stress and strength patterns that are time dependent. In this paper, we consider the problem of estimating the reliability of a system when bothX(t) andY(t) are assumed to be independent Brownian motion processes, whereX(t) is the system stress, andY(t) is the system strength, at timet.This research was partially supported by the Air-Force Office of Scientific Research Grants AFOSR-89-0402 and AFOSR-90-0402.     

Diffusion Approximations for Queues with Markovian Bases

Consider a base family of state-dependent queues whose queue-length process can be formulated by a continuous-time Markov process. In this paper, we develop a piecewise-constant diffusion model for an enlarged family of queues, each of whose members has arrival and service distributions generalized from those of the associated queue in the base. The enlarged family covers many standard queueing systems with finite waiting spaces, finite sources and so on. We provide a unifying explicit expression for the steady-state distribution, which is consistent with the exact result when the arrival and service distributions are those of the base. The model is an extension as well as a refinement of the M/M/s-consistent diffusion model for the GI/G/s queue developed by Kimura [13] where the base was a birth-and-death process. As a typical base, we still focus on birth-and-death processes, but we also consider a class of continuous-time Markov processes with lower-triangular infinitesimal generators.     

Density and Approximation Properties of Markov Systems

Borwein, Bojanov, Erdélyi, and others, have studieddensity and approximation properties of those Markov systems of differentiablefunctions on a closed interval [a,b], having the property thatthe system of derivatives is a Markov system on the open interval (a,b).In this paper we show that several of these results are valid for anyMarkov system of continuous functions on a closed interval.     

Functional Compatibility,Markov Chains,and Gibbs Sampling with Improper Posteriors

Abstract

The members of a set of conditional probability density functions are called compatible if there exists a joint probability density function that generates them. We generalize this concept by calling the conditionals functionally compatible if there exists a non-negative function that behaves like a joint density as far as generating the conditionals according to the probability calculus, but whose integral over the whole space is not necessarily finite. A necessary and sufficient condition for functional compatibility is given that provides a method of calculating this function, if it exists. A Markov transition function is then constructed using a set of functionally compatible conditional densities and it is shown, using the compatibility results, that the associated Markov chain is positive recurrent if and only if the conditionals are compatible. A Gibbs Markov chain, constructed via “Gibbs conditionals” from a hierarchical model with an improper posterior, is a special case. Therefore, the results of this article can be used to evaluate the consequences of applying the Gibbs sampler when the posterior's impropriety is unknown to the user. Our results cannot, however, be used to detect improper posteriors. Monte Carlo approximations based on Gibbs chains are shown to have undesirable limiting behavior when the posterior is improper. The results are applied to a Bayesian hierarchical one-way random effects model with an improper posterior distribution. The model is simple, but also quite similar to some models with improper posteriors that have been used in conjunction with the Gibbs sampler in the literature.     

Reduced-order modelling of self-excited,time-periodic systems using the method of Proper Orthogonal Decomposition and the Floquet theory

The mathematical models of dynamical systems become more and more complex, and hence, numerical investigations are a time-consuming process. This is particularly disadvantageous if a repeated evaluation is needed, as is the case in the field of model-based design, for example, where system parameters are subject of variation. Therefore, there exists a necessity for providing compact models which allow for a fast numerical evaluation. Nonetheless, reduced models should reflect at least the principle of system dynamics of the original model.

In this contribution, the reduction of dynamical systems with time-periodic coefficients, termed as parametrically excited systems, subjected to self-excitation is addressed. For certain frequencies of the time-periodic coefficients, referred to as parametric antiresonance frequencies, vibration suppression is achieved, as it is known from the literature. It is shown in this article that by using the method of Proper Orthogonal Decomposition (POD) excitation at a parametric antiresonance frequency results in a concentration of the main system dynamics in a subspace of the original solution space. The POD method allows to identify this subspace accurately and to set up reduced models which approximate the stability behaviour of the original model in the vicinity of the antiresonance frequency in a satisfying manner. For the sake of comparison, modally reduced models are established as well.     

On a decomposition for infinite transition matrices

Heyman gives an interesting factorization of I-P, where P is the transition probability matrix for an ergodic Markov chain. We show that this factorization is valid if and only if the Markov chain is recurrent. Moreover, we provide a decomposition result which includes all ergodic, null recurrent as well as the transient Markov chains as special cases. Such a decomposition has been shown to be useful in the analysis of queues. This revised version was published online in June 2006 with corrections to the Cover Date.     

A Regularly Preemptive Model and its Approximations

A regularly preemptive model D,MAP/D ₁,D ₂/1 is studied. Priority customers have constant inter-arrival times and constant service times. On the other hand, ordinary customers' arrivals follow a Markovian Arrival Process (MAP) with constant service times. Although this model can be formulated by using the piecewise Markov process, there remain some difficult problems on numerical calculations. In order to solve these problems, a novel approximation model MAP/MR/1 with Markov renewal services is proposed. These two queueing processes become different due to the existence of idle periods. Thus, a MAP/MR/1 queue with a general boundary condition is introduced. It is a model with the exceptional first service in each busy period. In particular, two special models are studied: one is a warm-up queue and the other is a cool-down queue. It can be proved that the waiting time of ordinary customers for the regular preemption model is stochastically smaller than the waiting time of the former model. On the other hand, it is stochastically larger than the waiting time of the latter model.     

A BMAP/SM/1 queue with service times depending on the arrival process

We study a BMAP/>SM/1 queue with batch Markov arrival process input and semi‐Markov service. Service times may depend on arrival phase states, that is, there are many types of arrivals which have different service time distributions. The service process is a heterogeneous Markov renewal process, and so our model necessarily includes known models. At first, we consider the first passage time from level {κ+1} (the set of the states that the number of customers in the system is κ+1) to level {κ} when a batch arrival occurs at time 0 and then a customer service included in that batch simultaneously starts. The service descipline is considered as a LIFO (Last‐In First‐Out) with preemption. This discipline has the fundamental role for the analysis of the first passage time. Using this first passage time distribution, the busy period length distribution can be obtained. The busy period remains unaltered in any service disciplines if they are work‐conserving. Next, we analyze the stationary workload distribution (the stationary virtual waiting time distribution). The workload as well as the busy period remain unaltered in any service disciplines if they are work‐conserving. Based on this fact, we derive the Laplace–Stieltjes transform for the stationary distribution of the actual waiting time under a FIFO discipline. In addition, we refer to the Laplace–Stieltjes transforms for the distributions of the actual waiting times of the individual types of customers. Using the relationship between the stationary waiting time distribution and the stationary distribution of the number of customers in the system at departure epochs, we derive the generating function for the stationary joint distribution of the numbers of different types of customers at departures. This revised version was published online in June 2006 with corrections to the Cover Date.     

The k-Client Problem

Virtually all previous research in online algorithms has focused on single-threaded systems where only a single sequence of requests compete for system resources. To model multithreaded online systems, we define and analyze the k-client problem, a dual of the well-studied k-server problem. In the basic k-client problem, there is a single server and k clients, each of which generates a sequence of requests for service in a metric space. The crux of the problem is deciding which client's request the single server should service rather than which server should be used to service the current request. We also consider variations where requests have nonzero processing times and where there are multiple servers as well as multiple clients.We evaluate the performance of algorithms using several cost functions including maximum completion time and average completion time. Two of the main results we derive are tight bounds on the performance of several commonly studied disk scheduling algorithms and lower bounds of on the competitive ratio of any online algorithm for the maximum completion time and average completion time cost functions when k is a power of 2. Most of our results are essentially identical for the maximum completion time and average completion time cost functions.     

Analysis of GI<Superscript><Emphasis Type="Italic">X</Emphasis></Superscript>/<Emphasis Type="Italic">M</Emphasis>(<Emphasis Type="Italic">n</Emphasis>)//<Emphasis Type="Italic">N</Emphasis> systems with stochastic customer acceptance policy

We investigate GI ^X /M(n)//N systems with stochastic customer acceptance policy, function of the customer batch size and the number of customers in the system at its arrival. We address the time-dependent and long-run analysis of the number of customers in the system at prearrivals and postarrivals of batches and seen by customers at their arrival to the system, as well as customer blocking probabilities. These results are then used to derive the continuous-time long-run distribution of the number of customers in the system. Our analysis combines Markov chain embedding with uniformization and uses stochastic ordering as a way to bound the errors of the computed performance measures.      

应力为SGBVE分布强度为指数分布下结构可靠度的估计

考虑了应力服从SGBVE分布,强度服从指数分布的应力—强度模型,分别在应力参数未知和部分强度参数未知的情形下给出了该模型可靠度的估计,并讨论了其性质.     

Swendsen‐Wang dynamics for general graphs in the tree uniqueness region

The Swendsen‐Wang (SW) dynamics is a popular Markov chain for sampling from the Gibbs distribution for the ferromagnetic Ising model on a graph G = (V,E). The dynamics is conjectured to converge to equilibrium in O(|V|^1/4) steps at any (inverse) temperature β, yet there are few results providing o(|V|) upper bounds. We prove fast convergence of the SW dynamics on general graphs in the tree uniqueness region. In particular, when β < β_c(d) where β_c(d) denotes the uniqueness/nonuniqueness threshold on infinite d‐regular trees, we prove that the relaxation time (i.e., the inverse spectral gap) of the SW dynamics is Θ(1) on any graph of maximum degree d ≥ 3. Our proof utilizes a monotone version of the SW dynamics which only updates isolated vertices. We establish that this variant of the SW dynamics has mixing time and relaxation time Θ(1) on any graph of maximum degree d for all β < β_c(d). Our proof technology can be applied to general monotone Markov chains, including for example the heat‐bath block dynamics, for which we obtain new tight mixing time bounds.     

应力服从一类嵌套多元指数分布的结构可靠度估计

本文研究应力服从一类嵌套多元指数分布, 强度服从指数分布的应力---强度结构可靠度模型.分别在强度参数未知、应力参数已知和强度参数已知、应力参数未知的情况下给出了结构可靠度$P_{A}$的估计$\wh{P}_{A1}$和$\wh{P}_{A2}$,并讨论了它们的渐近性质,而且获得了$P_{A}$的近似置信区间.最后对这两种情况下模型结构可靠度的估计$\wh{P}_{A1}$和$\wh{P}_{A2}$进行了随机模拟,随机模拟结果令人满意.     

Rapid mixing of Gibbs sampling on graphs that are sparse on average

Gibbs sampling also known as Glauber dynamics is a popular technique for sampling high dimensional distributions defined on graphs. Of special interest is the behavior of Gibbs sampling on the Erd?s‐Rényi random graph G(n,d/n), where each edge is chosen independently with probability d/n and d is fixed. While the average degree in G(n,d/n) is d(1 ‐ o(1)), it contains many nodes of degree of order log n/log log n. The existence of nodes of almost logarithmic degrees implies that for many natural distributions defined on G(n,p) such as uniform coloring (with a constant number of colors) or the Ising model at any fixed inverse temperature β, the mixing time of Gibbs sampling is at least n^{1+Ω(1/log log n)}. Recall that the Ising model with inverse temperature β defined on a graph G = (V,E) is the distribution over {±}^Vgiven by . High degree nodes pose a technical challenge in proving polynomial time mixing of the dynamics for many models including the Ising model and coloring. Almost all known sufficient conditions in terms of β or number of colors needed for rapid mixing of Gibbs samplers are stated in terms of the maximum degree of the underlying graph. In this work, we show that for every d < ∞ and the Ising model defined on G (n, d/n), there exists a β_d > 0, such that for all β < β_d with probability going to 1 as n →∞, the mixing time of the dynamics on G (n, d/n) is polynomial in n. Our results are the first polynomial time mixing results proven for a natural model on G (n, d/n) for d > 1 where the parameters of the model do not depend on n. They also provide a rare example where one can prove a polynomial time mixing of Gibbs sampler in a situation where the actual mixing time is slower than npolylog(n). Our proof exploits in novel ways the local tree like structure of Erd?s‐Rényi random graphs, comparison and block dynamics arguments and a recent result of Weitz. Our results extend to much more general families of graphs which are sparse in some average sense and to much more general interactions. In particular, they apply to any graph for which every vertex v of the graph has a neighborhood N(v) of radius O(log n) in which the induced sub‐graph is a tree union at most O(log n) edges and where for each simple path in N(v) the sum of the vertex degrees along the path is O(log n). Moreover, our result apply also in the case of arbitrary external fields and provide the first FPRAS for sampling the Ising distribution in this case. We finally present a non Markov Chain algorithm for sampling the distribution which is effective for a wider range of parameters. In particular, for G(n, d/n) it applies for all external fields and β < β_d, where d tanh(β_d) = 1 is the critical point for decay of correlation for the Ising model on G(n, d/n). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

A multi-dimensional Markov chain and the Meixner ensemble

We show that the transition probability of the Markov chain (G(i,1),...,G(i,n)) _i≥1, where the G(i,j)’s are certain directed last-passage times, is given by a determinant of a special form. An analogous formula has recently been obtained by Warren in a Brownian motion model. Furthermore we demonstrate that this formula leads to the Meixner ensemble when we compute the distribution function for G(m,n). We also obtain the Fredholm determinant representation of this distribution, where the kernel has a double contour integral representation.     

On blow-up solutions for systems of semilinear heat equations with quadratic nonlinearities

This article deals with blow-up solutions of the Cauchy–Dirichlet problem for system of semilinear heat equations with quadratic non-linearities. Sufficient conditions for the existence of blow-up solutions are established. Sets of initial values for these solutions as well as upper bounds for corresponding blow-up time are determined. Furthermore, an application to the Lotka-Volterra system with diffusion is also discussed. The result of this article may be considered as a continuation and a generalization of the results obtained in (Baris, J., Baris, P. and Ruchlewicz, B., 2006, On blow-up solutions of nonautonomous quadratic differential systems. Differential Equations, 42, 320–326; Baris, J., Baris, P. and Wawiórko, E., 2006, Asymptotic behaviour of solutions of Lotka-Volterra systems. Nonlinear Analysis: Real World Applications, 7, 610–618; Baris, J., Baris, P. and Ruchlewicz, B., 2006, On blow-up solutions of quadratic systems of differential equations. Sovremennaya Matematika. Fundamentalnye Napravleniya, 15, 29–35 (in Russian); Baris, J. and Wawiórko, E., On blow-up solutions of polynomial Kolmogorov systems. Nonlinear Analysis: Real World Applications, to appear).