|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'500'096
Articles rated: 2609
18 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Robust reconstruction on trees is determined by the second eigenvalue | | Svante Janson
; Elchanan Mossel
; | | Date: |
23 Jun 2004 | | Journal: | Annals of Probability 2004, Vol. 32, No. 3, 2630-2649 DOI: 10.1214/009117904000000153 | | Subject: | Probability; Combinatorics; Spectral Theory; Statistics MSC-class: 60K35 (Primary) 60J80, 82B26 (Secondary) | math.PR math.CO math.SP math.ST | | Abstract: | Consider a Markov chain on an infinite tree T=(V,E) rooted at
ho. In such a chain, once the initial root state sigma(
ho) 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(
ho)=j. The resulting measure mu_j is defined on configurations sigma=(sigma(x))_{xin 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
ho. Letting alpha_n=max_{i,jin 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 oinfty}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 oinfty. In this paper we study the problem of robust reconstruction. Let
u 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
u otherwise. We denote by mu_j^n[
u,epsilon ] the resulting measure on sigma’. The measure mu_j^n[
u,epsilon ] is a perturbation of the measure mu_j^n. | | Source: | arXiv, math.PR/0406447 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER