Transient analysis of acyclic markov chains

Continuous-time Markov chains are commonly used insystem reliability modeling. In this paper, we discuss a method for automatically deriving transient solutions that are symbolic in t for acyclic Markov chains. Our method also includes parametric sensitivity analysis of the transient solution and several cumulative measures associated with Markov chain behavior. We include three examples, one to show the use of our method in evaluating approximate solution techniques, one showing parametric sensitivity analysis of a large Markov model, and one demonstrating the computation of cumulative measures for an acyclic Markov reward process.     

An undecidable problem for countable markov chains

A nondeterministic defense system is considered for a linearly ordered sequences of nodes of a countable Markov chain with an environment. We prove undecidability of the problem of existence of a sequence of signals from attacking subsystems that render the central nodes completely defenseless.Translated from Kibernetika, No. 2, pp. 1–6, 15, March–April, 1991.     

Computation of mutual entropy in quantum markov chains

There are several damping phenomena in quantum optics. Such phenomena have been usually explained by open systems. In statistical physics, open system dynamics have been used to study the irreversibility and the approach to equilibrium. In this paper, the dynamical change of the mutual entropy for an open system, frequently studied in the quantum optics literature, is rigorously computed through a model of quantum Markov chain. In particular, the concrete formula of Stinespring expression for such a model is obtained and applied to the derivation of the mutual entropy, and some computational results are presented.     

Optimal control of markov chains admitting strong and weak interactions

This paper is devoted to the study of an optimal control problem for a Markov chain with generator B + εA, where ε is a small parameter. It is shown that an approximate solution can be calculated by a policy improvement algorithm involving computations relative to an ‘aggregated’ problem (the dimension of which is given by N, the number of ergodic sets for the B matrix) together with a family of ‘decentralized’ problems (the dimensions of which are given by the number of elements in each ergodic set for the B matrix).     

The analysis of academic retrenchment using parametric programming and markov chains

This paper, recognizing that retrenchment is the prognosis for the forseeable future for most collegiate institutions, employs Markov chains to trace the passage of faculty in time, and linear and parametric programming to provide guidelines for control of faculty size and composition. If cutbacks in size need to be carried out, how best should this be done? How does affirmative action influence the decision? What about accrediting agency regulations? What effects on quality can be anticipated? What policies should be recognized simultaneously? These and other questions are examined on both short-run and long-run bases using aggregated variables and a very detailed illustration.     

Optimal and near-optimal incentive strategies in the hierarchical control of markov chains

This paper considers Markovian Stackelberg problems with one leader and N followers. Firstly, an algorithm is proposed to compute optimal affine incentive strategy for the leader and Nash reactions of the followers, for general finite state Markov chains, under the average-cost-per-stage criteria. Next, this algorithm is analyzed in the context of weakly-coupled Markov chains to compute near-optimal strategies from a reduced-order aggregate model. The robustness of the near-optimal solution is established, and the multimodel feature of the computational algorithm is highlighted.     

Online learning with hidden markov models

We present an online version of the expectation-maximization (EM) algorithm for hidden Markov models (HMMs). The sufficient statistics required for parameters estimation is computed recursively with time, that is, in an online way instead of using the batch forward-backward procedure. This computational scheme is generalized to the case where the model parameters can change with time by introducing a discount factor into the recurrence relations. The resulting algorithm is equivalent to the batch EM algorithm, for appropriate discount factor and scheduling of parameters update. On the other hand, the online algorithm is able to deal with dynamic environments, i.e., when the statistics of the observed data is changing with time. The implications of the online algorithm for probabilistic modeling in neuroscience are briefly discussed.     

Predicting torsion angles in amino acid protein sequences based on a bayesian classification procedure on markov chains

Torsion angles formed by C ^α atoms of four neighboring residues are predicted using a Bayesian classification procedure on nonstationary Markov chains. The predicted sequence of torsion angles is used to construct a three-dimensional protein structure on Z ³ lattice.     

Characteristic of exit moments and models of enlargement of states for finite markov chains in terms of global memory functionals

A notion of local- and global-memory functionate for discrete-type distributions is introduced by analogy with the notion of the memory for continuous-type distributions introduced in Muth’s papers. In the class of PH-distributions (i.e., of distributions of the time of Markov chain exit from a subset of states) the necessary and sufficient conditions are obtained for the case where the exit time has an exponential (continuous-time) or a geometric (discrete time) distribution. A new notion of a global memory functional for decomposition of the state space of a finite Markov chain is introduced. Its properties as a measure of quality of decomposition and enlargement of a state space are studied. The asymptotic optimality is proved. Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 110–120, May–June, 2000.     

Temporal and spatial data mining with second-order hidden markov models

In the frame of designing a knowledge discovery system, we have developed stochastic models based on high-order hidden Markov models. These models are capable to map sequences of data into a Markov chain in which the transitions between the states depend on the n previous states according to the order of the model. We study the process of achieving information extraction from spatial and temporal data by means of an unsupervised classification. We use therefore a French national database related to the land use of a region, named Ter Uti, which describes the land use both in the spatial and temporal domain. Land-use categories (wheat, corn, forest, ...) are logged every year on each site regularly spaced in the region. They constitute a temporal sequence of images in which we look for spatial and temporal dependencies. The temporal segmentation of the data is done by means of a second-order Hidden Markov Model (HMM2) that appears to have very good capabilities to locate stationary segments, as shown in our previous work in speech recognition. The spatial classification is performed by defining a fractal scanning of the images with the help of a Hilbert–Peano curve that introduces a total order on the sites, preserving the relation of neighborhood between the sites. We show that the HMM2 performs a classification that is meaningful for the agronomists. Spatial and temporal classification may be achieved simultaneously by means of a two levels HMM2 that measures the a posteriori probability to map a temporal sequence of images onto a set of hidden classes.     

Hierarchical parallel search for markov control with enhanced selector

A new method of hierarchical parallel search is proposed for dealing with Markov planning/control processes in systems with uncertain information. It is based on a new concept of analyzing alternative with uncertain cost evaluation. Under definite conditions, instead of making an immediate choice based on expectation of cost at each step of the search, it is recommended to postpone the final decision until information is improved, and the uncertainty is reduced. In addition to elementary alternatives, their combinations are also considered for possible pursuit. The best set of rough elementary solutions is to be determined at the upper of two adjacent planning/control levels, then all elementary alternatives of this set as well as their combinations, are being pursued at the lower level with a higher resolution of information, while evaluation of the remaining cost for each of the alternatives, is being constantly improved due to the process of evolutionary uncertainty reduction. This bilevel process is easily extendible over the whole hierarchy of the system. The method is working in the graph-search and dynamic programming paradigms. The set of problems to be solved is formulated and some of them are addressed. Various applications are contemplated.     

Pascal-clarifications and recommended extensions

Summary The objectives of this paper are to clarify certain issues in the language Pascal that were left open by the defining Report and to recommend specific forms for certain extensions of the language that have repeatedly appeared in discussions and even implementations. By encouraging prospective implementors to adopt a common form, we wish to enhance the prospects for practical portability of Pascal programs. Except for parameters being procedures and functions, the language constructs described by the Pascal Report are not changed, i.e. the new syntax permits the same constructs with the same (intended) meaning. The paper expresses the author's proposal following a discussion among a small group of people who have been working on Pascal compilers and standardization. In itself it is not an attempt to standardize Pascal or present a complete revision of the Report. Concentrating on the type concept, the meaning of identifiers, and a limited number of extensions the need of which is generally accepted, the paper establishes guidelines for standardization and revision of the Pascal Report. It is presented as a carefully deliberated and (hopefully) consistent proposal for acceptance by whatever means the Pascal community may choose to adopt. I wish to thank everyone mentioned for his comments and cooperation, but above all Niklaus Wirth for his encouraging support and most valuable influence, especially in limiting the number of topics considered in detail. I thank R.D. Tennent and two anonymous referees for their valuable comments and suggestions.     

MRP lot sizing with multiple purchase discounts

Five MRP lot sizing models are modified to accommodate multiple purchase discounts and tested in an experiment involving different levels of requirements variability, discount attractiveness, and order cost. The testing of multiple purchase discounts is an extension of earlier research that compared MRP lot sizing models under a simplified discount structure involving a single price break [3, 4, 7]. The models tested here have either been implemented in some actual MRP systems or have been proposed as effective models by other researchers. Five hundred test problems were solved by each model, generating 2500 cost figures for comparison. The results indicate that an incremental version of part-period balancing and, to a lesser extent, the least unit cost method are the best models of those tested.     

Resource allocation with time intervals

We study a resource allocation problem where jobs have the following characteristic: each job consumes some quantity of a bounded resource during a certain time interval and induces a given profit. We aim to select a subset of jobs with maximal total profit such that the total resource consumed at any point in time remains bounded by the given resource capacity.While this case is trivially NP-hard in general and polynomially solvable for uniform resource consumptions, our main result shows the NP-hardness for the case of general resource consumptions but uniform profit values, i.e. for the case of maximizing the number of performed jobs. This result applies even for proper time intervals.We also give a deterministic (1/2−ε)-approximation algorithm for the general problem on proper intervals improving upon the currently known 1/3 ratio for general intervals. Finally, we study the worst-case performance ratio of a simple greedy algorithm.     

Use-definition chains with applications

Methods of compile-time program analysis for automatic code optimization usually include control flow analysis, in which possible execution flow paths are modeled, and data flow analysis, in which data relatiohsips are modeled. One representation of data relations in a program, via use-definition chains, is examined in the light of a particular example problem—the global elimination of “useless” computation. Two elimination algorithms which use differently organized use-definition chains are presented and compared for space complexity on two pathologically different families of flow graphs. Algorithms to compute chains of both varieties are also developed.     

Modal transition systems with weight intervals

We propose weighted modal transition systems, an extension to the well-studied specification formalism of modal transition systems that allows to express both required and optional behaviours of their intended implementations. In our extension we decorate each transition with a weight interval that indicates the range of concrete weight values available to the potential implementations. In this way resource constraints can be modelled using the modal approach. We focus on two problems. First, we study the question of existence/finding the largest common refinement for a number of finite deterministic specifications and we show PSPACE-completeness of this problem. By constructing the most general common refinement, we allow for a stepwise and iterative construction of a common implementation. Second, we study a logical characterisation of the formalism and show that a formula in a natural weight extension of the logic CTL is satisfied by a given modal specification if and only if it is satisfied by all its refinements. The weight extension is general enough to express different sorts of properties that we want our weights to satisfy.