A Unified Approach to the Characterization of Equivalence Classes of DAGs, Chain Graphs with no Flags and Chain Graphs

Abstract.  A Markov property associates a set of conditional independencies to a graph. Two alternative Markov properties are available for chain graphs (CGs), the Lauritzen–Wermuth–Frydenberg (LWF) and the Andersson–Madigan– Perlman (AMP) Markov properties, which are different in general but coincide for the subclass of CGs with no flags . Markov equivalence induces a partition of the class of CGs into equivalence classes and every equivalence class contains a, possibly empty, subclass of CGs with no flags itself containing a, possibly empty, subclass of directed acyclic graphs (DAGs). LWF-Markov equivalence classes of CGs can be naturally characterized by means of the so-called largest CGs , whereas a graphical characterization of equivalence classes of DAGs is provided by the essential graphs . In this paper, we show the existence of largest CGs with no flags that provide a natural characterization of equivalence classes of CGs of this kind, with respect to both the LWF- and the AMP-Markov properties. We propose a procedure for the construction of the largest CGs, the largest CGs with no flags and the essential graphs, thereby providing a unified approach to the problem. As by-products we obtain a characterization of graphs that are largest CGs with no flags and an alternative characterization of graphs which are largest CGs. Furthermore, a known characterization of the essential graphs is shown to be a special case of our more general framework. The three graphical characterizations have a common structure: they use two versions of a locally verifiable graphical rule. Moreover, in case of DAGs, an immediate comparison of three characterizing graphs is possible.     

Markov Properties for Acyclic Directed Mixed Graphs

We consider acyclic directed mixed graphs, in which directed edges ( x → y ) and bi-directed edges ( x ↔ y ) may occur. A simple extension of Pearl's d -separation criterion, called m -separation, is applied to these graphs. We introduce a local Markov property which is equivalent to the global property resulting from the m -separation criterion for arbitrary distributions.     

On Block Ordering of Variables in Graphical Modelling

Abstract.  In graphical modelling, the existence of substantive background knowledge on block ordering of variables is used to perform structural learning within the family of chain graphs (CGs) in which every block corresponds to an undirected graph and edges joining vertices in different blocks are directed in accordance with the ordering. We show that this practice may lead to an inappropriate restriction of the search space and introduce the concept of labelled block ordering B corresponding to a family of B - consistent CGs in which every block may be either an undirected graph or a directed acyclic graph or, more generally, a CG. In this way we provide a flexible tool for specifying subsets of chain graphs, and we observe that the most relevant subsets of CGs considered in the literature are families of B -consistent CGs for the appropriate choice of B . Structural learning within a family of B -consistent CGs requires to deal with Markov equivalence. We provide a graphical characterization of equivalence classes of B -consistent CGs, namely the B - essential graphs , as well as a procedure to construct the B -essential graph for any given equivalence class of B -consistent chain graphs. Both largest CGs and essential graphs turn out to be special cases of B -essential graphs.     

Alternative Markov Properties for Chain Graphs

Graphical Markov models use graphs to represent possible dependences among statistical variables. Lauritzen, Wermuth, and Frydenberg (LWF) introduced a Markov property for chain graphs (CG): graphs that can be used to represent both structural and associative dependences simultaneously and that include both undirected graphs (UG) and acyclic directed graphs (ADG) as special cases. Here an alternative Markov property (AMP) for CGs is introduced and shown to be the Markov property satisfied by a block-recursive linear system with multivariate normal errors. This model can be decomposed into a collection of conditional normal models, each of which combines the features of multivariate linear regression models and covariance selection models, facilitating the estimation of its parameters. In the general case, necessary and sufficient conditions are given for the equivalence of the LWF and AMP Markov properties of a CG, for the AMP Markov equivalence of two CGs, for the AMP Markov equivalence of a CG to some ADG or decomposable UG, and for other equivalences. For CGs, in some ways the AMP property is a more direct extension of the ADG Markov property than is the LWF property.     

On the Markov Equivalence of Chain Graphs, Undirected Graphs, and Acyclic Digraphs

Graphical Markov models use undirected graphs (UDGs), acyclic directed graphs (ADGs), or (mixed) chain graphs to represent possible dependencies among random variables in a multivariate distribution. Whereas a UDG is uniquely determined by its associated Markov model, this is not true for ADGs or for general chain graphs (which include both UDGs and ADGs as special cases). This paper addresses three questions regarding the equivalence of graphical Markov models: when is a given chain graph Markov equivalent (1) to some UDG? (2) to some (at least one) ADG? (3) to some decomposable UDG? The answers are obtained by means of an extension of Frydenberg’s (1990) elegant graph-theoretic characterization of the Markov equivalence of chain graphs.     

On the Validity of the Markov Interpretation of Path Diagrams of Gaussian Structural Equations Systems with Correlated Errors

Pearl's d -separation concept and the ensuing Markov property is applied to graphs which may have, between each two different vertices i and j , any subset of { i ← j , i → j , i ↔ j } as edges. The class of graphs so obtained is closed under marginalization. Furthermore, the approach permits a direct proof of this theorem: "The distribution of a multivariate normal random vector satisfying a system of linear simultaneous equations is Markov w.r.t. the path diagram of the linear system".     

RENEWAL COUNTING PROCESS INDUCED BY A DISCRETE MARKOV CHAIN

Some renewal theoretic properties of a renewal counting process induced by a Markov chain on the set of non-negative integers are established, namely, analogues of the classical elementary, Blackwell, and Breiman theorems and the key renewal theorem. These results generalize those of Vere-Jones (1975) who considered a Markov chain on the set of positive integers.     

Two remarks on order statistics

Let X₍₁₎,…,X_(n) be the order statistics of n iid distributed random variables. We prove that (X_(i)) have a certain Markov property for general distributions and secondly that the order statistics have monotone conditional regression dependence. Both properties are well known in the case of continuous distributions.     

Chain graph models: topological sorting of meta-arrows and efficient construction of $${\mathcal{B}}$$ -essential graphs

Essential graphs and largest chain graphs are well-established graphical representations of equivalence classes of directed acyclic graphs and chain graphs respectively, especially useful in the context of model selection. Recently, the notion of a labelled block ordering of vertices was introduced as a flexible tool for specifying subfamilies of chain graphs. In particular, both the family of directed acyclic graphs and the family of “unconstrained” chain graphs can be specified in this way, for the appropriate choice of . The family of chain graphs identified by a labelled block ordering of vertices is partitioned into equivalence classes each represented by means of a -essential graph. In this paper, we introduce a topological ordering of meta-arrows and use this concept to devise an efficient procedure for the construction of -essential graphs. In this way we also provide an efficient procedure for the construction of both largest chain graphs and essential graphs. The key feature of the proposed procedure is that every meta-arrow needs to be processed only once.     

Approximate Bayesian Computation for Exponential Random Graph Models for Large Social Networks

We consider the issue of sampling from the posterior distribution of exponential random graph (ERG) models and other statistical models with intractable normalizing constants. Existing methods based on exact sampling are either infeasible or require very long computing time. We study a class of approximate Markov chain Monte Carlo (MCMC) sampling schemes that deal with this issue. We also develop a new Metropolis–Hastings kernel to sample sparse large networks from ERG models. We illustrate the proposed methods on several examples.     

Non-linear autoregressive time series with multivariate Gaussian mixtures as marginal distributions

A new form of non-linear autoregressive time series is proposed to model solar radiation data, by specifying joint marginal distributions at low lags to be multivariate Gaussian mixtures. The model is also a type of multiprocess dynamic linear model, but with the advantage that the likelihood has a closed form.     

Stability of Approximations of Average Run Length of Risk-Adjusted CUSUM Schemes Using the Markov Approach: Comparing Two Methods of Calculating Transition Probabilities

Risk-adjusted CUSUM schemes are designed to monitor the number of adverse outcomes following a medical procedure. An approximation of the average run length (ARL), which is the usual performance measure for a risk-adjusted CUSUM, may be found using its Markov property. We compare two methods of computing transition probability matrices where the risk model classifies patient populations into discrete, finite levels of risk. For the first method, a process of scaling and rounding off concentrates probability in the center of the Markov states, which are non overlapping sub-intervals of the CUSUM decision interval, and, for the second, a smoothing process spreads probability uniformly across the Markov states. Examples of risk-adjusted CUSUM schemes are used to show, if rounding is used to calculate transition probabilities, the values of ARLs estimated using the Markov property vary erratically as the number of Markov states vary and, on occasion, fail to converge for mesh sizes up to 3,000. On the other hand, if smoothing is used, the approximate ARL values remain stable as the number of Markov states vary. The smoothing technique gave good estimates of the ARL where there were less than 1,000 Markov states.     

On the non-Markovian structure of discrete order statistics

In this note we show that the Markov Property holds for order statistics while sampling from a discrete parent population if and only if the population has at most two distinct units. This disproves the claim of Gupta and Gupta (1981) that for geometric parent, the order statistics form a Markov chain.     

Bayesian analysis of directed graphs data with applications to social networks

Summary.  A fully Bayesian analysis of directed graphs, with particular emphasis on applica- tions in social networks, is explored. The model is capable of incorporating the effects of covariates, within and between block ties and multiple responses. Inference is straightforward by using software that is based on Markov chain Monte Carlo methods. Examples are provided which highlight the variety of data sets that can be entertained and the ease with which they can be analysed.     

Analyses of the Markov modulated fluid flow with one-sided ph-type jumps using coupled queues and the completed graphs

In this paper, we analyze Markov modulated fluid flow processes with one-sided ph-type jumps using the completed graph and also through the limits of coupled queueing processes to be constructed. For the models, we derive various results on time-dependent distributions and distributions of first passage times, and present the Riccati equations that transform matrices of the first return times to 0 satisfy. The Riccati equations enable us to compute the transform matrices using Newton’s method which is known very fast and stable. Finally, we present some duality results between the model with ph-type downward jumps and the model with ph-type upward jumps. This paper contains extended results of Ahn (2009) and probabilistic interpretations given by the completed graphs.     

Bayesian phylogenetic inference from animal mitochondrial genome arrangements

Summary. The determination of evolutionary relationships is a fundamental problem in evolutionary biology. Genome arrangement data are potentially more informative than deoxyribonucleic acid sequence data for inferring evolutionary relationships between distantly related taxa. We describe a Bayesian framework for phylogenetic inference from mitochondrial genome arrangement data using Markov chain Monte Carlo methods. We apply the method to assess evolutionary relationships between eight animal phyla.     

The generalizations of strong law of large numbers for asymptotic even–odd Markov chains indexed by a homogeneous tree

Yang et al. (Yang et al., J. Math. Anal. Appl., 410 (2014), 179–189.) have obtained the strong law of large numbers and asymptotic equipartition property for the asymptotic even–odd Markov chains indexed by a homogeneous tree. In this article, we are going to study the strong law of large numbers and the asymptotic equipartition property for a class of non homogeneous Markov chains indexed by a homogeneous tree which are the generalizations of above results. We also provide an example showing that our generalizations are not trivial.     

Markov机制转换的状态空间模型及其在我国经济周期中的应用研究

 经济周期具有机制转换的特点,而传统的状态空间模型很难解决像具有机制转换特点的此类问题。为此,本文将Markov机制转换模型运用到状态空间模型中,并对我国经济周期进行了分析研究,实证结果表明Markov机制转换的状态空间模型,较好地刻画了我国经济周期的非对称性特征,从中得出一个重要的结论：政府的宏观调控政策会对我国经济产生正向的冲击,宏观调控是有效的。     

基于Markov转移模型的中国股市状态转换研究

文章对深交所1998～2008年间的月度股指数据进行统计性描述,并从偏度、峰度和滚动方差三个角度对其波动性进行分析;运用非线性的Markov状态转移模型,定义股市的三种状态,来系统分析股市在三种状态之间的变换及其规律.     

Granger-causality in Markov switching models

In this paper, we propose a new approach for characterizing and testing Granger-causality, which is well equipped to handle models where the change in regime evolves according to multiple Markov chains. Differently from the existing literature, we propose a method for analysing causal links that specifically takes into account Markov chains. Tests for independence are also provided. We illustrate the methodology with an empirical application, and in particular, we investigate the causality and interdependence between financial and economic cycles in USA using the bivariate Markov switching model proposed by Hamilton and Lin [13 J.D. Hamilton and J. Lin, Stock market volatility and business cycle, J. Appl. Econ. 11(5) (1996), pp. 573–593. doi: 10.1002/(SICI)1099-1255(199609)11:5<573::AID-JAE413>3.0.CO;2-T[Crossref], [Web of Science ®] , [Google Scholar]]. We find that financial variables are useful in forecasting the aggregate economic activity, and vice versa.