{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:41:06Z","timestamp":1787323266304,"version":"build-2736575974"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2017,1]]},"abstract":"<jats:p>The pattern maximum likelihood (PML) estimate, introduced by Orlitsky et al., is an estimate of the multiset of probabilities in an unknown probability distribution $\\mathbf{p}$, the estimate being obtained from $n$ independent and identically distributed samples drawn from $\\mathbf{p}$. The PML estimate involves solving a difficult optimization problem over the set of all probability mass functions of finite support. In this paper, we describe an interesting phase transition phenomenon in the PML estimate: at a certain sharp threshold, the uniform distribution goes from being a local maximum to being a local minimum for the optimization problem in the estimate. We go on to consider the question of whether a similar phase transition phenomenon also exists in the Bethe approximation of the PML estimate, the latter being an approximation method with origins in statistical physics. We show that the answer to this question is a qualified \u201cyes.\u201d Our analysis involves the computation of the mean and variance of the $(i,j)$th entry, $a_{i,j}$, in a random $k \\times k$ nonnegative integer matrix $A$ with row and column sums all equal to $M$, drawn according to a distribution that assigns to $A$ a probability proportional to $\\Pi_{i,j} \\frac{(M-a_{i,j})!}{a_{i,j}!}$.<\/jats:p>","DOI":"10.1137\/15m1028819","type":"journal-article","created":{"date-parts":[[2017,3,30]],"date-time":"2017-03-30T12:18:26Z","timestamp":1490876306000},"page":"597-631","source":"Crossref","is-referenced-by-count":1,"title":["Phase Transitions for the Uniform Distribution in the Pattern Maximum Likelihood Problem and its Bethe Approximation"],"prefix":"10.1137","volume":"31","author":[{"given":"Chun Lam","family":"Chan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Winston","family":"Fernandes","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Navin","family":"Kashyap","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Manjunath","family":"Krishnapur","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2017,3,30]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2004.830761"},{"key":"atypb2","unstructured":"A. Orlitsky, N. P. Santhanam, K. Viswanathan, and J. Zhang,\n                      On Estimating the Probability Multiset\n                      , manuscript,https:\/\/www-ee.eng.hawaii.edu\/~prasadsn\/skelnew59.pdf(2011)."},{"key":"atypb3","unstructured":"A. Orlitsky, N. P. Santhanam, K. Viswanathan, and J. Zhang,\n                      On modeling profiles instead of values\n                      , in Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence, 2004."},{"key":"atypb4","first-page":"304","author":"Orlitsky A.","year":"2004","journal-title":"Chicago"},{"key":"atypb5","first-page":"251","author":"Acharya J.","year":"2009","journal-title":"Greece"},{"key":"atypb6","first-page":"1130","author":"Orlitsky A.","year":"2009","journal-title":"South Korea"},{"key":"atypb7","first-page":"1135","author":"Orlitsky A.","year":"2009","journal-title":"South Korea"},{"key":"atypb8","first-page":"1498","author":"Acharya J.","year":"2010","journal-title":"TX"},{"key":"atypb9","first-page":"400","author":"Acharya J.","year":"2011","journal-title":"Russia"},{"key":"atypb10","first-page":"2012","author":"Vontobel P. O.","year":"2012","journal-title":"MA"},{"key":"atypb11","unstructured":"W. Fernandes,\n                      Calculation of Approximate Pattern Maximum Likelihood\n                      , M.E. Project Report, Department of Electrical Communication Engineering, Indian Institute of Science, 2013."},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.850085"},{"key":"atypb13","first-page":"318","author":"Fernandes W.","year":"2013","journal-title":"Spain"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2012.2227109"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1935.0122"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100019174"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008738"},{"key":"atypb19","unstructured":"M. Huber and J. Law,\n                      Fast approximation of the permanent for very dense problems\n                      , in Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, 2008."},{"key":"atypb20","unstructured":"M. Chertkov, L. Kroc, and M. Vergassola,\n                      Belief Propagation and Beyond for Particle Tracking\n                      ,arXiv:0806.1199, 2008."},{"key":"atypb21","unstructured":"B. Huang and T. Jebara,\n                      Approximating the Permanent with Belief Propagation\n                      ,arXiv:0908.1769, 2009."},{"key":"atypb22","first-page":"90","author":"Gurvits L.","year":"2014","journal-title":"Philadelphia"},{"key":"atypb23","unstructured":"L. Gurvits,\n                      Unharnessing the Power of Schrijver's Permanental Inequality\n                      ,arXiv:1106.2844, 2011."},{"key":"atypb24","first-page":"11","author":"Gurvits L.","year":"2011","journal-title":"TR"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2264715"},{"key":"atypb26","unstructured":"A. W. Marshall and I. Olkin,\n                      Inequalities: Theory of Majorization and Its Applications\n                      , Academic Press, New York, 1979."},{"key":"atypb27","unstructured":"W. Rudin,\n                      Principles of Mathematical Analysis\n                      , 3rd ed., McGraw-Hill, New York, 1976."},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"E. M. Stein and G. L. Weiss,\n                      Introduction to Fourier Analysis on Euclidean Spaces\n                      , Princeton University Press, Princeton, NJ, 1971.","DOI":"10.1515\/9781400883899"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/15M1028819","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:51:47Z","timestamp":1787320307000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/15M1028819"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["10.1137\/15M1028819"],"URL":"https:\/\/doi.org\/10.1137\/15m1028819","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1]]}}}