{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T09:54:38Z","timestamp":1740131678222,"version":"3.37.3"},"reference-count":55,"publisher":"Institute of Electrical and Electronics Engineers (IEEE)","issue":"6","license":[{"start":{"date-parts":[[2023,6,1]],"date-time":"2023-06-01T00:00:00Z","timestamp":1685577600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"},{"start":{"date-parts":[[2023,6,1]],"date-time":"2023-06-01T00:00:00Z","timestamp":1685577600000},"content-version":"am","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"},{"start":{"date-parts":[[2023,6,1]],"date-time":"2023-06-01T00:00:00Z","timestamp":1685577600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2023,6,1]],"date-time":"2023-06-01T00:00:00Z","timestamp":1685577600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1900507"],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF CAREER","doi-asserted-by":"publisher","award":["CCF-1651588"],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Alfred Sloan Fellowship"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEEE Trans. Inform. Theory"],"published-print":{"date-parts":[[2023,6]]},"DOI":"10.1109\/tit.2023.3239508","type":"journal-article","created":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T18:52:50Z","timestamp":1674845570000},"page":"3920-3959","source":"Crossref","is-referenced-by-count":0,"title":["Optimal Prediction of Markov Chains With and Without Spectral Gap"],"prefix":"10.1109","volume":"69","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8335-2364","authenticated-orcid":false,"given":"Yanjun","family":"Han","sequence":"first","affiliation":[{"name":"Institute of Data, Systems, and Society, Massachusetts Institute of Technology, Cambridge, MA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7547-9333","authenticated-orcid":false,"given":"Soham","family":"Jana","sequence":"additional","affiliation":[{"name":"Department of Operations Research and Financial Engineering, Princeton University, Princeton, NJ, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9239-7671","authenticated-orcid":false,"given":"Yihong","family":"Wu","sequence":"additional","affiliation":[{"name":"Department of Statistics and Data Science, Yale University, New Haven, CT, USA"}]}],"member":"263","reference":[{"key":"ref13","first-page":"1066","article-title":"On learning distributions from their samples","author":"kamath","year":"2015","journal-title":"Proc Conf Learn Theory"},{"key":"ref12","first-page":"1033","article-title":"Variational minimax estimation of discrete distributions under KL loss","volume":"17","author":"paninski","year":"2004","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref15","first-page":"439","article-title":"Learning without mixing: Towards a sharp analysis of linear system identification","author":"simchowitz","year":"2018","journal-title":"Proc Conf Learn Theory"},{"doi-asserted-by":"publisher","key":"ref14","DOI":"10.1214\/aos\/1017939142"},{"doi-asserted-by":"publisher","key":"ref53","DOI":"10.1214\/aop\/1024404522"},{"doi-asserted-by":"publisher","key":"ref52","DOI":"10.1016\/j.spl.2021.109306"},{"doi-asserted-by":"publisher","key":"ref11","DOI":"10.1007\/3-540-36169-3_30"},{"doi-asserted-by":"publisher","key":"ref55","DOI":"10.1073\/pnas.39.1.42"},{"doi-asserted-by":"publisher","key":"ref10","DOI":"10.1214\/18-AAP1457"},{"doi-asserted-by":"publisher","key":"ref54","DOI":"10.6028\/jres.071B.007"},{"doi-asserted-by":"publisher","key":"ref17","DOI":"10.1090\/mbk\/107"},{"key":"ref16","first-page":"1","article-title":"On the sample complexity of the linear quadratic regulator","volume":"20","author":"dean","year":"2019","journal-title":"Found Comput Math"},{"doi-asserted-by":"publisher","key":"ref19","DOI":"10.1214\/aoap\/1028903453"},{"doi-asserted-by":"publisher","key":"ref18","DOI":"10.1214\/EJP.v20-4039"},{"key":"ref51","first-page":"1","article-title":"On concentration of probability","volume":"10","author":"janson","year":"2002","journal-title":"Contemporary Combinatorics"},{"key":"ref50","volume":"48","author":"wainwright","year":"2019","journal-title":"High-dimensional statistics A non-asymptotic viewpoint"},{"key":"ref46","first-page":"16","article-title":"Redundancy of universal coding of arbitrary Markov sources","volume":"10","author":"trofimov","year":"1974","journal-title":"Probl Pered Inform"},{"doi-asserted-by":"publisher","key":"ref45","DOI":"10.1016\/1385-7258(74)90000-6"},{"doi-asserted-by":"publisher","key":"ref48","DOI":"10.1109\/TIT.2012.2195769"},{"doi-asserted-by":"publisher","key":"ref47","DOI":"10.1109\/18.556120"},{"key":"ref42","first-page":"798","article-title":"Identity testing of reversible Markov chains","author":"fried","year":"2022","journal-title":"Proc Int Conf Artif Intell Statist"},{"key":"ref41","first-page":"191","article-title":"Minimax testing of identity to a reference ergodic Markov chain","author":"wolfer","year":"2020","journal-title":"Proc Int Conf Artif Intell Statist"},{"year":"2006","author":"cover","journal-title":"Elements of Information Theory","key":"ref44"},{"year":"1982","author":"csisz\u00e1r","journal-title":"Information Theory Coding Theorems for Discrete Memoryless Systems","key":"ref43"},{"doi-asserted-by":"publisher","key":"ref49","DOI":"10.1109\/TIT.2004.836922"},{"key":"ref8","first-page":"685","article-title":"Estimation of entropy rate and Rényi entropy rate for Markov chains","author":"kamath","year":"2016","journal-title":"Proc IEEE Int Symp Inf Theory (ISIT)"},{"doi-asserted-by":"publisher","key":"ref7","DOI":"10.1109\/ISIT.2000.866316"},{"key":"ref9","first-page":"9781","article-title":"Entropy rate estimation for Markov chains with large state space","author":"han","year":"2018","journal-title":"Proc Adv Neural Inf Process Syst"},{"doi-asserted-by":"publisher","key":"ref4","DOI":"10.1214\/aoms\/1177707039"},{"doi-asserted-by":"publisher","key":"ref3","DOI":"10.1017\/S0305004100026402"},{"key":"ref6","first-page":"904","article-title":"Minimax learning of ergodic Markov chains","author":"wolfer","year":"2019","journal-title":"Proc 30th Int Conf Algorithmic Learn Theory"},{"doi-asserted-by":"publisher","key":"ref5","DOI":"10.1214\/aoms\/1177705136"},{"key":"ref40","first-page":"758","article-title":"Testing symmetric Markov chains without hitting","author":"cherapanamjeri","year":"2019","journal-title":"Proc Conf Learn Theory"},{"doi-asserted-by":"publisher","key":"ref35","DOI":"10.1007\/978-3-0348-8211-8_19"},{"doi-asserted-by":"publisher","key":"ref34","DOI":"10.1109\/18.782149"},{"key":"ref37","first-page":"2264","article-title":"Complexity of estimating Rényi entropy of Markov chains","author":"obremski","year":"2020","journal-title":"Proc IEEE Int Symp Inf Theory (ISIT)"},{"doi-asserted-by":"publisher","key":"ref36","DOI":"10.1214\/aoms\/1177703591"},{"doi-asserted-by":"publisher","key":"ref31","DOI":"10.1109\/TIT.1984.1056936"},{"doi-asserted-by":"publisher","key":"ref30","DOI":"10.1109\/TIT.1973.1055092"},{"key":"ref33","first-page":"87","article-title":"Prediction of random sequences and universal coding","volume":"24","author":"ryabko","year":"1988","journal-title":"Probl Pered Inform"},{"key":"ref32","first-page":"175","article-title":"Universal sequential coding of single messages","volume":"23","author":"shtarkov","year":"1987","journal-title":"Problems Inf Transmiss"},{"key":"ref2","first-page":"648","article-title":"On learning Markov chains","author":"hao","year":"2018","journal-title":"Proc Adv Neural Inf Process Syst"},{"doi-asserted-by":"publisher","key":"ref1","DOI":"10.1109\/ISIT.2016.7541787"},{"key":"ref39","first-page":"385","article-title":"Testing symmetric Markov chains from a single trajectory","author":"daskalakis","year":"2018","journal-title":"Proc Conf Learn Theory"},{"key":"ref38","first-page":"1702","article-title":"Estimating graph parameters via random walks with restarts","author":"ben-hamou","year":"2018","journal-title":"Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms"},{"doi-asserted-by":"publisher","key":"ref24","DOI":"10.1109\/TIT.2020.2996134"},{"doi-asserted-by":"publisher","key":"ref23","DOI":"10.1093\/imaiai\/iaz025"},{"doi-asserted-by":"publisher","key":"ref26","DOI":"10.1109\/ISIT.2018.8437764"},{"doi-asserted-by":"publisher","key":"ref25","DOI":"10.1109\/TIT.2020.3034539"},{"doi-asserted-by":"publisher","key":"ref20","DOI":"10.1111\/j.2517-6161.1955.tb00197.x"},{"doi-asserted-by":"publisher","key":"ref22","DOI":"10.1561\/0100000004"},{"doi-asserted-by":"publisher","key":"ref21","DOI":"10.1109\/TIT.1981.1056355"},{"year":"1962","author":"parzen","journal-title":"Stochastic Processes","key":"ref28"},{"doi-asserted-by":"publisher","key":"ref27","DOI":"10.1109\/TIT.1983.1056652"},{"doi-asserted-by":"publisher","key":"ref29","DOI":"10.1561\/0400000003"}],"container-title":["IEEE Transactions on Information Theory"],"original-title":[],"link":[{"URL":"https:\/\/ieeexplore.ieee.org\/ielam\/18\/10130037\/10028667-aam.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/18\/10130037\/10028667.pdf?arnumber=10028667","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,19]],"date-time":"2023-06-19T17:55:44Z","timestamp":1687197344000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/10028667\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6]]},"references-count":55,"journal-issue":{"issue":"6"},"URL":"https:\/\/doi.org\/10.1109\/tit.2023.3239508","relation":{},"ISSN":["0018-9448","1557-9654"],"issn-type":[{"type":"print","value":"0018-9448"},{"type":"electronic","value":"1557-9654"}],"subject":[],"published":{"date-parts":[[2023,6]]}}}