Reconstructing Markov processes from independent and anonymous experiments

作     者：Micali, Silvio Zhu, Zeyuan Allen 

作者机构：MIT CSAIL Cambridge MA 02139 USA 

出 版 物：《DISCRETE APPLIED MATHEMATICS》 (离散应用数学)

年 卷 期：2016年第200卷

页      面：108-122页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：Graph reconstruction Random walk Markov process Local algorithms 

摘      要：We investigate the problem of exactly reconstructing, with high confidence and up to isomorphism, the ball of radius r centered at the starting state of a Markov process from independent and anonymous experiments. In an anonymous experiment, the states are visited according to the underlying transition probabilities, but no global state names are known: one can only recognize whether two states, reached within the same experiment, are the same. We prove quite tight bounds for such exact reconstruction in terms of both the number of experiments and their lengths. (C) 2015 Elsevier B.V. All rights reserved.