Let simple random walk travel from to its first visit to , then stop on its subsequent first hit of in a finite connected unweighted loopless graph. Every directed edge has expected traversal countThe Strong Markov property splits the count into the two killed legs. By killed-walk occupation voltage, their contributions are and . Their Laplacians cancel, so the harmonic maximum principle on a finite graph makes the sum constant, with value . Summing over all directed edges recovers the commute time identity.
Articles by others on the same topic
There are currently no matching articles.