This is GraphicalModels.info, produced by Macaulay2, version 1.4

GraphicalModels -- A package for discrete and Gaussian statistical graphical models
***********************************************************************************

Description
===========

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

The package also constructs ideals of Gaussian Bayesian networks and Gaussian
graphical models (graphs containing both directed and bidirected edges), as
described in the papers: Seth Sullivant, "Algebraic geometry of Gaussian
Bayesian networks", Adv. in Appl. Math. 40 (2008), no. 4, 482--513; Seth
Sullivant, Kelli Talaska and Jan Draisma, "Trek separation for Gaussian
graphical models", Annals of Statistics 38 no.3 (2010) 1665--1685.

Further, the package contains procedures to solve the identifiability problem
for Gaussian graphical models as described in the paper: Luis D. Garcia-Puente,
Sarah Spielvogel and Seth Sullivant, "Identifying causal effects with computer
algebra", Proceedings of the $26^{th}$ Conference of Uncertainty in Artificial
Intelligence.

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 d --> c,b --> a.

+-----------------------------------------------------------------------------+
|i1 : G = digraph  {{a,{}},{b,{a}},{c,{a}},{d,{b,c}}}                         |
|                                                                             |
|o1 = Digraph{a => set {}    }                                                |
|             b => set {a}                                                    |
|             c => set {a}                                                    |
|             d => set {b, c}                                                 |
|                                                                             |
|o1 : Digraph                                                                 |
+-----------------------------------------------------------------------------+
|i2 : R = markovRing (2,2,2,2)                                                |
|                                                                             |
|o2 = R                                                                       |
|                                                                             |
|o2 : PolynomialRing                                                          |
+-----------------------------------------------------------------------------+
|i3 : S = globalMarkov G                                                      |
|                                                                             |
|o3 = {{{a}, {d}, {b, c}}, {{b}, {c}, {d}}}                                   |
|                                                                             |
|o3 : List                                                                    |
+-----------------------------------------------------------------------------+
|i4 : I = markovIdeal(R,G,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                                                              |
+-----------------------------------------------------------------------------+
|i5 : netList pack(2,I_*)                                                     |
|                                                                             |
|     +-----------------------------------------------------------------------|
|o5 = |- 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,2,1,2 2,2,1,1    1,2,1,1 2,2,1,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,2,2,1 2,1,1,1    1,2,1,1 2,1|
|     +-----------------------------------------------------------------------|
|-----------------------------------------------------------------------------|
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|     - p       p        - p       p        + p       p        + p       p    |
|,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,|
|-----------------------------------------------------------------------------|
|-----------------------------------------------------------------------------|
|---+-------------------------------------------------------------------------|
|   |- 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,2,2 2,2,2,1    1,2,2,1 2,2,2,2                                    |
|---+-------------------------------------------------------------------------|
|   |- p       p        + p       p        + p       p        - p       p     |
|2,1|   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|
|---+-------------------------------------------------------------------------|
|-----------------------------------------------------------------------------|
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|   - p       p        - p       p        + p       p        + p       p      |
|,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|                                                                           |
|-+                                                                           |
+-----------------------------------------------------------------------------+

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

+-----------------------------------------------------------------------------+
|i6 : F = marginMap(1,R)                                                      |
|                                                                             |
|o6 = map(R,R,{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  |
|                                                                             |
|o6 : RingMap R <--- R                                                        |
|-----------------------------------------------------------------------------|
|p        - p       , p        - p       , p        - p       , p        -    |
| 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      |
|-----------------------------------------------------------------------------|
|p       , p        - p       , p       , p       , p       , p       ,       |
| 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        |
|-----------------------------------------------------------------------------|
|p       , p       , p       , p       })                                     |
| 2,2,1,1   2,2,1,2   2,2,2,1   2,2,2,2                                       |
+-----------------------------------------------------------------------------+
|i7 : I = F I                                                                 |
|                                                                             |
|o7 = 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,1,2,2 1,2,1,2    1,1,1,2 1,2,2,2                 |
|                                                                             |
|o7 : Ideal of R                                                              |
+-----------------------------------------------------------------------------+
|i8 : netList pack(2,I_*)                                                     |
|                                                                             |
|     +-------------------------------------+---------------------------------|
|o8 = |- 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|
|     +-------------------------------------+---------------------------------|
|     |- 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|
|     +-------------------------------------+---------------------------------|
|     |- 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|                                                                        |
|----+                                                                        |
|    |                                                                        |
|,2,2|                                                                        |
|----+                                                                        |
|    |                                                                        |
|,2,2|                                                                        |
|----+                                                                        |
+-----------------------------------------------------------------------------+

This ideal has 5 primary components.  The first component is the one that has
statistical significance. It is the defining ideal of the variety parameterized
by the the factorization of the probability distributions according to the
graph G. The remaining components lie on the boundary of the simplex and are
still poorly understood.

+-----------------------------------------------------------------------------+
|i9 : netList primaryDecomposition I                                          |
|                                                                             |
|     +-----------------------------------------------------------------------|
|o9 = |ideal (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|
|     +-----------------------------------------------------------------------|
|     |ideal (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,|
|     +-----------------------------------------------------------------------|
|     |ideal (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,|
|     +-----------------------------------------------------------------------|
|     |ideal (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,|
|     +-----------------------------------------------------------------------|
|     |ideal (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,|
|     +-----------------------------------------------------------------------|
|-----------------------------------------------------------------------------|
|-----------------------------------------------------------------------------|
|p       , p       p        - p       p       , p       p        - p       p  |
| 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,|
|-----------------------------------------------------------------------------|
|   p       , p       p        - p       p       )                            |
|2,1 2,1,2,2   1,1,1,2 2,1,1,1    1,1,1,1 2,1,1,2                             |
|-----------------------------------------------------------------------------|
|   p       , p       p        - p       p       )                            |
|1,1 2,2,1,2   1,1,1,2 2,1,1,1    1,1,1,1 2,1,1,2                             |
|-----------------------------------------------------------------------------|
|   p       , p       p        - p       p       )                            |
|2,1 2,2,2,2   1,2,1,2 2,2,1,1    1,2,1,1 2,2,1,2                             |
|-----------------------------------------------------------------------------|
|   p       , p       p        - p       p       )                            |
|2,1 2,2,2,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,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|
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|-----------------------------------------------------------------------------|
|-----------------------------------------------------------------------------|
|  , p       p       p       p        - p       p       p       p       , p   |
|,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|
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|-----------------------------------------------------------------------------|
|-----------------------------------------------------------------------------|
|    p       p       p        - p       p       p       p       , p       p   |
|,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|
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|-----------------------------------------------------------------------------|
|-----------------------------------------------------------------------------|
|    p       p        - p       p       p       p       , p       p       p   |
|,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|
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|-----------------------------------------------------------------------------|
|-----------------------------------------------------------------------------|
|    p        - p       p       p       p       , p       p       p       p   |
|,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|
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|-----------------------------------------------------------------------------|
|-----------------------------------------------------------------------------|
|     - p       p       p       p       , p       p       p       p        - p|
|,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    |
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|-----------------------------------------------------------------------------|
|-----------------------------------------------------------------------------|
|       p       p       p       , p       p       p       p        - p       p|
|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 |
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|-----------------------------------------------------------------------------|
|-----------------------------------------------------------------------------|
|       p       p       , p       p       p       p        - p       p       p|
|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 |
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|-----------------------------------------------------------------------------|
|-----------------------------------------------------------------------------|
|       p       , p       p       p       p        - p       p       p       p|
|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 |                                                                    |
|--------+                                                                    |
|        |                                                                    |
|        |                                                                    |
|--------+                                                                    |
|        |                                                                    |
|        |                                                                    |
|--------+                                                                    |
|        |                                                                    |
|        |                                                                    |
|--------+                                                                    |
|        |                                                                    |
|        |                                                                    |
|--------+                                                                    |
+-----------------------------------------------------------------------------+

The following example illustrates the caveat below.

+-----------------------------------------------------------------------------+
|i10 : H = digraph {{d,{b,a}},{c,{}},{b,{c}},{a,{c}}}                         |
|                                                                             |
|o10 = Digraph{a => set {c}   }                                               |
|              b => set {c}                                                   |
|              c => set {}                                                    |
|              d => set {a, b}                                                |
|                                                                             |
|o10 : Digraph                                                                |
+-----------------------------------------------------------------------------+
|i11 : T = globalMarkov H                                                     |
|                                                                             |
|o11 = {{{a}, {b}, {d}}, {{c}, {d}, {b, a}}}                                  |
|                                                                             |
|o11 : List                                                                   |
+-----------------------------------------------------------------------------+
|i12 : J = markovIdeal(R,H,T);                                                |
|                                                                             |
|o12 : Ideal of R                                                             |
+-----------------------------------------------------------------------------+
|i13 : netList pack(2,J_*)                                                    |
|                                                                             |
|      +----------------------------------------------------------------------|
|o13 = |- p       p        - p       p        - p       p        - p       p  |
|      |   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,|
|      +----------------------------------------------------------------------|
|      |- p       p        + p       p                                        |
|      |   1,1,1,2 1,1,2,1    1,1,1,1 1,1,2,2                                 |
|      +----------------------------------------------------------------------|
|      |- p       p        + p       p                                        |
|      |   2,1,1,2 2,1,2,1    2,1,1,1 2,1,2,2                                 |
|      +----------------------------------------------------------------------|
|-----------------------------------------------------------------------------|
|-----------------------------------------------------------------------------|
|      + p       p        + p       p        + p       p        + p       p   |
|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|
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|-----------------------------------------------------------------------------|
|----+------------------------------------------------------------------------|
|    |- p       p        - p       p        - p       p        - p       p    |
|,2,1|   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,|
|----+------------------------------------------------------------------------|
|    |- p       p        + p       p                                          |
|    |   1,2,1,2 1,2,2,1    1,2,1,1 1,2,2,2                                   |
|----+------------------------------------------------------------------------|
|    |- p       p        + p       p                                          |
|    |   2,2,1,2 2,2,2,1    2,2,1,1 2,2,2,2                                   |
|----+------------------------------------------------------------------------|
|-----------------------------------------------------------------------------|
|-----------------------------------------------------------------------------|
|    + p       p        + p       p        + p       p        + p       p     |
|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|
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|-----------------------------------------------------------------------------|
|-----------------------------------------------------------------------------|
|--+                                                                          |
|  |                                                                          |
|,2|                                                                          |
|--+                                                                          |
|  |                                                                          |
|  |                                                                          |
|--+                                                                          |
|  |                                                                          |
|  |                                                                          |
|--+                                                                          |
+-----------------------------------------------------------------------------+
|i14 : F = marginMap(3,R);                                                    |
|                                                                             |
|o14 : RingMap R <--- R                                                       |
+-----------------------------------------------------------------------------+
|i15 : J = F J;                                                               |
|                                                                             |
|o15 : Ideal of R                                                             |
+-----------------------------------------------------------------------------+
|i16 : netList pack(2,J_*)                                                    |
|                                                                             |
|      +-------------------------------------+--------------------------------|
|o16 = |- p       p        + p       p       |- p       p        + p       p  |
|      |   1,2,1,1 2,1,1,1    1,1,1,1 2,2,1,1|   1,2,1,2 2,1,1,2    1,1,1,2 2,|
|      +-------------------------------------+--------------------------------|
|      |- p       p        + p       p       |- p       p        + p       p  |
|      |   1,1,1,2 1,1,2,1    1,1,1,1 1,1,2,2|   1,2,1,2 1,2,2,1    1,2,1,1 1,|
|      +-------------------------------------+--------------------------------|
|      |- p       p        + p       p       |- p       p        + p       p  |
|      |   2,1,1,2 2,1,2,1    2,1,1,1 2,1,2,2|   2,2,1,2 2,2,2,1    2,2,1,1 2,|
|      +-------------------------------------+--------------------------------|
|-----------------------------------------------------------------------------|
|-----+                                                                       |
|     |                                                                       |
|2,1,2|                                                                       |
|-----+                                                                       |
|     |                                                                       |
|2,2,2|                                                                       |
|-----+                                                                       |
|     |                                                                       |
|2,2,2|                                                                       |
|-----+                                                                       |
+-----------------------------------------------------------------------------+

Note that the graph $H$ is isomorphic to $G$, we have just relabeled the
vertices. Observe that the vertices of $H$ are stored in lexicographic order.
Also note that the this graph isomorphism lifts to an isomorphism of ideals.

Caveat
======

This package requires Graphs.m2, as a consequence it can do computations with
graphs whose vertices are not necessarily labeled by integers. This could
potentially create some confusion about what does $p_{i_1i_2\cdots i_n}$ mean.
The package orders the vertices lexicographically, so $p_{i_1i_2\cdots i_n} =
p(X_1 = i_1, X_2 = i_2, \dots, X_n = i_n)$ where the labels $X_1,X_2,\dots,X_n$
have been ordered lexicographically. Therefore, the user is encouraged to label
the vertices in a consistent way (all numbers, or all letters, etc).

Authors
=======

  * Luis Garcia-Puente <lgarcia@shsu.edu>
  * Mike Stillman <mike@math.cornell.edu>

Version
=======

This documentation describes version 0.1 of GraphicalModels.

Source code
===========

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

Exports
=======

  * Functions and commands
      * bidirectedEdgesMatrix -- the matrix
        corresponding to the bidirected edges of a mixed graph
      * covarianceMatrix -- the covariance matrix of a
        gaussian graphical model
      * directedEdgesMatrix -- the matrix
        corresponding to the directed edges of a mixed graph
      * gaussianIdeal -- correlation ideal of a Bayesian
        network of joint Gaussian variables
      * gaussianMatrices -- Matrices whose minors form
        the ideal corresponding to a conditional independence statements.
      * gaussianParametrization -- the
        parametrization of the covariance matrix in terms of treks
      * gaussianRing -- ring of gaussian correlations on n
        random variables
      * globalMarkov -- Global Markov statements for a
        directed graph.
      * hiddenMap -- Creates a linear map from a ring of
        probability distributions among observed discrete random variables into
        a ring of probability distributions among observed variables and one
        hidden variable specified by the integer input.
      * identifyParameters -- solving the
        identifiability problem: expressing each parameter in terms of
        covariances
      * localMarkov -- Local Markov statements for a
        directed graph.
      * marginMap -- Generates a linear map on joint
        probabilities for discrete variables that replaces marginals for
        indeterminates.
      * markovIdeal -- Ideal of constraints associated to a
        list of independent statements among discrete random variables.
      * markovMatrices -- The matrices whose minors form
        the ideal associated to the list of independence statements of the
        graph.
      * markovRing -- Ring of probability distributions on
        several discrete random variables.
      * pairMarkov -- Pairwise Markov statements for a
        directed graph.
      * trekIdeal -- the edge elimination ideal of a directed
        graph, or the trek separation ideal of a mixed graph
      * trekSeparation -- the trek separation statements
        of a mixed graph
  * Symbols
      * Coefficients -- Optional input to choose the base
        field.
      * SimpleTreks -- optional input to choose the type of
        parametrization in @TO gaussianParametrization@
      * VariableName -- Optional input to choose the
        letter for the variable name.

bidirectedEdgesMatrix -- the matrix corresponding to the bidirected edges of a mixed graph
******************************************************************************************

Synopsis
========

  * Usage:W = bidirectedEdgesMatrix(R,G)
  * Inputs:
      * R, a ring (Macaulay2Doc), which should be a gaussianRing
      * G, an object of class MixedGraph (Graphs), mixed
        graph with directed and bidirected edges
  * Outputs:
      * S, a matrix (Macaulay2Doc), the n x n symmetric matrix of
        symbols where we have $w_{(i,i)}$ for each vertex i, $w_{(i,j)}$ if
        there is a bidirected edge between i and j, and 0 otherwise.

Description
===========

Note that this matrix is symmetric in the symbols.

+----------------------------------------------------------------+
|i1 : G = mixedGraph(digraph {{b,{c,d}},{c,{d}}},bigraph {{a,d}})|
|                                                                |
|o1 = MixedGraph{Bigraph => Bigraph{a => set {d}}   }            |
|                                   d => set {a}                 |
|                Digraph => Digraph{b => set {c, d}}             |
|                                   c => set {d}                 |
|                                   d => set {}                  |
|                Graph => Graph{}                                |
|                                                                |
|o1 : MixedGraph                                                 |
+----------------------------------------------------------------+
|i2 : R = gaussianRing G                                         |
|                                                                |
|o2 = R                                                          |
|                                                                |
|o2 : PolynomialRing                                             |
+----------------------------------------------------------------+
|i3 : S = bidirectedEdgesMatrix(R,G)                             |
|                                                                |
|o3 = | p_(a,a) 0       0       p_(a,d) |                        |
|     | 0       p_(b,b) 0       0       |                        |
|     | 0       0       p_(c,c) 0       |                        |
|     | p_(a,d) 0       0       p_(d,d) |                        |
|                                                                |
|             4       4                                          |
|o3 : Matrix R  <--- R                                           |
+----------------------------------------------------------------+

See also
========

  * gaussianRing -- ring of gaussian correlations on n
    random variables
  * gaussianParametrization -- the
    parametrization of the covariance matrix in terms of treks
  * covarianceMatrix -- the covariance matrix of a
    gaussian graphical model
  * directedEdgesMatrix -- the matrix corresponding
    to the directed edges of a mixed graph

Ways to use bidirectedEdgesMatrix :
===================================

  * bidirectedEdgesMatrix(Ring,MixedGraph)

Coefficients -- Optional input to choose the base field.
********************************************************

Description
===========

Put {\tt Coefficients => r} for a choice of ring(field) r as an argument in the
function markovRing, or gaussianRing,

Functions with optional argument named Coefficients :
=====================================================

  * gaussianRing(..., Coefficients => ...), see gaussianRing,
    -- ring of gaussian correlations on n random variables
  * markovRing(..., Coefficients => ...), see markovRing, --
    Ring of probability distributions on several discrete random variables.

See also
========

  * markovRing -- Ring of probability distributions on
    several discrete random variables.
  * gaussianRing -- ring of gaussian correlations on n
    random variables

For the programmer
==================

The object Coefficients, is a symbol (Macaulay2Doc).

covarianceMatrix -- the covariance matrix of a gaussian graphical model
***********************************************************************

Synopsis
========

  * Usage:S = covarianceMatrix R or S = covarianceMatrix(R,G)
  * Inputs:
      * R, a ring (Macaulay2Doc), which should be a gaussianRing
      * G, an object of class Digraph (Graphs), a directed
        acyclic graph, or an object of class MixedGraph (Graphs),
        with directed and bidirected edges
  * Outputs:
      * S, a matrix (Macaulay2Doc), the n x n covariance matrix
        of symbols where n is the number of vertices in G

Description
===========

If this function is called without a graph G, it is assumed that R is the gauss
ring of a directed acyclic graph.

+-------------------------------------------------------+
|i1 : G = digraph {{a,{b,c}}, {b,{c,d}}, {c,{}}, {d,{}}}|
|                                                       |
|o1 = Digraph{a => set {b, c}}                          |
|             b => set {c, d}                           |
|             c => set {}                               |
|             d => set {}                               |
|                                                       |
|o1 : Digraph                                           |
+-------------------------------------------------------+
|i2 : R = gaussianRing G                                |
|                                                       |
|o2 = R                                                 |
|                                                       |
|o2 : PolynomialRing                                    |
+-------------------------------------------------------+
|i3 : S = covarianceMatrix R                            |
|                                                       |
|o3 = | s_(a,a) s_(a,b) s_(a,c) s_(a,d) |               |
|     | s_(a,b) s_(b,b) s_(b,c) s_(b,d) |               |
|     | s_(a,c) s_(b,c) s_(c,c) s_(c,d) |               |
|     | s_(a,d) s_(b,d) s_(c,d) s_(d,d) |               |
|                                                       |
|             4       4                                 |
|o3 : Matrix R  <--- R                                  |
+-------------------------------------------------------+

Note that the covariance matrix is symmetric in the symbols.

+----------------------------------------------------------------+
|i4 : G = mixedGraph(digraph {{b,{c,d}},{c,{d}}},bigraph {{a,d}})|
|                                                                |
|o4 = MixedGraph{Bigraph => Bigraph{a => set {d}}   }            |
|                                   d => set {a}                 |
|                Digraph => Digraph{b => set {c, d}}             |
|                                   c => set {d}                 |
|                                   d => set {}                  |
|                Graph => Graph{}                                |
|                                                                |
|o4 : MixedGraph                                                 |
+----------------------------------------------------------------+
|i5 : R = gaussianRing G                                         |
|                                                                |
|o5 = R                                                          |
|                                                                |
|o5 : PolynomialRing                                             |
+----------------------------------------------------------------+
|i6 : S = covarianceMatrix(R,G)                                  |
|                                                                |
|o6 = | s_(a,a) s_(a,b) s_(a,c) s_(a,d) |                        |
|     | s_(a,b) s_(b,b) s_(b,c) s_(b,d) |                        |
|     | s_(a,c) s_(b,c) s_(c,c) s_(c,d) |                        |
|     | s_(a,d) s_(b,d) s_(c,d) s_(d,d) |                        |
|                                                                |
|             4       4                                          |
|o6 : Matrix R  <--- R                                           |
+----------------------------------------------------------------+

See also
========

  * gaussianRing -- ring of gaussian correlations on n
    random variables
  * gaussianParametrization -- the
    parametrization of the covariance matrix in terms of treks
  * bidirectedEdgesMatrix -- the matrix
    corresponding to the bidirected edges of a mixed graph
  * directedEdgesMatrix -- the matrix corresponding
    to the directed edges of a mixed graph

Ways to use covarianceMatrix :
==============================

  * covarianceMatrix(Ring)
  * covarianceMatrix(Ring,Digraph)
  * covarianceMatrix(Ring,MixedGraph)

directedEdgesMatrix -- the matrix corresponding to the directed edges of a mixed graph
**************************************************************************************

Synopsis
========

  * Usage:L = directedEdgesMatrix(R,G)
  * Inputs:
      * R, a ring (Macaulay2Doc), which should be a gaussianRing
      * G, an object of class MixedGraph (Graphs), mixed
        graph with directed and bidirected edges
  * Outputs:
      * L, a matrix (Macaulay2Doc), the n x n matrix of symbols
        where we have $l_{(i,j)}$ if there is a directed edge i-->j, and 0
        otherwise.

Description
===========

Note that this matrix is NOT symmetric in the symbols.

+----------------------------------------------------------------+
|i1 : G = mixedGraph(digraph {{b,{c,d}},{c,{d}}},bigraph {{a,d}})|
|                                                                |
|o1 = MixedGraph{Bigraph => Bigraph{a => set {d}}   }            |
|                                   d => set {a}                 |
|                Digraph => Digraph{b => set {c, d}}             |
|                                   c => set {d}                 |
|                                   d => set {}                  |
|                Graph => Graph{}                                |
|                                                                |
|o1 : MixedGraph                                                 |
+----------------------------------------------------------------+
|i2 : R = gaussianRing G                                         |
|                                                                |
|o2 = R                                                          |
|                                                                |
|o2 : PolynomialRing                                             |
+----------------------------------------------------------------+
|i3 : S = directedEdgesMatrix(R,G)                               |
|                                                                |
|o3 = | 0 0 0       0       |                                    |
|     | 0 0 l_(b,c) l_(b,d) |                                    |
|     | 0 0 0       l_(c,d) |                                    |
|     | 0 0 0       0       |                                    |
|                                                                |
|             4       4                                          |
|o3 : Matrix R  <--- R                                           |
+----------------------------------------------------------------+

See also
========

  * gaussianRing -- ring of gaussian correlations on n
    random variables
  * gaussianParametrization -- the
    parametrization of the covariance matrix in terms of treks
  * covarianceMatrix -- the covariance matrix of a
    gaussian graphical model
  * bidirectedEdgesMatrix -- the matrix
    corresponding to the bidirected edges of a mixed graph

Ways to use directedEdgesMatrix :
=================================

  * directedEdgesMatrix(Ring,MixedGraph)

gaussianIdeal -- correlation ideal of a Bayesian network of joint Gaussian variables
************************************************************************************

Synopsis
========

  * Usage:I = gaussianIdeal(R,G) or I = gaussianIdeal(R,G,S)
  * Inputs:
      * R, a ring (Macaulay2Doc), created with gaussianRing,
      * G, an object of class Digraph (Graphs), an acyclic
        directed graph
      * S, a list (Macaulay2Doc), a list of independence statements
        for the graph G
  * Outputs:
      * I, an ideal (Macaulay2Doc), in R, of the relations in the
        correlations of the random variables implied by the independence
        statements of the graph G, or the list of independence statements G

Description
===========

The ideal corresponding to a conditional independence statement {A,B,C} (where
A,B,C, are disjoint lists of integers in the range 1..n (n is the number of
random variables) is the #C+1 x #C+1 minors of the submatrix of the generic
symmetric matrix M = (s_{(i,j)}), whose rows are in A union C, and whose
columns are in B union C.  In general, this ideal need not be prime.

These ideals were first written down by Seth Sullivant, in "Algebraic geometry
of Gaussian Bayesian networks". The routines in this package involving Gaussian
variables are all based on that paper.

+-----------------------------------------------------------------------------+
|i1 : R = gaussianRing 5;                                                     |
+-----------------------------------------------------------------------------+
|i2 : G = digraph { {1,{2}}, {2,{3}}, {3,{4,5}},{4,{5}} }                     |
|                                                                             |
|o2 = Digraph{1 => set {2}   }                                                |
|             2 => set {3}                                                    |
|             3 => set {4, 5}                                                 |
|             4 => set {5}                                                    |
|             5 => set {}                                                     |
|                                                                             |
|o2 : Digraph                                                                 |
+-----------------------------------------------------------------------------+
|i3 : (globalMarkov G)/print;                                                 |
|{{1, 2}, {4, 5}, {3}}                                                        |
|{{1}, {3, 4, 5}, {2}}                                                        |
+-----------------------------------------------------------------------------+
|i4 : J = gaussianIdeal(R,G)                                                  |
|                                                                             |
|o4 = ideal (- s   s    + s   s   , - s   s    + s   s   , - s   s    +       |
|               1,5 2,4    1,4 2,5     1,5 3,4    1,4 3,5     2,5 3,4         |
|     ------------------------------------------------------------------------|
|     s   s   , s   s    - s   s   , s   s    - s   s   , s   s    - s   s   ,|
|      2,4 3,5   1,4 2,3    1,3 2,4   1,4 3,3    1,3 3,4   2,4 3,3    2,3 3,4 |
|     ------------------------------------------------------------------------|
|     s   s    - s   s   , s   s    - s   s   , s   s    - s   s   , -        |
|      1,5 2,3    1,3 2,5   1,5 3,3    1,3 3,5   2,5 3,3    2,3 3,5           |
|     ------------------------------------------------------------------------|
|     s   s    + s   s   , - s   s    + s   s   , - s   s    + s   s   ,      |
|      1,4 2,3    1,3 2,4     1,5 2,3    1,3 2,5     1,5 2,4    1,4 2,5       |
|     ------------------------------------------------------------------------|
|     s   s    - s   s   , s   s    - s   s   , s   s    - s   s   )          |
|      1,3 2,2    1,2 2,3   1,4 2,2    1,2 2,4   1,5 2,2    1,2 2,5           |
|                                                                             |
|o4 : Ideal of R                                                              |
+-----------------------------------------------------------------------------+

A list of independence statements (as for example returned by globalMarkov) can
be provided instead of a graph:

+-----------------------------------------------------------------------------+
|i5 : S=pairMarkov G                                                          |
|                                                                             |
|o5 = {{{1}, {3}, {2}}, {{1}, {4}, {2, 3}}, {{1}, {5}, {4, 2, 3}}, {{2}, {5}, |
|     ------------------------------------------------------------------------|
|     {4, 1, 3}}, {{2}, {4}, {1, 3}}}                                         |
|                                                                             |
|o5 : List                                                                    |
+-----------------------------------------------------------------------------+
|i6 : I = gaussianIdeal(R,G,S)                                                |
|                                                                             |
|                                        2                                    |
|o6 = ideal (s   s    - s   s   , - s   s    + s   s   s    + s   s   s    -  |
|             1,3 2,2    1,2 2,3     1,4 2,3    1,3 2,3 2,4    1,4 2,2 3,3    |
|     ------------------------------------------------------------------------|
|                                                        2                    |
|     s   s   s    - s   s   s    + s   s   s   , - s   s   s    +            |
|      1,2 2,4 3,3    1,3 2,2 3,4    1,2 2,3 3,4     1,5 2,4 3,3              |
|     ------------------------------------------------------------------------|
|                                                                             |
|     s   s   s   s    + 2s   s   s   s    - s   s   s   s    -               |
|      1,4 2,4 2,5 3,3     1,5 2,3 2,4 3,4    1,4 2,3 2,5 3,4                 |
|     ------------------------------------------------------------------------|
|                                 2              2                            |
|     s   s   s   s    - s   s   s    + s   s   s    - s   s   s   s    +     |
|      1,3 2,4 2,5 3,4    1,5 2,2 3,4    1,2 2,5 3,4    1,4 2,3 2,4 3,5       |
|     ------------------------------------------------------------------------|
|          2                                                    2             |
|     s   s   s    + s   s   s   s    - s   s   s   s    - s   s   s    +     |
|      1,3 2,4 3,5    1,4 2,2 3,4 3,5    1,2 2,4 3,4 3,5    1,5 2,3 4,4       |
|     ------------------------------------------------------------------------|
|                                                                             |
|     s   s   s   s    + s   s   s   s    - s   s   s   s    -                |
|      1,3 2,3 2,5 4,4    1,5 2,2 3,3 4,4    1,2 2,5 3,3 4,4                  |
|     ------------------------------------------------------------------------|
|                                                2                            |
|     s   s   s   s    + s   s   s   s    + s   s   s    - s   s   s   s    - |
|      1,3 2,2 3,5 4,4    1,2 2,3 3,5 4,4    1,4 2,3 4,5    1,3 2,3 2,4 4,5   |
|     ------------------------------------------------------------------------|
|                                                                             |
|     s   s   s   s    + s   s   s   s    + s   s   s   s    -                |
|      1,4 2,2 3,3 4,5    1,2 2,4 3,3 4,5    1,3 2,2 3,4 4,5                  |
|     ------------------------------------------------------------------------|
|                                           2                                 |
|     s   s   s   s   , s   s   s   s    - s   s   s    - s   s   s   s    -  |
|      1,2 2,3 3,4 4,5   1,4 1,5 2,4 3,3    1,4 2,5 3,3    1,4 1,5 2,3 3,4    |
|     ------------------------------------------------------------------------|
|                                                     2              2        |
|     s   s   s   s    + 2s   s   s   s    + s   s   s    - s   s   s    +    |
|      1,3 1,5 2,4 3,4     1,3 1,4 2,5 3,4    1,2 1,5 3,4    1,1 2,5 3,4      |
|     ------------------------------------------------------------------------|
|      2                                                                      |
|     s   s   s    - s   s   s   s    - s   s   s   s    + s   s   s   s    + |
|      1,4 2,3 3,5    1,3 1,4 2,4 3,5    1,2 1,4 3,4 3,5    1,1 2,4 3,4 3,5   |
|     ------------------------------------------------------------------------|
|                         2                                                   |
|     s   s   s   s    - s   s   s    - s   s   s   s    + s   s   s   s    + |
|      1,3 1,5 2,3 4,4    1,3 2,5 4,4    1,2 1,5 3,3 4,4    1,1 2,5 3,3 4,4   |
|     ------------------------------------------------------------------------|
|                                                               2             |
|     s   s   s   s    - s   s   s   s    - s   s   s   s    + s   s   s    + |
|      1,2 1,3 3,5 4,4    1,1 2,3 3,5 4,4    1,3 1,4 2,3 4,5    1,3 2,4 4,5   |
|     ------------------------------------------------------------------------|
|                                                                             |
|     s   s   s   s    - s   s   s   s    - s   s   s   s    +                |
|      1,2 1,4 3,3 4,5    1,1 2,4 3,3 4,5    1,2 1,3 3,4 4,5                  |
|     ------------------------------------------------------------------------|
|                                       2                                     |
|     s   s   s   s   , s   s   s    - s   s    - s   s   s    + s   s   s    |
|      1,1 2,3 3,4 4,5   1,3 1,4 2,3    1,3 2,4    1,2 1,4 3,3    1,1 2,4 3,3 |
|     ------------------------------------------------------------------------|
|     + s   s   s    - s   s   s   )                                          |
|        1,2 1,3 3,4    1,1 2,3 3,4                                           |
|                                                                             |
|o6 : Ideal of R                                                              |
+-----------------------------------------------------------------------------+
|i7 : codim I                                                                 |
|                                                                             |
|o7 = 4                                                                       |
+-----------------------------------------------------------------------------+

See also
========

  * globalMarkov -- Global Markov statements for a
    directed graph.
  * localMarkov -- Local Markov statements for a directed
    graph.
  * gaussianRing -- ring of gaussian correlations on n
    random variables
  * gaussianMatrices -- Matrices whose minors form the
    ideal corresponding to a conditional independence statements.
  * trekIdeal -- the edge elimination ideal of a directed
    graph, or the trek separation ideal of a mixed graph

Ways to use gaussianIdeal :
===========================

  * gaussianIdeal(Ring,Digraph)
  * gaussianIdeal(Ring,Digraph,List)

gaussianMatrices -- Matrices whose minors form the ideal corresponding to a conditional independence statements.
****************************************************************************************************************

Synopsis
========

  * Usage:gaussianMatrices(R,G,S)gaussianMatrices(R,G)
  * Inputs:
      * R, a ring (Macaulay2Doc), must be a gaussianRing
      * G, an object of class Digraph (Graphs), a directed
        acyclic graph
      * S, a list (Macaulay2Doc), a conditional independence
        statement that holds for the graph G
  * Outputs:
      * a matrix (Macaulay2Doc), whose minors belong to the ideal
        corresponding to a conditional independence statements.

Description
===========

This method displays a list of matrices whose minors generate the ideal of
conditional independence statements. Its main purpose is to visualize these
polynomials in a simpler way before they are expanded as sums of monomials.

+----------------------------------------------------------------------------+
|i1 : G = digraph { {1,{2}}, {2,{3}}, {3,{4,5}},{4,{5}} } ;                  |
+----------------------------------------------------------------------------+
|i2 : S = localMarkov G;                                                     |
+----------------------------------------------------------------------------+
|i3 : R = gaussianRing G;                                                    |
+----------------------------------------------------------------------------+
|i4 : gaussianMatrices(R,G,S)                                                |
|                                                                            |
|o4 = {| s_(1,4) s_(1,3) |, | s_(1,5) s_(1,4) s_(1,3) |, | s_(1,3) s_(1,2) |}|
|      | s_(2,4) s_(2,3) |  | s_(2,5) s_(2,4) s_(2,3) |  | s_(2,3) s_(2,2) | |
|      | s_(3,4) s_(3,3) |  | s_(4,5) s_(4,4) s_(3,4) |                      |
|                           | s_(3,5) s_(3,4) s_(3,3) |                      |
|                                                                            |
|o4 : List                                                                   |
+----------------------------------------------------------------------------+
|i5 : gaussianMatrices(R,G)                                                  |
|                                                                            |
|o5 = {| s_(1,4) s_(1,5) s_(1,3) |, | s_(1,3) s_(1,4) s_(1,5) s_(1,2) |}     |
|      | s_(2,4) s_(2,5) s_(2,3) |  | s_(2,3) s_(2,4) s_(2,5) s_(2,2) |      |
|      | s_(3,4) s_(3,5) s_(3,3) |                                           |
|                                                                            |
|o5 : List                                                                   |
+----------------------------------------------------------------------------+

See also
========

  * gaussianRing -- ring of gaussian correlations on n
    random variables
  * gaussianIdeal -- correlation ideal of a Bayesian
    network of joint Gaussian variables

Ways to use gaussianMatrices :
==============================

  * gaussianMatrices(Ring,Digraph)
  * gaussianMatrices(Ring,Digraph,List)

gaussianParametrization -- the parametrization of the covariance matrix in terms of treks
*****************************************************************************************

Synopsis
========

  * Usage:M = gaussianParametrization(R,G)
  * Inputs:
      * R, a ring (Macaulay2Doc), which should be a gaussianRing
      * G, an object of class MixedGraph (Graphs), mixed
        graph with directed and bidirected edges
  * Optional inputs (Macaulay2Doc),:
      * SimpleTreks => ...,  -- the
        parametrization of the covariance matrix in terms of treks
  * Outputs:
      * M, a matrix (Macaulay2Doc), the parametrization of the
        covariance matrix in terms of treks

Description
===========

Given a mixed graph G with directed and bidirected edges, let L be the matrix
corresponding to the directed edges (see directedEdgesMatrix)
and let W be the matrix corresponding to the bidirected
edges (see bidirectedEdgesMatrix). Then, the
covariance matrix S (see covarianceMatrix) of the
random variables in the gaussian graphical model corresponding to the mixed
graph G can be parametrized by the matrix equation $S = (I-L)^{-T}W(I-L)^{-1}$,
where I is the identity matrix.

The entry $S_{(i,j)}$ of the covariance matrix can also be written as the sum
of all monomials corresponding to treks between vertices i and j. See
trekSeparation, for the definition of a trek. The monomial
corresponding to a trek is the product of all parameters associated to the
directed and bidirected edges on the trek.

The following example shows how to compute the ideal of the model using the
parametrization.

+-----------------------------------------------------------------------------+
|i1 : G = mixedGraph(digraph {{b,{c,d}},{c,{d}}},bigraph {{a,d}})             |
|                                                                             |
|o1 = MixedGraph{Bigraph => Bigraph{a => set {d}}   }                         |
|                                   d => set {a}                              |
|                Digraph => Digraph{b => set {c, d}}                          |
|                                   c => set {d}                              |
|                                   d => set {}                               |
|                Graph => Graph{}                                             |
|                                                                             |
|o1 : MixedGraph                                                              |
+-----------------------------------------------------------------------------+
|i2 : R = gaussianRing G                                                      |
|                                                                             |
|o2 = R                                                                       |
|                                                                             |
|o2 : PolynomialRing                                                          |
+-----------------------------------------------------------------------------+
|i3 : S = covarianceMatrix(R,G)                                               |
|                                                                             |
|o3 = | s_(a,a) s_(a,b) s_(a,c) s_(a,d) |                                     |
|     | s_(a,b) s_(b,b) s_(b,c) s_(b,d) |                                     |
|     | s_(a,c) s_(b,c) s_(c,c) s_(c,d) |                                     |
|     | s_(a,d) s_(b,d) s_(c,d) s_(d,d) |                                     |
|                                                                             |
|             4       4                                                       |
|o3 : Matrix R  <--- R                                                        |
+-----------------------------------------------------------------------------+
|i4 : L = directedEdgesMatrix(R,G)                                            |
|                                                                             |
|o4 = | 0 0 0       0       |                                                 |
|     | 0 0 l_(b,c) l_(b,d) |                                                 |
|     | 0 0 0       l_(c,d) |                                                 |
|     | 0 0 0       0       |                                                 |
|                                                                             |
|             4       4                                                       |
|o4 : Matrix R  <--- R                                                        |
+-----------------------------------------------------------------------------+
|i5 : W = bidirectedEdgesMatrix(R,G)                                          |
|                                                                             |
|o5 = | p_(a,a) 0       0       p_(a,d) |                                     |
|     | 0       p_(b,b) 0       0       |                                     |
|     | 0       0       p_(c,c) 0       |                                     |
|     | p_(a,d) 0       0       p_(d,d) |                                     |
|                                                                             |
|             4       4                                                       |
|o5 : Matrix R  <--- R                                                        |
+-----------------------------------------------------------------------------+
|i6 : M = gaussianParametrization(R,G)                                        |
|                                                                             |
|o6 = | p_(a,a) 0                                                             |
|     | 0       p_(b,b)                                                       |
|     | 0       l_(b,c)p_(b,b)                                                |
|     | p_(a,d) l_(b,c)l_(c,d)p_(b,b)+l_(b,d)p_(b,b)                          |
|     ------------------------------------------------------------------------|
|     0                                                                       |
|     l_(b,c)p_(b,b)                                                          |
|     l_(b,c)^2p_(b,b)+p_(c,c)                                                |
|     l_(b,c)^2l_(c,d)p_(b,b)+l_(b,c)l_(b,d)p_(b,b)+l_(c,d)p_(c,c)            |
|     ------------------------------------------------------------------------|
|     p_(a,d)                                                                 |
|     l_(b,c)l_(c,d)p_(b,b)+l_(b,d)p_(b,b)                                    |
|     l_(b,c)^2l_(c,d)p_(b,b)+l_(b,c)l_(b,d)p_(b,b)+l_(c,d)p_(c,c)            |
|     l_(b,c)^2l_(c,d)^2p_(b,b)+2l_(b,c)l_(b,d)l_(c,d)p_(b,b)+l_(b,d)^2p_(b,b |
|     ------------------------------------------------------------------------|
|                                |                                            |
|                                |                                            |
|                                |                                            |
|     )+l_(c,d)^2p_(c,c)+p_(d,d) |                                            |
|                                                                             |
|             4       4                                                       |
|o6 : Matrix R  <--- R                                                        |
+-----------------------------------------------------------------------------+
|i7 : J = delete(0_R, flatten entries (L|W))                                  |
|                                                                             |
|o7 = {p   , p   , l   , l   , p   , l   , p   , p   , p   }                  |
|       a,a   a,d   b,c   b,d   b,b   c,d   c,c   a,d   d,d                   |
|                                                                             |
|o7 : List                                                                    |
+-----------------------------------------------------------------------------+
|i8 : eliminate(J, ideal(S-M))                                                |
|                                                                             |
|o8 = ideal (s   , s   )                                                      |
|             a,c   a,b                                                       |
|                                                                             |
|o8 : Ideal of R                                                              |
+-----------------------------------------------------------------------------+

This next example shows how to use the option SimpleTreks,
to compute a parametrization using simple treks instead of all treks. The
resulting covariance matrix has diagonal entries equal to 1.

+-----------------------------------------------------------------------------+
|i9 : G = mixedGraph(digraph {{b,{c,d}},{c,{d}}},bigraph {{a,d}})             |
|                                                                             |
|o9 = MixedGraph{Bigraph => Bigraph{a => set {d}}   }                         |
|                                   d => set {a}                              |
|                Digraph => Digraph{b => set {c, d}}                          |
|                                   c => set {d}                              |
|                                   d => set {}                               |
|                Graph => Graph{}                                             |
|                                                                             |
|o9 : MixedGraph                                                              |
+-----------------------------------------------------------------------------+
|i10 : R = gaussianRing G                                                     |
|                                                                             |
|o10 = R                                                                      |
|                                                                             |
|o10 : PolynomialRing                                                         |
+-----------------------------------------------------------------------------+
|i11 : M = gaussianParametrization(R,G,SimpleTreks=>true)                     |
|                                                                             |
|o11 = | 1       0                      0                                     |
|      | 0       1                      l_(b,c)                               |
|      | 0       l_(b,c)                1                                     |
|      | p_(a,d) l_(b,c)l_(c,d)+l_(b,d) l_(b,c)l_(b,d)+l_(c,d)                |
|      -----------------------------------------------------------------------|
|      p_(a,d)                |                                               |
|      l_(b,c)l_(c,d)+l_(b,d) |                                               |
|      l_(b,c)l_(b,d)+l_(c,d) |                                               |
|      1                      |                                               |
|                                                                             |
|              4       4                                                      |
|o11 : Matrix R  <--- R                                                       |
+-----------------------------------------------------------------------------+

See also
========

  * covarianceMatrix -- the covariance matrix of a
    gaussian graphical model
  * directedEdgesMatrix -- the matrix corresponding
    to the directed edges of a mixed graph
  * bidirectedEdgesMatrix -- the matrix
    corresponding to the bidirected edges of a mixed graph
  * trekSeparation -- the trek separation statements of
    a mixed graph

Ways to use gaussianParametrization :
=====================================

  * gaussianParametrization(Ring,MixedGraph)

gaussianRing -- ring of gaussian correlations on n random variables
*******************************************************************

Synopsis
========

  * Usage:R = gaussianRing n or R = gaussianRing G or
    gaussianRing(n,Coefficients=>Ring) or gaussianRing(n,Variable=>Symbol)
  * Inputs:
      * n, an integer (Macaulay2Doc), the number of random variables
      * G, an object of class Digraph (Graphs), a directed
        acyclic graph, or an object of class MixedGraph (Graphs),
        with directed and bidirected edges
  * Optional inputs (Macaulay2Doc),:
      * Coefficients => ...,  -- ring of gaussian
        correlations on n random variables
      * VariableName => ...,  -- ring of gaussian
        correlations on n random variables
  * Outputs:
      * R, a ring (Macaulay2Doc), a ring with indeterminates
        $s_{(i,j)}$ for $1 \leq i \leq j \leq n$, and additionally $l_{(i,j)},
        w_{(i,j)}$ for mixed graphs

Description
===========

The routines  gaussianIdeal, and trekIdeal,
require that the ring be created by this function.

+-----------------------------------------------------------------------------+
|i1 : R = gaussianRing 5;                                                     |
+-----------------------------------------------------------------------------+
|i2 : gens R                                                                  |
|                                                                             |
|o2 = {s   , s   , s   , s   , s   , s   , s   , s   , s   , s   , s   , s   ,|
|       1,1   1,2   1,3   1,4   1,5   2,2   2,3   2,4   2,5   3,3   3,4   3,5 |
|     ------------------------------------------------------------------------|
|     s   , s   , s   }                                                       |
|      4,4   4,5   5,5                                                        |
|                                                                             |
|o2 : List                                                                    |
+-----------------------------------------------------------------------------+
|i3 : covarianceMatrix R                                                      |
|                                                                             |
|o3 = | s_(1,1) s_(1,2) s_(1,3) s_(1,4) s_(1,5) |                             |
|     | s_(1,2) s_(2,2) s_(2,3) s_(2,4) s_(2,5) |                             |
|     | s_(1,3) s_(2,3) s_(3,3) s_(3,4) s_(3,5) |                             |
|     | s_(1,4) s_(2,4) s_(3,4) s_(4,4) s_(4,5) |                             |
|     | s_(1,5) s_(2,5) s_(3,5) s_(4,5) s_(5,5) |                             |
|                                                                             |
|             5       5                                                       |
|o3 : Matrix R  <--- R                                                        |
+-----------------------------------------------------------------------------+

For mixed graphs, there is a variable $l_{(i,j)}$ for each directed edge i->j,
a variable $w_{(i,i)}$ for each node i, and a variable $w_{(i,j)}$ for each
bidirected edge i<->j.

+-----------------------------------------------------------------------------+
|i4 : G = mixedGraph(digraph {{b,{c,d}},{c,{d}}},bigraph {{a,d}})             |
|                                                                             |
|o4 = MixedGraph{Bigraph => Bigraph{a => set {d}}   }                         |
|                                   d => set {a}                              |
|                Digraph => Digraph{b => set {c, d}}                          |
|                                   c => set {d}                              |
|                                   d => set {}                               |
|                Graph => Graph{}                                             |
|                                                                             |
|o4 : MixedGraph                                                              |
+-----------------------------------------------------------------------------+
|i5 : R = gaussianRing G                                                      |
|                                                                             |
|o5 = R                                                                       |
|                                                                             |
|o5 : PolynomialRing                                                          |
+-----------------------------------------------------------------------------+
|i6 : gens R                                                                  |
|                                                                             |
|o6 = {l   , l   , l   , p   , p   , p   , p   , p   , s   , s   , s   , s   ,|
|       b,c   b,d   c,d   a,a   b,b   c,c   d,d   a,d   a,a   a,b   a,c   a,d |
|     ------------------------------------------------------------------------|
|     s   , s   , s   , s   , s   , s   }                                     |
|      b,b   b,c   b,d   c,c   c,d   d,d                                      |
|                                                                             |
|o6 : List                                                                    |
+-----------------------------------------------------------------------------+
|i7 : covarianceMatrix(R,G)                                                   |
|                                                                             |
|o7 = | s_(a,a) s_(a,b) s_(a,c) s_(a,d) |                                     |
|     | s_(a,b) s_(b,b) s_(b,c) s_(b,d) |                                     |
|     | s_(a,c) s_(b,c) s_(c,c) s_(c,d) |                                     |
|     | s_(a,d) s_(b,d) s_(c,d) s_(d,d) |                                     |
|                                                                             |
|             4       4                                                       |
|o7 : Matrix R  <--- R                                                        |
+-----------------------------------------------------------------------------+
|i8 : directedEdgesMatrix(R,G)                                                |
|                                                                             |
|o8 = | 0 0 0       0       |                                                 |
|     | 0 0 l_(b,c) l_(b,d) |                                                 |
|     | 0 0 0       l_(c,d) |                                                 |
|     | 0 0 0       0       |                                                 |
|                                                                             |
|             4       4                                                       |
|o8 : Matrix R  <--- R                                                        |
+-----------------------------------------------------------------------------+
|i9 : bidirectedEdgesMatrix(R,G)                                              |
|                                                                             |
|o9 = | p_(a,a) 0       0       p_(a,d) |                                     |
|     | 0       p_(b,b) 0       0       |                                     |
|     | 0       0       p_(c,c) 0       |                                     |
|     | p_(a,d) 0       0       p_(d,d) |                                     |
|                                                                             |
|             4       4                                                       |
|o9 : Matrix R  <--- R                                                        |
+-----------------------------------------------------------------------------+

See also
========

  * gaussianIdeal -- correlation ideal of a Bayesian
    network of joint Gaussian variables
  * covarianceMatrix -- the covariance matrix of a
    gaussian graphical model
  * directedEdgesMatrix -- the matrix corresponding
    to the directed edges of a mixed graph
  * bidirectedEdgesMatrix -- the matrix
    corresponding to the bidirected edges of a mixed graph
  * trekIdeal -- the edge elimination ideal of a directed
    graph, or the trek separation ideal of a mixed graph

Ways to use gaussianRing :
==========================

  * gaussianRing(Digraph)
  * gaussianRing(MixedGraph)
  * gaussianRing(ZZ)

globalMarkov -- Global Markov statements for a directed graph.
**************************************************************

Synopsis
========

  * Usage:globalMarkov G
  * Inputs:
      * G, an object of class Digraph (Graphs),
  * Outputs:
      * L, a list (Macaulay2Doc), whose entries are triples {A,B,C}
        representing global Markov  conditional independence statements of the
        form ''A is independent of B given C'' that hold for G.

Description
===========

Given a directed graph G, global Markov states that A is independent of B given
C for every triple of sets of vertices A, B, and C, such that A and B are
$d$-separated by C (in the graph G).\break

The global independent statements are computed using the Bayes ball algorithm,
as described in the paper "Bayes-Ball: The Rational Pastime (for Determining
Irrelevance and Requisite Information in Belief Networks and Influence
Diagrams)" by Ross D. Shachter.

For example, for the digraph D on 4 vertices with edges a->b, a->c, b->c, and
b->d, we get the following global Markov statements:

+-------------------------------------------------------+
|i1 : D = digraph {{a,{b,c}}, {b,{c,d}}, {c,{}}, {d,{}}}|
|                                                       |
|o1 = Digraph{a => set {b, c}}                          |
|             b => set {c, d}                           |
|             c => set {}                               |
|             d => set {}                               |
|                                                       |
|o1 : Digraph                                           |
+-------------------------------------------------------+
|i2 : L = globalMarkov D                                |
|                                                       |
|o2 = {{{a, c}, {d}, {b}}}                              |
|                                                       |
|o2 : List                                              |
+-------------------------------------------------------+

Note that the method displays only non-redundant statements.

Caveat
======

See also
========

  * localMarkov -- Local Markov statements for a directed
    graph.
  * pairMarkov -- Pairwise Markov statements for a directed
    graph.

Ways to use globalMarkov :
==========================

  * globalMarkov(Digraph)

hiddenMap -- Creates a linear map from a ring of probability distributions among observed discrete random variables into a ring of probability distributions among observed variables and one hidden variable specified by the integer input.
*********************************************************************************************************************************************************************************************************************************************

Synopsis
========

  * Usage:phi = hiddenMap(i,R)
  * Inputs:
      * i, an integer (Macaulay2Doc), the index corresponding to the
        hidden random variable
      * R, a ring (Macaulay2Doc), a Markov ring
  * Outputs:
      * phi, a ring map (Macaulay2Doc),

Description
===========

A linear map from a ring of probability distributions among observed discrete
random variables into a ring of probability distributions among observed
variables and one hidden variable specified by the integer input. This method
is used to work with Bayesian networks with hidden variables. For more details
see the paper "Algebraic Geometry of Bayesian Networks" by Garcia, Stillman,
and Sturmfels.

+-----------------------------------------------------------------------------+
|i1 : hiddenMap(1,markovRing(2,3,2))                                          |
|                                                                             |
|o1 = map(QQ[p     , p     , p     , p     , p     , p     , p     , p     , p|
|             1,1,1   1,1,2   1,2,1   1,2,2   1,3,1   1,3,2   2,1,1   2,1,2   |
|                                                                             |
|o1 : RingMap QQ[p     , p     , p     , p     , p     , p     , p     , p    |
|                 1,1,1   1,1,2   1,2,1   1,2,2   1,3,1   1,3,2   2,1,1   2,1,|
|-----------------------------------------------------------------------------|
|     , p     , p     , p     ],QQ[p   ,                                      |
|2,2,1   2,2,2   2,3,1   2,3,2      1,1                                       |
|                                                                             |
| , p     , p     , p     , p     ] <---                                      |
|2   2,2,1   2,2,2   2,3,1   2,3,2                                            |
|-----------------------------------------------------------------------------|
|p   , p   , p   , p   , p   ],{p      + p     , p      + p     , p      +    |
| 1,2   2,1   2,2   3,1   3,2    1,1,1    2,1,1   1,1,2    2,1,2   1,2,1      |
|                                                                             |
|QQ[p   , p   , p   , p   , p   , p   ]                                       |
|    1,1   1,2   2,1   2,2   3,1   3,2                                        |
|-----------------------------------------------------------------------------|
|p     , p      + p     , p      + p     , p      + p     })                  |
| 2,2,1   1,2,2    2,2,2   1,3,1    2,3,1   1,3,2    2,3,2                    |
+-----------------------------------------------------------------------------+

See also
========

  * marginMap -- Generates a linear map on joint
    probabilities for discrete variables that replaces marginals for
    indeterminates.

Ways to use hiddenMap :
=======================

  * hiddenMap(ZZ,Ring)

identifyParameters -- solving the identifiability problem: expressing each parameter in terms of covariances
************************************************************************************************************

Synopsis
========

  * Usage:H = identifyParameters(R,G)
  * Inputs:
      * R, a ring (Macaulay2Doc), which should be a gaussianRing
      * G, an object of class MixedGraph (Graphs), mixed
        graph with directed and bidirected edges
  * Outputs:
      * H, a hash table (Macaulay2Doc), where H#p is the ideal
        of equations involving only the parameter p and the covariances
        s_{(i,j)}

Description
===========

If H#p contains a linear equation a*p+b where a is always nonzero, then p is
identifiable.

If H#p contains a linear equation a*p+b where a may be zero, then p is
generically identifiable.

If H#p contains a polynomial in p of degree d, then p is algebraically
d-identifiable.

If H#p does not contain any polynomial in p, then p is not generically
identifiable.

+-----------------------------------------------------------------------------+
|i1 : G = mixedGraph(digraph {{b,{c,d}},{c,{d}}},bigraph {{a,d}})             |
|                                                                             |
|o1 = MixedGraph{Bigraph => Bigraph{a => set {d}}   }                         |
|                                   d => set {a}                              |
|                Digraph => Digraph{b => set {c, d}}                          |
|                                   c => set {d}                              |
|                                   d => set {}                               |
|                Graph => Graph{}                                             |
|                                                                             |
|o1 : MixedGraph                                                              |
+-----------------------------------------------------------------------------+
|i2 : R = gaussianRing G                                                      |
|                                                                             |
|o2 = R                                                                       |
|                                                                             |
|o2 : PolynomialRing                                                          |
+-----------------------------------------------------------------------------+
|i3 : H = identifyParameters(R,G)                                             |
|                                                                             |
|o3 = HashTable{l    => ideal (s   , s   , l   s    - s   )                   |
|                b,c            a,c   a,b   b,c b,b    b,c                    |
|                                               2                             |
|               l    => ideal (s   , s   , l   s    - l   s   s    + s   s    |
|                b,d            a,c   a,b   b,d b,c    b,d b,b c,c    b,d c,c |
|                                               2                             |
|               l    => ideal (s   , s   , l   s    - l   s   s    - s   s    |
|                c,d            a,c   a,b   c,d b,c    c,d b,b c,c    b,c b,d |
|               p    => ideal (s   , s   , p    - s   )                       |
|                a,a            a,c   a,b   a,a    a,a                        |
|               p    => ideal (s   , s   , p    - s   )                       |
|                a,d            a,c   a,b   a,d    a,d                        |
|               p    => ideal (s   , s   , p    - s   )                       |
|                b,b            a,c   a,b   b,b    b,b                        |
|                                                      2                      |
|               p    => ideal (s   , s   , p   s    + s    - s   s   )        |
|                c,c            a,c   a,b   c,c b,b    b,c    b,b c,c         |
|                                               2                     2       |
|               p    => ideal (s   , s   , p   s    - p   s   s    - s   s    |
|                d,d            a,c   a,b   d,d b,c    d,d b,b c,c    b,d c,c |
|                                                                             |
|o3 : HashTable                                                               |
|-----------------------------------------------------------------------------|
|                                                     }                       |
|                                                                             |
|                                                                             |
|- s   s   )                                                                  |
|   b,c c,d                                                                   |
|                                                                             |
|+ s   s   )                                                                  |
|   b,b c,d                                                                   |
|                                                                             |
|                                                                             |
|                                                                             |
|                                                                             |
|                                                                             |
|                                                                             |
|                                                                             |
|                                                                             |
|                                                                             |
|                       2      2                                              |
|+ 2s   s   s    - s   s    - s   s    + s   s   s   )                        |
|    b,c b,d c,d    b,b c,d    b,c d,d    b,b c,c d,d                         |
+-----------------------------------------------------------------------------+

See also
========

  * gaussianRing -- ring of gaussian correlations on n
    random variables

Ways to use identifyParameters :
================================

  * identifyParameters(Ring,MixedGraph)

localMarkov -- Local Markov statements for a directed graph.
************************************************************

Synopsis
========

  * Usage:localMarkov G
  * Inputs:
      * G, an object of class Digraph (Graphs),
  * Outputs:
      * L, a list (Macaulay2Doc), whose entries are triples {A,B,C}
        representing local Markov  conditional independence statements of the
        form ''A is independent of B given C'' that hold for G.

Description
===========

Given a directed graph G, local Markov statements are of the form \{$v$,
nondescendents($v$) - parents($v$), parents($v$)\} . That is, every vertex $v$
of G is independent of its nondescendents (excluding parents) given the
parents.

For example, for the digraph D on 4 vertices with edges a->b, a->c, b->c, and
b->d, we get the following local Markov statements:

+-------------------------------------------------------+
|i1 : D = digraph {{a,{b,c}}, {b,{c,d}}, {c,{}}, {d,{}}}|
|                                                       |
|o1 = Digraph{a => set {b, c}}                          |
|             b => set {c, d}                           |
|             c => set {}                               |
|             d => set {}                               |
|                                                       |
|o1 : Digraph                                           |
+-------------------------------------------------------+
|i2 : L = localMarkov D                                 |
|                                                       |
|o2 = {{{a, c}, {d}, {b}}}                              |
|                                                       |
|o2 : List                                              |
+-------------------------------------------------------+

Note that the method displays only non-redundant statements.

See also
========

  * pairMarkov -- Pairwise Markov statements for a directed
    graph.
  * globalMarkov -- Global Markov statements for a
    directed graph.

Ways to use localMarkov :
=========================

  * localMarkov(Digraph)

marginMap -- Generates a linear map on joint probabilities for discrete variables that replaces marginals for indeterminates.
*****************************************************************************************************************************

Synopsis
========

  * Usage:phi = marginMap(i,R)
  * Inputs:
      * i, an integer (Macaulay2Doc), the index of the variable to
        marginalize
      * R, a ring (Macaulay2Doc), a Markov ring
  * Outputs:
      * phi, a ring map (Macaulay2Doc),

Description
===========

Returns the ring map F : R -> R such that $ F p_{u_1,u_2,..., +,...,u_n} =
p_{u_1,u_2,...,1,...,u_n} $ and $ F p_{u1,u2,..., j,...,un} = p_{u1,u2,...,
j,...,un} $, for $ j\geq 2 $.

+-----------------------------------------------------------------------------+
|i1 : marginMap(1,markovRing(3,2))                                            |
|                                                                             |
|o1 = map(QQ[p   , p   , p   , p   , p   , p   ],QQ[p   ,                     |
|             1,1   1,2   2,1   2,2   3,1   3,2      1,1                      |
|                                                                             |
|o1 : RingMap QQ[p   , p   , p   , p   , p   , p   ] <---                     |
|                 1,1   1,2   2,1   2,2   3,1   3,2                           |
|-----------------------------------------------------------------------------|
|p   , p   , p   , p   , p   ],{p    - p    - p   , p    - p    - p   , p   , |
| 1,2   2,1   2,2   3,1   3,2    1,1    2,1    3,1   1,2    2,2    3,2   2,1  |
|                                                                             |
|QQ[p   , p   , p   , p   , p   , p   ]                                       |
|    1,1   1,2   2,1   2,2   3,1   3,2                                        |
|-----------------------------------------------------------------------------|
|p   , p   , p   })                                                           |
| 2,2   3,1   3,2                                                             |
+-----------------------------------------------------------------------------+

This linear transformation simplifies ideals and/or polynomials involving $
p_{u_1,u_2,..., +,...,u_n} $. In some cases, the resulting ideals are toric
ideals as the example at the beginning of the documentation. For more details
see the paper "Algebraic Geometry of Bayesian Networks" by Garcia, Stillman,
and Sturmfels.

See also
========

  * hiddenMap -- Creates a linear map from a ring of
    probability distributions among observed discrete random variables into a
    ring of probability distributions among observed variables and one hidden
    variable specified by the integer input.

Ways to use marginMap :
=======================

  * marginMap(ZZ,Ring)

markovIdeal -- Ideal of constraints associated to a list of independent statements among discrete random variables.
*******************************************************************************************************************

Synopsis
========

  * Usage:markovIdeal(R,G,S)
  * Inputs:
      * R, a ring (Macaulay2Doc), R must be a markovRing
      * G, an object of class Digraph (Graphs), directed acyclic
        graph
      * S, a list (Macaulay2Doc), (markovIdeal,Ring,Digraph,List)
  * Outputs:
      * an ideal (Macaulay2Doc),

Description
===========

This method computes the ideal of constraints associated to a list of
independent statements among discrete random variables. These constraints are
the 2x2 minors of the matrices computed by markovMatrices.

+-----------------------------------------------------------------------------+
|i1 : G = digraph { {1, {2,3}}, {2, {4}}, {3, {4}} }                          |
|                                                                             |
|o1 = Digraph{1 => set {2, 3}}                                                |
|             2 => set {4}                                                    |
|             3 => set {4}                                                    |
|             4 => set {}                                                     |
|                                                                             |
|o1 : Digraph                                                                 |
+-----------------------------------------------------------------------------+
|i2 : S = localMarkov G                                                       |
|                                                                             |
|o2 = {{{2}, {3}, {1}}, {{1}, {4}, {2, 3}}}                                   |
|                                                                             |
|o2 : List                                                                    |
+-----------------------------------------------------------------------------+
|i3 : R = markovRing (2,2,2,2)                                                |
|                                                                             |
|o3 = R                                                                       |
|                                                                             |
|o3 : PolynomialRing                                                          |
+-----------------------------------------------------------------------------+
|i4 : I = markovIdeal (R,G,S)                                                 |
|                                                                             |
|o4 = ideal (- 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         |
|     ------------------------------------------------------------------------|
|     p       p        + p       p        + p       p        +                |
|      1,1,2,2 1,2,1,2    1,1,1,1 1,2,2,1    1,1,1,2 1,2,2,1                  |
|     ------------------------------------------------------------------------|
|     p       p        + p       p       , - p       p        -               |
|      1,1,1,1 1,2,2,2    1,1,1,2 1,2,2,2     2,1,2,1 2,2,1,1                 |
|     ------------------------------------------------------------------------|
|     p       p        - p       p        - p       p        +                |
|      2,1,2,2 2,2,1,1    2,1,2,1 2,2,1,2    2,1,2,2 2,2,1,2                  |
|     ------------------------------------------------------------------------|
|     p       p        + p       p        + p       p        +                |
|      2,1,1,1 2,2,2,1    2,1,1,2 2,2,2,1    2,1,1,1 2,2,2,2                  |
|     ------------------------------------------------------------------------|
|     p       p       , - p       p        + p       p       , -              |
|      2,1,1,2 2,2,2,2     1,1,1,2 2,1,1,1    1,1,1,1 2,1,1,2                 |
|     ------------------------------------------------------------------------|
|     p       p        + p       p       , - p       p        +               |
|      1,1,2,2 2,1,2,1    1,1,2,1 2,1,2,2     1,2,1,2 2,2,1,1                 |
|     ------------------------------------------------------------------------|
|     p       p       , - p       p        + p       p       )                |
|      1,2,1,1 2,2,1,2     1,2,2,2 2,2,2,1    1,2,2,1 2,2,2,2                 |
|                                                                             |
|o4 : Ideal of R                                                              |
+-----------------------------------------------------------------------------+

See also
========

  * markovRing -- Ring of probability distributions on
    several discrete random variables.
  * markovMatrices -- The matrices whose minors form the
    ideal associated to the list of independence statements of the graph.

Ways to use markovIdeal :
=========================

  * markovIdeal(Ring,Digraph,List)

markovMatrices -- The matrices whose minors form the ideal associated to the list of independence statements of the graph.
**************************************************************************************************************************

Synopsis
========

  * Usage:markovMatrices(R,G,S)
  * Inputs:
      * R, a ring (Macaulay2Doc), R must be a markovRing
      * G, an object of class Digraph (Graphs), directed acyclic
        graph
      * S, a list (Macaulay2Doc), a list of independence statements
        that are true for the DAG G
  * Outputs:
      * a list (Macaulay2Doc), whose elements are instances of
        Matrix. Minors of these matrices form the independence ideal for the
        independent statements of the Digraph.

Description
===========

List of matrices encoding the independent statements of the Digraph G. The 2x2
minors of each matrix generate the ideal of independence constraints of the
Digraph G. the  This method is used in markovIdeals. But it is exported to be
able to see constraints not as polynomials but as minors of matrices in this
list.

+-----------------------------------------------------------------------------+
|i1 : G = digraph { {1, {2,3}}, {2, {4}}, {3, {4}} }                          |
|                                                                             |
|o1 = Digraph{1 => set {2, 3}}                                                |
|             2 => set {4}                                                    |
|             3 => set {4}                                                    |
|             4 => set {}                                                     |
|                                                                             |
|o1 : Digraph                                                                 |
+-----------------------------------------------------------------------------+
|i2 : S = localMarkov G                                                       |
|                                                                             |
|o2 = {{{2}, {3}, {1}}, {{1}, {4}, {2, 3}}}                                   |
|                                                                             |
|o2 : List                                                                    |
+-----------------------------------------------------------------------------+
|i3 : R = markovRing (4:2)                                                    |
|                                                                             |
|o3 = R                                                                       |
|                                                                             |
|o3 : PolynomialRing                                                          |
+-----------------------------------------------------------------------------+
|i4 : L = markovMatrices (R,G,S)                                              |
|                                                                             |
|o4 = {| p_(1,1,1,1)+p_(1,1,1,2) p_(1,1,2,1)+p_(1,1,2,2) |, |                 |
|      | p_(1,2,1,1)+p_(1,2,1,2) p_(1,2,2,1)+p_(1,2,2,2) |  |                 |
|     ------------------------------------------------------------------------|
|     p_(2,1,1,1)+p_(2,1,1,2) p_(2,1,2,1)+p_(2,1,2,2) |, | p_(1,1,1,1)        |
|     p_(2,2,1,1)+p_(2,2,1,2) p_(2,2,2,1)+p_(2,2,2,2) |  | p_(2,1,1,1)        |
|     ------------------------------------------------------------------------|
|     p_(1,1,1,2) |, | p_(1,1,2,1) p_(1,1,2,2) |, | p_(1,2,1,1) p_(1,2,1,2) |,|
|     p_(2,1,1,2) |  | p_(2,1,2,1) p_(2,1,2,2) |  | p_(2,2,1,1) p_(2,2,1,2) | |
|     ------------------------------------------------------------------------|
|     | p_(1,2,2,1) p_(1,2,2,2) |}                                            |
|     | p_(2,2,2,1) p_(2,2,2,2) |                                             |
|                                                                             |
|o4 : List                                                                    |
+-----------------------------------------------------------------------------+

See also
========

  * markovRing -- Ring of probability distributions on
    several discrete random variables.
  * markovIdeal -- Ideal of constraints associated to a
    list of independent statements among discrete random variables.

Ways to use markovMatrices :
============================

  * markovMatrices(Ring,Digraph,List)

markovRing -- Ring of probability distributions on several discrete random variables.
*************************************************************************************

Synopsis
========

  * Usage:markovRing(d) or markovRing(d,Coefficients=>Ring) or
    markovRing(d,Variable=>Symbol)
  * Inputs:
      * d, a sequence (Macaulay2Doc), with positive integer
        entries (d1,...,dr)
  * Optional inputs (Macaulay2Doc),:
      * Coefficients => ...,  -- Ring of probability
        distributions on several discrete random variables.
      * VariableName => ...,  -- Ring of probability
        distributions on several discrete random variables.
  * Outputs:
      * R, a ring (Macaulay2Doc), A polynomial ring with
        d1*d2*...*dr variables $p_{i_1,...,i_r}$, with each $i_j$ satisfying
        $1\leq i_j \leq d_j$.
  * Consequences:
      * Information about this sequence of integers is placed into the ring,
        and is used by other functions in this package.  Also, at most one ring
        for each such sequence is created: the results are cached.

Description
===========

The sequence $d$ represents the number of states each discrete random variable
can take. For example, if there are four random variables with the following
state space sizes

+-----------------+
|i1 : d=(2,3,4,5) |
|                 |
|o1 = (2, 3, 4, 5)|
|                 |
|o1 : Sequence    |
+-----------------+

the corresponding ring will have as variables all the possible joint
probability distributions for the four variables:

+-----------------------------------------------------------------+
|i2 : R = markovRing d;                                           |
+-----------------------------------------------------------------+
|i3 : numgens R                                                   |
|                                                                 |
|o3 = 120                                                         |
+-----------------------------------------------------------------+
|i4 : R_0, R_1, R_119 --here are some of the variables in the ring|
|                                                                 |
|o4 = (p       , p       , p       )                              |
|       1,1,1,1   1,1,1,2   2,3,4,5                               |
|                                                                 |
|o4 : Sequence                                                    |
+-----------------------------------------------------------------+

If no coefficient choice is specified, the polynomial ring is created over the
rationals.

+----------------------+
|i5 : coefficientRing R|
|                      |
|o5 = QQ               |
|                      |
|o5 : Ring             |
+----------------------+

If we prefer to have a different base field, the following command can be used:

+--------------------------------------------+
|i6 : Rnew = markovRing (d,Coefficients=>CC);|
+--------------------------------------------+
|i7 : coefficientRing Rnew                   |
|                                            |
|o7 = CC                                     |
|       53                                   |
|                                            |
|o7 : ComplexField                           |
+--------------------------------------------+

We might prefer to give different names to our variables. The letter ''p''
suggests a joint probability, but it might be useful to create a new ring where
the variables have changed. This can easily be done with the following option:

+-----------------------------------------------------+
|i8 : d=(1,2);                                        |
+-----------------------------------------------------+
|i9 : markovRing (d,VariableName=>q);                 |
+-----------------------------------------------------+
|i10 : vars oo --here is the list of variables.       |
|                                                     |
|o10 = | q_(1,1) q_(1,2) |                            |
|                                                     |
|                             1                      2|
|o10 : Matrix (QQ[q   , q   ])  <--- (QQ[q   , q   ]) |
|                  1,1   1,2              1,1   1,2   |
+-----------------------------------------------------+

Ways to use markovRing :
========================

  * markovRing(Sequence)

pairMarkov -- Pairwise Markov statements for a directed graph.
**************************************************************

Synopsis
========

  * Usage:pairMarkov G
  * Inputs:
      * G, an object of class Digraph (Graphs),
  * Outputs:
      * L, a list (Macaulay2Doc), whose entries are triples {A,B,C}
        representing pairwise Markov  conditional independence statements of
        the form ''A is independent of B given C'' that hold for G.

Description
===========

Given a directed graph G, pairwise Markov statements are statements of the form
\{v,w,nondescendents(G,v)-w\} for each vertex v of G. In other words, for every
vertex v of G and all nondescendents w of v, v is independent of w given all
other nondescendents.

For example, for the digraph D on $4$ vertices with edges a->b, a->c, b->c, and
b->d, we get the following pairwise Markov statements:

+-------------------------------------------------------+
|i1 : D = digraph {{a,{b,c}}, {b,{c,d}}, {c,{}}, {d,{}}}|
|                                                       |
|o1 = Digraph{a => set {b, c}}                          |
|             b => set {c, d}                           |
|             c => set {}                               |
|             d => set {}                               |
|                                                       |
|o1 : Digraph                                           |
+-------------------------------------------------------+
|i2 : L = pairMarkov D                                  |
|                                                       |
|o2 = {{{c}, {d}, {b, a}}, {{a}, {d}, {b, c}}}          |
|                                                       |
|o2 : List                                              |
+-------------------------------------------------------+

Note that the method displays only non-redundant statements.

See also
========

  * localMarkov -- Local Markov statements for a directed
    graph.
  * globalMarkov -- Global Markov statements for a
    directed graph.

Ways to use pairMarkov :
========================

  * pairMarkov(Digraph)

SimpleTreks -- optional input to choose the type of parametrization in @TO gaussianParametrization@
***************************************************************************************************

Description
===========

Put {\tt SimpleTreks => true} as an argument in the function
gaussianParametrization, to compute a parametrization
of the covariance matrix S=(s_{(i,j)}) where s_{(i,j)} is the sum of monomials
corresponding to simple treks between vertices i and j. Here, a simple trek is
a trek (P_L,P_R) where the paths P_L and P_R do not have any common vertices
except perhaps at their source. See trekSeparation, for
the definition of a trek.

If the option {\tt SimpleTreks => false} is used, then the sum is over all
treks, and not just simple treks.

Functions with optional argument named SimpleTreks :
====================================================

  * gaussianParametrization(..., SimpleTreks => ...), see
    gaussianParametrization, -- the parametrization of
    the covariance matrix in terms of treks

See also
========

  * gaussianParametrization -- the
    parametrization of the covariance matrix in terms of treks

For the programmer
==================

The object SimpleTreks, is a symbol (Macaulay2Doc).

trekIdeal -- the edge elimination ideal of a directed graph, or the trek separation ideal of a mixed graph
**********************************************************************************************************

Synopsis
========

  * Usage:I = trekIdeal(R,G) or I = trekIdeal(R,G,S)
  * Inputs:
      * R, a ring (Macaulay2Doc), which should be a gaussianRing
      * G, an object of class Digraph (Graphs), a directed
        acyclic graph, or an object of class MixedGraph (Graphs),
        with directed and bidirected edges
      * S, a list (Macaulay2Doc), trek separation statements that
        hold for a mixed graph G
  * Outputs:
      * I, an ideal (Macaulay2Doc), the ideal attained by
        eliminating edge parameters for a directed graph G, or the trek
        separation ideal implied by statements S for a mixed graph G.

Description
===========

For directed acyclic graphs, the covariance $s_{(i,j)}$ can be expressed as the
sum of all monomials corresponding to treks between vertices i and j. See
gaussianParametrization, for more information on
treks. The trek ideal for a directed acyclic graph consists of polynomial
relations between the covariances after eliminating parameters corresponding to
the directed edges.

+--------------------------------------------------------------------------+
|i1 : G = digraph {{a,{b,c}}, {b,{c,d}}, {c,{}}, {d,{}}}                   |
|                                                                          |
|o1 = Digraph{a => set {b, c}}                                             |
|             b => set {c, d}                                              |
|             c => set {}                                                  |
|             d => set {}                                                  |
|                                                                          |
|o1 : Digraph                                                              |
+--------------------------------------------------------------------------+
|i2 : R = gaussianRing G                                                   |
|                                                                          |
|o2 = R                                                                    |
|                                                                          |
|o2 : PolynomialRing                                                       |
+--------------------------------------------------------------------------+
|i3 : trekIdeal(R,G)                                                       |
|                                                                          |
|o3 = ideal (s   s    - s   s   , s   s    - s   s   , s   s    - s   s   )|
|             b,c b,d    b,b c,d   a,d b,c    a,b c,d   a,d b,b    a,b b,d |
|                                                                          |
|o3 : Ideal of R                                                           |
+--------------------------------------------------------------------------+

For mixed graphs, the ideal corresponding to a trek separation statement
{A,B,CA,CB} (where A,B,CA,CB are disjoint lists of vertices of G) is generated
by the r+1 x r+1 minors of the submatrix of the covariance matrix M =
(s_{(i,j)}), whose rows are in A, and whose columns are in B, and where r =
#CA+#CB.

These ideals are described in more detail by Sullivant, Talaska and Draisma in
"Trek Separation for Gaussian Graphical Models".

+-----------------------------------------------------------------------------+
|i4 : G = mixedGraph(digraph {{b,{c,d}},{c,{d}}},bigraph {{a,d}})             |
|                                                                             |
|o4 = MixedGraph{Bigraph => Bigraph{a => set {d}}   }                         |
|                                   d => set {a}                              |
|                Digraph => Digraph{b => set {c, d}}                          |
|                                   c => set {d}                              |
|                                   d => set {}                               |
|                Graph => Graph{}                                             |
|                                                                             |
|o4 : MixedGraph                                                              |
+-----------------------------------------------------------------------------+
|i5 : R = gaussianRing G                                                      |
|                                                                             |
|o5 = R                                                                       |
|                                                                             |
|o5 : PolynomialRing                                                          |
+-----------------------------------------------------------------------------+
|i6 : T = trekIdeal(R,G)                                                      |
|                                                                             |
|o6 = ideal (s   , s   , s   s    - s   s   , - s   s    + s   s   , s   s    |
|             a,c   a,b   a,c b,b    a,b b,c     a,c b,b    a,b b,c   a,c b,c |
|     ------------------------------------------------------------------------|
|     - s   s   , s   s    - s   s   )                                        |
|        a,b c,c   a,c b,d    a,b c,d                                         |
|                                                                             |
|o6 : Ideal of R                                                              |
+-----------------------------------------------------------------------------+
|i7 : ideal gens gb T                                                         |
|                                                                             |
|o7 = ideal (s   , s   )                                                      |
|             a,c   a,b                                                       |
|                                                                             |
|o7 : Ideal of R                                                              |
+-----------------------------------------------------------------------------+

See also
========

  * trekSeparation -- the trek separation statements of
    a mixed graph

Ways to use trekIdeal :
=======================

  * trekIdeal(Ring,Digraph)
  * trekIdeal(Ring,MixedGraph)
  * trekIdeal(Ring,MixedGraph,List)

trekSeparation -- the trek separation statements of a mixed graph
*****************************************************************

Synopsis
========

  * Usage:trek = trekSeparation(G)
  * Inputs:
      * G, an object of class MixedGraph (Graphs), mixed
        graph with directed and bidirected edges
  * Outputs:
      * trek, a list (Macaulay2Doc), of lists \{A,B,CA,CB\}, where
        (CA,CB) trek separates A from B

Description
===========

A trek between vertices i and j in a mixed graph G with directed and bidirected
edges is a triple (P_L,P_R) where P_L is a directed path of directed edges with
sink i and source k, P_R is a directed path of directed edges with sink j and
source l, and either k=l or there is a bidirected edge between k and l. Let
A,B,CA,CB be subsets of vertices of G.

We say that (CA,CB) trek-separates A from B in G if for every trek (P_L,P_R)
from a vertex in A to a vertex in B, either P_L contains a vertex in CA or P_R
contains a vertex in CB.

The function trekSeparation, returns a list of trek
separation statements \{A,B,CA,CB\}\,where #CA + #CB < min(#A, #B). Each
statement is maximal in the ordering where
\{A1,B1,CA,CB\}\,<\,\{A2,B2,CA,CB\}\,if A1 is a subset of A2 and B1 is a subset
of B2. Each statement is also unique up to symmetry, since \{B,A,CB,CA\}\,is a
trek separation statement if and only if \{A,B,CA,CB\}.

+-----------------------------------------------------------------------------+
|i1 : G = mixedGraph(digraph {{b,{c,d}},{c,{d}}},bigraph {{a,d}})             |
|                                                                             |
|o1 = MixedGraph{Bigraph => Bigraph{a => set {d}}   }                         |
|                                   d => set {a}                              |
|                Digraph => Digraph{b => set {c, d}}                          |
|                                   c => set {d}                              |
|                                   d => set {}                               |
|                Graph => Graph{}                                             |
|                                                                             |
|o1 : MixedGraph                                                              |
+-----------------------------------------------------------------------------+
|i2 : R = gaussianRing G                                                      |
|                                                                             |
|o2 = R                                                                       |
|                                                                             |
|o2 : PolynomialRing                                                          |
+-----------------------------------------------------------------------------+
|i3 : S = trekSeparation G                                                    |
|                                                                             |
|o3 = {{{a}, {b, c}, {}, {}}, {{a, b}, {b, c}, {}, {b}}, {{b, c}, {a, b}, {}, |
|     ------------------------------------------------------------------------|
|     {b}}, {{b, c}, {a, c}, {}, {c}}, {{b, c}, {d, a}, {}, {d}}}             |
|                                                                             |
|o3 : List                                                                    |
+-----------------------------------------------------------------------------+
|i4 : trekIdeal(R,G,S)                                                        |
|                                                                             |
|o4 = ideal (s   , s   , - s   s    + s   s   , - s   s    + s   s   , -      |
|             a,b   a,c     a,c b,b    a,b b,c     a,c b,b    a,b b,c         |
|     ------------------------------------------------------------------------|
|     s   s    + s   s   , s   s    - s   s   )                               |
|      a,c b,c    a,b c,c   a,c b,d    a,b c,d                                |
|                                                                             |
|o4 : Ideal of R                                                              |
+-----------------------------------------------------------------------------+

See also
========

  * trekIdeal -- the edge elimination ideal of a directed
    graph, or the trek separation ideal of a mixed graph

Ways to use trekSeparation :
============================

  * trekSeparation(MixedGraph)

VariableName -- Optional input to choose the letter for the variable name.
**************************************************************************

Description
===========

Put {\tt VariableName => s} for a choice of a symbol s as an argument in the
function markovRing, or gaussianRing, for
digraphs, and {\tt VariableName => \{s,l,w\}} in gaussianRing,
for mixed graphs

Functions with optional argument named VariableName :
=====================================================

  * gaussianRing(..., VariableName => ...), see gaussianRing,
    -- ring of gaussian correlations on n random variables
  * markovRing(..., VariableName => ...), see markovRing, --
    Ring of probability distributions on several discrete random variables.

See also
========

  * markovRing -- Ring of probability distributions on
    several discrete random variables.
  * gaussianRing -- ring of gaussian correlations on n
    random variables

For the programmer
==================

The object VariableName, is a symbol (Macaulay2Doc).