Rayleigh processes, real trees, and root growth with re-grafting

The real trees form a class of metric spaces that extends the class of trees with edge lengths by allowing behavior such as infinite total edge length and vertices with infinite branching degree. Aldous's Brownian continuum random tree, the random tree-like object naturally associated with a standard Brownian excursion, may be thought of as a random compact real tree. The continuum random tree is a scaling limit as N→∞ of both a critical Galton-Watson tree conditioned to have total population size N as well as a uniform random rooted combinatorial tree with N vertices. The Aldous–Broder algorithm is a Markov chain on the space of rooted combinatorial trees with N vertices that has the uniform tree as its stationary distribution. We construct and study a Markov process on the space of all rooted compact real trees that has the continuum random tree as its stationary distribution and arises as the scaling limit as N→∞ of the Aldous–Broder chain. A key technical ingredient in this work is the use of a pointed Gromov–Hausdorff distance to metrize the space of rooted compact real trees. Berkeley Statistics Technical Report No. 654 (February 2004), revised October 2004. To appear in Probability Theory and Related Fields. SNE supported in part by NSF grants DMS-0071468 and DMS-0405778, and a Miller Institute for Basic Research in Science research professorship JP supported in part by NSF grants DMS-0071448 and DMS-0405779 AW supported by a DFG Forchungsstipendium     

Projections of the Aldous chain on binary trees: Intertwining and consistency

Consider the Aldous Markov chain on the space of rooted binary trees with n labeled leaves in which at each transition a uniform random leaf is deleted and reattached to a uniform random edge. Now, fix 1 ≤ k<n and project the leaf mass onto the subtree spanned by the first k leaves. This yields a binary tree with edge weights that we call a “decorated k‐tree with total mass n.” We introduce label swapping dynamics for the Aldous chain so that, when it runs in stationarity, the decorated k‐trees evolve as Markov chains themselves, and are projectively consistent over k. The construction of projectively consistent chains is a crucial step in the construction of the Aldous diffusion on continuum trees by the present authors, which is the n→∞ continuum analog of the Aldous chain and will be taken up elsewhere.     

Evolutionary trees and the Ising model on the Bethe lattice: a proof of Steel��s conjecture

A major task of evolutionary biology is the reconstruction of phylogenetic trees from molecular data. The evolutionary model is given by a Markov chain on a tree. Given samples from the leaves of the Markov chain, the goal is to reconstruct the leaf-labelled tree. It is well known that in order to reconstruct a tree on n leaves, sample sequences of length ??(log n) are needed. It was conjectured by Steel that for the CFN/Ising evolutionary model, if the mutation probability on all edges of the tree is less than ${p^{\ast} = (\sqrt{2}-1)/2^{3/2}}$ , then the tree can be recovered from sequences of length O(log n). The value p* is given by the transition point for the extremality of the free Gibbs measure for the Ising model on the binary tree. Steel??s conjecture was proven by the second author in the special case where the tree is ??balanced.?? The second author also proved that if all edges have mutation probability larger than p* then the length needed is n ^??(1). Here we show that Steel??s conjecture holds true for general trees by giving a reconstruction algorithm that recovers the tree from O(log n)-length sequences when the mutation probabilities are discretized and less than p*. Our proof and results demonstrate that extremality of the free Gibbs measure on the infinite binary tree, which has been studied before in probability, statistical physics and computer science, determines how distinguishable are Gibbs measures on finite binary trees.     

Tokunaga and Horton self-similarity for level set trees of Markov chains

The Horton and Tokunaga branching laws provide a convenient framework for studying self-similarity in random trees. The Horton self-similarity is a weaker property that addresses the principal branching in a tree; it is a counterpart of the power-law size distribution for elements of a branching system. The stronger Tokunaga self-similarity addresses so-called side branching. The Horton and Tokunaga self-similarity have been empirically established in numerous observed and modeled systems, and proven for two paradigmatic models: the critical Galton–Watson branching process with finite progeny and the finite-tree representation of a regular Brownian excursion. This study establishes the Tokunaga and Horton self-similarity for a tree representation of a finite symmetric homogeneous Markov chain. We also extend the concept of Horton and Tokunaga self-similarity to infinite trees and establish self-similarity for an infinite-tree representation of a regular Brownian motion. We conjecture that fractional Brownian motions are also Tokunaga and Horton self-similar, with self-similarity parameters depending on the Hurst exponent.     

Exponential Stability in Mean Square for a General Class of Discrete-Time Linear Stochastic Systems

Abstract

The problem of the mean square exponential stability for a class of discrete-time linear stochastic systems subject to independent random perturbations and Markovian switching is investigated. The case of the linear systems whose coefficients depend both to present state and the previous state of the Markov chain is considered. Three different definitions of the concept of exponential stability in mean square are introduced and it is shown that they are not always equivalent. One definition of the concept of mean square exponential stability is done in terms of the exponential stability of the evolution defined by a sequence of linear positive operators on an ordered Hilbert space. The other two definitions are given in terms of different types of exponential behavior of the trajectories of the considered system. In our approach the Markov chain is not prefixed. The only available information about the Markov chain is the sequence of probability transition matrices and the set of its states. In this way one obtains that if the system is affected by Markovian jumping the property of exponential stability is independent of the initial distribution of the Markov chain.

The definition expressed in terms of exponential stability of the evolution generated by a sequence of linear positive operators, allows us to characterize the mean square exponential stability based on the existence of some quadratic Lyapunov functions.

The results developed in this article may be used to derive some procedures for designing stabilizing controllers for the considered class of discrete-time linear stochastic systems in the presence of a delay in the transmission of the data.     

Generating binary trees with uniform probability

A binary tree is characterized as a sequence of graftings. This sequence is used to construct a Markov chain useful for generating trees with uniform probability. A code for the Markov chain gives a characteristic binary string for the trees. The main result is the calculation of the transition probabilities of the Markov chain. Some applications are pointed out.     

On the distribution of binary search trees under the random permutation model

We study the distribution Q on the set B_n of binary search trees over a linearly ordered set of n records under the standard random permutation model. This distribution also arises as the stationary distribution for the move-to-root (MTR) Markov chain taking values in B_n when successive requests are independent and identically distributed with each record equally likely. We identify the minimum and maximum values of the functional Q and the trees achieving those values and argue that Q is a crude measure of the “shape” of the tree. We study the distribution of Q(T) for two choices of distribution for random trees T; uniform over B_n and Q. In the latter case, we obtain a limiting normal distribution for −ln Q(T). © 1996 John Wiley & Sons, Inc.     

Arbres de Markov couplePairwise Markov trees

The Hidden Markov Chain (HMC) models are widely applied in various problems. This succes is mainly due to the fact that the hidden model distribution conditional on observations remains a Markov chain distribution, and thus different processings, like Bayesian restorations, are handleable. These models have been recetly generalized to “Pairwise” Markov chains, which admit the same processing power and a better modeling one. The aim of this Note is to show that the Hidden Markov trees, which can be seen as extensions of the HMC models, can also be generalized to “Pairwise” Markov trees, which present the same processing advantages and better modelling power. To cite this article: W. Pieczynski, C. R. Acad. Sci. Paris, Ser. I 335 (2002) 79–82.     

Hypergraphs as a mean of discovering the dependence structure of a discrete multivariate probability distribution

Most everyday reasoning and decision making is based on uncertain premises. The premises or attributes, which we must take into consideration, are random variables, therefore we often have to deal with a high dimensional multivariate random vector. A multivariate random vector can be represented graphically as a Markov network. Usually the structure of the Markov network is unknown. In this paper we construct special type of junction trees, in order to obtain good approximations of the real probability distribution. These junction trees are capable of revealing some of the conditional independences of the network. We have already introduced the concept of the t-cherry junction tree (E. Kovács and T. Szántai in Proceedings of the IFIP/IIASA//GAMM Workshop on Coping with Uncertainty, 2010), based on the t-cherry tree graph structure. This approximation uses only two and three dimensional marginal probability distributions. Now we use k-th order t-cherry trees, also called simplex multitrees to introduce the concept of the k-th order t-cherry junction tree. We prove that the k-th order t-cherry junction tree gives the best approximation among the family of k-width junction trees. Then we give a method which starting from a k-th order t-cherry junction tree constructs a (k+1)-th order t-cherry junction tree which gives at least as good approximation. In the last part we present some numerical results and some possible applications.     

Joint Distributions of Runs in a Sequence of Multi-State Trials

In this paper we introduce a Markov chain imbeddable vector of multinomial type and a Markov chain imbeddable variable of returnable type and discuss some of their properties. These concepts are extensions of the Markov chain imbeddable random variable of binomial type which was introduced and developed by Koutras and Alexandrou (1995, Ann. Inst. Statist. Math., 47, 743–766). By using the results, we obtain the distributions and the probability generating functions of numbers of occurrences of runs of a specified length based on four different ways of counting in a sequence of multi-state trials. Our results also yield the distribution of the waiting time problems.     

Bethe树和Cayley树上奇偶马尔可夫链场的强极限定理

本文介绍了N元Bethe树TB,N(N元Cayley树TC,N)上的奇偶马尔可夫链场的定义,并通过构造两个非负鞅证得了随机变量序列的强极限定理,应用此强极限定理获得了奇偶马尔可夫链场上的一个强极限定理,作为它的推论得到了状态和状态序偶出现频率的一类强极限定理及其估计,从而推广了关于N元Bethe树上马氏链场和二进树上奇偶马氏链场的部分强极限定理.     

Hypothesis Tests of Convergence in Markov Chain Monte Carlo

Abstract

Deciding when a Markov chain has reached its stationary distribution is a major problem in applications of Markov Chain Monte Carlo methods. Many methods have been proposed ranging from simple graphical methods to complicated numerical methods. Most such methods require a lot of user interaction with the chain which can be very tedious and time-consuming for a slowly mixing chain. This article describes a system to reduce the burden on the user in assessing convergence. The method uses simple nonparametric hypothesis testing techniques to examine the output of several independent chains and so determines whether there is any evidence against the hypothesis of convergence. We illustrate the proposed method on some examples from the literature.     

Importance Link Function Estimation for Markov Chain Monte Carlo Methods

Abstract

This article focuses on improving estimation for Markov chain Monte Carlo simulation. The proposed methodology is based upon the use of importance link functions. With the help of appropriate importance sampling weights, effective estimates of functionals are developed. The method is most easily applied to irreducible Markov chains, where application is typically immediate. An important conceptual point is the applicability of the method to reducible Markov chains through the use of many-to-many importance link functions. Applications discussed include estimation of marginal genotypic probabilities for pedigree data, estimation for models with and without influential observations, and importance sampling for a target distribution with thick tails.     

Asymptotics of Markov Additive Chains on a Half-Plane: A Ratio Limit Theorem

Consider a Markov additive chain (V,Z) with a negative horizontal drift on a half-plane. We provide the limiting distribution of Z when V passes a threshold for the first time, as V tends to infinity. Our contribution is to allow the Markovian part of an associated twisted Markov chain to be null recurrent or transient. The positive recurrent case was treated by Kesten [Ann. Probab. 2 (1974), 355–386]. Moreover, a ratio limit will be established for a transition kernel with unbounded jumps.     

A new perspective on implementation by voting trees

Voting trees describe an iterative procedure for selecting a single vertex from a tournament. They provide a very general abstract model of decision‐making among a group of individuals, and it has therefore been studied which voting rules have a tree that implements them, i.e., chooses according to the rule for every tournament. While partial results concerning implementable rules and necessary conditions for implementability have been obtained over the past 40 years, a complete characterization of voting rules implementable by trees has proven surprisingly hard to find. A prominent rule that cannot be implemented by trees is the Copeland rule, which singles out vertices with maximum degree. In this paper, we suggest a new angle of attack and re‐examine the implementability of the Copeland solution using paradigms and techniques that are at the core of theoretical computer science. We study the extent to which voting trees can approximate the maximum degree in a tournament, and give upper and lower bounds on the worst‐case ratio between the degree of the vertex chosen by a tree and the maximum degree, both for the deterministic model concerned with a single fixed tree, and for randomizations over arbitrary sets of trees. Our main positive result is a randomization over surjective trees of polynomial size that provides an approximation ratio of at least 1/2. The proof is based on a connection between a randomization over caterpillar trees and a rapidly mixing Markov chain. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 39, 59–82, 2011     

No cut-off phenomenon for the “Insect Markov chain”

In this work we show that the probability measure associated with the Insect Markov chain defined on the ultrametric space of the leaves of the q-ary rooted tree of depth n ≥ 2 converges to the stationary distribution without a cut-off behavior.      

Comparison of Three Web Search Algorithms

In this paper we discuss three important kinds of Markov chains used in Web search algorithms-the maximal irreducible Markov chain, the miuimal irreducible Markov chain and the middle irreducible Markov chain, We discuss the stationary distributions, the convergence rates and the Maclaurin series of the stationary distributions of the three kinds of Markov chains. Among other things, our results show that the maximal and minimal Markov chains have the same stationary distribution and that the stationary distribution of the middle Markov chain reflects the real Web structure more objectively. Our results also prove that the maximal and middle Markov chains have the same convergence rate and that the maximal Markov chain converges faster than the minimal Markov chain when the damping factor α 〉1/√2.     

No cut-off phenomenon for the “Insect Markov chain”

In this work we show that the probability measure associated with the Insect Markov chain defined on the ultrametric space of the leaves of the q-ary rooted tree of depth n ≥ 2 converges to the stationary distribution without a cut-off behavior.     

Probabilities for Queueing Systems with Embedded Markov Chains

Abstract

Transition probabilities of embedded Markov chain for single-server queues are considered when the distribution of the inter-arrival time or that of the service time is specified. A comprehensive collection of formulas is derived for the transition probabilities, covering some seventeen flexible families. The corresponding estimation procedures are also derived by the method of moments. It is expected that this work could serve as a useful reference for the modeling of queuing systems with embedded Markov chains.