3-wise Independent Random Walks can be Slightly Unbounded

Shyam Narayanan

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…