{
  "id": "math/0406447",
  "version": "v2",
  "published": "2004-06-23T03:51:42.000Z",
  "updated": "2005-03-30T12:44:56.000Z",
  "title": "Robust reconstruction on trees is determined by the second eigenvalue",
  "authors": [
    "Svante Janson",
    "Elchanan Mossel"
  ],
  "comment": "Published at http://dx.doi.org/10.1214/009117904000000153 in the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)",
  "journal": "Annals of Probability 2004, Vol. 32, No. 3, 2630-2649",
  "doi": "10.1214/009117904000000153",
  "categories": [
    "math.PR",
    "math.CO",
    "math.SP",
    "math.ST",
    "stat.TH"
  ],
  "abstract": "Consider a Markov chain on an infinite tree T=(V,E) rooted at \\rho. In such a chain, once the initial root state \\sigma(\\rho) is chosen, each vertex iteratively chooses its state from the one of its parent by an application of a Markov transition rule (and all such applications are independent). Let \\mu_j denote the resulting measure for \\sigma(\\rho)=j. The resulting measure \\mu_j is defined on configurations \\sigma=(\\sigma(x))_{x\\in V}\\in A^V, where A is some finite set. Let \\mu_j^n denote the restriction of \\mu to the sigma-algebra generated by the variables \\sigma(x), where x is at distance exactly n from \\rho. Letting \\alpha_n=max_{i,j\\in A}d_{TV}(\\mu_i^n,\\mu_j^n), where d_{TV} denotes total variation distance, we say that the reconstruction problem is solvable if lim inf_{n\\to\\infty}\\alpha_n>0. Reconstruction solvability roughly means that the nth level of the tree contains a nonvanishing amount of information on the root of the tree as n\\to\\infty. In this paper we study the problem of robust reconstruction. Let \\nu be a nondegenerate distribution on A and \\epsilon >0. Let \\sigma be chosen according to \\mu_j^n and \\sigma' be obtained from \\sigma by letting for each node independently, \\sigma(v)=\\sigma'(v) with probability 1-\\epsilon and \\sigma'(v) be an independent sample from \\nu otherwise. We denote by \\mu_j^n[\\nu,\\epsilon ] the resulting measure on \\sigma'. The measure \\mu_j^n[\\nu,\\epsilon ] is a perturbation of the measure \\mu_j^n.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2005-03-30T12:44:56.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60K35",
      "60J80",
      "82B26"
    ],
    "keywords": [
      "robust reconstruction",
      "second eigenvalue",
      "resulting measure",
      "denotes total variation distance",
      "markov transition rule"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2004math......6447J"
    }
  }
}