Algebraic computation of pattern maximum likelihood
Jayadev Acharya, Hirakendu Das, Alon Orlitsky, Shengjun Pan · 2011
Pattern maximum likelihood (PML) is a technique for estimating the probability multiset of an unknown distribution. With any random sample, it associates the distribution maximizing the probability of its pattern. The required computation is a maximization of a monomial symmetric polynomial over the monotone simplex. The PML of only very few patterns have been found analytically, and for other patterns, the PML has been approximated by a heuristic algorithm. Taking an algebraic approach, we determine the PML of short patterns by solving a system of multivariate polynomial equations using the method of resultants. Using this approach, we determine the PML of the pattern 1112234, the last length-7 pattern whose PML was unknown. Under two plausible but yet unproved assumptions on the optimal alphabet size and the number of distinct probabilities, we also find the PML distribution of all previously unknown patterns of length up to 14.