{
  "id": "2112.07930",
  "version": "v2",
  "published": "2021-12-15T07:22:47.000Z",
  "updated": "2022-05-25T10:03:01.000Z",
  "title": "The secretary problem with non-uniform arrivals via a left-to-right-minimum exponentially tilted distribution",
  "authors": [
    "Ross G. Pinsky"
  ],
  "comment": "We have added some additional remarks and some additional references",
  "categories": [
    "math.PR"
  ],
  "abstract": "We solve the secretary problem in the case that the ranked items arrive in a statistically biased order rather than in uniformly random order. The bias is given by the left-to-right-minimum exponentially tilted distribution with parameter $q\\in(0,\\infty)$. That is, for $\\sigma\\in S_n$, $P_n(\\sigma)$ is proportional to $q^{\\text{LR}^{-}_n(\\sigma)}$, where the left-to-right minimum statistic $\\text{LR}^-_n$ is defined by $$ \\text{LR}^{-}_n(\\sigma)=|\\{j\\in[n]: \\sigma_j=\\min\\{\\sigma_i:1\\le i\\le j\\}\\}|,\\ \\sigma\\in S_n. $$ For $q\\in(0,1)$, higher ranked items tend to arrive earlier than in the case of the uniform distribution, and for $q\\in(1,\\infty)$, they tend to arrive later. In the classical problem, the asymptotically optimal strategy is to reject the first $M_n^*$ items, where $M_n^*\\sim\\frac ne$, and then to select the first item ranked higher than any of the first $M_n^*$ items (if such an item exists). This yields $e^{-1}$ as the limiting probability of success. With the above bias on arrivals, we calculate the asymptotic behavior of the optimal strategy $M_n^*$ and the corresponding limiting probability of success, for all regimes of $\\{q_n\\}_{n=1}^\\infty$. In particular, if the leading order asymptotic behavior of $\\{q_n\\}_{n=1}^\\infty$ is at least $\\frac1{\\log n}$, and if also its order is no more than $o(n)$, then the limiting probability of success when using an asymptotically optimal strategy is $e^{-1}$; otherwise, this limiting probability of success is greater than $e^{-1}$. Also, the limiting fraction of numbers, $\\lim_{n\\to\\infty}\\frac{M^*_n}n$, that are summarily rejected by an asymptotically optimal strategy lies in $(0,1)$ if and only if $\\lim_{n\\to\\infty}q_n\\in(0,\\infty)$.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2022-05-25T10:03:01.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60G40",
      "60C05"
    ],
    "keywords": [
      "left-to-right-minimum exponentially tilted distribution",
      "secretary problem",
      "non-uniform arrivals",
      "asymptotically optimal strategy",
      "limiting probability"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}