A matrix perturbation method for computing the steady-state probability distributions of probabilistic Boolean networks with gene perturbations

Modeling genetic regulatory interactions is an important issue in systems biology. Probabilistic Boolean networks (PBNs) have been proved to be a useful tool for the task. The steady-state probability distribution of a PBN gives important information about the captured genetic network. The computation of the steady-state probability distribution involves the construction of the transition probability matrix of the PBN. The size of the transition probability matrix is 2ⁿ×2ⁿ where n is the number of genes. Although given the number of genes and the perturbation probability in a perturbed PBN, the perturbation matrix is the same for different PBNs, the storage requirement for this matrix is huge if the number of genes is large. Thus an important issue is developing computational methods from the perturbation point of view. In this paper, we analyze and estimate the steady-state probability distribution of a PBN with gene perturbations. We first analyze the perturbation matrix. We then give a perturbation matrix analysis for the captured PBN problem and propose a method for computing the steady-state probability distribution. An approximation method with error analysis is then given for further reducing the computational complexity. Numerical experiments are given to demonstrate the efficiency of the proposed methods.     

A new method of performance sensitivity analysis for non-Markovian queueing networks

The paper develops a new method of calculating and estimating the sensitivities of a class of performance measures with respect to a parameter of the service or interarrival time distributions in queueing networks. The distribution functions may be of a general form. The study is based on perturbation analysis of queueing networks. A new concept, the realization factor of a perturbation, is introduced for the network studied. The properties of realization factors are discussed, and a set of linear differential equations specifying the realization factors are derived. The sensitivity of the steady-state performance with respect to a parameter can be expressed in a simple form using realization factors. Based on this, the sensitivity can be estimated by applying a perturbation analysis algorithm to a sample path of the system. We show that the derivative of the performance measure with respect to a parameter based on a single sample path converges with probability one to the derivative of the steady-state performance as the length of the sample path goes to infinity. The results provide a new analytical method of calculating performance sensitivities and justifies the application of perturbation analysis algorithms to non-Markovian queueing networks.     

基于最大熵的延迟启动/关闭N策略M/G/1可修排队稳态队长分布

研究具有延迟启动-关闭的N策略M/G/1可修排队系统,利用最大熵方法导出稳态队长分布的解析解,进一步得到基于最大熵的顾客平均等待时间.通过比较顾客的平均等待时间来检验最大熵方法的精度,结果表明基于最大熵方法得到的稳态队长分布是相当精确的.     

离散时间单重休假两部件并联可修系统的可靠性分析

利用离散向量Markov过程方法研究了离散时间单重休假两同型部件并联可修系统.在部件寿命服从几何分布,修理时间和修理工休假时间服从一般离散型概率分布的假定下,引入修理时间和休假时间尾概率,求得了系统的稳态可用度、稳态故障频度、待修概率、修理工空闲概率和休假概率,以及首次故障前平均时间等可靠性指标.并通过具体数值实例展示了离散向量马氏链状态转移频度的具体计算方法.     

基于分布矩拟合的小子样二项分布参数P的置信下限

基于分布矩拟合的原则,给出小子样二项分布成功率P的置信下限的一种计算方法,通过与经典置信下限及reformualtion方法计算的置信下限进行比较,得出分布矩拟合方法计算的置信下限是合理和可信的.     

On the Minimal Nonnegative Solution of Nonsymmetric Algebraic Riccati Equation

We study perturbation bound and structured condition number about the minimal nonnegative solution of nonsymmetric algebraic Riccati equation, obtaining a sharp perturbation bound and an accurate condition number. By using the matrix sign function method we present a new method for finding the minimal nonnegative solution of this algebraic Riccati equation. Based on this new method, we show how to compute the desired M-matrix solution of the quadratic matrix equation X^2 - EX - F = 0 by connecting it with the nonsymmetric algebraic Riccati equation, where E is a diagonal matrix and F is an M-matrix.     

Thermal models for copper-alloyed dies in pressure die casting

A recent innovation in pressure die casting is the use of copper-alloyed dies suitably protected with a thermally sprayed steel layer. The thermal response of copper-alloyed dies is dictated principally by the deposited layer, the cooling arrangement and the casting geometry. This paper is concerned with the development of efficient numerical models for the prediction of both steady-state and transient thermal behaviour of the new die designs. Die temperatures are cyclic but useful information is obtained from a steady-state model, which provides for time-averaged temperatures and energy fluxes. The modelling strategy presented in the paper involves the indirect determination of transient temperatures. A perturbation approach is adopted, where a model for the difference between transient and steady-state temperature is developed. It is shown that this approach can be utilised to determine transient temperature efficiently once steady-state information is available with the transient perturbation model only involving surfaces where a significant variation in temperature occurs.     

Relaxation Time for the Discrete D/G/1 Queue

When queueing models are used for performance analysis of some stochastic system, it is usually assumed that the system is in steady-state. Whether or not this is a realistic assumption depends on the speed at which the system tends to its steady-state. A characterization of this speed is known in the queueing literature as relaxation time.The discrete D/G/1 queue has a wide range of applications. We derive relaxation time asymptotics for the discrete D/G/1 queue in a purely analytical way, mostly relying on the saddle point method. We present a simple and useful approximate upper bound which is sharp in case the load on the system is not very high. A sharpening of this upper bound, which involves the complementary error function, is then developed and this covers both the cases of low and high loads.For the discrete D/G/1 queue, the stationary waiting time distribution can be expressed in terms of infinite series that follow from Spitzer’s identity. These series involve convolutions of the probability distribution of a discrete random variable, which makes them suitable for computation. For practical purposes, though, the infinite series should be truncated. The relaxation time asymptotics can be applied to determine an appropriate truncation level based on a sharp estimate of the error caused by truncating.This revised version was published online in June 2005 with corrected coverdate     

Estimation of optimal backward perturbation bounds for the linear least squares problem

In this paper a method of estimating the optimal backward perturbation bound for the linear least squares problem is presented. In contrast with the optimal bound, which requires a singular value decomposition, this method is better suited for practical use on large problems since it requiresO(mn) operations. The method presented involves the computation of a strict lower bound for the spectral norm and a strict upper bound for the Frobenius norm which gives a gap in which the optimal bounds for the spectral and the Frobenius norm must be. Numerical tests are performed showing that this method produces an efficient estimate of the optimal backward perturbation bound.     

Robustness in stochastic programs with risk constraints

This paper is a contribution to the robustness analysis for stochastic programs whose set of feasible solutions depends on the probability distribution?P. For various reasons, probability distribution P may not be precisely specified and we study robustness of results with respect to perturbations of?P. The main tool is the contamination technique. For the optimal value, local contamination bounds are derived and applied to robustness analysis of the optimal value of a portfolio performance under risk-shaping CVaR constraints. A?new robust portfolio efficiency test with respect to the second order stochastic dominance criterion is suggested and the contamination methodology is exploited to analyze its resistance with respect to additional scenarios.     

On condition numbers of polynomial eigenvalue problems

In this paper, we investigate condition numbers of eigenvalue problems of matrix polynomials with nonsingular leading coefficients, generalizing classical results of matrix perturbation theory. We provide a relation between the condition numbers of eigenvalues and the pseudospectral growth rate. We obtain that if a simple eigenvalue of a matrix polynomial is ill-conditioned in some respects, then it is close to be multiple, and we construct an upper bound for this distance (measured in the euclidean norm). We also derive a new expression for the condition number of a simple eigenvalue, which does not involve eigenvectors. Moreover, an Elsner-like perturbation bound for matrix polynomials is presented.     

On sharpness of tchebycheff-type inequalities

Summary In this paper we discuss the sharpness of Tchebycheff-type inequalities obtained by the standard method, and give a unified theory on sharp inequalities. The problem of existence of a probability distribution that attains the sharp bound is also considered. The proof, based on the theory of convex sets, is very simple and the results might be sufficiently general for practical applications.     

Gaussian estimates for the density of the non-linear stochastic heat equation in any space dimension

In this paper, we establish lower and upper Gaussian bounds for the probability density of the mild solution to the non-linear stochastic heat equation in any space dimension. The driving perturbation is a Gaussian noise which is white in time with some spatially homogeneous covariance. These estimates are obtained using tools of the Malliavin calculus. The most challenging part is the lower bound, which is obtained by adapting a general method developed by Kohatsu-Higa to the underlying spatially homogeneous Gaussian setting. Both lower and upper estimates have the same form: a Gaussian density with a variance which is equal to that of the mild solution of the corresponding linear equation with additive noise.     

Stationary analysis of a discrete-time GI/D-MSP/1 queue with multiple vacations

This paper analyzes the steady-state behavior of a discrete-time single-server queueing system with correlated service times and server vacations. The vacation times of the server are independent and geometrically distributed, and their durations are integral multiples of slot duration. The customers are served one at a time under discrete-time Markovian service process. The new service process starts with the initial phase distribution independent of the path followed by the previous service process when the server returns from a vacation and finds at least one waiting customer. The matrix-geometric method is used to obtain the probability distribution of system-length at prearrival epoch. With the help of Markov renewal theory approach, we also derive the system-length distribution at an arbitrary epoch. The analysis of actual-waiting-time distribution in the queue measured in slots has also been carried out. In addition, computational experiences with a variety of numerical results are discussed to display the effect of the system parameters on the performance measures.     

随机BA模型的度分布

本文将马氏链首达概率方法应用于一个随机BA模型,得到这个模型度分布的精确表达式,并严格证明了度分布的存在性,同时说明择优连接对无标度特性的产生至关重要。     

Robustness of perturbation analysis estimators for queueing systems with unknown distributions

Sample-path-based stochastic gradient estimators for performance measures of queueing systems rely on the assumption that a probability distribution of the random vector of interest (e.g., a service or interarrival time sequence) is given. In this paper, we address the issue of dealing with unknown probability distributions and investigate the robustness of such estimators with respect to possibly erroneous distribution choices. We show that infinitesimal perturbation analysis (IPA) can be robust in this sense and, in some cases, provides distribution-independent estimates. Comparisons with other gradient estimators are provided, including experimental results. We also show that finite perturbation analysis (FPA), though only providing gradient approximations, possesses some attractive robustness properties with respect to unknown distribution parameters. An application of FPA estimation is included for a queueing system performance optimization problem involving customers with real-time constraints.This work was supported in part by the National Science Foundation Grant ECS-88-01912 and by the Office of Naval Research Contract N00014-87-K-0304.The authors wish to thank Dr. Jack Holtzman for several useful comments and suggestions.     

Estimates for the finite-time ruin probability with insurance and financial risks

The paper gives estimates for the finite-time ruin probability with insurance and financial risks. When the distribution of the insurance risk belongs to the class L(??) for some ?? > 0 or the subexponential distribution class, we abtain some asymptotic equivalent relationships for the finite-time ruin probability, respectively. When the distribution of the insurance risk belongs to the dominated varying-tailed distribution class, we obtain asymptotic upper bound and lower bound for the finite-time ruin probability, where for the asymptotic upper bound, we completely get rid of the restriction of mutual independence on insurance risks, and for the lower bound, we only need the insurance risks to have a weak positive association structure. The obtained results extend and improve some existing results.     

Perturbation Analysis of Structured Least Squares Problems and Its Application in Calibration of Interest Rate Term Structure

A structured perturbation analysis of the least squares problem is considered in this paper.The new error bound proves to be sharper than that for general perturbations. We apply the new error bound to study sensitivity of changing the knots for curve fitting of interest rate term structure by cubic spline.Numerical experiments are given to illustrate the sharpness of this bound.     

Monotonicity of some perturbations of irreducibly diagonally dominant M-matrices

This paper presents a new result concerning the perturbation theory of M-matrices. We give the proof of a theorem showing that some perturbations of irreducibly diagonally dominant M-matrices are monotone, together with an explicit bound of the norm of the perturbation. One of the assumptions concerning the perturbation matrix is that the sum of the entries of each of its row is nonnegative. The resulting matrix is shown to be monotone, although it may not be diagonally dominant and its off diagonal part may have some positive entries. We give as an application the proof of the second order convergence of an non-centered finite difference scheme applied to an elliptic boundary value problem.     

Consistency of perturbation analysis for a queue with finite buffer space and loss policy

The subject of discrete-event dynamical systems has taken on a new direction with the advent of perturbation analysis (PA), an efficient method for estimating the gradients of a steady-state performance measure, by analyzing data obtained from a single-simulation experiment in the time domain. A crucial issue is whether PA gives strongly consistent estimates, namely, whether average time-domain-based gradients converge, over infinite horizon, to the steady-state gradients. In this paper, we investigate this issue for a queue with a finite buffer capacity and a loss policy. The performance measure in question is the average amount of lost customers, as a function of the buffer's capacity, which is assumed to be continuous in our work. It is shown that PA gives strongly consistent estimates. The analysis uses a new technique, based on busy period-dependent inequalities. This technique may have possible extensions to analyses of consistency of PA for more general queueing systems.