Self-similar and Markov composition structures

The bijection between composition structures and random closed subsets of the unit interval implies that the composition structures associated with S ⋂ [0, 1] for a self-similar random set S ⊂ ℝ₊ are those that are consistent with respect to a simple truncation operation. Using the standard coding of compositions by finite strings of binary digits starting with a 1, the random composition of n is defined by the first n terms of a random binary sequence of infinite length. The locations of 1’s in the sequence are the positions visited by an increasing time-homogeneous Markov chain on the positive integers if and only if S = exp(−W) for some stationary regenerative random subset W of the real line. Complementing our study presented in previous papers, we identify self-similar Markov composition structures associated with the two-parameter family of partition structures. Bibliography: 19 titles. Published in Zapiski Nauchnykh Seminarov POMI, Vol. 326, 2005, pp. 59–84.     

Limit theorems for random transformations and processes in random environments

I derive general relativized central limit theorems and laws of iterated logarithm for random transformations both via certain mixing assumptions and via the martingale differences approach. The results are applied to Markov chains in random environments, random subshifts of finite type, and random expanding in average transformations where I show that the conditions of the general theorems are satisfied and so the corresponding (fiberwise) central limit theorems and laws of iterated logarithm hold true in these cases. I consider also a continuous time version of such limit theorems for random suspensions which are continuous time random dynamical systems.

     

Finite computable dimension does not relativize

 In many classes of structures, each computable structure has computable dimension 1 or $\omega$. Nevertheless, Goncharov showed that for each $n < \omega$, there exists a computable structure with computable dimension $n$. In this paper we show that, under one natural definition of relativized computable dimension, no computable structure has finite relativized computable dimension greater than 1. Received: 27 July 1998/ Published online: 27 March 2002     

Quasi-stationary Distributions for a Class of Discrete-time Markov Chains

This paper is concerned with the circumstances under which a discrete-time absorbing Markov chain has a quasi-stationary distribution. We showed in a previous paper that a pure birth-death process with an absorbing bottom state has a quasi-stationary distribution—actually an infinite family of quasi-stationary distributions— if and only if absorption is certain and the chain is geometrically transient. If we widen the setting by allowing absorption in one step (killing) from any state, the two conditions are still necessary, but no longer sufficient. We show that the birth–death-type of behaviour prevails as long as the number of states in which killing can occur is finite. But if there are infinitely many such states, and if the chain is geometrically transient and absorption certain, then there may be 0, 1, or infinitely many quasi-stationary distributions. Examples of each type of behaviour are presented. We also survey and supplement the theory of quasi-stationary distributions for discrete-time Markov chains in general.      

Constructing finitary isomorphisms with finite expected coding times

This paper is motivated by the question of whether the invariants β, Δ,cΔ completely characterize isomorphism of Markov chains by finitary isomorphisms that have finite expected coding times (fect). We construct a finitary isomorphism with fect under an additional condition. Whether coincidence of β, Δ,cΔ implies the required condition remains open.     

Coding Markov chains from the past

It is shown that a mixing Markov chain is a unilateral or one-sided factor of every ergodic process of equal or greater entropy. This extends the work of Sinai, who showed that the result holds for independent processes, and the work of Ornstein and Weiss, who showed that the result holds for mixing Markov chains in which all transition probabilities are positive. The proof exploits the Rothstein-Burton joinings-space formulation of Ornstein’s isomorphism theory, and uses a random coding argument. Partially supported by an NSF Graduate Fellowship, an NSF Postdoctoral Fellowship, and NSF Grant # DMS 84-03182 during the writing of this article.     

Word functions of pseudo-Markov chains

A word function is a function from the set of all words over a finite alphabet into the set of real numbers. In particular, when the blocks of a partition over the state set of a Markov chain are taken as the letters of the finite alphabet, and the function represents the probabilities that the chain will visit sequences of such blocks consecutively, then the function is a function of a Markov chain. It is known that (the rank of a function is defined in the text), a word function is of “finite rank” if and only if it is a function of a pseudo Markov chain (“pseudo” means here that the initial vector and the matrix representing the chain may have positive, negative, or zero values and are not necessarily stochastic). The aim of this note is to show that any function of a pseudo Markov chain can be represented as the difference of two functions of true Markov chains multiplied by a factor which grows exponentially with the length of the arguments (considered as words over a finite alphabet).     

Markov Chains with Positive Transitions Are Not Determined by Any p-Marginals

 We prove that if is a finite valued stationary Markov Chain with strictly positive probability transitions, then for any natural number p, there exists a continuum of finite valued non Markovian processes which have the p-marginal distributions of X and with positive entropy, whereas for an irrational rotation and essentially bounded real measurable function f with no zero Fourier coefficient on the unit circle with normalized Lebesgue measure, the process is uniquely determined by its three-dimensional distributions in the class of ergodic processes. We give also a family of Gaussian non-Markovian dynamical systems for which the symbolic dynamic associated to the time zero partition has the two-dimensional distributions of a reversible mixing Markov Chain. (Received 22 July 1999; in revised form 24 February 2000)     

Finitarily deterministic generators for zero entropy systems

Zero entropy processes are known to be deterministic—the past determines the present. We show that each is isomorphic, as a system, to a finitarily deterministic one, i.e., one in which to determine the present from the past it suffices to scan a finite (of random length) portion of the past. In fact we show more: the finitary scanning can be done even if the scanner is noisy and passes only a small fraction of the readings, provided the noise is independent of our system. The main application we present here is that any zero entropy system can be extended to a random Markov process (namely one in which the conditional distribution of the present given the past is a mixture of finite state Markov chains). This allows one to study zero entropy transformations using a procedure completely different from the usual cutting and stacking.     

Markov Chains with Positive Transitions Are Not Determined by Any p -Marginals

 We prove that if is a finite valued stationary Markov Chain with strictly positive probability transitions, then for any natural number p, there exists a continuum of finite valued non Markovian processes which have the p-marginal distributions of X and with positive entropy, whereas for an irrational rotation and essentially bounded real measurable function f with no zero Fourier coefficient on the unit circle with normalized Lebesgue measure, the process is uniquely determined by its three-dimensional distributions in the class of ergodic processes. We give also a family of Gaussian non-Markovian dynamical systems for which the symbolic dynamic associated to the time zero partition has the two-dimensional distributions of a reversible mixing Markov Chain.     

The lumpability property for a family of Markov chains on poset block structures

We construct different classes of lumpings for a family of Markov chain products which reflect the structure of a given finite poset. We essentially use combinatorial methods. We prove that, for such a product, every lumping can be obtained from the action of a suitable subgroup of the generalized wreath product of symmetric groups, acting on the underlying poset block structure, if and only if the poset defining the Markov process is totally ordered, and one takes the uniform Markov operator in each factor state space. Finally we show that, when the state space is a homogeneous space associated with a Gelfand pair, the spectral analysis of the corresponding lumped Markov chain is completely determined by the decomposition of the group action into irreducible submodules.     

Local theory of almost split sequences for comodules

We show that almost split sequences in the category of comodules over a coalgebraΓ with finite-dimensional right-hand term are direct limits of almost split sequences over finite dimensional subcoalgebras. In previous work we showed that such almost split sequences exist if the right hand term has a quasifinitely copresented linear dual. Conversely, taking limits of almost split sequences over finte-dimensional comodule categories, we then show that, for countable-dimensional coalgebras, certain exact sequences exist which satisfy a condition weaker than being almost split, which we call “finitely almost split”. Under additional assumptions, these sequences are shown to be almost split in the appropriate category.

---

Sunto Dimostriamo che le successioni che quasi spezzano nella categoria dei comoduli su una coalgebra Γ con termine di destra di dimensione finita sono limiti diretti di successioni che quasi spezzano su sottoalgebre di dimensione finita. In un lavoro precedente abbiamo dimostrato che tali successioni che quasi spezzano esistono se il termine di destra ha un duale lineare quasi-finitamente copresentato. Viceversa, prendendo il limite delle successioni che quasi spezzano su categorie di comoduli di dimensione finita, dimostriamo che, per coalgebre di dimensione numerabile, esistono alcune successioni esatte che soddisfano una condizione più debole di essere quasi spezzanti, che noi chiamiamo “finitamente quasi spezzanti”. Sotto ipotesi aggiuntive, si dimostra che queste successioni quasi spezzano nelle opportune categorie.

     

Relativized Schnorr tests with universal behavior

A Schnorr test relative to some oracle A may informally be called “universal” if it covers all Schnorr tests. Since no true universal Schnorr test exists, such an A cannot be computable. We prove that the sets with this property are exactly those with high Turing degree. Our method is closely related to the proof of Terwijn and Zambella’s characterization of the oracles which are low for Schnorr tests. We also consider the oracles which compute relativized Schnorr tests with the weaker property of covering all computable reals. The degrees of these oracles strictly include the hyperimmune degrees and are strictly included in the degrees not computably traceable.     

Representation Dimension as a Relative Homological Invariant of Stable Equivalence

Over an Artin algebra Λ many standard concepts from homological algebra can be relativized with respect to a contravariantly finite subcategory of mod-Λ, which contains the projective modules. The main aim of this article is to prove that the resulting relative homological dimensions of modules are preserved by stable equivalences between Artin algebras. As a corollary, we see that Auslander’s notion of representation dimension is invariant under stable equivalence (a result recently obtained independently by Guo). We then apply these results to the syzygy functor for self-injective algebras of representation dimension three, where we bound the number of simple modules in terms of the number of indecomposable nonprojective summands of an Auslander generator.      

Stability of a pure random delay system with two-time-scale Markovian switching

This work examines almost sure stability of a pure random delay system whose delay time is modeled by a finite state continuous-time Markov chain with two-time scales. The Markov chain contains a fast-varying part and a slowly-changing part. Using the properties of the weighted occupation measure of the Markov chain, it is shown that the overall system?s almost-sure-asymptotic stability can be obtained by using the “averaged” delay. This feature implies that even if some longer delay times may destabilize the system individually, the system may still be stable if their impact is balanced. In other words, the Markov chain becomes a stabilizing factor. Numerical results are provided to demonstrate our results.     

On the representation of finite multiple Markov chains by weighted circuits

In this paper circuit chains of superior order are defined as multiple Markov chains for which transition probabilities are expressed in terms of the weights of a finite class of circuits in a finite set, in connection with kinetic properties along the circuits. Conversely, it is proved that if we join any finite doubly infinite strictly stationary Markov chain of order r for which transitions hold cyclically with a second chain with the same transitions for the inverse time-sense, then they may be represented as circuit chains of order r.     

A structure of doubly stochastic Markov chains

Kingman and Williams [6] showed that a pattern of positive elements can occur in a transition matrix of a finite state, nonhomogeneous Markov chain if and only if it may be expressed as a finite product of reflexive and transitive patterns. In this paper we solve a similar problem for doubly stochastic chains. We prove that a pattern of positive elements can occur in a transition matrix of a doubly stochastic Markov chain if and only if it may be expressed as a finite product of reflexive, transitive, and symmetric patterns. We provide an algorithm for determining whether a given pattern may be expressed as a finite product of reflexive, transitive, and symmetric patterns. This result has implications for the embedding problem for doubly stochastic Markov chains. We also give the application of the obtained characterization to the chain majorization.     

Regenerative embedding of Markov sets

Summary.  Given a closed Markov (i.e. regenerative) set in [0,∞), we characterize the laws of the Markov sets which are regeneratively embedded into the latter. Typically, let Φ⁽¹⁾ and Φ⁽²⁾ be two Laplace exponents corresponding to two regenerative laws, and M ⁽²⁾ a Markov set with exponent Φ⁽²⁾. There exists a Markov set M ⁽¹⁾ with exponent Φ⁽¹⁾ which is regeneratively embedded into M ⁽²⁾ if and only if Φ⁽¹⁾/Φ⁽²⁾ is a completely monotone function. Several examples and applications are discussed. Received: 12 April 1996 / In revised form: 12 March 1997     

On an N-person noncooperative Markov game with a metric state space

We consider a noncooperative N-person discounted Markov game with a metric state space, and define the total expected discounted gain. Under some conditions imposed on the objects in the game system, we prove that our game system has an equilibrium point and each player has his equilibrium strategy. Moreover in the case of a nondiscounted game, the total expected gain up to a finite time can be obtained, and we define the long-run expected average gain. Thus if we impose a further assumption for the objects besides the conditions in the case of the discounted game, then it is proved that the equilibrium point exists in the nondiscounted Markov game. The technique for proving the nondiscounted case is essentially to modify the objects of the game so that they become objects of a modified Markov game with a discounted factor which has an equilibrium point in addition to the equilibrium point of the discounted game.     

Fuzzy Markov Chains and Decision-Making

Decision-making in an environment of uncertainty and imprecision for real-world problems is a complex task. In this paper it is introduced general finite state fuzzy Markov chains that have a finite convergence to a stationary (may be periodic) solution. The Cesaro average and the -potential for fuzzy Markov chains are defined, then it is shown that the relationship between them corresponds to the Blackwell formula in the classical theory of Markov decision processes. Furthermore, it is pointed out that recurrency does not necessarily imply ergodicity. However, if a fuzzy Markov chain is ergodic, then the rows of its ergodic projection equal the greatest eigen fuzzy set of the transition matrix. Then, the fuzzy Markov chain is shown to be a robust system with respect to small perturbations of the transition matrix, which is not the case for the classical probabilistic Markov chains. Fuzzy Markov decision processes are finally introduced and discussed.