UC Berkeley

This dissertation studies the role of local time in the analysis of random walks and self-interacting random processes on finite graphs. Local time, which records the time a trajectory spends at a state, along an edge, or in a prescribed region, appears as a central object across four interconnected problems: non-reversible extensions of isomorphism theorems connecting local times to Gaussian and permanental fields; the time needed to achieve a second cover of a graph after the first; statistical estimation and information-theoretic analysis of edge-reinforced random walks; and acceleration of Markov chain Monte Carlo via self-repellent dynamics. In each setting, local time plays a different but related role. For non-reversible Markov chains, we develop a density-formula approach that unifies proofs of several isomorphism theorems and yields comparison inequalities for permanental processes and a symmetrization bound on cover times. For the second-cover problem, we combine the Ray-Knight isomorphism theorem with excursion decompositions to bound the marginal time to the second cover in terms of the geometry of the graph. For edge-reinforced random walks, we exploit the random-environment representation to give the first sample-complexity guarantees for parameter estimation, and to derive explicit formulas for entropy rate and Kullback-Leibler divergences between reinforced walk laws. For Markov chain Monte Carlo, we show that a true-self-avoiding-walk mechanism keeps empirical occupation counts close to stationarity at a rate nearly of order one over the number of steps, strictly improving on the diffusive rate of standard methods.