Compositional models and conditional independence in evidence theory

The goal of the paper is twofold. The first is to show that some of the ideas for representation of multidimensional distributions in probability and possibility theories can be transferred into evidence theory. Namely, we show that multidimensional basic assignments can be rather efficiently represented in a form of so-called compositional models. These models are based on the iterative application of the operator of composition, whose definition for basic assignments as well as its properties are presented. We also prove that the operator of composition in evidence theory is in a sense generalization of its probabilistic counterpart.The second goal of the paper is to introduce a new definition of conditional independence in evidence theory and to show in what sense it is superior to that formerly introduced by other authors.     

Conditional independence,conditional mixing and conditional association

Some properties of conditionally independent random variables are studied. Conditional versions of generalized Borel-Cantelli lemma, generalized Kolmogorov’s inequality and generalized Hájek-Rényi inequality are proved. As applications, a conditional version of the strong law of large numbers for conditionally independent random variables and a conditional version of the Kolmogorov’s strong law of large numbers for conditionally independent random variables with identical conditional distributions are obtained. The notions of conditional strong mixing and conditional association for a sequence of random variables are introduced. Some covariance inequalities and a central limit theorem for such sequences are mentioned.     

Induced and higher-dimensional stable independence

We provide several crucial technical extensions of the theory of stable independence notions in accessible categories. In particular, we describe circumstances under which a stable independence notion can be transferred from a subcategory to a category as a whole, and examine a number of applications to categories of groups and modules, extending results of [16]. We prove, too, that under the hypotheses of [11], a stable independence notion immediately yields higher-dimensional independence as in [26].     

NP-containment for the coherence test of assessments of conditional probability: a fuzzy logical approach

In this paper we investigate the problem of testing the coherence of an assessment of conditional probability following a purely logical setting. In particular we will prove that the coherence of an assessment of conditional probability χ can be characterized by means of the logical consistency of a suitable theory T _χ defined on the modal-fuzzy logic FP _k (RŁ_Δ) built up over the many-valued logic RŁ_Δ. Such modal-fuzzy logic was previously introduced in Flaminio (Lecture Notes in Computer Science, vol. 3571, 2005) in order to treat conditional probability by means of a list of simple probabilities following the well known (smart) ideas exposed by Halpern (Proceedings of the eighth conference on theoretical aspects of rationality and knowledge, pp 17–30, 2001) and by Coletti and Scozzafava (Trends Logic 15, 2002). Roughly speaking, such logic is obtained by adding to the language of RŁ_Δ a list of k modalities for “probably” and axioms reflecting the properties of simple probability measures. Moreover we prove that the satisfiability problem for modal formulas of FP _k (RŁ_Δ) is NP-complete. Finally, as main result of this paper, we prove FP _k (RŁ_Δ) in order to prove that the problem of establishing the coherence of rational assessments of conditional probability is NP-complete.      

Conditional independence structure and its closure: Inferential rules and algorithms

In this paper, we deal with conditional independence models closed with respect to graphoid properties. Such models come from different uncertainty measures, in particular in a probabilistic setting. We study some inferential rules and describe methods and algorithms to compute efficiently the closure of a set of conditional independence statements.     

On tests of independence in a trivariate exponential distribution

In this paper we consider the problem of testing a null hypothesis H₀ against an alternative hypothesis H_a, related to a trivariate model. H₀ is transformed into a hypothesis concerning the equality of scale parameters of three exponential distributions, following Bhattacharyya and Johnson. Two conditional tests for the transformed hypothesis are considered, and simple expressions for the power functions of our tests are obtained.     

Extending Mosaic Displays: Marginal,Conditional, and Partial Views of Categorical Data

Abstract

This article first illustrates the use of mosaic displays for the analysis of multiway contingency tables. We then introduce several extensions of mosaic displays designed to integrate graphical methods for categorical data with those used for quantitative data. The scatterplot matrix shows all pairwise (bivariate marginal) views of a set of variables in a coherent display. One analog for categorical data is a matrix of mosaic displays showing some aspect of the bivariate relation between all pairs of variables. The simplest case shows the bivariate marginal relation for each pair of variables. Another case shows the conditional relation between each pair, with all other variables partialled out. For quantitative data this represents (a) a visualization of the conditional independence relations studied by graphical models, and (b) a generalization of partial residual plots. The conditioning plot, or coplot shows a collection of partial views of several quantitative variables, conditioned by the values of one or more other variables. A direct analog of the coplot for categorical data is an array of mosaic plots of the dependence among two or more variables, stratified by the values of one or more given variables. Each such panel then shows the partial associations among the foreground variables; the collection of such plots shows how these associations change as the given variables vary.     

Asymptotic representations for importance-sampling estimators of value-at-risk and conditional value-at-risk

Value-at-risk (VaR) and conditional value-at-risk (CVaR) are important risk measures. They are often estimated by using importance-sampling (IS) techniques. In this paper, we derive the asymptotic representations for IS estimators of VaR and CVaR. Based on these representations, we are able to prove the consistency and asymptotic normality of the estimators and to provide simple conditions under which the IS estimators have smaller asymptotic variances than the ordinary Monte Carlo estimators.     

Pair-Copula Bayesian Networks

Pair-copula Bayesian networks (PCBNs) are a novel class of multivariate statistical models, which combine the distributional flexibility of pair-copula constructions (PCCs) with the parsimony of conditional independence models associated with directed acyclic graphs (DAGs). We are first to provide generic algorithms for random sampling and likelihood inference in arbitrary PCBNs as well as for selecting orderings of the parents of the vertices in the underlying graphs. Model selection of the DAG is facilitated using a version of the well-known PC algorithm that is based on a novel test for conditional independence of random variables tailored to the PCC framework. A simulation study shows the PC algorithm’s high aptitude for structure estimation in non-Gaussian PCBNs. The proposed methods are finally applied to modeling financial return data. Supplementary materials for this article are available online.     

A graphical characterization of the largest chain graphs

The paper presents a graphical characterization of the largest chain graphs which serve as unique representatives of classes of Markov equivalent chain graphs. The characterization is a basis for an algorithm constructing, for a given chain graph, the largest chain graph equivalent to it. The algorithm was used to generate a catalog of the largest chain graphs with at most five vertices. Every item of the catalog contains the largest chain graph of a class of Markov equivalent chain graphs and an economical record of the induced independency model.     

Bivariate distributions via a Pareto conditional distribution and a regression function

Uniqueness of specification of a bivariate distribution by a Pareto conditional and a consistent regression function is investigated. New characterizations of the Mardia bivariate Pareto distribution and the bivariate Pareto conditionals distribution are obtained.     

Logical analysis of numerical data

“Logical analysis of data” (LAD) is a methodology developed since the late eighties, aimed at discovering hidden structural information in data sets. LAD was originally developed for analyzing binary data by using the theory of partially defined Boolean functions. An extension of LAD for the analysis of numerical data sets is achieved through the process of “binarization” consisting in the replacement of each numerical variable by binary “indicator” variables, each showing whether the value of the original variable is above or below a certain level. Binarization was successfully applied to the analysis of a variety of real life data sets. This paper develops the theoretical foundations of the binarization process studying the combinatorial optimization problems related to the minimization of the number of binary variables. To provide an algorithmic framework for the practical solution of such problems, we construct compact linear integer programming formulations of them. We develop polynomial time algorithms for some of these minimization problems, and prove NP-hardness of others. The authors gratefully acknowledge the partial support by the Office of Naval Research (grants N00014-92-J1375 and N00014-92-J4083).     

Generalized conditional symmetries of evolution equations

We analyze the relationship of generalized conditional symmetries of evolution equations to the formal compatibility and passivity of systems of differential equations as well as to systems of vector fields in involution. Earlier results on the connection between generalized conditional invariance and generalized reduction of evolution equations are revisited. This leads to a no-go theorem on determining equations for operators of generalized conditional symmetry. It is also shown that up to certain equivalences there exists a one-to-one correspondence between generalized conditional symmetries of an evolution equation and parametric families of its solutions.     

Computational aspects of minimizing conditional value-at-risk

We consider optimization problems for minimizing conditional value-at-risk (CVaR) from a computational point of view, with an emphasis on financial applications. As a general solution approach, we suggest to reformulate these CVaR optimization problems as two-stage recourse problems of stochastic programming. Specializing the L-shaped method leads to a new algorithm for minimizing conditional value-at-risk. We implemented the algorithm as the solver CVaRMin. For illustrating the performance of this algorithm, we present some comparative computational results with two kinds of test problems. Firstly, we consider portfolio optimization problems with 5 random variables. Such problems involving conditional value at risk play an important role in financial risk management. Therefore, besides testing the performance of the proposed algorithm, we also present computational results of interest in finance. Secondly, with the explicit aim of testing algorithm performance, we also present comparative computational results with randomly generated test problems involving 50 random variables. In all our tests, the experimental solver, based on the new approach, outperformed by at least one order of magnitude all general-purpose solvers, with an accuracy of solution being in the same range as that with the LP solvers. János Mayer: Financial support by the national center of competence in research "Financial Valuation and Risk Management" is gratefully acknowledged. The national centers in research are managed by the Swiss National Science Foundation on behalf of the federal authorities.     

The computational complexity of evolutionarily stable strategies

The concept of evolutionarily stable strategies (ESS) has been central to applications of game theory in evolutionary biology, and it has also had an influence on the modern development of game theory. A regular ESS is an important refinement the ESS concept. Although there is a substantial literature on computing evolutionarily stable strategies, the precise computational complexity of determining the existence of an ESS in a symmetric two-player strategic form game has remained open, though it has been speculated that the problem is -hard. In this paper we show that determining the existence of an ESS is both -hard and -hard, and that the problem is contained in , the second level of the polynomial time hierarchy. We also show that determining the existence of a regular ESS is indeed -complete. Our upper bounds also yield algorithms for computing a (regular) ESS, if one exists, with the same complexities.     

Some properties of record values coming from the geometric distribution

The independence between spacings of record values and of individual record values is well known when the records come from a geometric distribution. Here we examine the form a function of two record values must have if we require independence from a lower record value. Also similar questions are examined in relation to conditional expectation and conditional variance.     

Linear independence of time-frequency translates

The refinement equation plays a key role in wavelet theory and in subdivision schemes in approximation theory. Viewed as an expression of linear dependence among the time-scale translates of , it is natural to ask if there exist similar dependencies among the time-frequency translates of . In other words, what is the effect of replacing the group representation of induced by the affine group with the corresponding representation induced by the Heisenberg group? This paper proves that there are no nonzero solutions to lattice-type generalizations of the refinement equation to the Heisenberg group. Moreover, it is proved that for each arbitrary finite collection , the set of all functions such that is independent is an open, dense subset of . It is conjectured that this set is all of .