This is a question about random walk from vertex $s$ in a graph (can be directed), which is defined in the following manner: The random variable $X_0$ (whose possible values is the set of vertices) takes $s$ with probability 1. The random variable $X_1$ takes a neighbor of $s$ uniformly.

After choosing the value of $X_{i-1}$, the random variable $X_i$ takes a vertex from the set of neighbors of of the vertex chosen $X_{i-1}$.

All the values of the random variables are picked independently.

Let $T_v$ be the smallest number that satisfies $X_{T_v}=v$ (The first time of arrival to $v$).

I need to prove that for every graph there exists a vertex $v$ which satisfies $E(T_v)=\Omega(n)$, such that $n$ is the number of vertices in the graph.

This is a question that I came across studying probabilistic methods and algorithms (I'm a CS student), my initial approach was to pick a random graph and prove something about the expected value of that pick but I didn't get anywhere. Thanks of the help in advance.



$$E(T_v)=\sum_{k\ge 0}P(T_v>k)\tag 1$$

Consider any path $p_k\in P_k$ of length $k\le n-2$ starting at $s$. It leaves at least $n-1-k$ vertices unvisited by time $k$, hence conditioning on $p_k$ and exchanging the order of summation we get: $$\sum_{v\ne s}P(T_v>k)=\sum_{p_k\in P_k}\sum_{v\ne s}P(T_v>k|p_k)P(p_k)\ge\sum_{p_k\in P_k}(n-1-k)P(p_k)=n-1-k\tag 2$$ Sum $(1)$ over all vertices $v\ne s$, exchange order of summation and use $(2)$:

$$\sum_{v\ne s}E(T_v)=\sum_{k\ge 0}\sum_{v\ne s}P(T_v>k)\ge \sum_{0\le k\le n-2} {(n-1-k)}=\frac {(n-1)n}2$$ Hence for some $v$,$$E(T_v)\ge \frac {n(n-1)}{2(n-1)}=\frac n 2 =\Omega(n).$$

  • $\begingroup$ I don't understand why (2) is correct, and where did you use the fact that in each step we choose uniformly from the set of neighbors of the vertex and that $T_v$ is is the first time of arrival. $\endgroup$ – user3208617 Nov 7 '15 at 19:15
  • $\begingroup$ I added an intermediate step to $(2)$. The result is independent of the details of random walk. I used definition of $T_v$ in $P(T_v>k|p_k)\in \{0,1\}$ depending on whether or not $p_k$ covers $v$. $\endgroup$ – A.S. Nov 7 '15 at 19:32
  • $\begingroup$ @user I'd even conjecture that $\exists v\in V\,s.t. E(T_v)\ge n-1$ for any random walk on a graph but don't have a quick proof of it. $\endgroup$ – A.S. Nov 7 '15 at 20:00

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.