# Random walk in a graph

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).$$
• 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. – user3208617 Nov 7 '15 at 19:15
• 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$. – A.S. Nov 7 '15 at 19:32
• @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. – A.S. Nov 7 '15 at 20:00