  We study the average probability that a discrete-time quantum walk finds a
marked vertex on a graph. We first show that, for a regular graph, the spectrum
of the transition matrix is determined by the weighted adjacency matrix of an
augmented graph. We then consider the average search probability on a distance
regular graph, and find a formula in terms of the adjacency matrix of its
vertex-deleted subgraph. In particular, for any family of (1) complete graphs,
or (2) strongly regular graphs, or (3) distance regular graphs of a fixed
parameter $d$, varying valency $k$ and varying size $n$, such that $k^{d-1}/n$
vanishes as $k$ increases, the average search probability approaches $1/4$ as
the valency goes to infinity. We also present a more relaxed criterion, in
terms of the intersection array, for this limit to be approached by distance
regular graphs.
