NDLI: Phase Transitions for the Uniform Distribution in the Pattern Maximum Likelihood Problem and its Bethe Approximation

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Fernandes, Winston Kashyap, Navin Krishnapur, Manjunath Chan, Chun Lam
Copyright Year	2017
Abstract	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 yes. 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}!}$.
Starting Page	597
Ending Page	631
Page Count	35
File Format	PDF
ISSN	08954801
DOI	10.1137/15M1028819
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	1
Volume Number	31
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2017-03-30
Access Restriction	Subscribed
Subject Keyword	Bethe approximation Probability in computer science pattern maximum likelihood
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Phase Transitions for the Uniform Distribution in the PML Problem and its Bethe Approximation

A phase transition for the uniform distribution in the pattern maximum likelihood problem

The Bethe approximation of the pattern maximum likelihood distribution

A Phase Transition For The Uniform Distribution In The Pattern Maximum Likelihood Problem

The bethe and sinkhorn approximations of the pattern maximum likelihood estimate and their connections to the valiant–valiant estimate.

The Bethe and Sinkhorn approximations of the pattern maximum likelihood estimate and their connections to the Valiant-Valiant estimate

Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels

Maximum-likelihood principle for possibility distributions viewed as families of probabilities

Counting Independent Sets Using the Bethe Approximation

Phase Transitions for the Uniform Distribution in the Pattern Maximum Likelihood Problem and its Bethe Approximation

Similar Documents

Phase Transitions for the Uniform Distribution in the PML Problem and its Bethe Approximation

A phase transition for the uniform distribution in the pattern maximum likelihood problem

The Bethe approximation of the pattern maximum likelihood distribution

A Phase Transition For The Uniform Distribution In The Pattern Maximum Likelihood Problem

The bethe and sinkhorn approximations of the pattern maximum likelihood estimate and their connections to the valiant–valiant estimate.

The Bethe and Sinkhorn approximations of the pattern maximum likelihood estimate and their connections to the Valiant-Valiant estimate

Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels

Maximum-likelihood principle for possibility distributions viewed as families of probabilities

Counting Independent Sets Using the Bethe Approximation

Phase Transitions for the Uniform Distribution in the Pattern Maximum Likelihood Problem and its Bethe Approximation