Invariance: intuition

Outline

Topics

  • Intuition behind invariance
  • Invariance as a fixed point

Rationale

Invariance is the key condition needed to establish a law of large numbers for Markov chains. Hence it is useful to build some intuition on what it means.

Analogy: fixed point iteration

Goal here: gaining some intuition on what is the notion of \(\pi\)-invariance, using an analogy.

Fixed point iteration

  • You are given a function \(f(x)\)
  • Game:
    • Pick any starting point \(x_1\) (e.g. in figure, \(x_1 = -1\))
    • Compute \(x_2 = f(x_1)\) (e.g. in figure, \(x_2 = 0.5\))
    • Compute \(x_3 = f(x_2)\)
    • Compute \(x_4 = f(x_3)\)
    • etc.
  • Can we predict where will \(x_n\) end up after an infinite number of iterations?
    • Hint: try to understand why the figure has a blue line \(y = x\).

Fixed points

Surprise: sometimes, we can predict where \(\lim_{n\to\infty} x_n\) ends up!

Definition: a fixed point of a function \(f\) is a point \(x\) such that \(f(x) = x\).

Question: what are the fixed point in this picture?

The 3 yellow points. These are the points where the curve intersect the line \(y = x\).

Example:

  • look at the fixed point iteration picture more closely,
  • note that indeed here we end up at a fixed point (blue diagonal line shows the linear function \(y = x\))

Back to Markov chain

Intuition: \(\pi\)-invariance means “\(\pi\) acts like a fixed-point of \(K\).”

Connection:

  • replace “points” by “probability distributions”,
  • replace “function application” by “simulating the Markov chain for 1 step”,
  • replace “fixed point” by “\(\pi\)-invariance”.