Random Walks On Graphs And expected Hitting Times

Abstract

Random walks on graphs constitute a fundamental framework in probability theory and combinatorics with extensive applications across mathematics, computer science, and physics. This paper examines the theoretical foundations of random walks on finite graphs with emphasis on expected hitting times, which quantify the average number of steps required for a random walk to reach a target vertex from a given source. We establish the connection between random walks and Markov chains, derive the fundamental system of linear equations governing hitting times, and present closed-form solutions for several canonical graph structures including paths, cycles, and complete graphs. The analysis employs techniques from linear algebra, particularly the properties of the transition matrix and its relationship to the graph Laplacian. We demonstrate applications of hitting time calculations to problems in network analysis, algorithm design, and theoretical computer science, providing both theoretical results and computational examples. The methods presented offer insights into the structural properties of graphs and their influence on stochastic processes.