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