Take the 2-minute tour ×

Consider a connected graph $G$ with non-negative weights on each edge. The sum of edge weights is the same for each vertex, call this sum $W$. A random walk on the graph at vertex $u$ transitions an edge $(u,v)$ with probability w(u)/W.

The uniform weights imply a uniform staionary distribution. Can we say, that like unweighted regular graphs, the cover time is $O(n^2)$? If it helps, we can include that the maximum hitting time is known to be $O(n^2)$.

share|improve this question
I think for weighted graphs the cover time is \Omega (n^3) –  Suresh Venkat Jul 23 '10 at 7:49
Hi Suresh, Thanks for your answer. $O(n^3)$ is too big for my particular problem, but it's actually ok, my specific problem involves more parameters, and I think I might have a reasonable avenue for investigation. I will return to this question if I fail to make progress. –  MAKCL Jul 23 '10 at 8:25

2 Answers 2

You'll need some further assumption beyond just the bound on the maximum expected hitting time.

for example, for $n$ even consider a graph on $n$ vertices arranged into $n/2$ pairs. If $u$ and $v$ are a pair of vertices, let the edge between them have weight $1$, otherwise let it have weight $n^{-2}$.

now the probability of jumping from one vertex to the other in the same pair is roughly $1-1/n$. Otherwise, the walk chooses between all other vertices uniformly at random.

so the process stays at some pair for time roughly exponential with mean $n$, before jumping to a new randomly chosen pair.

this is essentially coupon collector. the maximum expected hitting time has order $n^2$ but the cover time has order $n^2 \log n$.

share|improve this answer
in fact the dumbell graph (two cliques of size n connected by a path of length n) give the $n^3$ bound. –  Suresh Venkat Jul 23 '10 at 8:28
James, thanks for your answer. This is the problem with asking these types of questions on the net. I have a certain set of constraints in mind, that your example would violate, but the more specific I get about the problem, the less it becomes mine to solve, if you know what I mean. As a consequence, I don't really think through the implications of relaxing (ie not mentioning) those constraints. It's ok though, I think I might have an idea. –  MAKCL Jul 23 '10 at 9:40
btw Suresh, $O(n^2)$ max hitting time implies $O(n^2\log n)$ cover time by Matthews' technique. –  MAKCL Jul 23 '10 at 10:04
what "bound" are you talking about, Suresh? There are certainly examples of families of weighted graphs where the cover time is of larger order than $n^3$, and there are certainly examples (like the one I described) where the cover time is of smaller order than $n^3$. –  James Martin Jul 23 '10 at 17:05
So the question now seems to be: does the conditions on the weights given in the first paragraph cause the cover time to be $O(n^2\log n)$, rather than merely $O(n^3)$? –  Emil Jul 23 '10 at 23:36

A search for "algebraic connectivity" of a graph may be helpful, as well as the extensive literature on rapid mixing.

The problems mainly occur when the graph is nearly disconnected because different component-like sets have too few edges between them, or edges with weights too close to zero (which is the weight of a non-edge). If you make certain edges exponentially small, the cover time also becomes exponential.

Your adjacency matrix has Perron root and spectral radius $W$, and the usual bounds on mixing or covering time are in terms of the eigenvalue of second-highest magnitude, as a fraction of $W$. (Bipartite graphs are a special case, where $-W$ is also an eigenvalue.) The limiting distribution, in this case uniform, is the $W$ eigenvector, and is the only all-positive eigenvector. Convergence to uniform is exponential, but with base the ratio of $W$ to other eigenvalues, by the spectral decomposition theorem. Sometimes you can actually get a clue to the worst component-like pieces from the positive and negative parts of large eigenvectors.

share|improve this answer

Your Answer


