{
  "id": "math/0604067",
  "version": "v3",
  "published": "2006-04-04T11:12:33.000Z",
  "updated": "2007-07-26T07:57:23.000Z",
  "title": "When the law of large numbers fails for increasing subsequences of random permutations",
  "authors": [
    "Ross G. Pinsky"
  ],
  "comment": "Published at http://dx.doi.org/10.1214/009117906000000728 in the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)",
  "journal": "Annals of Probability 2007, Vol. 35, No. 2, 758-772",
  "doi": "10.1214/009117906000000728",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "Let the random variable $Z_{n,k}$ denote the number of increasing subsequences of length $k$ in a random permutation from $S_n$, the symmetric group of permutations of $\\{1,...,n\\}$. In a recent paper [Random Structures Algorithms 29 (2006) 277--295] we showed that the weak law of large numbers holds for $Z_{n,k_n}$ if $k_n=o(n^{2/5})$; that is, \\[\\lim_{n\\to\\infty}\\frac{Z_{n,k_n}}{EZ_{n,k_n}}=1\\qquad in probability.\\] The method of proof employed there used the second moment method and demonstrated that this method cannot work if the condition $k_n=o(n^{2/5})$ does not hold. It follows from results concerning the longest increasing subsequence of a random permutation that the law of large numbers cannot hold for $Z_{n,k_n}$ if $k_n\\ge cn^{1/2}$, with $c>2$. Presumably there is a critical exponent $l_0$ such that the law of large numbers holds if $k_n=O(n^l)$, with $l<l_0$, and does not hold if $\\limsup_{n\\to\\infty}\\frac{k_n}{n^l}>0$, for some $l>l_0$. Several phase transitions concerning increasing subsequences occur at $l=1/2$, and these would suggest that $l_0={1/2}$. However, in this paper, we show that the law of large numbers fails for $Z_{n,k_n}$ if $\\limsup_{n\\to\\infty}\\frac{k_n}{n^{4/9}}=\\infty$. Thus, the critical exponent, if it exists, must satisfy $l_0\\in[{2/5},{4/9}]$.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2007-07-26T07:57:23.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60F05",
      "60C05"
    ],
    "keywords": [
      "large numbers fails",
      "random permutation",
      "large numbers holds",
      "critical exponent",
      "second moment method"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2006math......4067P"
    }
  }
}