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.

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

a: b: c:

Click for choices

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

Click for answer

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. On the other hand, with the “hub” model, 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.

Global balance

Question: combine

• the definition of \(\pi\)-invariance, with
  
• the formula we derived for the marginals of a Markov chain, i.e., \[\mu_2(x') = \sum_x \mu_1(x) K(x' | x),\]

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

Click for choices

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.

Click for answer

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).”

Click for choices

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.

Click for answer

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?

Click for choices

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.

Click for answer

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.