Probabilistic compositional models: Solution of an equivalence problem

Probabilistic compositional models, similarly to graphical Markov models, are able to represent multidimensional probability distributions using factorization and closely related concept of conditional independence. Compositional models represent an algebraic alternative to the graphical models. The system of related conditional independencies is not encoded explicitly (e.g. using a graph) but it is hidden in a model structure itself. This paper provides answers to the question how to recognize whether two different compositional model structures are equivalent – i.e., whether they induce the same system of conditional independencies. Above that, it provides an easy way to convert one structure into an equivalent one in terms of some elementary operations on structures, closely related ability to generate all structures equivalent with a given one, and a unique representative of a class of equivalent structures.     

Marginal AMP chain graphs

We present a new family of models that is based on graphs that may have undirected, directed and bidirected edges. We name these new models marginal AMP (MAMP) chain graphs because each of them is Markov equivalent to some AMP chain graph under marginalization of some of its nodes. However, MAMP chain graphs do not only subsume AMP chain graphs but also multivariate regression chain graphs. We describe global and pairwise Markov properties for MAMP chain graphs and prove their equivalence for compositional graphoids. We also characterize when two MAMP chain graphs are Markov equivalent.For Gaussian probability distributions, we also show that every MAMP chain graph is Markov equivalent to some directed and acyclic graph with deterministic nodes under marginalization and conditioning on some of its nodes. This is important because it implies that the independence model represented by a MAMP chain graph can be accounted for by some data generating process that is partially observed and has selection bias. Finally, we modify MAMP chain graphs so that they are closed under marginalization for Gaussian probability distributions. This is a desirable feature because it guarantees parsimonious models under marginalization.     

Independence equivalence classes of cycles

The independence equivalence class of a graph G is the set of graphs that have the same independence polynomial as G. Beaton, Brown and Cameron (2019) found the independence equivalence classes of even cycles, and raised the problem of finding the independence equivalence class of odd cycles. The problem is completely solved in this paper.     

Independence equivalence classes of paths

The independence equivalence class of a graph G is the set of graphs that have the same independence polynomial as G. A graph whose independence equivalence class contains only itself, up to isomorphism, is independence unique. Beaton, Brown and Cameron [2] showed that paths with an odd number of vertices are independence unique and raised the problem of finding the independence equivalence class of paths with an even number of vertices. The problem is completely solved in this paper.     

A logical approach to context-specific independence

Directed acyclic graphs (DAGs) constitute a qualitative representation for conditional independence (CI) properties of a probability distribution. It is known that every CI statement implied by the topology of a DAG is witnessed over it under a graph-theoretic criterion of d-separation. Alternatively, all such implied CI statements are derivable from the local independencies encoded by a DAG using the so-called semi-graphoid axioms. We consider Labeled Directed Acyclic Graphs (LDAGs) modeling graphically scenarios exhibiting context-specific independence (CSI). Such CSI statements are modeled by labeled edges, where labels encode contexts in which the edge vanishes. We study the problem of identifying all independence statements implied by the structure and the labels of an LDAG. We show that this problem is coNP-hard for LDAGs and formulate a sound extension of the semi-graphoid axioms for the derivation of such implied independencies. Finally we connect our study to certain qualitative versions of independence ubiquitous in database theory and teams semantics.     

On the Enumeration and Generation of Nonweight Equivalent Rate 1/2 Convolutional Codes

The weight equivalence of rate $\frac{1}{2} $ binary convolutional codes and the problem of enumeration and generation of all nonweight equivalent codes is considered for a given memory order m. This is done during the generation process by first ordering the encoders into classes such that it becomes easy to recognize the weight equivalence as well as the catastrophic error propagation conditions. Subclasses of respectively self and nonself reciprocal as well as catastrophic and noncatastrophic encoders are introduced. The cardinal number of these classes and subsequently the number of “nonweight equivalent” codes are then computed recursively as a function of m. Finally, since all the relations amount to simple convolutions they are compactly represented by generating functions which are tabulated.     

Exploiting independencies to compute semigraphoid and graphoid structures

We deal with conditional independencies, which have a fundamental role in probability and multivariate statistics. The structure of probabilistic independencies is described by semigraphoids or, for strictly positive probabilities, by graphoids. In this paper, given a set of independencies compatible with a probability, the attention is focused toward the problem of computing efficiently the closure with respect to the semigraphoid and graphoid structures. We introduce a suitable notion of projection in order to provide a new method which properly uses conditional independence statements.     

Structural stability of market models

A market structure in the Arrow-Debreu framework can be represented by a finite number of traded securities. We examine an interesting structure that exists among markets. The partitioning of the set of all markets. M into its rank classes is a stratification of M. Some properties of an equivalence relation among markets are also studied. Some results on the ‘genericity’ of the properties of market structures are obtained.     

Covering location problem of emergency service facilities in an uncertain environment

In practical location problems on networks, the response time between any pair of vertices and the demands of vertices are usually indeterminate. This paper employs uncertainty theory to address the location problem of emergency service facilities under uncertainty. We first model the location set covering problem in an uncertain environment, which is called the uncertain location set covering model. Using the inverse uncertainty distribution, the uncertain location set covering model can be transformed into an equivalent deterministic location model. Based on this equivalence relation, the uncertain location set covering model can be solved. Second, the maximal covering location problem is investigated in an uncertain environment. This paper first studies the uncertainty distribution of the covered demand that is associated with the covering constraint confidence level α. In addition, we model the maximal covering location problem in an uncertain environment using different modelling ideas, namely, the (α, β)-maximal covering location model and the α-chance maximal covering location model. It is also proved that the (α, β)-maximal covering location model can be transformed into an equivalent deterministic location model, and then, it can be solved. We also point out that there exists an equivalence relation between the (α, β)-maximal covering location model and the α-chance maximal covering location model, which leads to a method for solving the α-chance maximal covering location model. Finally, the ideas of uncertain models are illustrated by a case study.     

L 2 -discrete hedging in a continuous-time model

In the setting of the Black-Scholes option pricing market model, the seller of a European option must trade continuously in time. This is, of course, unrealistic from the practical viewpoint. He must then follow a discrete trading strategy. However, it does not seem natural to hedge at deterministic times regardless of moves of the spot price. In this paper, it is supposed that the hedger trades at a fixed number N of rebalancing (stopping) times. The problem (P^N) of selecting the optimal hedging times and ratios which allow one to minimize the variance of replication error is considered. For given N rebalancing, the discrete optimal hedging strategy is identified for this criterion. The problem (P^N) is then transformed into a multidimensional optimal stopping problem with boundary constraints. The restrictive problem (P^N _BS) of selecting the optimal rebalancing for the same criterion is also considered when the ratios are given by Black-Scholes. Using the vector-valued optimal stopping theory, the existence is shown of an optimal sequence of rebalancing for each one of the problems (P^N) and (P^N _BS). It also shown BS that they are asymptotically equivalent when the number of rebalances becomes large and an optimality criterion is stated for the problem (P^N). The same study is made when more realistic restrictions are imposed on the hedging times. In the special case of two rebalances, the problem (P² _BS) is solved and the problems (P² _BS) and (P²) are transformed into two optimal stopping problems. This transformation is useful for numerical purposes.     

Optimal selection of thek best of a sequence withk stops

We first consider the situation in which the decision-maker is allowed to have five choices with purpose to choose exactly the five absolute best candidates fromN applicants. The optimal stopping rule and the maximum probability of making the right five-choice are given for largeN εN, the maximum asymptotic value of the probability of the best choice being lim _N→∝ P (win) ≈ 0.104305. Then, we study the general problem of selecting thek best of a sequence withk stops, constructing first a rough solution for this problem. Using this suboptimal solution, we find an approximation for the optimal probability valuesP _k of the form $$P_k \approx \frac{1}{{(e - 1)k + 1}}$$ for any k εN.     

The number of flags in finite vector spaces: asymptotic normality and Mahonian statistics

We study the generalized Galois numbers which count flags of length r in N-dimensional vector spaces over finite fields. We prove that the coefficients of those polynomials are asymptotically Gaussian normally distributed as N becomes large. Furthermore, we interpret the generalized Galois numbers as weighted inversion statistics on the descent classes of the symmetric group on N elements and identify their asymptotic limit as the Mahonian inversion statistic when r approaches ∞. Finally, we apply our statements to derive further statistical aspects of generalized Rogers–Szeg? polynomials, reinterpret the asymptotic behavior of linear q-ary codes and characters of the symmetric group acting on subspaces over finite fields, and discuss implications for affine Demazure modules and joint probability generating functions of descent-inversion statistics.     

Homeomorphic measures on stationary Bratteli diagrams

We study the set S of ergodic probability Borel measures on stationary non-simple Bratteli diagrams which are invariant with respect to the tail equivalence relation R. Equivalently, the set S is formed by ergodic probability measures invariant with respect to aperiodic substitution dynamical systems. The paper is devoted to the classification of measures μ from S with respect to a homeomorphism. The properties of the clopen values set S(μ) are studied. It is shown that for every measure μ∈S there exists a subgroup G⊂R such that S(μ)=G∩[0,1]. A criterion of goodness is proved for such measures. Based on this result, the measures from S are classified up to a homeomorphism. We prove that for every good measure μ∈S there exist countably many measures {μi}_i∈N⊂S such that the measures μ and μi are homeomorphic but the tail equivalence relations on the corresponding Bratteli diagrams are not orbit equivalent.     

Spatio-Temporal Dynamical Systems in Inner-Shell Photoionization in Free Molecules,Clusters, and Solids

Dynamic spatial hole localization and symmetry breaking phenomena are examined. Absorption of X-ray synchrotron and free-electron–laser radiation in matter is accompanied by strong dynamic corehole localization and temporary trap of the electron ejected from a deep level within the finite size potential barrier. As a result the symmetry of core excited states is reduced in comparison with ground state as the inversion symmetry is being broken. This is a very general property of coreexcited polyatomic compounds with equivalent atoms as their equivalence implies their equal probability of excitation averaged over large timescale but not simultaneous core excitation. Different approaches to rationalizing the symmetry breaking phenomena are presented and discussed with the emphasis on the quasiatomic dynamic corehole localization model. By examining the experimental ultrafast probe of photoabsorption processes we demonstrate an important role of spatio-temporal (nanometric-femtosecond) dynamically localized coreexcited moieties in molecule, clusters and solids. The photoelectron angular distributions from N and O 1s levels in fixed-in-space N₂ and CO₂ molecules, the photoelectron induced rotational heating of N₂, the Auger decay spectra of N₂ and the near S 1s edge X-ray absorption fine structure of free SF₆ molecules are discussed in more detail.     

Implementing pure adaptive search for global optimization using Markov chain sampling

The Pure Adaptive Search (PAS) algorithm for global optimization yields a sequence of points, each of which is uniformly distributed in the level set corresponding to its predecessor. This algorithm has the highly desirable property of solving a large class of global optimization problems using a number of iterations that increases at most linearly in the dimension of the problem. Unfortunately, PAS has remained of mostly theoretical interest due to the difficulty of generating, in each iteration, a point uniformly distributed in the improving feasible region. In this article, we derive a coupling equivalence between generating an approximately uniformly distributed point using Markov chain sampling, and generating an exactly uniformly distributed point with a certain probability. This result is used to characterize the complexity of a PAS-implementation as a function of (a) the number of iterations required by PAS to achieve a certain solution quality guarantee, and (b) the complexity of the sampling algorithm used. As an application, we use this equivalence to show that PAS, using the so-called Random ball walk Markov chain sampling method for generating nearly uniform points in a convex region, can be used to solve most convex programming problems in polynomial time.     

On genus and embeddings of torsion-free nilpotent groups of class two

Summary We study embeddings between torsion-free nilpotent groups having isomorphic localizations. Firstly, we show that for finitely generated torsion-free nilpotent groups of nilpotency class 2, the property of having isomorphicP-localizations (whereP denotes any set of primes) is equivalent to the existence of mutual embeddings of finite index not divisible by any prime inP. We then focus on a certain family Γ of nilpotent groups whose Mislin genera can be identified with quotient sets of ideal class groups in quadratic fields. We show that the multiplication of equivalence classes of groups in Γ induced by the ideal class group structure can be described by means of certain pull-back diagrams reflecting the existence of enough embeddings between members of each Mislin genus. In this sense, the family Γ resembles the family N₀ of infinite, finitely generated nilpotent groups with finite commutator subgroup. We also show that, in further analogy with N₀, two groups in Γ with isomorphic localizations at every prime have isomorphic localizations at every finite set of primes. We supply counterexamples showing that this is not true in general, neither for finitely generated torsion-free nilpotent groups of class 2 nor for torsion-free abelian groups of finite rank. Supported by DGICYT grant PB94-0725 This article was processed by the author using the LAT_EX style filecljour1 from Springer-Verlag.     

A folk model structure on omega-cat

The primary aim of this work is an intrinsic homotopy theory of strict ω-categories. We establish a model structure on ωCat, the category of strict ω-categories. The constructions leading to the model structure in question are expressed entirely within the scope of ωCat, building on a set of generating cofibrations and a class of weak equivalences as basic items. All objects are fibrant while free objects are cofibrant. We further exhibit model structures of this type on n-categories for arbitrary n∈N, as specializations of the ω-categorical one along right adjoints. In particular, known cases for n=1 and n=2 nicely fit into the scheme.     

Pattern avoidance in binary trees

This paper considers the enumeration of trees avoiding a contiguous pattern. We provide an algorithm for computing the generating function that counts n-leaf binary trees avoiding a given binary tree pattern t. Equipped with this counting mechanism, we study the analogue of Wilf equivalence in which two tree patterns are equivalent if the respective n-leaf trees that avoid them are equinumerous. We investigate the equivalence classes combinatorially. Toward establishing bijective proofs of tree pattern equivalence, we develop a general method of restructuring trees that conjecturally succeeds to produce an explicit bijection for each pair of equivalent tree patterns.     

A theoretical investigation of regular equivalences for fuzzy graphs

The notion of regular equivalence or bisimulation arises in different applications, such as positional analysis of social networks and behavior analysis of state transition systems. The common characteristic of these applications is that the system under modeling can be represented as a graph. Thus, regular equivalence is a notion used to capture the similarity between nodes based on their linking patterns with other nodes. According to Borgatti and Everett, two nodes are regularly equivalent if they are equally related to equivalent others. In recent years, fuzzy graphs have also received considerable attention because they can represent both the qualitative relationships and the degrees of connection between nodes. In this paper, we generalize the notion of regular equivalence to fuzzy graphs based on two alternative definitions of regular equivalence. While the two definitions are equivalent for crisp graphs, they induce different generalizations for fuzzy graphs. The first generalization, called regular similarity, is based on the characterization of regular equivalence as an equivalence relation that commutes with the underlying graph edges. The regular similarity is then a fuzzy binary relation that specifies the degree of similarity between nodes in the graph. The second generalization, called generalized regular equivalence, is based on the definition of coloring. A coloring is a mapping from the set of nodes to a set of colors. A coloring is regular if nodes that are mapped to the same color, have the same colors in their neighborhoods. Hence, generalized regular equivalence is an equivalence relation that can determine a crisp partition of the nodes in a fuzzy graph.     

A generalization of the Curtiss theorem for moment generating functions

The Curtiss theorem deals with the relation between the weak convergence of probability measures on the line and the convergence of theirmoment generating functions in a neighborhood of zero. We present a multidimensional generalization of this result. To this end, we consider arbitrary σ-finite measures whose moment generating functions exist in a domain of multidimensional Euclidean space not necessarily containing zero. We also prove the corresponding converse statement.