Three‐wise independent random walks can be slightly unbounded. Issue 3 (3rd January 2022)

• Record Type: Journal Article
• Authors: Narayanan, Shyam
• Is Part Of: Random structures & algorithms. Volume 61:Issue 3(2022)
• Page Start: 573
• Page End: 598
• Publication Date: 2022-01-03
• Subjects: k‐wise independence -- moments -- random walk; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21075
• Languages: English
• ISSNs: 1042-9832

Abstract

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\left(\sqrt{n}\right) $$ . 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 ) $$ \Omega \left(\sqrt{n}\lg n\right) $$ 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\left(\sum {X}_i^2\right) $$ . 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.