Markov Bases: How to Use Them and How to Compute Them

To run Fisher's exact test for independence, we have to find all integer tables with prescribed row sums and column sums. More generally, to run Fisher's exact test for graphical models, we have to find all n-way tables with prescribed marginals. Often, it is impossible to list all such tables explicitly, but for statistical purposes it ;suffices to sample from this set, for example by running an MCMC algorithm using a fixed (finite) set of moves to jump from one table to the next.

Formally, consider a system of linear integer equations A x = b (for example, marginal conditions) and inequalities C x ≥ d (for example, non-negativity of the sample counts). If m ∈ ker_ℤ A, then x + m is another solution, provided that C (x + m) ≥ d. A Markov basis Β is a finite set of moves in ker_ℤ A such that any two solutions x, x' can be connected by iteratively choosing moves from Β such that all intermediate points are themselves solutions. This property ensures that the MCMC constructed from a Markov basis is connected.

A theorem of Diaconis and Sturmfels says that finite Markov bases exist and can be chosen independently of b and d. Markov bases can be computed from generating sets of toric ideals. These toric ideals consist of polynomial invariants that describe exponential families; for example, graphical models. Therefore, Markov bases also give information about these statistical models, such as the possible support sets. In turn, the support sets are important, since they provide information about existence or non-existence of the MLE.

In my talk, I give an overview of Markov bases and their applications, and I present a lifting procedure that allows to compute Markov bases inductively. Joint work with Seth Sullivant, Hélène Massam and Nanwei Wang.

Event Topic

Nonlinear Algebra and Statistics (NLASTATS)