Perturbation of Transition Functions and a Feynman-Kac Formula for the Incorporation of Mortality

Markov transition kernels are perturbed by output kernels with a special emphasis on building mortality into structured population models. A Feynman-Kac formula is derived which illustrates the interplay of mortality with a Markov process associated with the unperturbed kernel. partially supported by NSF grants DMS-0314529 and SES-0345945 partially supported by NSF grants DMS-9706787 and DMS-0314529     

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.     

Anosov maps with rectangular holes. Nonergodic cases

We study Anosov diffeomorphisms on manifolds in which some holes are cut. The points that are mapped into our holes will disappear and never return. We study the case where the holes are rectangles of a Markov partition. Such maps with holes generalize Smale's horseshoes and certain open billiards. The set of nonwandering points of our map is a Cantor-like set we call arepeller. In our previous paper, we assumed that the map restricted to the remaining rectangles of the Markov partition is topologically mixing. Under this assumption we constructed invariant and conditionally invariant measures on the sets of nonwandering points. Here we relax the mixing assumption and extend our results to nonmixing and nonergodic cases.To the memory of Ricardo MañéPartially supported by NSF grant DMS-9401417.Partially supported by CONICYT and CSIC, Univ. de la Republica (Uruguay).     

Ergodic properties of Anosov maps with rectangular holes

We study Anosov diffeomorphisms on manifolds in which some holes are cut. The points that are mapped into those holes disappear and never return. The holes studied here are rectangles of a Markov partition. Such maps generalize Smale's horseshoes and certain open billiards. The set of nonwandering points of a map of this kind is a Cantor-like set calledrepeller. We construct invariant and conditionally invariant measures on the sets of nonwandering points. Then we establish ergodic, statistical, and fractal properties of those measures.To the memory of Ricardo MañéPartially supported by NSF grant DMS-9401417.Partially supported by CONICYT and SCIC, Univ. de la Republica (Uruguay).     

Isoperimetric Invariants For Product Markov Chains and Graph Products

Bounds on some isoperimetric constants of the Cartesian product of Markov chains are obtained in terms of related isoperimetric quantities of the individual chains.* Research supported in part by NSF Grants. Research supported by NSF Grant No. CCR-9503952 and DMS-9800351.     

The lower and upper bound problems for cubical polytopes

We construct a family of cubical polytypes which shows that the upper bound on the number of facets of a cubical polytope (given a fixed number of vertices) is higher than previously suspected. We also formulate a lower bound conjecture for cubical polytopes.This paper was researched and written while the author was a graduate student at MIT. The author was partially supported by an NSF Graduate Fellowship.     

On the complexity of approximating the maximal inscribed ellipsoid for a polytope

We give a new polynomial bound on the complexity of approximating the maximal inscribed ellipsoid for a polytope.Research supported by NSF Grant DMS-8706133.Research supported by NSF Grant DMS-8904406.     

The FENE dumbbell model near equilibrium

We study the global existence of smooth solutions near the equilibrium to a coupled microscopic-macroscopic FENE dumbbell model which arises from the kinetic theory of diluted solutions of polymeric liquids with noninteracting polymer chains.     

A theory of recursive dimension for ordered sets

The classical theorem of R. P. Dilworth asserts that a partially ordered set of width n can be partitioned into n chains. Dilworth's theorem plays a central role in the dimension theory of partially ordered sets since chain partitions can be used to provide embeddings of partially ordered sets in the Cartesian product of chains. In particular, the dimension of a partially-ordered set never exceeds its width. In this paper, we consider analogous problems in the setting of recursive combinatorics where it is required that the partially ordered set and any associated partition or embedding be described by recursive functions. We establish several theorems providing upper bounds on the recursive dimension of a partially ordered set in terms of its width. The proofs are highly combinatorial in nature and involve a detailed analysis of a 2-person game in which one person builds a partially ordered set one point at a time and the other builds the partition or embedding.This paper was prepared while the authors were supported, in part, by NSF grant ISP-80-11451. In addition, the second author received support under NSF grant MCS-80-01778 and the third author received support under NSF grant MCS-82-02172.     

On heat kernel estimates and parabolic Harnack inequality for jump processes on metric measure spaces

In this paper, we discuss necessary and sufficient conditions on jumping kernels for a class of jump-type Markov processes on metric measure spaces to have scale-invariant finite range parabolic Harnack inequality.     

Markov chains,Riesz transforms and Lipschitz maps

it is shown that a version of Maurey's extension theorem holds for Lipschitz maps between metric spaces satisfying certain geometric conditions, analogous to type and cotype. As a consequence, a classical Theorem of Kirszbraun can be generalised to include maps intoL _p , 1<p<2. These conditions describe the wandering of symmetric Markov processes in the spaces in question. Estimates are obtained for the root-mean-square wandering of such processes in theL _p spaces. The duality theory for these geometric conditions (in normed spaces) is shown to be closely related to the behavior of the Riesz transforms associated to Markov chains. Several natural open problems are collected in the final chapter.Supported in part by NSF DMS-8807243.     

Markov Incremental Constructions

A classic result asserts that many geometric structures can be constructed optimally by successively inserting their constituent parts in random order. These randomized incremental constructions (RICs) still work with imperfect randomness: the dynamic operations need only be “locally” random. Much attention has been given recently to inputs generated by Markov sources. These are particularly interesting to study in the framework of RICs, because Markov chains provide highly nonlocal randomness, which incapacitates virtually all known RIC technology. We generalize Mulmuley’s theory of Θ-series and prove that Markov incremental constructions with bounded spectral gap are optimal within polylog factors for trapezoidal maps, segment intersections, and convex hulls in any fixed dimension. The main contribution of this work is threefold: (i) extending the theory of abstract configuration spaces to the Markov setting; (ii) proving Clarkson–Shor-type bounds for this new model; (iii) applying the results to classical geometric problems. We hope that this work will pioneer a new approach to randomized analysis in computational geometry. This work was supported in part by NSF grants CCR-0306283, CCF-0634958.     

Application of Jensen's inequality to adaptive suboptimal design

In this paper, it is shown that, if the expected cost-to-go functions generated by a suboptimal design for a partially observed, discrete-time, Markov decision problem with a specific state measurement quality are concave, then the suboptimal design has a desirable adaptivity characteristic relative to that state measurement quality. Optimal strategies are shown to possess this adaptivity characteristic, as does a suboptimal design presented in an example.This research was supported by NSF Grant No. ENG-76-15774 and NSF Grant No. ENG-78-06733.     

Rigidity of measures—The high entropy case and non-commuting foliations

We consider invariant measures for partially hyperbolic, semisimple, higher rank actions on homogeneous spaces defined by products of real andp-adic Lie groups. In this paper we generalize our earlier work to establish measure rigidity in the high entropy case in that setting. We avoid any additional ergodicity-type assumptions but rely on, and extend the theory of conditional measures. To Hillel Furstenberg with friendship and admiration Manfred Einsiedler is partially supported by the NSF Grant DMS 0400587. Anatole Katok is partially supported by the NSF Grant DMS 0071339.     

Quasiregular maps on Carnot groups

In this paper we initiate the study of quasiregular maps in a sub-Riemannian geometry of general Carnot groups. We suggest an analytic definition for quasiregularity and then show that nonconstant quasiregular maps are open and discrete maps on Carnot groups which are two-step nilpotent and of Heisenberg type; we further establish, under the same assumption, that the branch set of a nonconstant quasiregular map has Haar measure zero and, consequently, that quasiregular maps are almost everywhere differentiable in the sense of Pansu. Our method is that of nonlinear potential theory. We have aimed at an exposition accessible to readers of varied background. Dedicated to Seppo Rickman on his sixtieth birthday J.H. was partially supported by NSF, the Academy of Finland, and the A. P. Sloan Foundation. I.H. was partially supported by the EU HCM contract no. CHRX-CT92-0071.     

On groups of hyperbolic length

We investigate the recently introduced notion of rotation numbers for periodic orbits of interval maps. We identify twist orbits, that is those orbits that are the simplest ones with given rotation number. We estimate from below the topological entropy of a map having an orbit with given rotation number. Our estimates are sharp: there are unimodal maps where the equality holds. We also discuss what happens for maps with larger modality. In the Appendix we present a new approach to the problem of monotonicity of entropy in one-parameter families of unimodal maps. This work was partially done during the first author’s visit to IUPUI (funded by a Faculty Research Grant from UAB Graduate School) and his visit to MSRI (the research at MSRI funded in part by NSF grant DMS-9022140) whose support the first author acknowledges with gratitude. The second author was partially supported by NSF grant DMS-9305899, and his gratitude is as great as that of the first author.     

Effective bandwidths for Markov regenerative sources

In this paper we consider the multiplexing of independent stochastic fluid sources onto a single buffer. The rate at which a source generates fluid is assumed to be modulated by a Markov regenerative process. We develop the exponential decay rates for the tails of the steady-state distribution of the buffer content. We also develop expressions for the effective bandwidths for such sources. All the results are in terms of the Perron-Frobenius eigenvalue of a matrix defined for the Markov regenerative source. As a special case we derive similar results for regenerative sources. We apply the results to video sources.This research was partially supported by NSF Grant No. NCR-9406823.     

A characterization of the complex affine line

Summary A characterization of affine nonsingular complex algebraic curves that are biregularly isomorphic to ℂ is given; it is stated in terms of approximation of holomorphic maps by regular maps. The author was partially supported by an NSF grant and NATO Collaborative Research Grants Programme, CRG 930238. This article was processed by the author using theLatext style file from Springer-Verlag.     

Equilibrium states with incomplete supports and periodic trajectories

The relationship between analytic properties of the Artin-Mazur-Ruelle zeta function and the structure of the state of equilibrium states for a topological Markov chain is studied for a class of functions constant on a system of cylinder sets. The convergence of discrete invariant measures to equilibrium states is studied. Special attention is paid to the case in which the uniqueness condition is violated. Dynamic Ruelle-Smale zeta functions are considered, as well as the distribution laws for the number of periodic trajectories of special flows corresponding to topological Markov chains and to positive functions of this class.Translated fromMatematicheskie Zametki, Vol. 59, No. 2, pp. 230–253, February, 1996.The author is grateful to B. M. Gurevich for discussing the paper.This work was partially supported by the International Science Foundation under grant No. M8X000.     

Lang maps and Harris’s conjecture

We show that any variety in characteristic 0 possesses a universal dominant rational map, which we callthe Lang map, to a variety of general type. We discuss a conjecture of J. Harris regarding the relation between rational points and Lang maps. Partially supported by NSF grant DMS-9503276.