diff c98320d..d214c92 switch_chain_polynomial_mixing_v2.txt
diff --git a/switch_chain_polynomial_mixing_v2.txt b/switch_chain_polynomial_mixing_v2.txt index 0364349..ba70a81 100644 --- a/switch_chain_polynomial_mixing_v2.txt +++ b/switch_chain_polynomial_mixing_v2.txt @@ -25,20 +25,10 @@ That single sentence hides a long and beautiful mathematical story. This paper proves the *simple undirected form of the Kannan-Tetali- Vempala conjecture*: the switch chain on simple undirected graphs mixes in polynomial time for EVERY degree sequence that can actually occur. -It also gives an EXACT uniform sampler. What you are reading now is a -guided tour that keeps every ingredient of the original proof but -explains each step in plain language, so a diligent high schooler can -follow along. +It also gives an EXACT uniform sampler. --------------------------------------------------------------------------- -HOW TO READ THIS -------------------------------------------------------------------------- -The paper is structured so that you can stop at any section and still -have learned something real. Section 1 fixes vocabulary and states the -main theorem. Sections 2-7 are the "engine room": they prove a single -operator inequality H^2 >= H. Section 8 converts that into a mixing -time. Section 9 upgrades nearby-uniform to exactly uniform. Three simple objects recur throughout: @@ -59,12 +49,7 @@ The main engine inequality H^2 >= H is proved in two pieces: Then Section 8 assembles the two pieces and shows the kernel of H is constants, which is what gives a spectral gap. -You do NOT need to understand every technical lemma to follow the arc -of the argument. But if you do follow the arc, you will end up knowing -what a spectral gap is, why mixing time has anything to do with -eigenvalues, and how to correct the small bias of a Markov chain to -make sampling exactly uniform. Those are three of the deepest -everyday ideas in modern probability, and they are all on show here. + -------------------------------------------------------------------------- SECTION 1. VOCABULARY AND THE MAIN THEOREM