  Directed and undirected graphical models, also called Bayesian networks and
Markov random fields, respectively, are important statistical tools in a wide
variety of fields, ranging from computational biology to probabilistic
artificial intelligence. We give an upper bound on the number of inference
functions of any graphical model. This bound is polynomial on the size of the
model, for a fixed number of parameters, thus improving the exponential upper
bound given by Pachter and Sturmfels. We also show that our bound is tight up
to a constant factor, by constructing a family of hidden Markov models whose
number of inference functions agrees asymptotically with the upper bound.
Finally, we apply this bound to a model for sequence alignment that is used in
computational biology.
