Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 215 / 2 / a

Table of contents
- i a
  - Solution i
- ii a
  - Solution ii

i

Solution

With stationary flow

Q (x, y) = π (x) P (x, y)

, the conductance of a Markov chain is

Φ (A) = Q (A, A^{c}) / π (A)

. The bottleneck ratio and isoperimetric profile are

Φ_{*} = in f_{0 < π (A) \leq 1/2} Φ (A), Φ_{*} (r) = in f_{0 < π (A) \leq r} Φ (A), 0 < r \leq \frac{1}{2} .

ii

Solution

No transition joins distinct

A_{i}

, so

Q (A, A^{c}) = \sum_{i} Q (A_{i}, A_{i}^{c}) .

Consequently

Φ (A) = \sum_{i} \frac{π ( A _{i} )}{π ( A )} Φ (A_{i}) \geq in f_{i} Φ (A_{i}) .

 Ancestors (10)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version