# conditionalIndependenceIdeal -- ideal of a list of conditional independent statements

## Synopsis

• Usage:
conditionalIndependenceIdeal(R,Stmts)
conditionalIndependenceIdeal(R,Stmts,VarNames)
• Inputs:
• R, a ring, it must be a gaussianRing or a markovRing
• Stmts, a list, list of conditional independence statements
• VarNames, a list, list of names of random variables in conditional independence statements in Stmts. This argument allows to choose a subset of random variables and is only available for markov rings. By default, this is a list of integers 1 to $n$ where $n$ is the number of variables in the declaration of markovRing or gaussianRing. If R is a gaussian ring, then only the default input is accepted.
• Outputs:
• an ideal, ideal of conditional independence relations

## Description

conditionalIndependenceIdeal computes the ideal of a list of conditional independence statements. This method works for both discrete and Gaussian graphical models. In the case of discrete random variables, it computes the 2x2 minors of the matrices produced by markovMatrices. For Gaussian graphical models, it computes the minors of the matrices produced by gaussianMatrices.

A single conditional independence statement is a list consisting of three disjoint lists of indices for random variables, e.g. $\{ \{1,2\},\{4\}, \{3\} \}$ which represents the conditional independence statement $(X_1, X_2)$ is conditionally independent of $X_4$ given $X_3$''. In the input to conditionalIndependenceIdeal a list of conditional independence statements is used.

A common way that we arrive at collections of conditional independence statements is through the Markov statements implied by a graph. Below are two examples of independence ideals on discrete random variables, using globalMarkov statements and localMarkov statements.

 i1 : G = graph {{1,2},{2,3},{3,4},{4,1}} o1 = Graph{1 => {2, 4}} 2 => {1, 3} 3 => {2, 4} 4 => {1, 3} o1 : Graph i2 : D = digraph {{1,{}},{2,{1}},{3,{1}},{4,{2,3}}} o2 = Digraph{1 => {} } 2 => {1} 3 => {1} 4 => {2, 3} o2 : Digraph i3 : R = markovRing (2,2,2,2) o3 = R o3 : PolynomialRing i4 : conditionalIndependenceIdeal (R, globalMarkov(G)) / print; - p p + p p 1,1,2,1 2,1,1,1 1,1,1,1 2,1,2,1 - p p + p p 1,1,2,2 2,1,1,2 1,1,1,2 2,1,2,2 - p p + p p 1,2,2,1 2,2,1,1 1,2,1,1 2,2,2,1 - p p + p p 1,2,2,2 2,2,1,2 1,2,1,2 2,2,2,2 - p p + p p 1,1,1,2 1,2,1,1 1,1,1,1 1,2,1,2 - p p + p p 1,1,2,2 1,2,2,1 1,1,2,1 1,2,2,2 - p p + p p 2,1,1,2 2,2,1,1 2,1,1,1 2,2,1,2 - p p + p p 2,1,2,2 2,2,2,1 2,1,2,1 2,2,2,2 i5 : conditionalIndependenceIdeal (R, localMarkov(D)) / print; - p p + p p 1,1,1,2 2,1,1,1 1,1,1,1 2,1,1,2 - p p + p p 1,1,2,2 2,1,2,1 1,1,2,1 2,1,2,2 - p p + p p 1,2,1,2 2,2,1,1 1,2,1,1 2,2,1,2 - p p + p p 1,2,2,2 2,2,2,1 1,2,2,1 2,2,2,2 - p p + p p + p p - p p - p p - p p + p p + p p 1,1,2,1 1,2,1,1 1,1,1,1 1,2,2,1 1,2,2,1 2,1,1,1 1,2,1,1 2,1,2,1 1,1,2,1 2,2,1,1 2,1,2,1 2,2,1,1 1,1,1,1 2,2,2,1 2,1,1,1 2,2,2,1 - p p + p p + p p - p p - p p - p p + p p + p p 1,1,2,2 1,2,1,2 1,1,1,2 1,2,2,2 1,2,2,2 2,1,1,2 1,2,1,2 2,1,2,2 1,1,2,2 2,2,1,2 2,1,2,2 2,2,1,2 1,1,1,2 2,2,2,2 2,1,1,2 2,2,2,2

The following example is an independence ideal of a Gaussian graphical model.

 i6 : G = graph {{a,b},{b,c},{c,d},{d,a}} o6 = Graph{a => {b, d}} b => {a, c} c => {b, d} d => {a, c} o6 : Graph i7 : R=gaussianRing G o7 = R o7 : PolynomialRing i8 : conditionalIndependenceIdeal (R,globalMarkov(G)) / print; 2 s s s - s s - s s s + s s s + s s s - s s s a,d b,c b,d a,c b,d a,d b,b c,d a,b b,d c,d a,c b,b d,d a,b b,c d,d 2 s s s - s s - s s s + s s s + s s s - s s s a,c a,d b,c a,c b,d a,b a,d c,c a,a b,d c,c a,b a,c c,d a,a b,c c,d

For Gaussian models, conditionalIndependenceIdeal can compute the ideal of a list of independence statements on a graph even if the ring was not constructed with that specific graph. However, the vertex labels in the graph should be integers.

 i9 : G = graph({{1,2},{2,3},{3,4},{4,1}}) o9 = Graph{1 => {2, 4}} 2 => {1, 3} 3 => {2, 4} 4 => {1, 3} o9 : Graph i10 : R=gaussianRing 4 o10 = R o10 : PolynomialRing i11 : conditionalIndependenceIdeal (R, globalMarkov G) / print; 2 s s s - s s - s s s + s s s + s s s - s s s 1,4 2,3 2,4 1,3 2,4 1,4 2,2 3,4 1,2 2,4 3,4 1,3 2,2 4,4 1,2 2,3 4,4 2 s s s - s s - s s s + s s s + s s s - s s s 1,3 1,4 2,3 1,3 2,4 1,2 1,4 3,3 1,1 2,4 3,3 1,2 1,3 3,4 1,1 2,3 3,4

This method also accepts as input arbitrary lists of independent statements that may not arise from a graphical model.

 i12 : R=gaussianRing 5 o12 = R o12 : PolynomialRing i13 : S={{{1},{2},{3,4}}, {{2,3},{1},{5}}} o13 = {{{1}, {2}, {3, 4}}, {{2, 3}, {1}, {5}}} o13 : List i14 : conditionalIndependenceIdeal (R,S) / print; 2 - s s s + s s s + s s s - s s - s s s + s s s 1,4 2,4 3,3 1,4 2,3 3,4 1,3 2,4 3,4 1,2 3,4 1,3 2,3 4,4 1,2 3,3 4,4 - s s + s s 1,3 2,5 1,2 3,5 - s s + s s 1,5 2,5 1,2 5,5 - s s + s s 1,5 3,5 1,3 5,5

For general discrete independence models (not necessarily arising from a graph), conditionalIndependenceIdeal requires one of the following two options: \break (1) the random variables are labelled by integers (as in the first example above) or \break (2) in case the random variables have arbitrary names, an extra input parameter must be used in order to specify the names of the random variables.

 i15 : R = markovRing (2,2,2,2) o15 = R o15 : PolynomialRing i16 : VarNames = {c,d,e,f} o16 = {c, d, e, f} o16 : List i17 : Stmts = { {{c,d},{e},{}}, {{d,e},{c},{f}}} o17 = {{{c, d}, {e}, {}}, {{d, e}, {c}, {f}}} o17 : List i18 : conditionalIndependenceIdeal(R,Stmts,VarNames) / print; - p p - p p - p p - p p + p p + p p + p p + p p 1,1,2,1 1,2,1,1 1,1,2,2 1,2,1,1 1,1,2,1 1,2,1,2 1,1,2,2 1,2,1,2 1,1,1,1 1,2,2,1 1,1,1,2 1,2,2,1 1,1,1,1 1,2,2,2 1,1,1,2 1,2,2,2 - p p - p p - p p - p p + p p + p p + p p + p p 1,1,2,1 2,1,1,1 1,1,2,2 2,1,1,1 1,1,2,1 2,1,1,2 1,1,2,2 2,1,1,2 1,1,1,1 2,1,2,1 1,1,1,2 2,1,2,1 1,1,1,1 2,1,2,2 1,1,1,2 2,1,2,2 - p p - p p - p p - p p + p p + p p + p p + p p 1,2,2,1 2,1,1,1 1,2,2,2 2,1,1,1 1,2,2,1 2,1,1,2 1,2,2,2 2,1,1,2 1,2,1,1 2,1,2,1 1,2,1,2 2,1,2,1 1,2,1,1 2,1,2,2 1,2,1,2 2,1,2,2 - p p - p p - p p - p p + p p + p p + p p + p p 1,1,2,1 2,2,1,1 1,1,2,2 2,2,1,1 1,1,2,1 2,2,1,2 1,1,2,2 2,2,1,2 1,1,1,1 2,2,2,1 1,1,1,2 2,2,2,1 1,1,1,1 2,2,2,2 1,1,1,2 2,2,2,2 - p p - p p - p p - p p + p p + p p + p p + p p 1,2,2,1 2,2,1,1 1,2,2,2 2,2,1,1 1,2,2,1 2,2,1,2 1,2,2,2 2,2,1,2 1,2,1,1 2,2,2,1 1,2,1,2 2,2,2,1 1,2,1,1 2,2,2,2 1,2,1,2 2,2,2,2 - p p - p p - p p - p p + p p + p p + p p + p p 2,1,2,1 2,2,1,1 2,1,2,2 2,2,1,1 2,1,2,1 2,2,1,2 2,1,2,2 2,2,1,2 2,1,1,1 2,2,2,1 2,1,1,2 2,2,2,1 2,1,1,1 2,2,2,2 2,1,1,2 2,2,2,2 - p p + p p 1,1,2,1 2,1,1,1 1,1,1,1 2,1,2,1 - p p + p p 1,2,1,1 2,1,1,1 1,1,1,1 2,2,1,1 - p p + p p 1,2,1,1 2,1,2,1 1,1,2,1 2,2,1,1 - p p + p p 1,2,2,1 2,1,1,1 1,1,1,1 2,2,2,1 - p p + p p 1,2,2,1 2,1,2,1 1,1,2,1 2,2,2,1 - p p + p p 1,2,2,1 2,2,1,1 1,2,1,1 2,2,2,1 - p p + p p 1,1,2,2 2,1,1,2 1,1,1,2 2,1,2,2 - p p + p p 1,2,1,2 2,1,1,2 1,1,1,2 2,2,1,2 - p p + p p 1,2,1,2 2,1,2,2 1,1,2,2 2,2,1,2 - p p + p p 1,2,2,2 2,1,1,2 1,1,1,2 2,2,2,2 - p p + p p 1,2,2,2 2,1,2,2 1,1,2,2 2,2,2,2 - p p + p p 1,2,2,2 2,2,1,2 1,2,1,2 2,2,2,2

The following example illustrates the caveat below.

 i19 : D = digraph {{b,{a}},{a,{c}},{c,{}}} o19 = Digraph{a => {c}} b => {a} c => {} o19 : Digraph i20 : R = markovRing (2,3,2) o20 = R o20 : PolynomialRing i21 : VarNames = {b,a,c} o21 = {b, a, c} o21 : List i22 : S = globalMarkov D o22 = {{{b}, {c}, {a}}} o22 : List i23 : conditionalIndependenceIdeal(R, S, VarNames) / print; - p p + p p 1,1,2 2,1,1 1,1,1 2,1,2 - p p + p p 1,2,2 2,2,1 1,2,1 2,2,2 - p p + p p 1,3,2 2,3,1 1,3,1 2,3,2 i24 : vertices D o24 = {c, a, b} o24 : List i25 : conditionalIndependenceIdeal(R, S, vertices D) / print; - p p + p p 1,1,2 2,1,1 1,1,1 2,1,2 - p p + p p 1,2,2 2,2,1 1,2,1 2,2,2 - p p + p p 1,3,2 2,3,1 1,3,1 2,3,2

## Caveat

We note that the list of random variable names must be in the same order as the implicit order used in the sequence $d$. In the previous example, we have the graph $b \to a \to c$, where $a$ has three states and $b$ and $c$ are both binary. Note that the ring $R$ was created with the sequence $d = (2,3,2)$, having in mind the topological order of the graph as opposed to the vertex labels. Note how the first instance of this method returns the correct output, however, the second instance returns an incorrect ideal since vertices D is not in the same order as the sequence $d$.

• discreteVanishingIdeal -- vanishing ideal of a discrete graphical model
• gaussianRing -- ring of Gaussian correlations on n random variables or a graphical model
• gaussianVanishingIdeal -- vanishing ideal of a Gaussian graphical model
• markovRing -- ring of joint probability distributions on several discrete random variables
• trekIdeal -- trek separation ideal of a mixed graph

## Ways to use conditionalIndependenceIdeal :

• "conditionalIndependenceIdeal(Ring,List)"
• "conditionalIndependenceIdeal(Ring,List,List)"

## For the programmer

The object conditionalIndependenceIdeal is .