Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
417986 | Discrete Applied Mathematics | 2016 | 15 Pages |
Abstract
We investigate the problem of exactly reconstructing, with high confidence and up to isomorphism, the ball of radius rr 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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Silvio Micali, Zeyuan Allen Zhu,