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)$.

  • $\begingroup$ I think for weighted graphs the cover time is \Omega (n^3) $\endgroup$ – Suresh Venkat Jul 23 '10 at 7:49
  • $\begingroup$ 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. $\endgroup$ – MAKCL Jul 23 '10 at 8:25

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$.

  • $\begingroup$ in fact the dumbell graph (two cliques of size n connected by a path of length n) give the $n^3$ bound. $\endgroup$ – Suresh Venkat Jul 23 '10 at 8:28
  • $\begingroup$ 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. $\endgroup$ – MAKCL Jul 23 '10 at 9:40
  • $\begingroup$ btw Suresh, $O(n^2)$ max hitting time implies $O(n^2\log n)$ cover time by Matthews' technique. $\endgroup$ – MAKCL Jul 23 '10 at 10:04
  • $\begingroup$ 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$. $\endgroup$ – James Martin Jul 23 '10 at 17:05
  • $\begingroup$ 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)$? $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.