Inverse problems for random walks on trees: network tomography

Abstract

Let $G$ be a finite tree with root $r$ and associate to the internal vertices of $G$ a collection of transition probabilities for a simple nondegenerate Markov chain. Embedd $G$ into a graph $G^{\prime }$ constructed by gluing finite linear chains of length at least 2 to the terminal vertices of $G.$ Then $G^{\prime }$ admits distinguished boundary layers and the transition probabilities associated to the internal vertices of $G$ can be augmented to define a simple nondegenerate Markov chain $X$ on the vertices of $G^{\prime }.$ We show that the transition probabilities of $X$ can be recovered from the joint distribution of first hitting time and first hitting place of $X$ started at the root $r$ for the distinguished boundary layers of $G^{\prime }.$

11 pages, 1 figure