Markov chains and discrete chaos

The connection between the statistics of a one-dimensional system exhibiting discrete chaos and its underlying deterministic law is formulated in terms of Markov chains. The correlation functions of piecewise linear Markovian maps are computed exactly using linear recursion formulae. An example of a non-Markovian map is given which can be approximated by Markovian maps.     

Nonstationary Markov chains and convergence of the annealing algorithm

We study the asymptotic behavior as timet + of certain nonstationary Markov chains, and prove the convergence of the annealing algorithm in Monte Carlo simulations. We find that in the limitt + , a nonstationary Markov chain may exhibit phase transitions. Nonstationary Markov chains in general, and the annealing algorithm in particular, lead to biased estimators for the expectation values of the process. We compute the leading terms in the bias and the variance of the sample-means estimator. We find that the annealing algorithm converges if the temperatureT(t) goes to zero no faster thanC/log(t/t ₀) ast+, with a computable constantC andt ₀ the initial time. The bias and the variance of the sample-means estimator in the annealing algorithm go to zero likeO(t^–1+) for some 0<1, with =0 only in very special circumstances. Our results concerning the convergence of the annealing algorithm, and the rate of convergence to zero of the bias and the variance of the sample-means estimator, provide a rigorous procedure for choosing the optimal annealing schedule. This optimal choice reflects the competition between two physical effects: (a) The adiabatic effect, whereby if the temperature is loweredtoo abruptly the system may end up not in a ground state but in a nearby metastable state, and (b) the super-cooling effect, whereby if the temperature is loweredtoo slowly the system will indeed approach the ground state(s) but may do so extremely slowly.     

Markov chains theory for scale-free networks

This paper proposes a Markov chain method to predict the growth dynamics of the individual nodes in scale-free networks, and uses this to calculate numerically the degree distribution. We first find that the degree evolution of a node in the BA model is a nonhomogeneous Markov chain. An efficient algorithm to calculate the degree distribution is developed by the theory of Markov chains. The numerical results for the BA model are consistent with those of the analytical approach. A directed network with the logarithmic growth is introduced. The algorithm is applied to calculate the degree distribution for the model. The numerical results show that the system self-organizes into a scale-free network.     

Algebraic decay in self-similar Markov chains

A continuous-time Markov chain is used to model motion in the neighborhood of a critical invariant circle for a Hamiltonian map. States in the infinite chain represent successive rational approximants to the frequency of the invariant circle. For the case of a noble frequency, the chain is self-similar and the nonlinear integral equation for the first passage time distribution is solved exactly. The asymptotic distribution is a power law times a function periodic in the logarithm of the time. For parameters relevant to the critical noble circle, the decay proceeds ast ^–4.05.     

Dynamical entropy of generalized quantum Markov chains

We compute the dynamical entropy in the sense of Connes, Narnhofer, and Thirring of shift automorphism of generalized quantum Markov chains as defined by Accardi and Frigerio. For any generalized quantum Markov chain defined via a finite set of conditional density amplitudes, we show that the dynamical entropy is equal to the mean entropy.Research supported in part by the Basic Science Research Program, Korean Ministry of Education, 1993–1994.     

Binary N-step Markov chains and long-range correlated systems

A theory of systems with long-range correlations based on the consideration of binary N-step Markov chains is developed. In our model, the conditional probability that the ith symbol in the chain equals zero (or unity) is a linear function of the number of unities among the preceding N symbols. The correlation and distribution functions as well as the variance of number of symbols in the words of arbitrary length L are obtained analytically and numerically. If the persistent correlations are not extremely strong, the variance is shown to be nonlinearly dependent on L. A self-similarity of the studied stochastic process is revealed. The applicability of the developed theory to the coarse-grained written and DNA texts is discussed.     

Reduced Markov chains at stochastic spin models

From Glauber's stochastic spin model in discrete time, reduced Markov-chain models are constructed. The transition matrices of the reduced models utilize equilibrium correlation functions of the full N-spin system; however, the reduced models involve the time-dependent behavior of only a cluster of spins. The reduced models have as an invariant vector the exact marginal equilibrium probability for the spins in the cluster. In that sense, the reduced models have the same equilibrium as the N-spin Glauber model, but will, in general, display a different time dependence. One of the reduced models is solved exactly here for a one-dimensional lattice, a square lattice, and a simple-cubic lattice.     

Renormalization group for Markov chains and application to metastability

In this paper we introduce a new renormalization group method for the study of the long-time behavior of Markov chains with finite state space and with transition probabilities exponentially small in an external parameter. A general approach of metastability problems emerges from this analysis and is discussed in detail in the case of a two-dimensional Ising system at low temperature,     

On multiple phase transitions for branching Markov chains

We consider branching Markov chains on a countable set. We give a necessary and sufficient condition in terms of the transition kernel of the underlying Markov chain to have two phase transitions. We compute the critical values. We apply this result to prove that asymmetric branching random walks onZ have two phase transitions.     

Two-layer model for the formation of states of the hidden Markov chains

Procedures for the formation of states of the hidden Markov models are described. Formant amplitudes and frequencies are used as state features. The training strategy is presented that allows one to calculate the parameters of conditional probabilities of the generation of a given formant set by a given hidden state with the help of the maximum likelihood method.     

Memory functions of the additive Markov chains: applications to complex dynamic systems

A new approach to describing correlation properties of complex dynamic systems with long-range memory based on a concept of additive Markov chains (Phys. Rev. E 68 (2003) 061107) is developed. An equation connecting the memory and correlation function of the system under study is presented. This equation allows reconstructing a memory function using a correlation function of the system. Effectiveness and robustness of the proposed method is demonstrated by simple model examples. Memory functions of concrete coarse-grained literary texts are found and their universal power-law behavior at long distances is revealed.     

Group theory,Markov chains,and excluded volume effect in polymers

A restricted walk of orderr on a lattice is defined as a random walk in which polygons withr vertices or less are excluded. A study of restricted walks for increasingr provides an understanding of how the transition in properties is effected from random to self-avoiding walks which is important in our understanding of the excluded volume effect in polymers and in the study of many other problems. Here the properties of restricted walks are studied by the transition matrix method based on the theory of Markov chains. A group theoretical method is used to reduce the transition matrix governing the walk in a systematic manner and to classify the eigenvalues of the transition matrix according to the various representations of the appropriate group. It is shown that only those eigenvalues corresponding to two particular representations of the group contribute to the correlations among the steps of the walk. The distributions of eigenvalues for walks of various ordersr on the two-dimensional triangular lattice and the three-dimensional face-centered cubic lattice are presented, and they are shown to have some remarkable features.     

Guidelines for choosing the transition matrix in Monte Carlo methods using Markov chains

The sampling method proposed by Metropolis et al. (J. Chem. Phys. 21 (1953), 1087) requires the simulation of a Markov chain with a specified π as its stationary distribution. Hastings (Biometrika 57 (1970). 97) outlined a general procedure for constructing and simulating such a Markov chain. The matrix P = {p_ij} of transition probabilities is constructed using a defined symmetric function s and an arbitrary transition matrix Q. With respect to asymptotic variance reduction, Peskun (Biometrika 60 (1973), 607) determined, for a given Q, the optimum choice for s_ij. Here, guidelines are given for choosing Q so that the resulting Markov chain sampling method is as precise as is practically possible. Examples illustrating the use of the guidelines, including potential applications to problems in statistical mechanics and to the problem of estimating the probability of an simple event by “hit-ormiss” Monte Carlo in conjunction with Markov chain sampling, are discussed.     

Coevolution of game and network structure with adjustable linking

Most papers about the evolutionary game on graph assume the statistic network structure. However, in the real world, social interaction could change the relationship among people. And the change of social structure will also affect people’s strategies. We build a coevolution model of prisoner’s dilemma game and network structure to study the dynamic interaction in the real world. Differing from other coevolution models, players rewire their network connections according to the density of cooperation and other players’ payoffs. We use a parameter α to control the effect of payoff in the process of rewiring. Based on the asynchronous update rule and Monte Carlo simulation, we find that, when players prefer to rewire their links to those who are richer, the temptation can increase the cooperation density.     

Electronic structure of linear chains of fullerenes

The band structure of linear chains of fullerene molecules is calculated as a function of the intermolecular π-electron overlap integral T, which increases under increasing external pressure. Chains consisting of neutral (C₆₀) and charged (C ₆₀ ⁻ ) molecules are studied. It is shown that there is a sharp transition from a metal (or narrow-gap semiconductor) to an insulator (with band gap ∼1 eV)with increasing T. The proposed model makes it possible to describe the formation of solid-carbon struc-tures, containing chains of covalently bound fullerene molecules, with different pressure-dependent semiconductor properties. Pis’ma Zh. éksp. Teor. Fiz. 65, No. 8, 647–650 (25 April 1997)     

Statistical mechanics of braided Markov chains: I. Analytic methods and numerical simulations

We investigate numerically and analytically the statistics of Markov chains on so-called braid (B _n ) and locally free (ℒℱ _n ) groups. Namely, we compute the mean length 〈μ〉 and the variance 〈μ²〉−〈μ〉² of the shortest word which remains after applying of all group relations to the randomly generatedN-letter word (Markov chain). We express the conjecture (numerically justified) that the mean value 〈μ〉 for the random walk on the groupB _n (n≫1) coincides with high accuracy with the same value for the random walk on the “locally free group weth errors” if the number of errors is of order of 20%.     

Genetic code: Lucky chance or fundamental law of nature?

The amount of publications devoted to the rise and structure of the genetic code is ever-increasing, which include semantic and structural analyses of the code as well as the problem of the origin of the code among others. The genetic code consisting of its triplet structure and canonical sets of nucleotides and amino acids was previously suggested to be a frozen accident or the result of accidental selection in the process of the evolution of a prebiotic system. These ideas are reviewed in this paper. It becomes clear that the information code is intrinsically related to the physical laws of the universe, and thus life may be an inevitable outcome of our universe. The lack of success in explaining the origin of the code and life itself in the last several decades suggest that we miss something very fundamental about life, possibly something fundamental about matter and the universe itself. Certainly, the advent of the genetic code was no “play of chance”.     

Promotion of cooperation induced by the interplay between structure and game dynamics

We consider the coupled dynamics of the adaption of network structure and the evolution of strategies played by individuals occupying the network vertices. We propose a computational model in which each agent plays a n-round Prisoner's Dilemma game with its immediate neighbors, after that, based upon self-interest, partial individuals may punish their defective neighbors by dismissing the social tie to the one who defects the most times, meanwhile seek for a new partner at random from the neighbors of the punished agent. It is found that the promotion of cooperation is attributed to the entangled evolution of individual strategy and network structure. Moreover, we show that the emerging social networks exhibit high heterogeneity and disassortative mixing pattern. For a given average connectivity of the population and the number of rounds, there is a critical value for the fraction of individuals adapting their social interactions, above which cooperators wipe out defectors. Besides, the effects of the average degree, the number of rounds, and the intensity of selection are investigated by extensive numerical simulations. Our results to some extent reflect the underlying mechanism promoting cooperation.     

On the phase structure of spin-1 planar magnetic chains

The phase structure of a class of quantum spin-1 chains with axial symmetry is analyzed in the light of a pseudospin approach developed recently for the study of planar ferromagnets. The prominent feature of the resulting picture is that a transition to a Goldstone-like phase occurs at some critical coupling, in spite of the one-dimensional nature of the system which would prevent spontaneous breaking of the axial symmetry in the ordinary sense.