Results on Markov chains, cuts, the flat cubic and metric Markov cotype, with their assumptions

The course proves the statements below; each link leads to the statement with its assumptions and its proof. The lessons are self-checked by the writing AI; independent mathematical review is not complete.

• Geometric and uniform times — Lemma 3.1. For a stationary chain and data in any metric space, the mean squared displacement at an independent geometric time of mean t is at most 28 times its average over the times 1, ..., t.
• Cut representation — Lemma 1.1. Finitely many points of l1 are T(z_i) for binary vectors z_i with ||x_i - x_j||_1 = ||z_i - z_j||_(1,w) = ||z_i - z_j||_H^2, where T is affine and 1-Lipschitz from the weighted l1 norm into l1.
• Flatness of the cubic (OpenAI) — Lemma 2.1. The squared weighted l1 increment of the coordinatewise cubic 3r^2 - 2r^3 is at most 108 times the second-order remainder of the fourth-power potential centred at a binary vector.
• Telescoping along a harmonic function — Lemma 3.1. Along a harmonic function of a finite Markov chain, the expected squared increments after the cubic are at most 108 times the increase of the fourth-power potential.
• The jump identity — Lemma 2.1. For the walk killed with probability 1/(t+1), the expected squared jumps after the cubic add up to B + t E_A.
• The terminal cost — Lemma 2.2. B + t E_A is at most 108 times the mean squared l1 displacement of the data at the killing time.
• Metric Markov cotype two of l1 (OpenAI) — Theorem 3.1. The cotype inequality holds in l1 with C^2 = 3024 for every stochastic matrix and stationary vector.
• Expected medians (OpenAI) — Proposition 4.1. The new point at i is the expected coordinatewise median of the data at three independent stopped-walk endpoints from i.
• Complex scalars — Corollary 5.1. The complex space l1 has metric Markov cotype two with constant at most 12 sqrt(42).

Reading order

Read the lessons in order. The first sets up the definition and the comparison of time averages. The second provides the cut representation and the flat cubic. The third proves the theorem.