{
  "id": "1711.04059",
  "version": "v1",
  "published": "2017-11-11T02:04:06.000Z",
  "updated": "2017-11-11T02:04:06.000Z",
  "title": "On The Time Constant for Last Passage Percolation on Complete Graph",
  "authors": [
    "Xian-Yuan Wu",
    "Rui Zhu"
  ],
  "comment": "12 pages, 1 figure",
  "categories": [
    "math.PR"
  ],
  "abstract": "This paper focuses on the time constant for last passage percolation on complete graph. Let $G_n=([n],E_n)$ be the complete graph on vertex set $[n]=\\{1,2,\\ldots,n\\}$, and i.i.d. sequence $\\{X_e:e\\in E_n\\}$ be the passage times of edges. Denote by $W_n$ the largest passage time among all self-avoiding paths from 1 to $n$. First, it is proved that $W_n/n$ converges to constant $\\mu$, where $\\mu$ is called the time constant and coincides with the essential supremum of $X_e$. Second, when $\\mu<\\infty$, it is proved that the deviation probability $P(W_n/n\\leq \\mu-x)$ decays as fast as $e^{-\\Theta(n^2)}$, and as a corollary, an upper bound for the variance of $W_n$ is obtained. Finally, when $\\mu=\\infty$, lower and upper bounds for $W_n/n$ are given.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-11-11T02:04:06.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "complete graph",
      "time constant",
      "passage percolation",
      "upper bound",
      "largest passage time"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 12,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}