Amnon Ta-Shma, Ron Zadiario

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., ...
more >>>