Chains of Infinite Order,Chains with Memory of Variable Length,and Maps of the Interval

We show how to construct a topological Markov map of the interval whose invariant probability measure is the stationary law of a given stochastic chain of infinite order. In particular we characterize the maps corresponding to stochastic chains with memory of variable length. The problem treated here is the converse of the classical construction of the Gibbs formalism for Markov expanding maps of the interval.     

Metastates in Mean-Field Models with Random External Fields Generated by Markov Chains

We extend the construction by Külske and Iacobelli of metastates in finite-state mean-field models in independent disorder to situations where the local disorder terms are a sample of an external ergodic Markov chain in equilibrium. We show that for non-degenerate Markov chains, the structure of the theorems is analogous to the case of i.i.d. variables when the limiting weights in the metastate are expressed with the aid of a CLT for the occupation time measure of the chain.     

Subshifts on Infinite Alphabets and Their Entropy

We analyze symbolic dynamics to infinite alphabets by endowing the alphabet with the cofinite topology. The topological entropy is shown to be equal to the supremum of the growth rate of the complexity function with respect to finite subalphabets. For the case of topological Markov chains induced by countably infinite graphs, our approach yields the same entropy as the approach of Gurevich We give formulae for the entropy of countable topological Markov chains in terms of the spectral radius in l2.     

Polymers and random graphs

We establish a precise connection between gelation of polymers in Lushnikov's model and the emergence of the giant component in random graph theory. This is achieved by defining a modified version of the Erdös-Rényi process; when contracting to a polymer state space, this process becomes a discrete-time Markov chain embedded in Lushnikov's process. The asymptotic distribution of the number of transitions in Lushnikov's model is studied. A criterion for a general Markov chain to retain the Markov property under the grouping of states is derived. We obtain a noncombinatorial proof of a theorem of Erdös-Rényi type.     

Bayesian inference with optimal maps

We present a new approach to Bayesian inference that entirely avoids Markov chain simulation, by constructing a map that pushes forward the prior measure to the posterior measure. Existence and uniqueness of a suitable measure-preserving map is established by formulating the problem in the context of optimal transport theory. We discuss various means of explicitly parameterizing the map and computing it efficiently through solution of an optimization problem, exploiting gradient information from the forward model when possible. The resulting algorithm overcomes many of the computational bottlenecks associated with Markov chain Monte Carlo. Advantages of a map-based representation of the posterior include analytical expressions for posterior moments and the ability to generate arbitrary numbers of independent posterior samples without additional likelihood evaluations or forward solves. The optimization approach also provides clear convergence criteria for posterior approximation and facilitates model selection through automatic evaluation of the marginal likelihood. We demonstrate the accuracy and efficiency of the approach on nonlinear inverse problems of varying dimension, involving the inference of parameters appearing in ordinary and partial differential equations.     

Induced maps,Markov extensions and invariant measures in one-dimensional dynamics

A way to study ergodic and measure theoretic aspects of interval maps is by means of the Markov extension. This tool, which ties interval maps to the theory of Markov chains, was introduced by Hofbauer and Keller. More generally known are induced maps, i.e. maps that, restricted to an element of an interval partition, coincide with an iterate of the original map.We will discuss the relation between the Markov extension and induced maps. The main idea is that an induced map of an interval map often appears as a first return map in the Markov extension. For S-unimodal maps, we derive a necessary condition for the existence of invariant probability measures which are absolutely continuous with respect to Lebesgue measure. Two corollaries are given.     

Fractal structure of hyperbolic Lipschitzian dynamical systems

In the paper, dynamical systems admitting no smooth structure are studied. A theorem on the semiconjugacy of a Lipschitzian dynamical system to the corresponding topological Markov chain is proved. A new approach to evaluating bounds for the Hausdorff and the Kolmogorov dimensions of the set of nonwandering points from a Markov partition is suggested.     

Multilayer Markov Chains with Applications to Polymers in Shear Flow

We present an analysis of multilayer Markov chains and apply the results to a model of a tethered polymer chain in shear flow. We find that the stationary probability measure in the direction of the flow is nonmonotonic, and has several maxima and minima for sufficiently high shear rates. This is in agreement with the experimental observation of cyclic dynamics for such polymer systems. Estimates for the stationary variance and expectation value were obtained and showed to be in accordance with our numerical results.     

Stochastic Processes and Mean Field Systems Defined by Nonlinear Markov Chains: An Illustration for a Model of Evolutionary Population Dynamics

In physics, there is a growing interest in studying stochastic processes described by evolution equations such as nonlinear master equations and nonlinear Fokker–Planck equations that define the so-called nonlinear Markov processes and are nonlinear with respect to probability densities. In this context, however, relatively little is known about nonlinear Markov processes defined by nonlinear Markov chains. In the present work, we demonstrate explicitly how the nonlinear Markov chain approach can be carried out by addressing a model for evolutionary population dynamics. In line with the nonlinear Markov chain approach, we derive a measure that tells us how attractive it is for a biological entity to evolve towards a particular biological type. Likewise, a measure for the noise level of the evolutionary process is obtained. Both measures are found to be implicitly time dependent. Finally, a simulation scheme for the many-body system corresponding to the Markov chain model is discussed.     

Entropy Preservation Under Markov Coding

Using the notion of topological entropy for non-compact sets we prove that for a C ¹⁺ -map with a finite Markov partition the corresponding coding map preserves topological entropy of subsets. We also provide an example of a piecewise linear conformal repeller with a Markov coding decreasing topological entropy. These results are generalized to the notions of u-dimensions.     

Constrained Markovian Dynamics of Random Graphs

We introduce a statistical mechanics formalism for the study of constrained graph evolution as a Markovian stochastic process, in analogy with that available for spin systems, deriving its basic properties and highlighting the role of the ‘mobility’ (the number of allowed moves for any given graph). As an application of the general theory we analyze the properties of degree-preserving Markov chains based on elementary edge switchings. We give an exact yet simple formula for the mobility in terms of the graph’s adjacency matrix and its spectrum. This formula allows us to define acceptance probabilities for edge switchings, such that the Markov chains become controlled Glauber-type detailed balance processes, designed to evolve to any required invariant measure (representing the asymptotic frequencies with which the allowed graphs are visited during the process). As a corollary we also derive a condition in terms of simple degree statistics, sufficient to guarantee that, in the limit where the number of nodes diverges, even for state-independent acceptance probabilities of proposed moves the invariant measure of the process will be uniform. We test our theory on synthetic graphs and on realistic larger graphs as studied in cellular biology, showing explicitly that, for instances where the simple edge swap dynamics fails to converge to the uniform measure, a suitably modified Markov chain instead generates the correct phase space sampling.     

Random composition of two rational maps: Singularity of the invariant measure

We study the invariant measure of a Markov chain obtained by randomly composing two rational maps related to the Anderson model with a Bernoulli potential. For a certain range of the parameters we show that the invariant measure is singular continuous. In certain cases the support turns out to be a Cantor set with a multifractal structure.     

Space-Time Invariant Measures, Entropy, and Dimension for Stochastic Ginzburg–Landau Equations

We consider a randomly forced Ginzburg–Landau equation on an unbounded domain. The forcing is smooth and homogeneous in space and white noise in time. We prove existence and smoothness of solutions, existence of an invariant measure for the corresponding Markov process and we define the spatial densities of topological entropy, of measure-theoretic entropy, and of upper box-counting dimension. We prove inequalities relating these different quantities. The proof of existence of an invariant measure uses the compact embedding of some space of uniformly smooth functions into the space of locally square-integrable functions and a priori bounds on the semi-flow in these spaces. The bounds on the entropy follow from spatially localised estimates on the rate of divergence of nearby orbits and on the smoothing effect of the evolution. Received: 21 June 2000 / Accepted: 28 September 2001     

Suspension Flows Over Countable Markov Shifts

We introduce the notion of topological pressure for suspension flows over countable Markov shifts, and we develop the associated thermodynamic formalism. In particular, we establish a variational principle for the topological pressure, and an approximation property in terms of the pressure on compact invariant sets. As an application we present a multifractal analysis for the entropy spectrum of Birkhoff averages for suspension flows over countable Markov shifts. The domain of the spectrum may be unbounded and the spectrum may not be analytic. We provide explicit examples where this happens. We also discuss the existence of full measures on the level sets of the multifractal decomposition.     

An interacting geometry model and induced gravity

We propose the theory of quantum gravity with interactions introduced by topological principle. The fundamental property of such a theory is that its energy-momentum tensor is a BRST anticommutator. Physical states are elements of the BRST cohomology group. The model with only topological excitations, introduced recently by Witten, is discussed from the point of view of the induced gravity program. We find that the mass scale is induced dynamically by gravitational instantons. The low-energy effective theory has gravitons, which occur as the collective excitations of geometry, when the metric becomes dynamical. Applications of cobordism theory to quantum gravity are discussed.This essay received the second award from the Gravity Research Foundation for the year 1988.—Ed.     

Quantum Probing Topological Phase Transitions by Non‐Markovianity

Understanding the physical significance and probing the global invariants characterizing quantum topological phases in extended systems is a main challenge in modern physics with major impact in different areas of science. Here, a quantum‐information‐inspired probing method is proposed where topological phase transitions are revealed by a non‐Markovianity quantifier. The idea is illustrated by considering the decoherence dynamics of an external read‐out qubit that probes a Su–Schrieffer–Heeger (SSH) chain with either pure dephasing or dissipative coupling. Qubit decoherence features and non‐Markovianity measure clearly signal the topological phase transition of the SSH chain.     

Multifractal Nonrigidity of Topological Markov Chains

Given a multifractal spectrum, we consider the problem of whether it is possible to recover the potential that originates the spectrum. The affirmative solution of this problem would correspond to a “multifractal” classification of dynamical systems, i.e., a classification solely based on the information given by multifractal spectra. For the entropy spectrum on topological Markov chains we show that it is possible to have both multifractal rigidity and multifractal “nonrigidity”, by appropriately varying the Markov chain and the potential defining the spectrum. The “nonrigidity” even occurs in some generic sense. This strongly contrasts to the usual opinion among some experts that it should be possible to recover the potential up to some equivalence relation, at least in some generic sense. Supported by the Center for Mathematical Analysis, Geometry, and Dynamical Systems, through FCT by Program POCTI/FEDER and the grant SFRH/BD/10154/2002.     

Topological and Nontopological Edge States Induced by Qubit-Assisted Coupling Potentials

In the usual Su–Schrieffer–Heeger (SSH) chain, the topology of the energy spectrum is divided into two categories in different parameter regions. Here, the topological and nontopological edge states induced by qubit-assisted coupling potentials in circuit quantum electrodynamics (QED) lattice modeled as a SSH chain are studied. It is found that, when the coupling potential added on only one end of the system raises to a certain extent, the strong coupling potential will induce a new topologically nontrivial phase accompanied by the appearance of a nontopological edge state, and the novel phase transition leads to the inversion of odd–even effect directly. Furthermore, the topological phase transitions when two unbalanced coupling potentials are injected into both ends of the circuit QED lattice are studied, and it is found that the system exhibits three distinguishing phases with multiple flips of energy bands. These phases are significantly different from the previous phase induced via unilateral coupling potential due to the existence of a pair of nontopological edge states. The scheme provides a feasible and visible method to induce different topological and nontopological edge states through controlling the qubit-assisted coupling potentials in circuit QED lattice both in experiment and theory.     

The Optimal Sink and the Best Source in a Markov Chain

It is well known that the distributions of hitting times in Markov chains are quite irregular, unless the limit as time tends to infinity is considered. We show that nevertheless for a typical finite irreducible Markov chain and for nondegenerate initial distributions the tails of the distributions of the hitting times for the states of a Markov chain can be ordered, i.e., they do not overlap after a certain finite moment of time. If one considers instead each state of a Markov chain as a source rather than a sink then again the states can generically be ordered according to their efficiency. The mechanisms underlying these two orderings are essentially different though. Our results can be used, e.g., for a choice of the initial distribution in numerical experiments with the fastest convergence to equilibrium/stationary distribution, for characterization of the elements of a dynamical network according to their ability to absorb and transmit the substance (“information”) that is circulated over the network, for determining optimal stopping moments (stopping signals/words) when dealing with sequences of symbols, etc.     

Stochasticity from deterministic dynamics: an explicit example of generation of Markovian strings

Markov chains are used to characterize a Dynamical system after it has reached the chaotic regime when certain external parameters have passed specific critical values. For a quantitative treatment of this stochastic behavior one needs an invariant measure. This measure then depends on the external parameters. We propose an emperical method to construct from first principles an invariant measure for the particular case of the triangular map.