Markov -- Markov ideals, arising from Bayesian networks in statistics

Description

This package is used to construct ideals corresponding to discrete graphical models, as described in several places, including the paper: Garcia, Stillman and Sturmfels, "The algebraic geometry of Bayesian networks", J. Symbolic Comput., 39(3-4):331–355, 2005.

The paper also constructs Gaussian ideals, as described in the paper by Seth Sullivant: "Algebraic geometry of Gaussian Bayesian networks", Adv. in Appl. Math. 40 (2008), no. 4, 482–513.

Here is a typical use of this package. We create the ideal in 16 variables whose zero set represents the probability distributions on four binary random variables which satisfy the conditional independence statements coming from the "diamond" graph 4 --> 2,3 --> 1.

i1 : R = markovRing(2,2,2,2)

o1 = R

o1 : PolynomialRing

i2 : G = makeGraph{{},{1},{1},{2,3}}

o2 = Graph{1 => set {}    }
           2 => set {1}
           3 => set {1}
           4 => set {2, 3}

o2 : Graph

i3 : S = globalMarkovStmts G

o3 = {{{1}, {4}, {2, 3}}, {{2}, {3}, {4}}}

o3 : List

i4 : I = markovIdeal(R,S)

o4 = ideal (- p       p        + p       p       , - p       p        +
               1,1,1,2 2,1,1,1    1,1,1,1 2,1,1,2     1,1,2,2 2,1,2,1  
     ------------------------------------------------------------------------
     p       p       , - p       p        + p       p       , -
      1,1,2,1 2,1,2,2     1,2,1,2 2,2,1,1    1,2,1,1 2,2,1,2   
     ------------------------------------------------------------------------
     p       p        + p       p       , - p       p        +
      1,2,2,2 2,2,2,1    1,2,2,1 2,2,2,2     1,1,2,1 1,2,1,1  
     ------------------------------------------------------------------------
     p       p        + p       p        - p       p        -
      1,1,1,1 1,2,2,1    1,2,2,1 2,1,1,1    1,2,1,1 2,1,2,1  
     ------------------------------------------------------------------------
     p       p        - p       p        + p       p        +
      1,1,2,1 2,2,1,1    2,1,2,1 2,2,1,1    1,1,1,1 2,2,2,1  
     ------------------------------------------------------------------------
     p       p       , - p       p        + p       p        +
      2,1,1,1 2,2,2,1     1,1,2,2 1,2,1,2    1,1,1,2 1,2,2,2  
     ------------------------------------------------------------------------
     p       p        - p       p        - p       p        -
      1,2,2,2 2,1,1,2    1,2,1,2 2,1,2,2    1,1,2,2 2,2,1,2  
     ------------------------------------------------------------------------
     p       p        + p       p        + p       p       )
      2,1,2,2 2,2,1,2    1,1,1,2 2,2,2,2    2,1,1,2 2,2,2,2

o4 : Ideal of R

Sometime an ideal can be simplified by changing variables. Very often, by using marginMap (missing documentation) , such ideals can be transformed to binomial ideals. This is the case here.

i5 : F = marginMap(1,R)

o5 = map (R, R, {p        - p       , p        - p       , p        - p       , p        - p       , p        - p       , p        - p       , p        - p       , p        - p       , p       , p       , p       , p       , p       , p       , p       , p       })
                  1,1,1,1    2,1,1,1   1,1,1,2    2,1,1,2   1,1,2,1    2,1,2,1   1,1,2,2    2,1,2,2   1,2,1,1    2,2,1,1   1,2,1,2    2,2,1,2   1,2,2,1    2,2,2,1   1,2,2,2    2,2,2,2   2,1,1,1   2,1,1,2   2,1,2,1   2,1,2,2   2,2,1,1   2,2,1,2   2,2,2,1   2,2,2,2

o5 : RingMap R <--- R

i6 : J = F I;

o6 : Ideal of R

i7 : netList pack(2,J_*)

     +-------------------------------------+-------------------------------------+
o7 = |- p       p        + p       p       |- p       p        + p       p       |
     |   1,1,1,2 2,1,1,1    1,1,1,1 2,1,1,2|   1,1,2,2 2,1,2,1    1,1,2,1 2,1,2,2|
     +-------------------------------------+-------------------------------------+
     |- p       p        + p       p       |- p       p        + p       p       |
     |   1,2,1,2 2,2,1,1    1,2,1,1 2,2,1,2|   1,2,2,2 2,2,2,1    1,2,2,1 2,2,2,2|
     +-------------------------------------+-------------------------------------+
     |- 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,1,2,2 1,2,1,2    1,1,1,2 1,2,2,2|
     +-------------------------------------+-------------------------------------+

This ideal has 5 primary components. The first is the one that has statistical significance. The significance of the other components is still poorly understood.

i8 : time netList primaryDecomposition J
     -- used 0.851341 seconds

     +---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
o8 = |ideal (p       , p       , p       , p       , p       p        - p       p       , p       p        - p       p       )                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         |
     |        1,2,2,2   1,2,2,1   1,2,1,2   1,2,1,1   1,1,2,2 2,1,2,1    1,1,2,1 2,1,2,2   1,1,1,2 2,1,1,1    1,1,1,1 2,1,1,2                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          |
     +---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
     |ideal (p       , p       , p       , p       , p       p        - p       p       , p       p        - p       p       )                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         |
     |        1,2,2,2   1,2,2,1   1,1,2,2   1,1,2,1   1,2,1,2 2,2,1,1    1,2,1,1 2,2,1,2   1,1,1,2 2,1,1,1    1,1,1,1 2,1,1,2                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          |
     +---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
     |ideal (p       , p       , p       , p       , p       p        - p       p       , p       p        - p       p       )                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         |
     |        1,2,1,2   1,2,1,1   1,1,1,2   1,1,1,1   1,2,2,2 2,2,2,1    1,2,2,1 2,2,2,2   1,1,2,2 2,1,2,1    1,1,2,1 2,1,2,2                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          |
     +---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
     |ideal (p       , p       , p       , p       , p       p        - p       p       , p       p        - p       p       )                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         |
     |        1,1,2,2   1,1,2,1   1,1,1,2   1,1,1,1   1,2,2,2 2,2,2,1    1,2,2,1 2,2,2,2   1,2,1,2 2,2,1,1    1,2,1,1 2,2,1,2                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          |
     +---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
     |ideal (p       p        - p       p       , p       p        - p       p       , p       p        - p       p       , p       p        - p       p       , p       p        - p       p       , p       p        - p       p       , p       p       p       p        - p       p       p       p       , p       p       p       p        - p       p       p       p       , p       p       p       p        - p       p       p       p       , p       p       p       p        - p       p       p       p       , p       p       p       p        - p       p       p       p       , p       p       p       p        - p       p       p       p       , p       p       p       p        - p       p       p       p       , p       p       p       p        - p       p       p       p       , p       p       p       p        - p       p       p       p       )|
     |        1,2,2,2 2,2,2,1    1,2,2,1 2,2,2,2   1,2,1,2 2,2,1,1    1,2,1,1 2,2,1,2   1,1,2,2 2,1,2,1    1,1,2,1 2,1,2,2   1,1,1,2 2,1,1,1    1,1,1,1 2,1,1,2   1,1,2,2 1,2,1,2    1,1,1,2 1,2,2,2   1,1,2,1 1,2,1,1    1,1,1,1 1,2,2,1   2,1,1,1 2,1,2,2 2,2,1,2 2,2,2,1    2,1,1,2 2,1,2,1 2,2,1,1 2,2,2,2   1,1,1,1 2,1,2,2 2,2,1,2 2,2,2,1    1,1,1,2 2,1,2,1 2,2,1,1 2,2,2,2   1,1,2,2 2,1,1,1 2,2,1,2 2,2,2,1    1,1,2,1 2,1,1,2 2,2,1,1 2,2,2,2   1,1,1,1 1,1,2,2 2,2,1,2 2,2,2,1    1,1,1,2 1,1,2,1 2,2,1,1 2,2,2,2   1,2,1,2 2,1,1,1 2,1,2,2 2,2,2,1    1,2,1,1 2,1,1,2 2,1,2,1 2,2,2,2   1,1,1,1 1,2,1,2 2,1,2,2 2,2,2,1    1,1,1,2 1,2,1,1 2,1,2,1 2,2,2,2   1,2,2,2 2,1,1,2 2,1,2,1 2,2,1,1    1,2,2,1 2,1,1,1 2,1,2,2 2,2,1,2   1,1,2,1 1,2,2,2 2,1,1,2 2,2,1,1    1,1,2,2 1,2,2,1 2,1,1,1 2,2,1,2   1,2,1,1 1,2,2,2 2,1,1,2 2,1,2,1    1,2,1,2 1,2,2,1 2,1,1,1 2,1,2,2 |
     +---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+

Caveat

The parts of the package involving graphs might eventually be changed to use a package dealing specifically with graphs. This might change the interface to this package.

Authors

Luis Garcia-Puente
Mike Stillman

Version

This documentation describes version 1.3 of Markov.

Source code

The source code from which this documentation is derived is in the file Markov.m2.

Exports

Types
- Graph (missing documentation)
Functions and commands
- displayGraph (missing documentation)
- gaussIdeal -- correlation ideal of a Bayesian network of joint Gaussian variables
- gaussMinors (missing documentation)
- gaussRing -- ring of gaussian correlations on n random variables
- gaussTrekIdeal (missing documentation)
- globalMarkovStmts (missing documentation)
- hideMap (missing documentation)
- localMarkovStmts (missing documentation)
- makeGraph (missing documentation)
- marginMap (missing documentation)
- markovIdeal (missing documentation)
- markovMatrices (missing documentation)
- markovRing -- ring of probability distributions on several discrete random variables
- pairMarkovStmts (missing documentation)
- removeRedundants (missing documentation)
- writeDotFile (missing documentation)
Methods
- "gaussIdeal(Ring,Graph)" -- see gaussIdeal -- correlation ideal of a Bayesian network of joint Gaussian variables
- "gaussIdeal(Ring,List)" -- see gaussIdeal -- correlation ideal of a Bayesian network of joint Gaussian variables
- "gaussRing(ZZ)" -- see gaussRing -- ring of gaussian correlations on n random variables
Other things
- dotBinary (missing documentation)

For the programmer

The object Markov is a package.