Abstract
Random walks on expanders are a central and versatile tool in pseudorandomness. If an arbitrary half of the vertices of an expander graph are marked, known Chernoff bounds for expander walks imply that the number M of marked vertices visited in a long nstep random walk strongly concentrates around the expected n/2 value. Surprisingly, it was recently shown that the parity of M also has exponentially small bias.
Is there a common unification of these results? What other statistics about M resemble the binomial distribution (the Hamming weight of a random nbit string)? To gain insight into such questions, we analyze a simpler model called the sticky random walk. This model is a natural stepping stone towards understanding expander random walks, and we also show that it is a necessary step. The sticky random walk starts with a random bit and then each subsequent bit independently equals the previous bit with probability (1+λ)/2. Here λ is the proxy for the expander’s (second largest) eigenvalue.
Using Krawtchouk expansion of functions, we derive several probabilistic results about the sticky random walk. We show an asymptotically tight Θ(λ) bound on the total variation distance between the (Hamming weight of the) sticky walk and the binomial distribution. We prove that the correlation between the majority and parity bit of the sticky walk is bounded by O(n^{1/4}). This lends hope to unifying Chernoff bounds and parity concentration, as well as establishing other interesting statistical properties, of expander random walks.
BibTeX  Entry
@InProceedings{guruswami_et_al:LIPIcs.ITCS.2021.48,
author = {Venkatesan Guruswami and Vinayak M. Kumar},
title = {{Pseudobinomiality of the Sticky Random Walk}},
booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
pages = {48:148:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771771},
ISSN = {18688969},
year = {2021},
volume = {185},
editor = {James R. Lee},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13587},
URN = {urn:nbn:de:0030drops135870},
doi = {10.4230/LIPIcs.ITCS.2021.48},
annote = {Keywords: Expander Graphs, Fourier analysis, Markov Chains, Pseudorandomness, Random Walks}
}
Keywords: 

Expander Graphs, Fourier analysis, Markov Chains, Pseudorandomness, Random Walks 
Collection: 

12th Innovations in Theoretical Computer Science Conference (ITCS 2021) 
Issue Date: 

2021 
Date of publication: 

04.02.2021 