Pseudobinomiality of the Sticky Random Walk
summary
Defines a sticky random walk (first bit uniform, later bits stay with prob (1+λ)/2) and proves the Hamming-weight distribution differs from Bin(n,1/2) by total variation Θ(λ) for small λ. Proof uses Fourier expansion in Kravchuk functions, Parseval and an exact expectation lemma to reduce TV to an L2 sum and get O(λ). Also proves Pr[weight even and > n/2] = 1/4 + o(1), with a central-coefficient bound O(n^{-1/4}); follow-up work tightens that to O(n^{-1/2}) and extends to general expanders.
AI-written summary · about