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( n). For small values of k, there exist k-wise inde- pendent 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 equired bty demonstrating a pairwise independent random walk with steps uniform in ±1 and expected maximum distance O(√n1gn) 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 lg2 n). Also, for any even k ≥ 4, we show that the kth movement of the maximum distance of any k-wise independent random walk is O(nk/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 equiva- lent statement that requires only 4-wise independent random variables with bounded second moments, which also genralizes a result of [5].