Markov decision processes with noise-corrupted and delayed state observations

We consider the partially observed Markov decision process with observations delayed by k time periods. We show that at stage t, a sufficient statistic is the probability distribution of the underlying system state at stage t - k and all actions taken from stage t - k through stage t - 1. We show that improved observation quality and/or reduced data delay will not decrease the optimal expected total discounted reward, and we explore the optimality conditions for three important special cases. We present a measure of the marginal value of receiving state observations delayed by (k - 1) stages rather than delayed by k stages. We show that in the limit as k →∞ the problem is equivalent to the completely unobserved case. We present numerical examples which illustrate the value of receiving state information delayed by k stages.     

Adjoining batch Markov arrival processes of a Markov chain

A batch Markov arrival process (BMAP) X* = (N, J) is a 2-dimensional Markov process with two components, one is the counting process N and the other one is the phase process J. It is proved that the phase process is a time-homogeneous Markov chain with a finite state-space, or for short, Markov chain. In this paper, a new and inverse problem is proposed firstly: given a Markov chain J, can we deploy a process N such that the 2-dimensional process X* = (N, J) is a BMAP? The process X* = (N, J) is said to be an adjoining BMAP for the Markov chain J. For a given Markov chain the adjoining processes exist and they are not unique. Two kinds of adjoining BMAPs have been constructed. One is the BMAPs with fixed constant batches, the other one is the BMAPs with independent and identically distributed (i.i.d) random batches. The method we used in this paper is not the usual matrix-analytic method of studying BMAP, it is a path-analytic method. We constructed directly sample paths of adjoining BMAPs. The expressions of characteristic (D _k , k = 0, 1, 2 · · ·) and transition probabilities of the adjoining BMAP are obtained by the density matrix Q of the given Markov chain J. Moreover, we obtained two frontal Theorems. We present these expressions in the first time.     

Negative entropy,zero temperature and Markov chains on the interval

We consider ergodic optimization for the shift map on the modified Bernoulli space σ: [0, 1]^? → [0, 1]^?, where [0, 1] is the unit closed interval, and the potential A: [0, 1]^? → ? considered depends on the two first coordinates of [0, 1]^?. We are interested in finding stationary Markov probabilities µ_∞ on [0, 1]^? that maximize the value ∫ Adµ, among all stationary (i.e. σ-invariant) probabilities µ on [0, 1]^?. This problem correspond in Statistical Mechanics to the zero temperature case for the interaction described by the potential A. The main purpose of this paper is to show, under the hypothesis of uniqueness of the maximizing probability, a Large Deviation Principle for a family of absolutely continuous Markov probabilities µ _β which weakly converges to µ_∞. The probabilities µ _β are obtained via an information we get from a Perron operator and they satisfy a variational principle similar to the pressure in Thermodynamic Formalism. As the potential A depends only on the first two coordinates, instead of the probability µ on [0, 1]^?, we can consider its projection ν on [0, 1]². We look at the problem in both ways. If µ_∞ is the maximizing probability on [0, 1]^?, we also have that its projection ν _∞ is maximizing for A. The hypothesis about stationarity on the maximization problem can also be seen as a transhipment problem. Under the hypothesis of A being C ² and the twist condition, that is,

$\frac{{\partial ^2 A}}{{\partial x\partial y}}(x,y) \ne 0, for all (x,y) \in [0,1]^2 ,$

we show the graph property of the maximizing probability ν on [0, 1]². Moreover, the graph is monotonous. An important result we get is: the maximizing probability is unique generically in Mañé’s sense. Finally, we exhibit a separating sub-action for A.

     

Properties of the false vacuum as a quantum unstable state

We analyze properties of unstable vacuum states from the standpoint of quantum theory. Some suggestions can be found in the literature that some false (unstable) vacuum states can survive up to times when their survival probability takes a nonexponential form. At asymptotically large times, the survival probability as a function of the time t has an inverse power-law form. We show that in this time region, the energy of false vacuum states tends to the energy of the true vacuum state as 1/t ² as t→∞. This means that the energy density in the unstable vacuum state and hence also the cosmological constant Λ = Λ(t) should have analogous properties. The conclusion is that Λ in a universe with an unstable vacuum should have the form of a sum of the “bare” cosmological constant and a term of the type 1/t ²: Λ(t) ≡ Λ_bare + d/t ² (where Λ_bare is the cosmological constant for a universe with the true vacuum).     

Estimates on the amplitude of the first Dirichlet eigenvector in discrete frameworks

Consider a finite absorbing Markov generator, irreducible on the non-absorbing states. PerronFrobenius theory ensures the existence of a corresponding positive eigenvector ψ. The goal of the paper is to give bounds on the amplitude max ψ/ min ψ. Two approaches are proposed: One using a path method and the other one, restricted to the reversible situation, based on spectral estimates. The latter approach is extended to denumerable birth and death processes absorbing at 0 for which infinity is an entrance boundary. The interest of estimating the ratio is the reduction of the quantitative study of convergence to quasi-stationarity to the convergence to equilibrium of related ergodic processes, as seen by Diaconis and Miclo(2014).     

Approximation and estimation of very small probabilities of multivariate extreme events

This article discusses modelling of the tail of a multivariate distribution function by means of a large deviation principle (LDP), and its application to the estimation of the probability p _n of a multivariate extreme event from a sample of n iid random vectors, with \(p_{n}\in [n^{-\tau _{2}},n^{-\tau _{1}}]\) for some t ₁>1 and t ₂>t ₁. One way to view the classical tail limits is as limits of probability ratios. In contrast, the tail LDP provides asymptotic bounds or limits for log-probability ratios. After standardising the marginals to standard exponential, tail dependence is represented by a homogeneous rate function I. Furthermore, the tail LDP can be extended to represent both dependence and marginals, the latter implying marginal log-Generalised Weibull tail limits. A connection is established between the tail LDP and residual tail dependence (or hidden regular variation) and a recent extension of it. Under a smoothness assumption, they are implied by the tail LDP. Based on the tail LDP, a simple estimator for very small probabilities of extreme events is formulated. It avoids estimation of I by making use of its homogeneity. Strong consistency in the sense of convergence of log-probability ratios is proven. Simulations and an application illustrate the difference between the classical approach and the LDP-based approach.     

Existence of infinite Viterbi path for pairwise Markov models

For hidden Markov models one of the most popular estimates of the hidden chain is the Viterbi path — the path maximizing the posterior probability. We consider a more general setting, called the pairwise Markov model, where the joint process consisting of finite-state hidden regime and observation process is assumed to be a Markov chain. We prove that under some conditions it is possible to extend the Viterbi path to infinity for almost every observation sequence which in turn enables to define an infinite Viterbi decoding of the observation process, called the Viterbi process. This is done by constructing a block of observations, called a barrier, which ensures that the Viterbi path goes through a given state whenever this block occurs in the observation sequence.     

Interpretation of the Evolution of the Homogeneous Markov System (or,equivalently, of the Embedded Markov Chain) as the Deformation of a Viscoelastic Medium. The 3-D Case

Every attainable structure of a continuous time homogeneous Markov chain (HMC) with n states, or of a closed Markov system with an embedded HMC with n states, or more generally of a Markov system driven by an HMC, is considered as a point-particle of ? ⁿ . Then, the motion of the attainable structure corresponds to the motion of the respective point-particle in ? ⁿ . Under the assumption that “the motion of every particle at every time point is due to the interaction with its surroundings”, ? ⁿ (and equivalently the set of the accosiated attainable structures of the homogeneous Markov system (HMS), or alternatively of the underlying embedded HMC) becomes a continuum. Thus, the evolution of the set of the attainable structures corresponds to the motion of the continuum. In this paper it is shown that the evolution of a three-dimensional HMS (n = 3) or simply of an HMC, can be interpreted through the evolution of a two-dimensional isotropic viscoelastic medium.     

Markov Chains on Graded Posets

We consider two types of discrete-time Markov chains where the state space is a graded poset and the transitions are taken along the covering relations in the poset. The first type of Markov chain goes only in one direction, either up or down in the poset (an up chain or down chain). The second type toggles between two adjacent rank levels (an up-and-down chain). We introduce two compatibility concepts between the up-directed transition probabilities (an up rule) and the down-directed (a down rule), and we relate these to compatibility between up-and-down chains. This framework is used to prove a conjecture about a limit shape for a process on Young’s lattice. Finally, we settle the questions whether the reverse of an up chain is a down chain for some down rule and whether there exists an up or down chain at all if the rank function is not bounded.     

Waiting times and stopping probabilities for patterns in Markov chains

Suppose that C is a finite collection of patterns. Observe a Markov chain until one of the patterns in C occurs as a run. This time is denoted by τ. In this paper, we aim to give an easy way to calculate the mean waiting time E(τ) and the stopping probabilities P(τ = τA)with A ∈ C, where τA is the waiting time until the pattern A appears as a run.     

Two new heuristics for the <Emphasis Type="Italic">GI</Emphasis>/<Emphasis Type="Italic">G</Emphasis>/<Emphasis Type="Italic">n</Emphasis>/0 queueing loss system with examples based on the two-phase Coxian distribution

In this paper, we introduce a new heuristic approach for the numerical analysis of queueing systems. In particular, we study the general, multi-server queueing loss system, the GI/G/n/0 queue, with an emphasis on the calculation of steady-state loss probabilities. Two new heuristics are developed, called the GM Heuristic and the MG Heuristic, both of which make use of an exact analysis of the corresponding single-server GI/G/1/0 queue. The GM Heuristic also uses an exact analysis of the GI/M/n/0 queue, while the MG Heuristic uses an exact analysis of the M/G/n/0 queue. Experimental results are based on the use of two-phase Coxian distributions for both the inter-arrival time and the service time; these include an error analysis for each heuristic and the derivation of experimental probability bounds for the loss probability. For the class of problems studied, it is concluded that there are likely to be many situations where the accuracy of the GM Heuristic is adequate for practical purposes. Methods are also developed for combining the GM and MG Heuristics. In some cases, this leads to approximations that are significantly more accurate than those obtained by the individual heuristics.     

The Factorization of Queueing Equations and Their Interpretation

There are many queueing systems, including the M ^x /M ^y /c queue, the GI ^x /M/c queue and the M/D/c queue, in which the distribution of the queue length at certain epochs is determined by a Markov chain with the following structure. Except for a number of boundary states, all columns of the transition matrix are identical except for a shift which assures that there is always the same element occupying the main diagonal. This paper describes how one can find the equilibrium distribution for such Markov chains. Typically, this problem is solved by factorizing of a certain expression characterizing the repeated columns. In this paper, we show that this factorization has a probabilistic significance and we use this result to develop new approaches for finding the equilibrium distribution in question.     

Properties of the promotion Markov chain on linear extensions

The Tsetlin library is a very well-studied model for the way an arrangement of books on a library shelf evolves over time. One of the most interesting properties of this Markov chain is that its spectrum can be computed exactly and that the eigenvalues are linear in the transition probabilities. This result has been generalized in different ways by various people. In this work, we investigate one of the generalizations given by the extended promotion Markov chain on linear extensions of a poset P introduced by Ayyer et al. (J Algebr Comb 39(4):853–881, 2014). They showed that if the poset P is a rooted forest, the transition matrix of this Markov chain has eigenvalues that are linear in the transition probabilities and described their multiplicities. We show that the same property holds for a larger class of posets for which we also derive convergence to stationarity results.     

Uniform approximation of continuous functions by probability functions of Boolean bases

Random Boolean expressions obtained by random and independent substitution of the constants 1, 0 with probabilities p, 1 ? p, respectively, into random non-iterated formulas over a given basis are considered. The limit of the probability of appearance of expressions with the value 1 under unrestricted growth of the complexity of expressions, which is called the probability function, is considered. It is shown that for an arbitrary continuous function f(p) mapping the segment [0, 1] into itself there exists a sequence of bases whose probability functions uniformly approximate the function f(p) on the segment [0, 1].     

On the Heterogeneous M/G/n Blocking System in a Random Environment

This paper discusses the equilibrium behaviour of the generalized M/G/n blocking system with heterogeneous servers. The system is evolving in a random environment controlled by an irreducible, aperiodic, m-state Markov chain Z(t). This paper deals with the main characteristics, such as utilization, the average length of busy period of the system, the mean number of occupied servers and the probability of blocking. Finally, numerical examples illustrate the problem in question.     

Extended Gelfand–Tsetlin graph,its q-boundary,and q-B-splines

The boundary of the Gelfand–Tsetlin graph is an infinite-dimensional locally compact space whose points parameterize the extreme characters of the infinite-dimensional group U(∞). The problem of harmonic analysis on the group U(∞) leads to a continuous family of probability measures on the boundary—the so-called zw-measures. Recently Vadim Gorin and the author have begun to study a q-analogue of the zw-measures. It turned out that constructing them requires introducing a novel combinatorial object, the extended Gelfand–Tsetlin graph. In the present paper it is proved that the Markov kernels connected with the extended Gelfand–Tsetlin graph and its q-boundary possess the Feller property. This property is needed for constructing a Markov dynamics on the q-boundary. A connection with the B-splines and their q-analogues is also discussed.     

Condition monitoring: a new perspective

We present a novel approach to support preventive replacement decisions based on condition monitoring. It is assumed that the condition of a technical unit is measured continuously, with the measurement indicating in which of k≥2 states the unit is. A new unit is in state S₁, and failure occurs the moment a unit leaves state S _k . A unit will only go from state S _j to state S_j+1, and these immediately observed transitions occur at random times. At such transition moments a decision is required on preventive replacement of the unit, which would require preparation time. Such a decision needs to be based on inferences about the total residual time till failure. We present a method for such inferences that relies on minimal model assumptions added to data on state transitions. We illustrate the approach via simulated examples, and discuss possible use of the method and related aspects.     

On the Conservativeness of Some Markov Processes

We give a unified method to obtain the conservativeness of a class of Markov processes associated with lower bounded semi-Dirichlet forms on L ²(X;m), including symmetric diffusion processes, some non-symmetric diffusion processes and jump type Markov processes on X, where X is a locally compact separable metric space and m is a positive Radon measure on X with full topological support. Using the method, we give an example in each section, providing the conservativeness of the processes, that are given by the “increasingness of the volume of some sets(balls)” and “that of the coefficients on the sets” of the Markov processes.     

Hitting and martingale characterizations of one-dimensional diffusions

The main theorem of the paper is that, for a large class of one-dimensional diffusions (i. e. strong Markov processes with continuous sample paths): if x(t) is a continuous stochastic process possessing the hitting probabilities and mean exit times of the given diffusion, then x(t) is Markovian, with the transition probabilities of the diffusion. For a diffusion x(t) with natural boundaries at ± ∞, there is constructed a sequence π _n (t, x) of functions with the property that the π _n (t, x (t)) are martingales, reducing in the case of the Brownian motion to the familiar martingale polynomials. It is finally shown that if a stochastic process x (t) is a martingale with continuous paths, with the additional property that

$$\mathop \smallint \limits_0^{x\left( t \right)} m\left( {0,y} \right]dy - t$$     

New Cases of the Polynomial Solvability of the Independent Set Problem for Graphs with Forbidden Paths

The independent set problem is solvable in polynomial time for the graphs not containing the path P _k for any fixed k. If the induced path P _k is forbidden then the complexity of this problem is unknown for k > 6. We consider the intermediate cases that the induced path P _k and some of its spanning supergraphs are forbidden. We prove the solvability of the independent set problem in polynomial time for the following cases: (1) the supergraphs whose minimal degree is less than k/2 are forbidden; (2) the supergraphs whose complementary graph has more than k/2 edges are forbidden; (3) the supergraphs from which we can obtain P _k by means of graph intersection are forbidden.