TR24-118 Authors: Amnon Ta-Shma, Ron Zadiario

Publication: 14th July 2024 11:38

Downloads: 163

Keywords:

Numerous works have studied the probability that a length $t-1$ random walk on an expander is confined to a given rectangle $S_1 \times \ldots \times S_t$, providing both upper and lower bounds for this probability.

However, when the densities of the sets $S_i$ may depend on the walk length (e.g., when all set are equal and the density is $1-1/t$), the currently best known upper and lower bounds are very far from each other. We give an improved confinement lower bound that almost matches the upper bound.

We also study the more general question, of how well random walks fool various classes of test functions.

Recently, Golowich and Vadhan proved that random walks on $\lambda$-expanders fool \emph{Boolean},

\emph{symmetric} functions up to a $O(\lambda)$ error in \emph{total variation distance}, with \emph{no dependence on the labeling bias}.

Our techniques extend this result to cases not covered by it, e.g., to the confinement problem to $S_1 \times \ldots \times S_t$, where all sets $S_i$ either have density $\rho$ or $1-\rho$, for arbitrary $\rho$.

Technique-wise, we extend Beck's framework for analyzing what is often referred to as the ``flow" of linear operators, reducing it to bounding the entries of a product of $2\times 2$ matrices.