{
  "id": "1108.2633",
  "version": "v2",
  "published": "2011-08-12T14:54:31.000Z",
  "updated": "2011-09-24T15:42:13.000Z",
  "title": "Optimal Sequential Selection of a Unimodal Subsequence of a Random Sequence",
  "authors": [
    "Alessandro Arlotto",
    "J. Michael Steele"
  ],
  "journal": "Combinatorics, Probability and Computing (2011) 20, 799--814",
  "doi": "10.1017/S0963548311000411",
  "categories": [
    "math.PR",
    "math.CO",
    "math.OC"
  ],
  "abstract": "We consider the problem of selecting sequentially a unimodal subsequence from a sequence of independent identically distributed random variables, and we find that a person doing optimal sequential selection does within a factor of the square root of two as well as a prophet who knows all of the random observations in advance of any selections. Our analysis applies in fact to selections of subsequences that have d+1 monotone blocks, and, by including the case d=0, our analysis also covers monotone subsequences.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2011-09-24T15:42:13.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60C05",
      "90C40",
      "60G42",
      "90C27",
      "90C39"
    ],
    "keywords": [
      "optimal sequential selection",
      "unimodal subsequence",
      "random sequence",
      "covers monotone subsequences",
      "independent identically distributed random variables"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1108.2633A"
    }
  }
}