Robust reconstruction on trees is determined by the second eigenvalue
| dc.creator | Janson, Svante | |
| dc.creator | Mossel, Elchanan | |
| dc.date | 2004-06-23 | |
| dc.date | 2005-03-30 | |
| dc.date.accessioned | 2026-07-07T08:06:19Z | |
| dc.date.available | 2026-07-07T08:06:19Z | |
| dc.description | Consider a Markov chain on an infinite tree T=(V,E) rooted at ρ. In such a chain, once the initial root state σ(ρ) 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 μ_j denote the resulting measure for σ(ρ)=j. The resulting measure μ_j is defined on configurations σ=(σ(x))_{x\in V}\in A^V, where A is some finite set. Let μ_j^n denote the restriction of μto the sigma-algebra generated by the variables σ(x), where x is at distance exactly n from ρ. Letting α_n=max_{i,j\in A}d_{TV}(μ_i^n,μ_j^n), where d_{TV} denotes total variation distance, we say that the reconstruction problem is solvable if lim inf_{n\to\infty}α_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 νbe a nondegenerate distribution on A and ε>0. Let σbe chosen according to μ_j^n and σ' be obtained from σby letting for each node independently, σ(v)=σ'(v) with probability 1-εand σ'(v) be an independent sample from νotherwise. We denote by μ_j^n[ν,ε] the resulting measure on σ'. The measure μ_j^n[ν,ε] is a perturbation of the measure μ_j^n. | |
| dc.description | 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) | |
| dc.identifier | https://arxiv.org/abs/math/0406447 | |
| dc.identifier | http://arxiv.org/abs/math/0406447 | |
| dc.identifier | Annals of Probability 2004, Vol. 32, No. 3, 2630-2649 | |
| dc.identifier | doi:10.1214/009117904000000153 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/130566 | |
| dc.subject | Probability | |
| dc.subject | Combinatorics | |
| dc.subject | Spectral Theory | |
| dc.subject | Statistics Theory | |
| dc.subject | 60K35 (Primary) 60J80, 82B26 (Secondary) | |
| dc.title | Robust reconstruction on trees is determined by the second eigenvalue | |
| dc.type | text |