English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the problem of identity testing of markov chains. In this setting,we are given access to a single trajectory from a markov chain with unknowntransition matrix $Q$ and the goal is to determine whether $Q = P$ for someknown matrix $P$ or $\text{Dist}(P, Q) \geq \epsilon$ where $\text{Dist}$ issuitably defined. In recent work by Daskalakis, Dikkala and Gravin, 2018, itwas shown that it is possible to distinguish between the two cases provided thelength of the observed trajectory is at least super-linear in the hitting timeof $P$ which may be arbitrarily large.  In this paper, we propose an algorithm that avoids this dependence on hittingtime thus enabling efficient testing of markov chains even in cases where it isinfeasible to observe every state in the chain. Our algorithm is based oncombining classical ideas from approximation algorithms with techniques for thespectral analysis of markov chains.

Testing Markov Chains without Hitting