Random Walks and Electric Resistance on Distance-Regular Graphs

A graph is a set of vertices V (can be taken to be {1,2,...,n}) and edges E, where each edge is an element of V × V. We assume all graphs in this talk are simple, which means that (a,a) / ∈ E and E has no repeated elements, and undirected, which means that (a,b) and (b,a) represent the same edge. Random Walks The degree of a vertex of a graph is the number of edges containing that vertex. A random walk is a process in which a walker moves on the vertices of a graph, at each stage moving to the adjacent vertices with probability 1/d, where d is the degree of the current vertex. Formally, a random walk is a random process Xn with independent increments on the vertices of the graph, with conditional probabilities P(Xn+1 = b|Xn = a) = 1 deg(a) if a ∼ b 0 if a b