Three‐wise independent random walks can be slightly unbounded. Issue 3 (3rd January 2022) - Narayanan, Shyam
Abstract: Recently, many streaming algorithms have utilized generalizations of the fact that the expected maximum distance of any 4‐wise independent random walk on a line over n steps is O ( n ) O(n) . In this paper, we show that 4‐wise independence is required for all of these algorithms, by constructing a 3‐wise independent random walk with expected maximum distance Ω ( n lg n ) Ω (nn) from the origin. We prove that this bound is tight for the first and second moment, and also extract a surprising matrix inequality from these results. Next, we consider a generalization where the steps X i X_i are k ‐wise independent random variables with bounded p th moments. We highlight the case k = 4, p = 2 k=4, p=2 : here, we prove that the second moment of the furthest distance traveled is O ∑ X i 2 O(X_i^2) . This implies an asymptotically stronger statement than Kolmogorov's maximal inequality that requires only 4‐wise independent random variables, and generalizes a recent result of Błasiok.