• 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 ?.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.