{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T15:17:23Z","timestamp":1648653443634},"reference-count":14,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2010,5,14]],"date-time":"2010-05-14T00:00:00Z","timestamp":1273795200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2010,7]]},"abstract":"<jats:p>Consider a finite irreducible Markov chain on state space<jats:italic>S<\/jats:italic>with transition matrix<jats:italic>M<\/jats:italic>and stationary distribution \u03c0. Let<jats:italic>R<\/jats:italic>be the diagonal matrix of return times,<jats:italic>R<\/jats:italic><jats:sub><jats:italic>ii<\/jats:italic><\/jats:sub>= 1\/\u03c0<jats:sub><jats:italic>i<\/jats:italic><\/jats:sub>. Given distributions \u03c3, \u03c4 and<jats:italic>k<\/jats:italic>\u2208<jats:italic>S<\/jats:italic>, the exit frequency<jats:italic>x<\/jats:italic><jats:sub><jats:italic>k<\/jats:italic><\/jats:sub>(\u03c3, \u03c4) denotes the expected number of times a random walk exits state<jats:italic>k<\/jats:italic>before an optimal stopping rule from \u03c3 to \u03c4 halts the walk. For a target distribution \u03c4, we define<jats:italic>X<\/jats:italic><jats:sub>\u03c4<\/jats:sub>as the<jats:italic>n<\/jats:italic>\u00d7<jats:italic>n<\/jats:italic>matrix given by (<jats:italic>X<\/jats:italic><jats:sub>\u03c4<\/jats:sub>)<jats:sub><jats:italic>ij<\/jats:italic><\/jats:sub>=<jats:italic>x<\/jats:italic><jats:sub><jats:italic>j<\/jats:italic><\/jats:sub>(<jats:italic>i<\/jats:italic>, \u03c4), where<jats:italic>i<\/jats:italic>also denotes the singleton distribution on state<jats:italic>i<\/jats:italic>.<\/jats:p><jats:p>The dual Markov chain with transition matrix<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548310000118_char1\" \/><\/jats:private-char>=<jats:italic>RM<\/jats:italic><jats:sup>\u22a4<\/jats:sup><jats:italic>R<\/jats:italic><jats:sup>\u22121<\/jats:sup>is called the<jats:italic>reverse chain<\/jats:italic>. We prove that Markov chain duality extends to matrices of exit frequencies. Specifically, for each target distribution \u03c4, we associate a unique dual distribution \u03c4*. Let<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548310000118_inline1\"><jats:alt-text>$\\rX_{\\fc{\\t}}$<\/jats:alt-text><\/jats:inline-graphic>denote the matrix of exit frequencies from singletons to \u03c4* on the reverse chain. We show that<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548310000118_inline2\"><jats:alt-text>$\\rX_{\\fc{\\t}} = R (X_{\\t}^{\\top} - \\vb^{\\top} \\one)R^{-1}$<\/jats:alt-text><\/jats:inline-graphic>, where<jats:bold>b<\/jats:bold>is a non-negative constant vector (depending on \u03c4). We explore this exit frequency duality and further illuminate the relationship between stopping rules on the original chain and reverse chain.<\/jats:p>","DOI":"10.1017\/s0963548310000118","type":"journal-article","created":{"date-parts":[[2010,5,14]],"date-time":"2010-05-14T10:11:06Z","timestamp":1273831866000},"page":"541-560","source":"Crossref","is-referenced-by-count":2,"title":["Exit Frequency Matrices for Finite Markov Chains"],"prefix":"10.1017","volume":"19","author":[{"given":"ANDREW","family":"BEVERIDGE","sequence":"first","affiliation":[]},{"given":"L\u00c1SZL\u00d3","family":"LOV\u00c1SZ","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2010,5,14]]},"reference":[{"key":"S0963548310000118_ref11","first-page":"119","volume-title":"Surveys in Combinatorics","author":"Lov\u00e1sz","year":"1995"},{"key":"S0963548310000118_ref10","doi-asserted-by":"crossref","unstructured":"[10] Lov\u00e1sz L. and Winkler P. (1995) Efficient stopping rules for Markov chains. In Proc. 27th ACM Symposium on the Theory of Computing, pp. 76\u201382.","DOI":"10.1145\/225058.225086"},{"key":"S0963548310000118_ref8","volume-title":"The Theory of Matrices","author":"Lancaster","year":"1985"},{"key":"S0963548310000118_ref7","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511613586"},{"key":"S0963548310000118_ref6","doi-asserted-by":"crossref","unstructured":"[6] Doyle P. and Snell J. L. Random walks and electric networks. http:\/\/arxiv.org\/abs\/math\/0001057. Derived from Random Walks and Electric Networks (1984), Carus Monographs, Mathematical Association of America.","DOI":"10.5948\/UPO9781614440222"},{"key":"S0963548310000118_ref5","doi-asserted-by":"publisher","DOI":"10.1137\/0406029"},{"key":"S0963548310000118_ref3","doi-asserted-by":"publisher","DOI":"10.1137\/070687402"},{"key":"S0963548310000118_ref13","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/041\/06"},{"key":"S0963548310000118_ref1","unstructured":"[1] Aldous D. J. and Fill J. Reversible Markov Chains and Random Walks on Graphs. To appear. http:\/\/www.stat.berkeley.edu\/~aldous\/RWG\/book.html."},{"key":"S0963548310000118_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-4149(97)00037-9"},{"key":"S0963548310000118_ref9","first-page":"353","volume-title":"Combinatorics: Paul Erd\u0151s is Eighty","author":"Lov\u00e1sz","year":"1996"},{"key":"S0963548310000118_ref4","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199810)29:2<57::AID-JGT1>3.0.CO;2-B"},{"key":"S0963548310000118_ref14","doi-asserted-by":"publisher","DOI":"10.2307\/1425817"},{"key":"S0963548310000118_ref12","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548397003349"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548310000118","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,4]],"date-time":"2020-06-04T17:26:14Z","timestamp":1591291574000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548310000118\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,5,14]]},"references-count":14,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,7]]}},"alternative-id":["S0963548310000118"],"URL":"https:\/\/doi.org\/10.1017\/s0963548310000118","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,5,14]]}}}