We study the problem of estimating the pattern maximum likelihood (PML) distribution for time-homogeneous discrete-time Markov chains (DTMCs). The PML problem for memoryless sources has been well studied in the literature and we propose an extension of the same for DTMCs. For memoryless sources, Acharya et al. have shown that plug-in estimators obtained from the PML estimate yield good estimates for symmetric functionals of the distribution. We show that this holds for the PML estimate of DTMCs as well. Finally, we express the PML estimate for DTMCs as the double minimization of a certain free energy function and discuss some mean-field approximations to approximate the PML estimate efficiently. © 2016 IEEE.