Asymptotically optimal pointwise and minimax quickest change-point detection for dependent data

We consider the quickest change-point detection problem in pointwise and minimax settings for general dependent data models. Two new classes of sequential detection procedures associated with the maximal “local” probability of a false alarm within a period of some fixed length are introduced. For these classes of detection procedures, we consider two popular risks: the expected positive part of the delay to detection and the conditional delay to detection. Under very general conditions for the observations, we show that the popular Shiryaev–Roberts procedure is asymptotically optimal, as the local probability of false alarm goes to zero, with respect to both these risks pointwise (uniformly for every possible point of change) and in the minimax sense (with respect to maximal over point of change expected detection delays). The conditions are formulated in terms of the rate of convergence in the strong law of large numbers for the log-likelihood ratios between the “change” and “no-change” hypotheses, specifically as a uniform complete convergence of the normalized log-likelihood ratio to a positive and finite number. We also develop tools and a set of sufficient conditions for verification of the uniform complete convergence for a large class of Markov processes. These tools are based on concentration inequalities for functions of Markov processes and the Meyn–Tweedie geometric ergodic theory. Finally, we check these sufficient conditions for a number of challenging examples (time series) frequently arising in applications, such as autoregression, autoregressive GARCH, etc.     

Discretisation of stochastic control problems for continuous time dynamics with delay

As a main step in the numerical solution of control problems in continuous time, the controlled process is approximated by sequences of controlled Markov chains, thus discretising time and space. A new feature in this context is to allow for delay in the dynamics. The existence of an optimal strategy with respect to the cost functional can be guaranteed in the class of relaxed controls. Weak convergence of the approximating extended Markov chains to the original process together with convergence of the associated optimal strategies is established.     

Iterative Methods for a Linearly Perturbed Algebraic Matrix Riccati Equation Arising in Stochastic Control

We start with a discussion of coupled algebraic Riccati equations arising in the study of linear-quadratic optimal control problems for Markov jump linear systems. Under suitable assumptions, this system of equations has a unique positive semidefinite solution, which is the solution of practical interest. The coupled equations can be rewritten as a single linearly perturbed matrix Riccati equation with special structures. We study the linearly perturbed Riccati equation in a more general setting and obtain a class of iterative methods from different splittings of a positive operator involved in the Riccati equation. We prove some special properties of the sequences generated by these methods and determine and compare the convergence rates of these methods. Our results are then applied to the coupled Riccati equations of jump linear systems. We obtain linear convergence of the Lyapunov iteration and the modified Lyapunov iteration, and confirm that the modified Lyapunov iteration indeed has faster convergence than the original Lyapunov iteration.     

Stochastic Modeling and Convergence Analysis of Internet Routers北大核心CSCD

目前建立的路由收敛模型大部分都是确定性模型,而路由器在收敛过程中存在丢包、链路噪声、互连拓扑结构突变等现象。针对这些随机问题,该文引入Bernoulli白序列分布、Wiener过程、Markov过程,提出了一种新的随机动力系统模型,应用随机微分方程理论和随机分析方法得出其路由收敛的充分条件,结果证明,随机环境下路由状态收敛与路由器连接拓扑的Laplace矩阵、Markov切换的平稳分布、网络中数据包的成功传输率以及噪声强度息息相关。最后通过一个数值实例验证了相关结论的有效性。     

Successive approximations for Markov decision processes and Markov games with unbounded rewards

The aim of this paper is to give a survey of recent developments in the area of successive approximations for Markov decision processes and Markov games. We will emphasize two aspects, viz. the conditions under which successive approximations converge in some strong sense and variations of these methods which diminish the amount of computational work to be executed. With respect to the first aspect it will be shown how much unboundedness of the rewards may be allowed without violation of the convergence

With respect to the second aspect we will present four ideas, that can be applied in conjunction, which may diminish the amount of work to be done. These ideas are: 1. the use of the actual convergence of the iterates for the construction of upper and lower bounds (Macqueen bounds), 2. the use of alternative policy improvement procedures (based on stopping times), 3. a better evaluation of the values of actual policies in each iteration step by a value oriented approach, 4. the elimination of suboptimal actions not only permanently, but also temporarily. The general presentation is given for Markov decision processes with a final section devoted to the possibilities of extension to Markov games.     

Discrete time Markov chains with interval probabilities

The parameters of Markov chain models are often not known precisely. Instead of ignoring this problem, a better way to cope with it is to incorporate the imprecision into the models. This has become possible with the development of models of imprecise probabilities, such as the interval probability model. In this paper we discuss some modelling approaches which range from simple probability intervals to the general interval probability models and further to the models allowing completely general convex sets of probabilities. The basic idea is that precisely known initial distributions and transition matrices are replaced by imprecise ones, which effectively means that sets of possible candidates are considered. Consequently, sets of possible results are obtained and represented using similar imprecise probability models.We first set up the model and then show how to perform calculations of the distributions corresponding to the consecutive steps of a Markov chain. We present several approaches to such calculations and compare them with respect to the accuracy of the results. Next we consider a generalisation of the concept of regularity and study the convergence of regular imprecise Markov chains. We also give some numerical examples to compare different approaches to calculations of the sets of probabilities.     

Constrained Stochastic Estimation Algorithms for a Class of Hybrid Stock Market Models

This paper is concerned with a class of hybrid stock market models, in which both the return rate and the volatility depend on a hidden, continuous-time Markov chain with a finite state space. One of the crucial issues is to estimate the generator of the underlying Markov chain. We develop a stochastic optimization procedure for this task, prove its convergence, and establish the rate of convergence. Numerical tests are carried out via simulation as well as using real market data. In addition, we demonstrate how to use the estimated generator in making stock liquidation decisions.     

Stable strong order 1.0 schemes for solving stochastic ordinary differential equations

The Balanced method was introduced as a class of quasi-implicit methods, based upon the Euler-Maruyama scheme, for solving stiff stochastic differential equations. We extend the Balanced method to introduce a class of stable strong order 1.0 numerical schemes for solving stochastic ordinary differential equations. We derive convergence results for this class of numerical schemes. We illustrate the asymptotic stability of this class of schemes is illustrated and is compared with contemporary schemes of strong order 1.0. We present some evidence on parametric selection with respect to minimising the error convergence terms. Furthermore we provide a convergence result for general Balanced style schemes of higher orders.     

Normal approximations for discrete-time occupancy processes

We study normal approximations for a class of discrete-time occupancy processes, namely, Markov chains with transition kernels of product Bernoulli form. This class encompasses numerous models which appear in the complex networks literature, including stochastic patch occupancy models in ecology, network models in epidemiology, and a variety of dynamic random graph models. Bounds on the rate of convergence for a central limit theorem are obtained using Stein’s method and moment inequalities on the deviation from an analogous deterministic model. As a consequence, our work also implies a uniform law of large numbers for a subclass of these processes.     

Decomposition of unreliable assembly/disassembly networks with limited buffer capacity and random processing times

An assembly/disassembly (A/D) network is a manufacturing system in which machines perform assembly and/or disassembly operations. We consider tree-structured systems of unreliable machines that produce discrete parts. Processing times, times to failure and times to repair in the inhomogeneous system are assumed to be stochastic and machine-dependent. Machines are separated by buffers of limited capacity. We develop Markov process models for discrete time and continuous time systems and derive approximate decomposition equations to determine performance measures such as production rate and average buffer levels in an iterative algorithm. An improved parameter updating procedure leads to a dramatic improvement with respect to convergence reliability. Numerical results demonstrate that the methods are quite accurate.     

Assessing Convergence and Mixing of MCMC Implementations via Stratification

Some posterior distributions lead to Markov chain Monte Carlo (MCMC) chains that are naturally viewed as collections of subchains. Examples include mixture models, regime-switching models, and hidden Markov models. We obtain MCMC-based estimators of posterior expectations by combining different subgroup (subchain) estimators using stratification and poststratification methods. Variance estimates of the limiting distributions of such estimators are developed. Based on these variance estimates, we propose a test statistic to aid in the assessment of convergence and mixing of chains. We compare our diagnostic with other commonly used methods. The approach is illustrated in two examples: a latent variable model for arsenic concentration in public water systems in Arizona and a Bayesian hierarchical model for Pacific sea surface temperatures. Supplementary materials, which include MATLAB codes for the proposed method, are available online.     

Active-set Newton methods for mathematical programs with vanishing constraints

Mathematical programs with vanishing constraints constitute a new class of difficult optimization problems with important applications in optimal topology design of mechanical structures. Vanishing constraints usually violate standard constraint qualifications, which gives rise to serious difficulties in theoretical and numerical treatment of these problems. In this work, we suggest several globalization strategies for the active-set Newton-type methods developed earlier by the authors for this problem class, preserving superlinear convergence rate of these methods under weak assumptions. Preliminary numerical results demonstrate that our approach is rather promising and competitive with respect to the existing alternatives.     

Bayesian Monte Carlo estimation for profile hidden Markov models

Hidden Markov models are used as tools for pattern recognition in a number of areas, ranging from speech processing to biological sequence analysis. Profile hidden Markov models represent a class of so-called “left–right” models that have an architecture that is specifically relevant to classification of proteins into structural families based on their amino acid sequences. Standard learning methods for such models employ a variety of heuristics applied to the expectation-maximization implementation of the maximum likelihood estimation procedure in order to find the global maximum of the likelihood function. Here, we compare maximum likelihood estimation to fully Bayesian estimation of parameters for profile hidden Markov models with a small number of parameters. We find that, relative to maximum likelihood methods, Bayesian methods assign higher scores to data sequences that are distantly related to the pattern consensus, show better performance in classifying these sequences correctly, and continue to perform robustly with regard to misspecification of the number of model parameters. Though our study is limited in scope, we expect our results to remain relevant for models with a large number of parameters and other types of left–right hidden Markov models.     

Iterative schemes for trifunction hemivariational inequalities

In this paper, we consider and study a new class of hemivariational inequalities, which is called trifunction hemivariational inequality. We suggest and analyze a class of iterative methods for solving trifunction hemivariational inequalities using the auxiliary principle technique. We prove that the convergence of these new methods either requires partially relaxed strongly monotonicity or pseudomonotonicity, which is a weaker condition than monotonicity. Results obtained in this paper include several new and known results as special cases.     

Exponential convergence to quasi-stationary distribution and $$$$-process

For general, almost surely absorbed Markov processes, we obtain necessary and sufficient conditions for exponential convergence to a unique quasi-stationary distribution in the total variation norm. These conditions also ensure the existence and exponential ergodicity of the \(Q\)-process (the process conditioned to never be absorbed). We apply these results to one-dimensional birth and death processes with catastrophes, multi-dimensional birth and death processes, infinite-dimensional population models with Brownian mutations and neutron transport dynamics absorbed at the boundary of a bounded domain.     

Self-Interacting Markov Chains

Abstract

In this article we study a class of self-interacting Markov chain models. We propose a novel theoretical basis based on measure-valued processes and semigroup techniques to analyze its asymptotic behavior as the time parameter tends to infinity. We exhibit different types of decays to equilibrium, depending on the level of interaction. We illustrate these results in a variety of examples, including Gaussian or Poisson self-interacting models. We analyze the long-time behavior of a new class of evolutionary self-interacting chain models. These genetic type algorithms can also be regarded as reinforced stochastic explorations of an environment with obstacles related to a potential function.     

Interior proximal methods and central paths for convex second-order cone programming

We make a unified analysis of interior proximal methods of solving convex second-order cone programming problems. These methods use a proximal distance with respect to second-order cones which can be produced with an appropriate closed proper univariate function in three ways. Under some mild conditions, the sequence generated is bounded with each limit point being a solution, and global rates of convergence estimates are obtained in terms of objective values. A class of regularized proximal distances is also constructed which can guarantee the global convergence of the sequence to an optimal solution. These results are illustrated with some examples. In addition, we also study the central paths associated with these distance-like functions, and for the linear SOCP we discuss their relations with the sequence generated by the interior proximal methods. From this, we obtain improved convergence results for the sequence for the interior proximal methods using a proximal distance continuous at the boundary of second-order cones.     

A higher-order Markov model for the Newsboy's problem

Markov models are commonly used in modelling many practical systems such as telecommunication systems, manufacturing systems and inventory systems. However, higher-order Markov models are not commonly used in practice because of their huge number of states and parameters that lead to computational difficulties. In this paper, we propose a higher-order Markov model whose number of states and parameters are linear with respect to the order of the model. We also develop efficient estimation methods for the model parameters. We then apply the model and method to solve the generalised Newsboy's problem. Numerical examples with applications to production planning are given to illustrate the power of our proposed model.     

On the conditions of convergence for one class of methods used for the solution of ill-posed problems

We propose a new class of projection methods for the solution of ill-posed problems with inaccurately specified coefficients. For methods from this class, we establish the conditions of convergence to the normal solution of an operator equation of the first kind. We also present additional conditions for these methods guaranteeing the convergence with a given rate to normal solutions from a certain set. Translated from Ukrains'kyi Matematychnyi Zhurnal, Vol. 60, No. 6, pp. 843–850, June, 2008.