0
$\begingroup$
  • 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 ?.

$\endgroup$

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.