UC Berkeley

This thesis examines two objects: the stacked-instructions representation of a walk on a general state space, and the novel quantile path transformation for real-valued walks.

Instead of representing a walk by a chronological sequence of states visited, we may represent the walk by a collection of lists of instructions located at each state. On successive visits to a state, the walker reads and follows successive instructions from the list. However, there are some collections of finite lists for which there is no walk that follows all listed instructions; given such instructions, a walker would eventually arrive at some state at which it had already exhausted all instructions, and become stuck, prior to having read all instructions at other states. This thesis characterizes the instruction sets that can be exhausted by the walker before they become stuck.

The quantile transform is a novel path transformation on real-valued walks and Brownian motions of finite duration. This transformation relates to identities in fluctuation theory due to Wendel, Port, Dassios and others, and to discrete and Brownian versions of Tanaka's formula. For an n-step random walk, the quantile transform reorders increments according to the value of the walk at the start of each increment. We describe the distribution of the quantile transform of a simple random walk of n steps, using a bijection to characterize the number of pre-images of each possible transformed path. We deduce, both for simple random walks and for Brownian motion, that the quantile transform has the same distribution as Vervaat's transform. For Brownian motion, the quantile transforms of the embedded simple random walks converge to a time change of the local time profile. We characterize the distribution of the local time profile, giving rise to an identity that generalizes Jeulin's description of the local time profile of a Brownian bridge or excursion.