# The conductance of a random walk on an undirected graph

• Consider a random walk on an undirected graph consisting of an $$n$$-vertex path with self-loops at the both ends. With the self loops, we have $$p_{xy} =1/2$$ on all edges $$\left(x,y\right)$$, and so the stationary distribution is a uniform $$1/n$$ over all vertices.
• The set with minimum normalized conductance is the set $$S$$ with probability $$\pi\left(S\right) \leq 1/2$$ having the smallest ratio of probability mass exiting it, $$\sum_{\left(x,y\right)\ \in\ \left(S, \overline{S}\right)} \pi_{x}p_{xy}$$, to probability mass inside it, $$\pi(S)$$.
• This set consists of the first $$n/2$$ vertices, for which the numerator is $$1/\left(2n\right)$$ and denominator is $$1/2$$. Thus, $$\Phi\left(S\right) = 1/n$$.

Can anyone explain the above paragraph more clearly ?.