A rapidly mixing Markov chain has tx(e) polynomially bounded in the input size (in e is automatically polynomially bounded if the chain is irreducible and aperiodic). Hence we need a polynomial bound for d. To find such a bound define the ergodic flow F_S out of S as follows.
The probability of leaving S under the condition that the chain is in S is F_S /p (S). The conductance of the Markov chain is the following.
Conductance and p 2 are related by the theorem: If the Markov chain is irreducible, aperiodic and time reversible...