Balance equations

Outline

Topics

  • Global balance (synonym: invariance)
  • Detailed balance (synonym: time-reversibility)

Rationale

We need formulas to help us prove that MH is \(\pi\)-invariant (and hence combined with irreducibility, admits a LLN).

Example

We continue our eccentric tourists example…

Question: which travelling scheme(s) are \(\pi\)-invariant?

Intuition: \(\pi\)-invariance in this context just means the fraction of tourists in each city will stay constant over time.

Look at the Figures: Consider the following situations, where let us say in all case you observe that the planes are always full.

  1. Pairs of cities, where each pair of cities is assigned a fixed number of planes going back and forth between the two cities.
  2. A tour where a fixed number of planes, equal to the number of cities, go around the world on a common route.
  3. A central “hub”, where all flights land at the hub.

Follow-up: how to express “fraction of planes between cities \(x\) and \(x'\)” in terms of \(\mu_i\), \(K\)?

a: b: c:

  1. a only.
  2. b only.
  3. c only.
  4. a, b only.
  5. b, c only.

The correct answer is 4.

Intuition: in (a) and (b) there is always the same number of planes leaving and arriving each airport on a given weekend. Since the planes are full, this means the city’s tourist population stays constant.

On the other hand, with the “hub” model, (c) it is easy to see that the city with the hub airport will have a number of people in it increasing over time, hence not invariant.

Follow-up question: mathematically, the number of planes is proportional to \(\mu_i(x) K(x' | x)\). It is the flow from state \(x\) to \(x'\).

Global balance

Question: combine

to get an equation characterizing \(\pi\)-invariance in terms of \(K\).

  1. \(\pi(x) K(x' | x) = \pi(x') K(x | x')\)
  2. \(\pi(x) K(x' | x) = \sum_x \pi(x) K(x' | x)\)
  3. \(\pi(x) = \sum_{x'} \pi(x) K(x | x')\)
  4. \(\pi(x') = \sum_x \pi(x) K(x' | x)\)
  5. None of the above.

The correct answer is 4.

This equation, \(\pi(x') = \sum_x \pi(x) K(x' | x)\) is called global balance.

Detailed balance

Question: write mathematically “pairs of cities, where each pair of cities is assigned a fixed number of planes going back and forth between the two cities (planes always full).”

  1. \(\pi(x) K(x' | x) = \pi(x') K(x | x')\)
  2. \(\pi(x) K(x' | x) = \sum_x \pi(x) K(x' | x)\)
  3. \(\pi(x) = \sum_{x'} \pi(x) K(x | x')\)
  4. \(\pi(x') = \sum_x \pi(x) K(x' | x)\)
  5. None of the above.

The correct answer is 1.

  • We want the number of tourist moving from city 1 to 2 to be the same as from city 2 to 1.
  • Flow from city 1 to 2:
    • The fraction of tourist in city 1: \(\pi(x)\)
    • The fraction of those going to city 2: \(K(x' | x)\)
    • Therefore the flow in one direction: \(\pi(x) K(x' | x)\).
  • By a similar argument, flow from 2 to 1: \(\pi(x') K(x | x')\)

This equation, \(\pi(x) K(x' | x) = \pi(x') K(x | x')\) is called detailed balance.

Relationship between detailed and global balance

Question: what is the relationship between local and global balance? Does one imply the other?

  1. Global balance implies local balance (converse is false).
  2. Local balance implies global balance (converse is false).
  3. Local balance holds iff global balance holds.
  4. Additional conditions are needed.
  5. None of the above ever hold.

Local balance implies global balance (converse is false).

Proposition: if local balance holds \[\pi(x) K(x' | x) = \pi(x') K(x | x'),\] then global balance holds \[\pi(x') = \sum_x \pi(x) K(x' | x).\]

Proof: Suppose local balance holds, then

\[\begin{align*} \sum_x \pi(x) K(x' | x) &= \sum_x \pi(x') K(x | x') \;\;\text{(by local balance)} \\ &= \pi(x') \sum_x K(x | x') \\ &= \pi(x'). \;\;\text{(since $K(\cdot|x')$ is a probability)} \end{align*}\]

Reverse implication does not hold: The “tour” travelling scheme shows that there are situations where global balance holds but not detailed balance.