diff 9fd1fa8..bd7269b switch_chain_polynomial_mixing_v2.txt
diff --git a/switch_chain_polynomial_mixing_v2.txt b/switch_chain_polynomial_mixing_v2.txt
index e0e9e6f..fda358f 100644
--- a/switch_chain_polynomial_mixing_v2.txt
+++ b/switch_chain_polynomial_mixing_v2.txt
@@ -36,9 +36,9 @@ 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-8 are the "engine room": they prove a single
-operator inequality H^2 >= H. Section 9 converts that into a mixing
-time. Section 10 upgrades nearby-uniform to exactly uniform.
+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:
@@ -1991,46 +1991,40 @@ Compute ||h^0||^2 = E_pi[ (h^0)^2 ]. Since pi_d(G) = 1/M:
h^0(G) = M - 1,
h^0(H) = -1 (for H != G),
- ||h^0||^2 = (1/M)(M-1)^2 + (1 - 1/M)(-1)^2 = (M-1)/M <= 1.
-
-Wait, small correction: ||h^0||^2 <= 1/pi_d(G) = M. The exact bound:
-(1/M)(M-1)^2 + (M-1)/M = (M-1)(M-1+1)/M = M - 1 <= M. Good.
+ ||h^0||^2 = (1/M)(M-1)^2 + ((M-1)/M) * 1
+ = (M-1)^2/M + (M-1)/M
+ = (M-1) <= M.
So ||h^t||^2 <= (1 - gamma_0)^{2t} ||h^0||^2 <= M (1 - gamma_0)^{2t}.
And TV distance:
-||P_d^t(G, .) - pi_d||_TV = (1/2) sum_H pi_d(H) |P_d^t(G, H)/pi_d(H) - 1|
+||P_d^t(G, .) - pi_d||_TV = (1/2) sum_H pi_d(H) | P_d^t(G, H)/pi_d(H) - 1 |
= (1/2) E_pi |h^t|
<= (1/2) sqrt( E_pi |h^t|^2 ) (Cauchy-Schwarz)
= (1/2) ||h^t||
- <= (1/2) sqrt(M) (1 - gamma_0)^t. Good.
-
-Mixing time bound: pick
-
- t = ceil( (24 n^2 C(n,4)) * ( log 2 + (1/2) log M ) ).
+ <= (1/2) sqrt(M) (1 - gamma_0)^t.
-Then (1 - gamma_0)^t e^{gamma_0 t} <= ... hmm, we need (1-gamma)^t <= e^{-gamma t} (valid since log(1-x) <= -x), and using log 2 + (1/2) log M as our target:
+Mixing time bound. Pick
- (1 - gamma_0)^t <= e^{-gamma_0 t} = e^{-gamma_0 ceil(gamma_0^{-1} * target)}
- <= e^{-target} = e^{-log 2 - (1/2) log M} = 1/(2 sqrt M).
+ t = ceil( 24 n^2 C(n,4) * ( log 2 + (1/2) log M ) ).
-So (1/2) sqrt(M) * (1 - gamma_0)^t <= 1/4. Good, t_mix <= t.
+Using (1 - gamma)^t <= e^{-gamma t} (valid since log(1-x) <= -x):
-Now simplify t. Use M <= 2^{C(n,2)}, so (1/2) log M <= (1/2) C(n,2) log 2.
-Also for n >= 4: 1 + C(n,2)/2 = 1 + n(n-1)/4 <= n^2.
-And 24 n^2 C(n,4) <= n^6. So
+ (1 - gamma_0)^t <= e^{-gamma_0 t}
+ = e^{-gamma_0 ceil( gamma_0^{-1} * (log 2 + (1/2) log M) )}
+ <= e^{-log 2 - (1/2) log M}
+ = 1 / (2 sqrt M).
- t <= ceil( n^6 * n^2 * log 2 * (1 + C(n,2)/2) / n^0 * ... )
+So (1/2) sqrt(M) * (1 - gamma_0)^t <= 1/4. Hence t_mix(d) <= t.
-Hmm let me redo. t = ceil(24 n^2 C(n,4) * (log 2 + (1/2) log M))
+Simplification. Use M <= 2^{C(n,2)} and n >= 4:
- <= ceil(24 n^2 C(n,4) * log 2 * (1 + C(n,2)/2))
+ log 2 + (1/2) log M <= (log 2) * ( 1 + C(n,2)/2 ) <= (log 2) * n^2,
+ 24 n^2 C(n,4) <= n^6.
- <= ceil(n^6 * log 2 * n^2)
-
- = ceil(n^8 log 2)
+So
- <= ceil(n^8) = n^8 <= 2 n^8.
+ t <= ceil( (log 2) * n^8 ) <= ceil( n^8 ) = n^8 <= 2 n^8.
So t_mix(d) <= 2 n^8. Theorem 1 proven.
@@ -2210,7 +2204,7 @@ arbitrary hosts, weighted edges, etc.) are open in general. Bounds
for sampling FROM a specific distribution other than uniform remain
an active problem.
-The big idea you should take away. Three moves, all simple in
+The big idea you should take away. Four moves, all simple in
hindsight:
1. Replace "one switch at a time" by "resample a whole fiber at once".
@@ -2226,8 +2220,7 @@ hindsight:
4. Upgrade to exact uniform via a rare-branch correction.
-Four moves, actually. The whole paper is these four moves, developed
-carefully.
+The whole paper is these four moves, developed carefully.
If you followed this far, you know what a spectral gap is, why mixing
time depends on it, how to compare one Markov chain to another, and how