Abstract
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 4wise independent random walk on a line over n steps is O(sqrt{n}). For small values of k, there exist kwise 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, 4wise independence is required by demonstrating a pairwise independent random walk with steps uniform in +/ 1 and expected maximum distance Omega(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 2wise independent random walk is always O(n lg^2 n). Also, for any even k >= 4, we show that the kth moment of the maximum distance of any kwise independent random walk is O(n^{k/2}). The previous two results generalize to random walks tracking insertiononly streams, and provide higher moment bounds than currently known. We also prove a generalization of Kolmogorov's maximal inequality by showing an asymptotically equivalent statement that requires only 4wise independent random variables with bounded second moments, which also generalizes a result of Blasiok.
BibTeX  Entry
@InProceedings{narayanan:LIPIcs:2019:11278,
author = {Shyam Narayanan},
title = {{Pairwise Independent Random Walks Can Be Slightly Unbounded}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {63:163:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771252},
ISSN = {18688969},
year = {2019},
volume = {145},
editor = {Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11278},
URN = {urn:nbn:de:0030drops112787},
doi = {10.4230/LIPIcs.APPROXRANDOM.2019.63},
annote = {Keywords: kwise Independence, Random Walks, Moments, Chaining}
}
Keywords: 

kwise Independence, Random Walks, Moments, Chaining 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) 
Issue Date: 

2019 
Date of publication: 

17.09.2019 