Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 215 / 2 / b

Solution

Assume without loss of generality that

μ (f) - ν (f) = r σ

and let

m = (μ (f) + ν (f)) /2

μ (f < m) \leq \frac{4}{r ^{2}}, ν (f \geq m) \leq \frac{4}{r ^{2}} .

Using the event

{f \geq m}

∥ μ - ν ∥_{TV} \geq 1 - \frac{8}{r ^{2}} .

Start the lazy hypercube walk at

0^{n}

and write

Φ (x) = \sum_{i = 1}^{n} (- 1)^{x_{i}} = n - 2 \sum_{i = 1}^{n} x_{i} .

1 - 1/ n

, so

E_{0} Φ (X_{t}) = n (1 - 1/ n)^{t}, E_{π} Φ = 0.

The stated variance estimates allow the preceding lemma with

σ = n

and

r = n (1 - 1/ n)^{t} .

For

t = \frac{1}{2} n lo g n - C n

r^{2}

is bounded below by a constant multiple of

e^{2 C}

, uniformly for all sufficiently large

n

. Choosing

C = C (ε)

so that

1 - 8/ r^{2} > ε

, and absorbing finitely many small

n

into the constant, proves

t_{mix} (ε) g e q \frac{1}{2} n lo g n - C (ε) n .

Solved by gpt-5.6-sol high.

There are no discussions about this article yet.

There are currently no matching articles.