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

<blockquote>
  <p>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 <em>same</em> 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.</p>
</blockquote>

CC BY-SA 3.0
2011-10-12T13:43:39.190Z
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.)
user6584
CC BY-SA 3.0
2011-10-12T13:47:53.933Z
@user686 Can you share the reference?
Tyson Williams
CC BY-SA 3.0
2011-10-12T07:09:02.427Z
2011-10-13T03:01:12.843Z
2011-10-13T03:01:12.843Z
Piyush
<p>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) &lt; 2m$.) </p>

<p><em>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.</em></p>

<p>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)&lt;2m$ when $i$ and $j$ are adjacent in $G$, since both $h(i,j)$ and $h(j,i)$ are strictly positive.</p>

<p>The identity $C(i,j) = 2mR(i,j)$ holds for arbitrary vertices $i$ and $j$.  A proof appears, for example in the <a href="http://mypage.iu.edu/~rdlyons/prbtree/prbtree.html" rel="nofollow" title="book">book</a> by Lyons and Peres.</p>

CC BY-SA 3.0
2011-10-17T14:16:09.617Z
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!
user6584
CC BY-SA 3.0
2011-10-16T23:50:07.697Z
2011-10-17T00:02:15.443Z
2011-10-17T00:02:15.443Z
Piyush
<p>@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&#39;$ 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&#39;}$, and the expected hitting times therefore have to be equal.</p>

<p>Also, since the bound $h_{i,j} &lt; 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?</p>

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

CC BY-SA 3.0
2011-10-12T18:41:02.153Z
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.
Piyush
CC BY-SA 3.0
2011-10-12T20:57:40.657Z
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. :)
Kaveh
CC BY-SA 3.0
2011-10-13T00:58:31.187Z
@Kaveh: Thanks, I am new here.  My earlier answer was not incorrect but didn't answer what user686 considered the important issue.
Piyush
CC BY-SA 3.0
2011-10-13T01:04:00.040Z
@Piyush: just add a line in bold to its top so it is clear that it is not answering the question.
Kaveh
CC BY-SA 3.0
2011-10-12T17:32:22.793Z
2011-10-13T00:56:36.633Z
2011-10-13T00:56:36.633Z
Piyush
<p>(My original question still has not been answered. I have added further clarifications.)</p>

<p>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. </p>

<p>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&#39;$ non-bipartite; applying the fundamental theorem of Markov chains to $G&#39;$ we then get that $h_{i,j} &lt; 2m+1$ in $G&#39;$, and this is clearly also an upper bound for $h_{i,j}$ in $G$. </p>

<p>Question: Is it true that the stronger claim $h_{i,j} &lt; 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?</p>

<pr.probability><random-walks>
Technical question about random walks
user6584
# Technical question about random walks

(Asked by: username_0 on 2011-10-12)

(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?

**Tags:** pr.probability, random-walks

---

## 3 answers

### Answer by username_1 on 2011-10-12. Score: 5

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

> **Comments:**
> **username_0**: 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.)  
> **username_2**: @user686 Can you share the reference?  

---

### Answer by username_1 on 2011-10-16. Score: 2

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](http://mypage.iu.edu/~rdlyons/prbtree/prbtree.html "book") by Lyons and Peres.

> **Comments:**
> **username_0**: 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!  

---

### Answer by username_1 on 2011-10-12. Score: 0

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

> **Comments:**
> **username_1**: 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.  
> **username_3**: 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. :)  
> **username_1**: @Kaveh: Thanks, I am new here.  My earlier answer was not incorrect but didn't answer what user686 considered the important issue.  
> **username_3**: @Piyush: just add a line in bold to its top so it is clear that it is not answering the question.  

---

