Past exam of the mathematics course of the University of Cambridge / 2018 / ib / Paper 4 / 9H (Markov Chains)

Table of contents
- a 9H
  - Solution a
- b 9H
  - Solution b
- c 9H
  - Solution c

a

Solution

π

is an invariant distribution when

π_{j} = \sum_{i \in S} π_{i} p_{ij}

for every

j

, equivalently

π P = π

.

b

Solution

Detailed balance means

π_{i} p_{ij} = π_{j} p_{ji}

for all

i, j

. Summing over

i

gives

\sum_{i} π_{i} p_{ij} = π_{j} \sum_{i} p_{ji} = π_{j},

so detailed balance implies invariance.

c

Solution

Let

D_{i}

be the degree of a vertex and put

π_{i} = \frac{D _{i}}{\sum _{k} D _{k}} .

If

i

and

j

are adjacent, then

π_{i} p_{ij} = 1/ \sum_{k} D_{k} = π_{j} p_{ji}

; if they are not adjacent, both sides vanish. Thus the walk is in detailed balance, and its invariant distribution is proportional to vertex degree.

 Ancestors (9)

 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