An asymptotic study for path reversal

AbstractA path reversal is performed in a rooted tree when a node becomes the root of all the nodes along the path from it to the former root. This algorithm on trees is presented as a transition system specified by induction over a convenient view of the tree structure. When each tree node is assigned a fixed weight representing its relative probability to move to the root, the transition system defines a finite Markov chain. This paper presents some of its asymptotic properties. A closed formula for the stationary distribution and a tight upper bound for the average computational complexity of path reversal are also given as new results