Let (u,v) be any edge in a connected component. Why is the expectation E[T] <= 2 * |E| in a random walk. Here T denotes a random variable with the numbers of steps taken in a random walk starting at vertex u until v is encountered in an undirected graph.
This was a subtask of Oded Goldreichs exercise 1.5.4 3 from foundations of cryptography.
It mentions a hint.
"Consider the 'frequency' with which this edge is traversed in a certain direction during an infinite random walk, and note that this frequency is independent of the identitiy of the edge and direction.".
Each edge has the same probability to be traversed in both directions. But how will this help me?
I know E[T] = 1 * Pr[T=1] + 2 * Pr[T=2] + ..., and the probability for Pr[T=1] is minimal 1/|E|. My idea in general without this hint was to try to maximize E[T] by constructing a graph with |E| edges and trying to keep the probability for the smallest facotors like 1 small, and steadily increasing for bigger factors. I can't seem to think of an algorithm that always constructs our graph to maximize E[T]. But already using all |E| edges for 1-step-v-reached would be fatal of course.
 A: Let $(X_k)_{k \ge 0}$ with $x_0 = u$ be the random walk in the graph, starting from $u$.
We can define a new Markov chain $(Y_k)_{k \ge 0}$ in terms of the random walk: let $Y_0 = (v,u)$ and let $Y_k = (X_{k-1}, X_k)$ for $k \ge 1$. The states in this Markov chain are ordered pairs of adjacent vertices in the graph: edges, together with a direction we're walking in.
It can be checked that for this new Markov chain, the uniform distribution is a stationary distribution: every state $(x,y)$ has probability $\frac1{2|E|}$. There are $\deg(x)$ states that can be followed by $(x,y)$, and each one goes to $(x,y)$ with probability $\frac1{\deg(x)}$.
In a finite, irreducible Markov chain like this one, there is a unique stationary distribution $\pi$, and we can show that the expected time until we return to a state $x$ is $\frac1{\pi_x}$. In particular, in the Markov chain $(Y_k)_{k\ge0}$, the expected time until we return to state $Y_0 = (v,u)$ is exactly $2|E|$.

Now, to return to the question you asked: the value $2|E|$ is an upper bound for the number of steps until we reach $v$ from $u$, because it's the exact expected time until we take a step from $v$ to $u$, and in order to take such a step, we must certainly reach $v$.
