9
$\begingroup$

(My original question still has not been answered. I have added further clarifications.)

When analyzing random walks (on undirected graphs) by viewing the random walk as a Markov chain, we require the graph to be non-bipartite so that the fundamental theorem of Markov chains applies.

What happens if the graph $G$ is instead bipartite? I am specifically interested in the hitting time $h_{i,j}$, where there is an edge between $i$ and $j$ in $G$. Say the bipartite graph $G$ has $m$ edges. We can add a self-loop to an arbitrary vertex in the graph to make the resulting graph $G'$ non-bipartite; applying the fundamental theorem of Markov chains to $G'$ we then get that $h_{i,j} < 2m+1$ in $G'$, and this is clearly also an upper bound for $h_{i,j}$ in $G$.

Question: Is it true that the stronger claim $h_{i,j} < 2m$ holds in $G$? (It have seen this claimed in analyses of the random walk algorithm for 2SAT.) Or do we really have to go through this extra step of adding the self-loop?

$\endgroup$

3 Answers 3

5
$\begingroup$

This answer proved something different from what the questioner was actually interested in. Leaving it here so others won't repeat the same mistake.

In most cases, one can formally justify the intuitive notion that "self loops can only slow down the walk" by a coupling argument. In this case for example, one can couple the walk with the self loops (let's call it $A$) and the one without the self loops (let's call that $B$) so that $A$ takes the same steps as $B$, but delayed in time. This can for example be done as follows: Suppose that $B$ starts at $u = x_0$ and goes through $x_i: i =1,2,\ldots,k$. Now, we implement $A$ as follows: $A$ also goes through the same vertices as $B$, except that vertex $x_i$, it waits for Geometric($p_i$) time where $p_i$ is the self loop probability at $x_i$. Note that this is a correct implementation of $A$ (all transition probabilities are correct), and the form of the coupling ensures that $A$ never reaches any vertex before $B$, that is, we have coupled $H_t^A$ and $H_t^B$ (the random hitting times in the two walks) so that $H_t^A \geq H_t^B$ with probability $1$. Thus, the inequality for the expected hitting time follows.

$\endgroup$
2
  • $\begingroup$ Sorry, but I don't think this answers my question. I agree that $h_{i,j}$ in $G$ is upper bounded by $h_{i,j}$ in $G'$, which is in turn upper bounded by $2m+1$. But I would like to obtain the stronger bound that $h_{i,j}$ in $G$ is upper bounded by $2m$. (OK, I realize that the "$+1$" is not a big deal, but on the other hand I have seen the claim made without the "$+1$" and so I wonder whether it is technically accurate.) $\endgroup$
    – user6584
    Oct 12, 2011 at 13:43
  • $\begingroup$ @user686 Can you share the reference? $\endgroup$ Oct 12, 2011 at 13:47
2
$\begingroup$

I had posted this as a comment before, and I believe it answers user686's modified question in the affirmative (when $i$ and $j$ are connected by an edge in a graph $G$ (no matter whether it is bipartite or not), $h(i,j)$, the expected hitting time from $i$ to $j$ satisfies $h(i,j) < 2m$.)

I should also note that in its original unedited version, the question did not state that $i$ and $j$ are adjacent, so while the earlier answers are relevant to the original question, they are not relevant to the new edited version.

If $i$ and $j$ are adjacent, the commute time $C(i,j)=h(i,j)+h(j,i)=2mR(i,j)$, where $R(i,j)$ is the effective resistance between $i$ and $j$ in G, and is at most $1$ (since $i$ and $j$ are connected by an edge). This shows that $h(i,j)<2m$ when $i$ and $j$ are adjacent in $G$, since both $h(i,j)$ and $h(j,i)$ are strictly positive.

The identity $C(i,j) = 2mR(i,j)$ holds for arbitrary vertices $i$ and $j$. A proof appears, for example in the book by Lyons and Peres.

$\endgroup$
1
  • $\begingroup$ Thank you; if the result you stated holds also for bipartite graphs (I will check the reference you provided) then this does indeed answer my question! $\endgroup$
    – user6584
    Oct 17, 2011 at 14:16
0
$\begingroup$

@user686 Sorry, for my earlier answer: I didn't realize you were concerned about $2m+1$ vs $2m$. However, in that case I don't think the claim made there is true if you add a self loop only at $j$. Random walks starting at $i$ in the case of both $G'$ and and $G$ can be coupled so that they take the $same$ steps at the same times until they reach $j$. This means that $H(i,j)_G=H(i,j)_{G'}$, and the expected hitting times therefore have to be equal.

Also, since the bound $h_{i,j} < 2m+1$ is not correct in general (on a path of $m$ nodes, $h_{i,j}$ can be as large as $\Theta(m^2)$), is your graph special?

PS: I updated my earlier answer since it seems it was not addressing your main concern.

$\endgroup$
4
  • $\begingroup$ On the other hand, if $i$ and $j$ are adjacent, the commute time $C(i,j) = h(i,j) + h(j,i) = 2mR(i,j)$, where $R(i,j)$ is the effective resistance between $i$ and $j$ in $G$, and is at most $1$. This shows that $h(i,j) < 2m$ when $i$ and $j$ are adjacent in $G$, since both $h(i,j)$ and $h(j,i)$ are strictly positive. $\endgroup$
    – Piyush
    Oct 12, 2011 at 18:41
  • $\begingroup$ It is fine (and sometimes better) to keep the answer even when it is incorrect or does not answer the question so others will not make the same mistake, just add a line to the start of the answer explaining why it is incorrect or does not answer the question. :) $\endgroup$
    – Kaveh
    Oct 12, 2011 at 20:57
  • $\begingroup$ @Kaveh: Thanks, I am new here. My earlier answer was not incorrect but didn't answer what user686 considered the important issue. $\endgroup$
    – Piyush
    Oct 13, 2011 at 0:58
  • $\begingroup$ @Piyush: just add a line in bold to its top so it is clear that it is not answering the question. $\endgroup$
    – Kaveh
    Oct 13, 2011 at 1:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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