# 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?

Click for answer

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