Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 215 / 3 / ii

Table of contents
- Solution ii

Solution

For a nonregular graph, use the degree-weighted Hamming metric

W_{t} = \sum_{v \in V} de g (v) 1_{{σ_{t} (v) \neq = σ_{t}^{'} (v)}} .

Under the same coupling,

E [W_{t + 1} - W_{t} ∣ σ_{t}, σ_{t}^{'}] = = - \frac{1}{n} v \in D_{t} \sum de g (v) + \frac{1 - p}{n} v \sum de g (v) \frac{∣ N ( v ) \cap D _{t} ∣}{de g ( v )} - \frac{p}{n} W_{t} .

Here the final double sum equals

\sum_{u \in D_{t}} de g (u) = W_{t}

. Since

W_{0} \leq \sum_{v} de g (v) = 2∣ E ∣

and

W_{t} \geq 1

whenever the chains differ,

σ, σ^{'} max ∥ P^{t} (σ, \cdot) - P^{t} (σ^{'}, \cdot) ∥_{TV} \leq 2∣ E ∣ (1 - \frac{p}{n})^{t} .

 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