Foundations of the 2N-ary Choice Tree Model

We define the 2N-ary choice tree model for reaction times and choice probabilities in N-alternative preferential choice by specifying a random walk on a 2N-ary tree. It allows for calculation of expected choice response times and expected choice probabilities in closed form and accounts for several preference reversal effects that emerge from the context. Here, we focus on the expected values and on the definition of the transition probabilities that constitute the random walk.     

L2 − L∞ filtering for Markovian jump systems with time-varying delays and partly unknown transition probabilities

This paper considers the L₂ − L_∞ filtering problem for Markovian jump systems. The systems under consideration involve time-varying delays, disturbance signal and partly unknown transition probabilities. The aim of this paper is to design a filter, which is suitable for exactly known and partly unknown transition probabilities, such that the filtering error system is stochastically stable and a prescribed L₂ − L_∞ disturbance attenuation level is guaranteed. By using the Lyapunov-Krasovskii functional, sufficient conditions are formulated in terms of linear matrix inequalities (LMIs). A numerical example is given to illustrate the effectiveness of the proposed main results. All these results are expected to be of use in the study of filter design for Markovian jump systems with partly unknown transition probabilities.     

Numerical Approach for Assessing System Dynamic Availability Via Continuous Time Homogeneous Semi-Markov Processes

Continuous-time homogeneous semi-Markov processes (CTHSMP) are important stochastic tools to model reliability measures for systems whose future behavior is dependent on the current and next states occupied by the process as well as on sojourn times in these states. A method to solve the interval transition probabilities of CTHSMP consists of directly applying any general quadrature method to the N ² coupled integral equations which describe the future behavior of a CTHSMP, where N is the number of states. However, the major drawback of this approach is its considerable computational effort. In this work, it is proposed a new more efficient numerical approach for CTHSMPs described through either transition probabilities or transition rates. Rather than N ² coupled integral equations, the approach consists of solving only N coupled integral equations and N straightforward integrations. Two examples in the context of availability assessment are presented in order to validate the effectiveness of this method against the comparison with the results provided by the classical and Monte Carlo approaches. From these examples, it is shown that the proposed approach is significantly less time-consuming and has accuracy comparable to the method of N ² computational effort.     

Control problems with time-lag. II

Consider a continuous time Markov chain with stationary transition probabilities. A function of the state is observed. A regular conditional probability distribution for the trajectory of the chain, given observations up to time t, is obtained. This distribution also corresponds to a Markov chain, but the conditional chain has nonstationary transition probabilities. In particular, computation of the conditional distribution of the state at time s is discussed. For s > t, we have prediction (extrapolation), while s < t corresponds to smoothing (interpolation). Equations for the conditional state distribution are given on matrix form and as recursive differential equations with varying s or t. These differential equations are closely related to Kolmogorov's forward and backward equations. Markov chains with one observed and one unobserved component are treated as a special case. In an example, the conditional distribution of the change-point is derived for a Poisson process with a changing intensity, given observations of the Poisson process.     

The approximate calculation of invariant measures of diffusions via finite difference approximations to degenerate elliptic partial differential equations

If $\text{L}$ is the (possibly degenerate) differential generator of a diffusion process whose measures converge to a unique invariant measure μ, then formally the value γ in $\text{F}$V(x)+k(x)?γ=0 is ∝ k(x) μ(dx). A finite difference approximation is used to solve the differential equation. The coefficients in the finite difference equation are one-step transition probabilities for some Markov chain whose (suitable) continuous time interpolations converge weakly to the diffusion. Under reasonable conditions, the invariant measure of the sequence of chains converges weakly to the weak sense density of μ. as the finite difference intervals go to zero. The approximating measure can be taken to be the invariant measure (or Cesaro sum of the n-step transition probabilities for the chain), of the chain, suitably weighted.     

On a bilateral birth-death process with alternating rates

We consider a bilateral birth-death process characterized by a constant transition rate ?? from even states and a possibly different transition rate??? from odd states. We determine the probability generating functions of the even and odd states, the transition probabilities, mean and variance of the process for arbitrary initial state. Some features of the birth-death process confined to the non-negative integers by a reflecting boundary in the zero-state are also analyzed. In particular, making use of a Laplace transform approach we obtain a series form of the transition probability from state 1 to the zero-state.     

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.     

Random walk with long-range interaction with a barrier and its dual: Exact results

We consider the random walk on Z₊={0,1,…}, with up and down transition probabilities given the chain is in state x∈{1,2,…}:

(1)     

The coalescent

The n-coalescent is a continuous-time Markov chain on a finite set of states, which describes the family relationships among a sample of n members drawn from a large haploid population. Its transition probabilities can be calculated from a factorization of the chain into two independent components, a pure death process and a discrete-time jump chain. For a deeper study, it is useful to construct a more complicated Markov process in which n-coalescents for all values of n are embedded in a natural way.     

Mixing times with applications to perturbed Markov chains

A measure of the “mixing time” or “time to stationarity” in a finite irreducible discrete time Markov chain is considered. The statistic , where {π_j} is the stationary distribution and m_ij is the mean first passage time from state i to state j of the Markov chain, is shown to be independent of the initial state i (so that η_i = η for all i), is minimal in the case of a periodic chain, yet can be arbitrarily large in a variety of situations. An application considering the effects perturbations of the transition probabilities have on the stationary distributions of Markov chains leads to a new bound, involving η, for the 1-norm of the difference between the stationary probability vectors of the original and the perturbed chain. When η is large the stationary distribution of the Markov chain is very sensitive to perturbations of the transition probabilities.     

Further results on the relationship between μ-invariant measures and quasi-stationary distributions for absorbing continuous-time Markov chains

This note considers continuous-time Markov chains whose state space consists of an irreducible class, C, and an absorbing state which is accessible from C. The purpose is to provide results on μ-invariant and μ-subinvariant measures where absorption occurs with probability less than one. In particular, the well-known premise that the μ-invariant measure, m, for the transition rates be finite is replaced by the more natural premise that m be finite with respect to the absorption probabilities. The relationship between μ-invariant measures and quasi-stationary distributions is discussed.     

Bounds for the regret loss in dynamic programming under adaptive control

We consider a Markovian dynamic programming model in which the transition probabilities depend on an unknown parameterθ. We estimate the unknownθ and adapt the control action to the estimated value. Bounds are given for the expected regret loss under this adaptive procedure, i.e. for the loss caused by using the adaptive procedure instead of an (unknown) optimal one. We assume that the dependence of the model onθ is Lipschitz continuous. The bounds depend on the expected estimation error. When confidence intervals forθ with fixed width are available, we obtain bounds for the expected regret loss that hold uniformly inθ.     

Double-markov risk model

Given a new Double-Markov risk model DM=(μ,Q,ν,H;Y,Z) and Double-Markov risk process U={U(t),t≥ 0}. The ruin or survival problem is addressed. Equations which the survival probability satisfied and the formulas of calculating survival probability are obtained. Recursion formulas of calculating the survival probability and analytic expression of recursion items are obtained. The conclusions are expressed by Q matrix for a Markov chain and transition probabilities for another Markov Chain.     

Shy couplings

A pair (X, Y) of Markov processes on a metric space is called a Markov coupling if X and Y have the same transition probabilities and (X, Y) is a Markov process. We say that a coupling is “shy” if inf _{t ≥ 0} dist(X _t , Y _t ) >  0 with positive probability. We investigate whether shy couplings exist for several classes of Markov processes.     

Asymptotic coupling and a general form of Harris�� theorem with applications to stochastic delay equations

There are many Markov chains on infinite dimensional spaces whose one-step transition kernels are mutually singular when starting from different initial conditions. We give results which prove unique ergodicity under minimal assumptions on one hand and the existence of a spectral gap under conditions reminiscent of Harris?? theorem. The first uses the existence of couplings which draw the solutions together as time goes to infinity. Such ??asymptotic couplings?? were central to (Mattingly and Sinai in Comm Math Phys 219(3):523?C565, 2001; Mattingly in Comm Math Phys 230(3):461?C462, 2002; Hairer in Prob Theory Relat Field 124:345?C380, 2002; Bakhtin and Mattingly in Commun Contemp Math 7:553?C582, 2005) on which this work builds. As in Bakhtin and Mattingly (2005) the emphasis here is on stochastic differential delay equations. Harris?? celebrated theorem states that if a Markov chain admits a Lyapunov function whose level sets are ??small?? (in the sense that transition probabilities are uniformly bounded from below), then it admits a unique invariant measure and transition probabilities converge towards it at exponential speed. This convergence takes place in a total variation norm, weighted by the Lyapunov function. A second aim of this article is to replace the notion of a ??small set?? by the much weaker notion of a ??d-small set,?? which takes the topology of the underlying space into account via a distance-like function d. With this notion at hand, we prove an analogue to Harris?? theorem, where the convergence takes place in a Wasserstein-like distance weighted again by the Lyapunov function. This abstract result is then applied to the framework of stochastic delay equations. In this framework, the usual theory of Harris chains does not apply, since there are natural examples for which there exist no small sets (except for sets consisting of only one point). This gives a solution to the long-standing open problem of finding natural conditions under which a stochastic delay equation admits at most one invariant measure and transition probabilities converge to it.     

Perturbed Markov Chains with Damping Component

The paper is devoted to studies of regularly and singularly perturbed Markov chains with damping component. In such models, a matrix of transition probabilities is regularised by adding a special damping matrix multiplied by a small damping (perturbation) parameter ε. We perform a detailed perturbation analysis for such Markov chains, particularly, give effective upper bounds for the rate of approximation for stationary distributions of unperturbed Markov chains by stationary distributions of perturbed Markov chains with regularised matrices of transition probabilities, asymptotic expansions for approximating stationary distributions with respect to damping parameter, explicit coupling type upper bounds for the rate of convergence in ergodic theorems for n-step transition probabilities, as well as ergodic theorems in triangular array mode.

     

Random state transitions of knots: a first step towards modeling unknotting by type II topoisomerases

Type II topoisomerases are enzymes that change the topology of DNA by performing strand-passage. In particular, they unknot knotted DNA very efficiently. Motivated by this experimental observation, we investigate transition probabilities between knots. We use the BFACF algorithm to generate ensembles of polygons in Z³ of fixed knot type. We introduce a novel strand-passage algorithm which generates a Markov chain in knot space. The entries of the corresponding transition probability matrix determine state-transitions in knot space and can track the evolution of different knots after repeated strand-passage events. We outline future applications of this work to DNA unknotting.     

Exact probabilities of correct classifications for uncorrelated repeated measurements from elliptically contoured distributions

Euclidean distance-based classification rules are derived within a certain nonclassical linear model approach and applied to elliptically contoured samples having a density generating function g. Then a geometric measure theoretical method to evaluate exact probabilities of correct classification for multivariate uncorrelated feature vectors is developed. When doing this one has to measure suitably defined sets with certain standardized measures. The geometric key point is that the intersection percentage functions of the areas under investigation coincide with those of certain parabolic cylinder type sets. The intersection percentage functions of the latter sets can be described as threefold integrals. It turns out that these intersection percentage functions yield simultaneously geometric representation formulae for the doubly noncentral g-generalized F-distributions. Hence, we get beyond new formulae for evaluating probabilities of correct classification new geometric representation formulae for the doubly noncentral g-generalized F-distributions. A numerical study concerning several aspects of evaluating both probabilities of correct classification and values of the doubly noncentral g-generalized F-distributions demonstrates the advantageous computational properties of the present new approach. This impression will be supported by comparison with the literature.It is shown that probabilities of correct classification depend on the parameters of the underlying sample distribution through a certain well-defined set of secondary parameters. If the underlying parameters are unknown, we propose to estimate probabilities of correct classification.     

Lower deviation probabilities for supercritical Galton-Watson processes

There is a well-known sequence of constants cn describing the growth of supercritical Galton-Watson processes Zn. By lower deviation probabilities we refer to P(Zn=kn) with kn=o(cn) as n increases. We give a detailed picture of the asymptotic behavior of such lower deviation probabilities. This complements and corrects results known from the literature concerning special cases. Knowledge on lower deviation probabilities is needed to describe large deviations of the ratio Zn+1/Zn. The latter are important in statistical inference to estimate the offspring mean. For our proofs, we adapt the well-known Cramér method for proving large deviations of sums of independent variables to our needs.     

Diffusion approximation for signaling stochastic networks

This paper introduces an unified approach to diffusion approximations of signaling networks. This is accomplished by the characterization of a broad class of networks that can be described by a set of quantities which suffer exchanges stochastically in time. We call this class stochastic Petri nets with probabilistic transitions, since it is described as a stochastic Petri net but allows a finite set of random outcomes for each transition. This extension permits effects on the network which are commonly interpreted as “routing” in queueing systems. The class is general enough to include, for instance, G-networks with negative customers and triggers as a particular case. With this class at hand, we derive a heavy traffic approximation, where the processes that drive the transitions are given by state-dependent Poisson-type processes and where the probabilities of the random outcomes are also state-dependent. The objective of this approach is to have a diffusion approximation which can be readily applied in several practical problems. We illustrate the use of the results with some numerical experiments.