Pairwise Independent Random Walks can be Slightly Unbounded

Shyam Narayanan

Published 2018-07-13Version 1

A family of problems that have been studied in the context of various streaming algorithms are generalizations of the fact that the expected maximum distance of a $4$-wise independent random walk on a line over $n$ steps is $O(\sqrt{n})$. For small values of $k$, there exist $k$-wise independent random walks that can be stored in much less space than storing $n$ random bits, so these properties are often useful for lowering space bounds. In this paper, we show that for all of these examples, $4$-wise independence is required by demonstrating a pairwise independent random walk with steps uniform in $\pm 1$ and expected maximum distance $O(\sqrt{n} \lg n)$ from the origin. We also show that this bound is tight for the first and second moment, i.e. the expected maximum square distance of a $2$-wise independent random walk is always $O(n \lg^2 n).$ Also, for any even $k \ge 4,$ we show that the $k$th moment of the maximum distance of any $k$-wise independent random walk is $O(n^{k/2}).$ The previous two results generalize to random walks tracking insertion-only streams, and provide higher moment bounds than currently known. We also prove a generalization of Kolmogorov's maximal inequality by showing an equivalent statement that requires only $4$-wise independent random variables with bounded second moments, which also generalizes a result of [5].