- Main
Markov Bases: Their Complexity and Applications to Network Analysis
- Almendra Hernandez, Felix
- Advisor(s): De Loera, Jesus A.
Abstract
Algebraic statistics is an emerging field that employs tools from algebraic geometry, commutative algebra, and combinatorics to address statistical problems and their applications. This interdisciplinary subject not only applies algebraic techniques to solve statistical challenges but also fosters the development of new algebraic results motivated by statistical applications. This dynamic exchange has enriched both disciplines, driving advancements in areas such as experimental design, graphical models, and parametric inference.In 1998, Diaconis and Sturmfels made a foundational contribution to the field by introducing a Markov Chain Monte Carlo algorithm for sampling fibers of log-linear models. The algorithm’s inherently algebraic nature relies on the construction of a Markov basis, a set of moves with origin in polynomial algebra, thereby establishing a connection between commutative algebra, probability and statistics.Since this seminal work, there has been a surge of research into various aspects of Markov bases and their structure for specific sets of discrete exponential families. This dissertation investigates the complexity of Markov bases in general and explores their combinatorial aspects in the context of popular random network models and their applications in statistics.In Chapter 2, we extend the classical notion of Markov basis by allowing moves to connect fibers, even when these occasionally take steps in a negative relaxation of the fiber. This concept is motivated by earlier work of Bunea and Besag in the context of the Rasch model, and Chen, Dinwoodie, Dobra, and Huber in the context of logistic regression. These studies considered alternative methods for defining irreducible Markov chains on fibers without computing a full Markov basis in certain specific cases.Nevertheless, we show that for general log-linear models, there is no universal upper bound on the level of negative relaxation required to connect fibers. Moreover, we extend a result by De Loera and Onn, showing that Markov basis elements with arbitrarily large degrees may exist even when relaxed fibers are employed. On the other hand, we provide positive results for hierarchical models, establishing a polynomial upper bound on the size of their Graver basis in terms of certain structural parameters of the model.In Chapter 3, we present a combinatorial description of the Markov basis for a degree-corrected variant of the Stochastic Block Model (SBM), resolving an open problem posed by Karwa et al. in their study of goodness-of-fit tests for mixtures of log-linear models. Furthermore, we establish that the algebraic counterparts of this Markov basis constitute a Gröbner basis for the associated toric ideal under a pure lexicographical order, thereby extending work by De Loera et al. Furthermore, we analyze the Markov basis for the 0/1 restricted fibers of this model, showing that its degree increases as the number of blocks in the SBM grows.Finally, in Chapter 4, we consider a labeled generalization of the SBM and provide a complete combinatorial description of its Markov basis. This result is directly relevant to the conditional goodness-of-fit testing framework for mixtures of exponential log-linear models introduced by Karwa et al. We also provide theoretical guarantees for the test in the frequentist setting.