Reconstructing Markov processes from independent and anonymous experiments

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.