{
  "id": "1307.6919",
  "version": "v1",
  "published": "2013-07-26T04:29:52.000Z",
  "updated": "2013-07-26T04:29:52.000Z",
  "title": "Convergence of a Second Order Markov Chain",
  "authors": [
    "Shenglong Hu",
    "Liqun Qi"
  ],
  "comment": "16 pages, 3 figures",
  "categories": [
    "math.NA",
    "math.OC"
  ],
  "abstract": "In this paper, we consider convergence properties of a second order Markov chain. Similar to a column stochastic matrix is associated to a Markov chain, a so called {\\em transition probability tensor} $P$ of order 3 and dimension $n$ is associated to a second order Markov chain with $n$ states. For this $P$, define $F_P$ as $F_P(x):=Px^{2}$ on the $n-1$ dimensional standard simplex $\\Delta_n$. If 1 is not an eigenvalue of $\\nabla F_P$ on $\\Delta_n$ and $P$ is irreducible, then there exists a unique fixed point of $F_P$ on $\\Delta_n$. In particular, if every entry of $P$ is greater than $\\frac{1}{2n}$, then 1 is not an eigenvalue of $\\nabla F_P$ on $\\Delta_n$. Under the latter condition, we further show that the second order power method for finding the unique fixed point of $F_P$ on $\\Delta_n$ is globally linearly convergent and the corresponding second order Markov process is globally $R$-linearly convergent.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-07-26T04:29:52.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "second order markov chain",
      "convergence",
      "unique fixed point",
      "corresponding second order markov process",
      "second order power method"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1307.6919H"
    }
  }
}