{
  "id": "1807.04910",
  "version": "v1",
  "published": "2018-07-13T04:48:14.000Z",
  "updated": "2018-07-13T04:48:14.000Z",
  "title": "Pairwise Independent Random Walks can be Slightly Unbounded",
  "authors": [
    "Shyam Narayanan"
  ],
  "comment": "19 pages",
  "categories": [
    "math.PR",
    "cs.DM",
    "cs.DS"
  ],
  "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 $4$-wise independent random walk on a line over $n$ steps is $O(\\sqrt{n})$. For small values of $k$, there exist $k$-wise 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, $4$-wise independence is required by demonstrating a pairwise independent random walk with steps uniform in $\\pm 1$ and expected maximum distance $O(\\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 $2$-wise independent random walk is always $O(n \\lg^2 n).$ Also, for any even $k \\ge 4,$ we show that the $k$th moment of the maximum distance of any $k$-wise independent random walk is $O(n^{k/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 equivalent statement that requires only $4$-wise independent random variables with bounded second moments, which also generalizes a result of [5].",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-07-13T04:48:14.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60G50"
    ],
    "keywords": [
      "pairwise independent random walk",
      "walks tracking insertion-only streams",
      "expected maximum distance",
      "second moment",
      "wise independent random variables"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 19,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}