Macaulay2 » Documentation
Packages » AllMarkovBases :: AllMarkovBases
next | previous | forward | backward | up | index | toc

AllMarkovBases -- compute all minimal Markov Bases of a toric ideal

Description

Fix a matrix $A = (a_{i,j}) \in \ZZ^{d \times n}$ satisfying $\ker(A) \cap (\ZZ_{\ge 0})^n = \{0\}$. The toric ideal $I_A$ is the kernel of the associated monomial map $\phi_A : k[x_1, \dots, x_n] \rightarrow k[t_1, \dots, t_d]$ given by $\phi(x_i) = t_1^{a_{1,i}} t_2^{a_{2,i}} \dots t_d^{a_{d,i}}$ for each $i \in [n]$. A Markov basis is a minimal generating set for a toric ideal. Markov bases are used in Algebraic Statistics in hypothesis testing for contingency tables; for further details we refer to: M. Drton, B. Sturmfels, and S. Sullivant Lectures on Algebraic Statistics

This package computes the set of all minimal Markov bases of a given toric ideal $I_A$. We do this by using FourTiTwo to efficiently compute one Markov basis $M$. We then compute all spanning forests of the fiber graph of $A$ in the generating fibers using the well-known bijection of Prüfer. Each spanning forest corresponds to a Markov basis, which gives us an efficient way to compute the number of Markov bases of $A$ as well as produce the Markov bases. For further theoretical details, see H. Charalambous, K. Anargyros, A. Thoma Minimal systems of binomial generators and the indispensable complex of a toric ideal.

Below is an example showing how to compute all Markov bases for the matrix $A = (7 \ 8 \ 9 \ 10) \in \ZZ^{1 \times 4}$.

i1 : A = matrix "7,8,9,10";

              1       4
o1 : Matrix ZZ  <-- ZZ
 
i2 : countMarkov A

o2 = 4
 
i3 : netList markovBases A

     +--------------+
o3 = || 1 -2 1  0  ||
     || 1 -1 -1 1  ||
     || 0 1  -2 1  ||
     || 4 -1 0  -2 ||
     || 3 1  -1 -2 ||
     || 2 2  0  -3 ||
     +--------------+
     || 1 -2 1  0  ||
     || 1 -1 -1 1  ||
     || 0 1  -2 1  ||
     || 4 -1 0  -2 ||
     || 3 1  -1 -2 ||
     || 3 0  1  -3 ||
     +--------------+
     || 1 -2 1  0  ||
     || 1 -1 -1 1  ||
     || 0 1  -2 1  ||
     || 4 0  -2 -1 ||
     || 3 1  -1 -2 ||
     || 2 2  0  -3 ||
     +--------------+
     || 1 -2 1  0  ||
     || 1 -1 -1 1  ||
     || 0 1  -2 1  ||
     || 4 0  -2 -1 ||
     || 3 1  -1 -2 ||
     || 3 0  1  -3 ||
     +--------------+

The format of the output follows that of toricMarkov, so each minimal Markov basis is given by a matrix whose rows correspond to elements of the Markov basis.

If the configuration matrix has too many minimal Markov bases, then it may be convenient to use a random Markov basis. This package provides a method to produce a random minimal Markov basis that is uniformly sampled from the set of all minimal Markov bases.

i4 : A = matrix "2,3,5,7,30,31,32";

              1       7
o4 : Matrix ZZ  <-- ZZ
 
i5 : countMarkov A

o5 = 228960
 
i6 : randomMarkov A

o6 = | 1  1  -1 0  0  0  0  |
     | 3  -2 0  0  0  0  0  |
     | 2  1  0  -1 0  0  0  |
     | 3  0  2  2  -1 0  0  |
     | 0  8  0  1  0  -1 0  |
     | 11 1  0  1  0  0  -1 |

              6       7
o6 : Matrix ZZ  <-- ZZ

The package also provides methods to compute the indispensable set and universal Markov basis; see toricIndispensableSet and toricUniversalMarkov. These methods exploit the fiber graph to compute these respective sets of binomials.

References

  • B. Sturmfels. Groebner bases and Convex Polytopes. Volume 8 of University Lecture Series. American Mathematical Society, Providence, RI, 1996.
  • M. Drton, B. Sturmfels, and S. Sullivant. Lectures on Algebraic Statistics.Oberwolfach Seminar Series39 Basel, Switzerland, Birkhäuser Verlag, 2009.
  • H. Charalambous, K. Anargyros, and A. Thoma. Minimal systems of binomial generators and the indispensable complex of a toric ideal. Volume 135 of Proceedings of the American Mathematical Society2007.
  • Prüfer, H. (1918). Neuer Beweis eines Satzes über Permutationen.Arch. Math. Phys. 27: 742–744.

Menu

Authors

Version

This documentation describes version 1.0 of AllMarkovBases.

Citation

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

@misc{AllMarkovBasesSource,
  title = {{AllMarkovBases: computing all minimal Markov bases of a configuration matrix. Version~1.0}},
  author = {Alexander Milner and Oliver Clarke},
  howpublished = {A \emph{Macaulay2} package available at
    \url{https://github.com/Macaulay2/M2/tree/master/M2/Macaulay2/packages}}
}

Exports

  • Functions and commands
  • Methods
    • computeFiber(Matrix,Vector) -- see computeFiber -- compute a single fiber of configuration matrix
    • countMarkov(Matrix) -- see countMarkov -- the number of minimal Markov bases of a configuration matrix
    • fiberGraph(Matrix) -- see fiberGraph -- generating fibers of a configuration matrix
    • markovBases(Matrix) -- see markovBases -- all minimal Markov bases of a configuration matrix
    • markovBases(Matrix,Ring) -- see markovBases -- all minimal Markov bases of a configuration matrix
    • pruferSequence(List) -- see pruferSequence -- the edge set of a spanning tree corresponding to a Prüfer sequence
    • randomMarkov(Matrix) -- see randomMarkov -- get a random minimal Markov basis
    • randomMarkov(Matrix,Ring) -- see randomMarkov -- get a random minimal Markov basis
    • toricIndispensableSet(Matrix) -- see toricIndispensableSet -- the indispensable set of toric binomials
    • toricIndispensableSet(Matrix,Ring) -- see toricIndispensableSet -- the indispensable set of toric binomials
    • toricIndispensableSet(Matrix,Matrix) (missing documentation)
    • toricUniversalMarkov(Matrix) -- see toricUniversalMarkov -- the universal Markov basis
    • toricUniversalMarkov(Matrix,Ring) -- see toricUniversalMarkov -- the universal Markov basis
  • Symbols
    • FiberAlgorithm -- see computeFiber -- compute a single fiber of configuration matrix
    • ReturnConnectedComponents -- see computeFiber -- compute a single fiber of configuration matrix
    • AlwaysReturnList -- see randomMarkov -- get a random minimal Markov basis
    • NumberOfBases -- see randomMarkov -- get a random minimal Markov basis
    • ReturnFiberValues (missing documentation)

For the programmer

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

The source of this document is in AllMarkovBases.m2:680:0.