Random Walks on Graphs: non-standard upper bounds for maximum hitting time

In this article (motivated by question on existence of finite-memory algorithm to determine connectedness of a graph) we explore a non-standard approach to finding upper bounds for maximum hitting time for random walks on finite undirected graphs.We prove specific (and in some cases, exact) upper bounds for maximum hitting time for random walks on undirected graphs formulated as functions of the number of graph’s edges. Among them, the theorem that states that the maximum hitting time for symmetric random walk on connected graph with n edges is less than or equal to n2.We also consider asymmetric random walks on trees and connected graphs to find upper bounds for hitting time as simple functions of n and , where is a simple measure of walk’s asymmetry (or bias).