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 2.90554s (cpu); 1.89346s (thread); 0s (gc)

     +---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
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 David Garcia Puente
Mike Stillman

Version

This documentation describes version 1.3 of Markov.

Citation

If you have used this package in your research, please cite it as follows:

@misc{MarkovSource,
  title = {{Markov: Markov ideals arising from Bayesian networks in statistics. Version~1.3}},
  author = {Luis David Garcia Puente and Mike Stillman},
  howpublished = {A \emph{Macaulay2} package available at
    \url{https://github.com/Macaulay2/M2/tree/master/M2/Macaulay2/packages}}
}

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
- displayGraph(Graph) (missing documentation)
- displayGraph(String,Graph) (missing documentation)
- displayGraph(String,String,Graph) (missing documentation)
- 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
- gaussMinors(Matrix,List) (missing documentation)
- gaussRing(ZZ) -- see gaussRing -- ring of gaussian correlations on n random variables
- gaussTrekIdeal(Ring,Graph) (missing documentation)
- globalMarkovStmts(Graph) (missing documentation)
- hideMap(ZZ,Ring) (missing documentation)
- localMarkovStmts(Graph) (missing documentation)
- makeGraph(List) (missing documentation)
- marginMap(ZZ,Ring) (missing documentation)
- markovIdeal(Ring,List) (missing documentation)
- markovMatrices(Ring,List) (missing documentation)
- pairMarkovStmts(Graph) (missing documentation)
- writeDotFile(String,Graph) (missing documentation)
Mutable symbols
- dotBinary (missing documentation)
Other things
- dotBinary (missing documentation)

For the programmer

The object Markov is a package, defined in Markov.m2.

The source of this document is in Markov.m2:558:0.