Reliability Approximation for Markov Chain Imbeddable Systems

In the present article, a simple method is developed for approximating the reliability of Markov chain imbeddable systems. The approximating formula reduces the problem to the reliability assessment of smaller systems with structure similar to the original systems. Two specific reliability structures which have attracted considerable research interest recently (r-within-consecutive-k-out-of-n system and two dimensional r-within-k₁ × k₂-out-of-n₁ × n₂ system) are studied by the new approach and numerical calculations are carried out, which reveal the high quality of our approximations. Several possible extensions and generalizations are also presented in brief.     

Poisson approximations for 2-dimensional patterns

LetX=(X _ij) _n×n be a random matrix whose elements are independent Bernoulli random variables, taking the values 0 and 1 with probabilityq _ij andp _ij (p _ij+q _ij=1) respectively. Upper and lower bounds for the probabilities ofm non-overlapping occurrences of a square submatrix with all its elements being equal to 1, are obtained. Some Poisson convergence theorems are established forn . Numerical results indicate that the proposed bounds perform very well, even for moderate and small values ofn.This work is supported in part by the Natural Science and Engineering Research Council of Canada under Grant NSERC A-9216.     

Bivariate Markov chain embeddable variables of polynomial type

The primary aim of the present article is to provide a general framework for investigating the joint distribution of run length accumulating/enumerating variables by the aid of a Markov chain embedding technique. To achieve that we introduce first a class of bivariate discrete random variables whose joint distribution can be described by the aid of a Markov chain and develop formulae for their joint probability mass function, generating functions and moments. The results are then exploited for the derivation of the distribution of a bivariate run-related statistic. Finally, some interesting uses of our results in reliability theory and educational psychology are highlighted. Research supported by General Secretary of Research and Technology of Greece under grand PENED 2001.     

Fast formula of a reliability ofm-consecutive-k-out-of-n:F system with cyclek

Anm-consecutive-k-out-of-n:F system is a system ofn linearly arranged components which fails if and only if at leastm non-overlapping sequences ofk components fail, when there arek distinct components with failure probabilitiesq _i fori=1,...,k and where the failure probability of thej-th component (j=rk+i (1 ≤i ≤k) isq _j =q _i , we call this system by anm-consecutive-k-out-of-n:F system with cycle (or period)k. In this paper we give a formula of the failure probability ofm-consecutive-k-out-of-n:F system with cyclek via the failure probability of consecutive-k-out-of-n:F system.     

Reliability formula &; limit law of the failure time of “<Emphasis Type="Italic">m</Emphasis>-consecutive-<Emphasis Type="Italic">k</Emphasis>-out-of-<Emphasis Type="Italic">n</Emphasis>:<Emphasis Type="Italic">F</Emphasis> system”

An “m-consecutive-k-out-of-n:F system” consists of n components ordered on a line; the system fails if and only if there are at least m nonoverlapping runs of k consecutive failed components. In this paper, we give a recursive formula to compute the reliability of such a system. Thereafter, we state two asymptotic results concerning the failure time Z _n of the system. The first result concerns a limit theorem for Z _n when the failure times of components are not necessarily with identical failure distributions. In the second one, we prove that, for an arbitrary common failure distribution of components, the limit system failure distribution is always of the Poisson class.      

Waiting Time Problems in a Two-State Markov Chain

Let F ₀ be the event that l ₀ 0-runs of length k ₀ occur and F ₁ be the event that l ₁ 1-runs of length k ₁ occur in a two-state Markov chain. In this paper using a combinatorial method and the Markov chain imbedding method, we obtained explicit formulas of the probability generating functions of the sooner and later waiting time between F ₀ and F ₁ by the non-overlapping, overlapping and "greater than or equal" enumeration scheme. These formulas are convenient for evaluating the distributions of the sooner and later waiting time problems.     

Asymptotic Results and a Markovian Approximation for the M(n)/M(n)/s+GI System

In this paper for the M(n)/M(n)/s+GI system, i.e. for a s-server queueing system where the calls in the queue may leave the system due to impatience, we present new asymptotic results for the intensities of calls leaving the system due to impatience and a Markovian system approximation where these results are applied. Furthermore, we present a new proof for the formulae of the conditional density of the virtual waiting time distributions, recently given by Movaghar for the less general M(n)/M/s+GI system. Also we obtain new explicit expressions for refined virtual waiting time characteristics as a byproduct.     

Bounds for increasing multi-state consecutive k-out-of-r-from-n: F system with equal components probabilities

The consecutive k-out-of-r-from-n: F system was generalized to multi-state case. This system consists of n linearly ordered components which are at state below j if and only if at least k_j components out of any r consecutive are in state below j. In this paper we suggest bounds of increasing multi-state consecutive-k-out-of-r-from-n: F system (k₁ ? k₂ ? ? ? k_M) by applying second order Boole–Bonferroni bounds and applying Hunter–Worsley upper bound. Also numerical results are given. The programs in V.B.6 of the algorithms are available upon request from the authors.     

Reliability of a consecutive (r, s)-out-of-(m, n):F lattice system with conditions on the number of failed components in the system

A consecutive(r, s)-out-of-(m, n):F lattice system which is defined as a two-dimensional version of a consecutive k-out-of-n:F system is used as a reliability evaluation model for a sensor system, an X-ray diagnostic system, a pattern search system, etc. This system consists of m × n components arranged like an (m, n) matrix and fails iff the system has an (r, s) submatrix that contains all failed components. In this paper we deal a combined model of a k-out-of-mn:F and a consecutive (r, s)-out-of-(m, n):F lattice system. Namely, the system has one more condition of system down, that is the total number of failed components, in addition to that of a consecutive (r, s)-out-of-(m, n):F lattice system. We present a method to obtain reliability of the system. The proposed method obtains the reliability by using a combinatorial equation that does not depend on the system size. Some numerical examples are presented to show the relationship between component reliability and system reliability.     

Algorithm for a general discrete k-out-of-n: G system subject to several types of failure with an indefinite number of repairpersons

A discrete k-out-of-n: G system with multi-state components is modelled by means of block-structured Markov chains. An indefinite number of repairpersons are assumed and PH distributions for the lifetime of the units and for the repair time are considered. The units can undergo two types of failures, repairable or non-repairable. The repairability of the failure can depend on the time elapsed up to failure. The system is modelled and the stationary distribution is built by using matrix analytic methods. Several performance measures of interest, such as the conditional probability of failure for the units and for the system, are built into the transient and stationary regimes. Rewards are included in the model. All results are shown in a matrix algorithmic form and are implemented computationally with Matlab. A numerical example of an optimization problem shows the versatility of the model.     

Reliability analysis for the consecutive-k-out-of-n: F system with repairmen taking multiple vacations

Commonly studied models of the consecutive-k-out-of-n: F repairable systems in the existing literatures were considering the systems which had one repairman without vacation or infinite repairmen without vacations. In addition to those models, multiple repairmen without vacations are studied occasionally. However, technical personnel are very short in some fields. Some failed components cannot be repaired in time. This paper deals with the phenomenon of waiting for repair by supposing R repairmen with multiple vacations in the system. Using the pairs (i, |j|), the factor that the R repairmen taking multiple vacations was embedded into the classical C(k, n: F) system. Reliability indexes are presented. Finally, the Runge–Kutta method was used to a special case, and the experimental results demonstrate the necessity and validity of the new model.     

Limit theorems for the minimum interpoint distance between any pair of i.i.d. random points in R d

The limit theorem for the minimum interpoint distance between any pair of i.i.d. random points in R ^d with common density fL ² was studied by a method which makes use of the convergence of point processes. Some one-dimensional examples with fL ² (including the cases Beta and Gamma distributions) were also considered.     

Active redundancy allocation for a k-out-of-n:F system of dependent components

We characterize active redundancy through compensator transform and use the reverse rule of order 2 (RR₂) property between compensator processes to investigate the problem of where to allocate a spare in a k-out-of-n:F system of dependent components through active redundancy.     

Approximation results for the weighted partition problem

We present several new standard and differential approximation results for the P₄-partition problem using the Hassin and Rubinstein algorithm [Information Processing Letters 63 (1997) 63–67]. Those results concern both minimization and maximization versions of the problem. However, the main point of this paper lies in the establishment of the robustness of this algorithm, in the sense that it provides good quality solutions for a variety of versions of the problem, under both standard and differential approximation ratios.     

Recursive algorithm for the reliability of a connected-(1, 2)-or-(2, 1)-out-of-(m, n):F lattice system

The connected-(1, 2)-or-(2, 1)-out-of-(m, n):F lattice system is included by the connected-X-out-of-(m, n):F lattice system defined by Boehme et al. [Boehme, T.K., Kossow, A., Preuss, W., 1992. A generalization of consecutive-k-out-of-n:F system. IEEE Transactions on Reliability 41, 451–457]. This system fails if and only if at least one subset of connected failed components occurs which includes at least a (1, 2)-matrix (that is, a row and two columns) or a (2, 1)-matrix(that is, two rows and a column) of failed components. This system is applied to two-dimensional network problems with adjacent constraints, and various systems, for example, a supervision system, etc.     

The decomposition theorem for the family of complete quasi-convex mappings

In this paper, we will give a decomposition theorem for some type of holomorphic mappings. This result is the generalization of many known results.     

Delay-dependent stability of symmetric schemes in Boundary Value Methods for DDEs

We consider the symmetric schemes in Boundary Value Methods (BVMs) applied to delay differential equations y^′(t)=ay(t)+by(t-τ) with real coefficients a and b. If the numerical solution tends to zero whenever the exact solution does, the symmetric scheme with (k₁+m,k₂)-boundary conditions is called τ_k1,k2(0)-stable. Three families of symmetric schemes, namely the Extended Trapezoidal Rules of first (ETRs) and second (ETR₂s) kind, and the Top Order Methods (TOMs), are considered in this paper.By using the boundary locus technology, the delay-dependent stability region of the symmetric schemes are analyzed and their boundaries are found. Then by using a necessary and sufficient condition, the considered symmetric schemes are proved to be τ_ν,ν-1(0)-stable.     

Labeling the -path with a condition at distance two

For integer r≥2, the infinite r-path P_∞(r) is the graph on vertices …v₋₃,v₋₂,v₋₁,v₀,v₁,v₂,v₃… such that v_s is adjacent to v_t if and only if |s−t|≤r−1. The r-path on n vertices is the subgraph of P_∞(r) induced by vertices v₀,v₁,v₂,…,v_n−1. For non-negative reals x₁ and x₂, a λ_x1,x2-labeling of a simple graph G is an assignment of non-negative reals to the vertices of G such that adjacent vertices receive reals that differ by at least x₁, vertices at distance two receive reals that differ by at least x₂, and the absolute difference between the largest and smallest assigned reals is minimized. With λ_x1,x2(G) denoting that minimum difference, we derive λ_x1,x2(P_n(r)) for r≥3, 1≤n≤∞, and . For , we obtain upper bounds on λ_x1,x2(P_∞(r)) and use them to give λ_x1,x2(P_∞(r)) for r≥5 and . We also determine λ_x1,x2(P_∞(3)) and λ_x1,x2(P_∞(4)) for all .     

Graphic sequences with a realization containing a generalized friendship graph

Gould, Jacobson and Lehel [R.J. Gould, M.S. Jacobson, J. Lehel, Potentially G-graphical degree sequences, in: Y. Alavi, et al. (Eds.), Combinatorics, Graph Theory and Algorithms, vol. I, New Issues Press, Kalamazoo, MI, 1999, pp. 451-460] considered a variation of the classical Turán-type extremal problems as follows: for any simple graph H, determine the smallest even integer σ(H,n) such that every n-term graphic sequence π=(d₁,d₂,…,d_n) with term sum σ(π)=d₁+d₂+?+d_n≥σ(H,n) has a realization G containing H as a subgraph. Let F_t,r,k denote the generalized friendship graph on kt−kr+r vertices, that is, the graph of k copies of K_t meeting in a common r set, where K_t is the complete graph on t vertices and 0≤r≤t. In this paper, we determine σ(F_t,r,k,n) for k≥2, t≥3, 1≤r≤t−2 and n sufficiently large.     

A projected subgradient method for solving generalized mixed variational inequalities

We consider the projected subgradient method for solving generalized mixed variational inequalities. In each step, we choose an ε_k-subgradient u^k of the function f and w^k in a set-valued mapping T, followed by an orthogonal projection onto the feasible set. We prove that the sequence is weakly convergent.