{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T01:50:02Z","timestamp":1780537802510,"version":"3.54.1"},"reference-count":21,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2021,8,25]],"date-time":"2021-08-25T00:00:00Z","timestamp":1629849600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We obtain a polynomial upper bound on the mixing time <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000328_inline1.png\"\/><jats:tex-math>\n$T_{CHR}(\\epsilon)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> of the coordinate Hit-and-Run (CHR) random walk on an <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000328_inline2.png\"\/><jats:tex-math>\n$n-$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>dimensional convex body, where <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000328_inline3.png\"\/><jats:tex-math>\n$T_{CHR}(\\epsilon)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is the number of steps needed to reach within <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000328_inline4.png\"\/><jats:tex-math>\n$\\epsilon$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> of the uniform distribution with respect to the total variation distance, starting from a warm start (i.e., a distribution which has a density with respect to the uniform distribution on the convex body that is bounded above by a constant). Our upper bound is polynomial in <jats:italic>n<\/jats:italic>, <jats:italic>R<\/jats:italic> and <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000328_inline5.png\"\/><jats:tex-math>\n$\\frac{1}{\\epsilon}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, where we assume that the convex body contains the unit <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000328_inline6.png\"\/><jats:tex-math>\n$\\Vert\\cdot\\Vert_\\infty$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-unit ball <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000328_inline7.png\"\/><jats:tex-math>\n$B_\\infty$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and is contained in its <jats:italic>R<\/jats:italic>-dilation <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000328_inline8.png\"\/><jats:tex-math>\n$R\\cdot B_\\infty$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Whether CHR has a polynomial mixing time has been an open question.<\/jats:p>","DOI":"10.1017\/s0963548321000328","type":"journal-article","created":{"date-parts":[[2021,8,25]],"date-time":"2021-08-25T05:51:15Z","timestamp":1629870675000},"page":"320-332","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":8,"title":["On the mixing time of coordinate Hit-and-Run"],"prefix":"10.1017","volume":"31","author":[{"given":"Hariharan","family":"Narayanan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Piyush","family":"Srivastava","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2021,8,25]]},"reference":[{"key":"S0963548321000328_ref21","doi-asserted-by":"publisher","DOI":"10.1287\/opre.32.6.1296"},{"key":"S0963548321000328_ref15","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240040402"},{"key":"S0963548321000328_ref9","unstructured":"[9] Laddha, A. and Vempala, S. S. (2021) Convergence of Gibbs Sampling: Coordinate Hit-and-Run Mixes Fast. In Proceedings of the 37th International Symposium on Computational Geometry, (SoCG 2021), pp. 51:1\u201351:12. Also available at arXiv:2009.11338."},{"key":"S0963548321000328_ref13","doi-asserted-by":"crossref","unstructured":"[13] Lee, Y. T. and Vempala, S. S. (2018) The Kannan-Lov\u00e1sz-Simonovits Conjecture. arXiv:1807.03465.","DOI":"10.4310\/CDM.2017.v2017.n1.a1"},{"key":"S0963548321000328_ref7","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199708)11:1<1::AID-RSA1>3.0.CO;2-X"},{"key":"S0963548321000328_ref12","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188774"},{"key":"S0963548321000328_ref16","first-page":"392","article-title":"Simulated annealing in convex bodies and an O\n*(n\n4) volume algorithm J. Comput. Sys.","volume":"72","author":"Lov\u00e1sz","year":"2006","journal-title":"Sci."},{"key":"S0963548321000328_ref14","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1007\/s101070050099","article-title":"Hit-and-run mixes fast","volume":"86","author":"Lov\u00e1sz","year":"1999","journal-title":"Math. Prog."},{"key":"S0963548321000328_ref17","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970544727X"},{"key":"S0963548321000328_ref5","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0235393"},{"key":"S0963548321000328_ref1","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199535255.001.0001"},{"key":"S0963548321000328_ref6","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btx052"},{"key":"S0963548321000328_ref19","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075"},{"key":"S0963548321000328_ref20","doi-asserted-by":"publisher","DOI":"10.1214\/15-AAP1104"},{"key":"S0963548321000328_ref3","unstructured":"[3] Cousins, B. (2017) Efficient High-Dimensional Sampling and Integration. PhD thesis, Georgia Institute of Technology."},{"key":"S0963548321000328_ref11","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055416"},{"key":"S0963548321000328_ref4","doi-asserted-by":"publisher","DOI":"10.1145\/102782.102783"},{"key":"S0963548321000328_ref8","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1110.0519"},{"key":"S0963548321000328_ref18","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00082"},{"key":"S0963548321000328_ref10","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384272"},{"key":"S0963548321000328_ref2","first-page":"2146","article-title":"Fast MCMC sampling algorithms on polytopes","volume":"19","author":"Chen","year":"2018","journal-title":"J. Mach. Learn. Res."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548321000328","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,2]],"date-time":"2022-03-02T09:33:44Z","timestamp":1646213624000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548321000328\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,25]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["S0963548321000328"],"URL":"https:\/\/doi.org\/10.1017\/s0963548321000328","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,25]]},"assertion":[{"value":"\u00a9 The Author(s), 2021. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}