报告题目：Testing Markov Chains

        报告摘要：A commonly used technique in casinos to shuffle decks of 52 cards is the riffle shuffle: first, the dealer cuts the deck into two piles, then the shuffler successively drops cards from the bottom of each pile to form a new pile. The classic model proposed in 1955 by Gilbert, Shannon, and Reeds describes the randomness in the riffle shuffle process. But how do we verify that a specific dealer shuffles according to the model? How many trials are needed to test that dealer's shuffles conform to GSR-model? These questions can be formulated as ``identity testing problem'' in the classic distribution testing framework. Standard distribution testing assumes access to i.i.d. samples from the distributions that are being tested, whereas in our problem samples are coming in a stream of dependent samples generated by a Markov chain. I will introduce a theoretical framework to study Markov Chain testing and present our theoretical results for the identity testing problem, where we get to observe a single trajectory of k samples from an unknown Markov Chain P and our goal is to test whether P is identical to a given model Markov Chain Q.