Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLarge Degree Asymptotics and the Reconstruction Threshold of the Asymmetric Binary Channels
72
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In this paper, we consider a broadcasting process in which information is propagated from a given root node on a noisy tree network, and answer the question that whether the symbols at the nth level of the tree contain non-vanishing information of the root as n goes to infinity. Although the reconstruction problem on the tree has been studied in numerous contexts including information theory, mathematical genetics and statistical physics, the existing literatures with rigorous reconstruction thresholds established are very limited. In the remarkable work of Borgs, Chayes, Mossel and Roch (The Kesten-Stigum reconstruction bound is tight for roughly symmetric binary channels), the exact threshold for the reconstruction problem for a binary asymmetric channel on the d-ary tree is establish, provided that the asymmetry is sufficiently small, which is the first exact reconstruction threshold obtained in roughly a decade. In this paper, by means of refined analyses of moment recursion on a weighted version of the magnetization, and concentration investigations, we rigorously give a complete answer to the question of how small it needs to be to establish the tightness of the reconstruction threshold and further determine its asymptotics of large degrees.
rate research
Read More
The study of Markov processes and broadcasting on trees has deep connections to a variety of areas including statistical physics, phylogenetic reconstruction, MCMC algorithms, and community detection in random graphs. Notably, the celebrated Belief Propagation (BP) algorithm achieves Bayes-optimal performance for the reconstruction problem of predicting the value of the Markov process at the root of the tree from its values at the leaves. Recently, the analysis of low-degree polynomials has emerged as a valuable tool for predicting computational-to-statistical gaps. In this work, we investigate the performance of low-degree polynomials for the reconstruction problem on trees. Perhaps surprisingly, we show that there are simple tree models with $N$ leaves where (1) nontrivial reconstruction of the root value is possible with a simple polynomial time algorithm and with robustness to noise, but not with any polynomial of degree $N^{c}$ for $c > 0$ a constant, and (2) when the tree is unknown and given multiple samples with correlated root assignments, nontrivial reconstruction of the root value is possible with a simple, noise-robust, and computationally efficient SQ (Statistical Query) algorithm but not with any polynomial of degree $N^c$. These results clarify some of the limitations of low-degree polynomials vs. polynomial time algorithms for Bayesian estimation problems. They also complement recent work of Moitra, Mossel, and Sandon who studied the circuit complexity of Belief Propagation. We pose related open questions about low-degree polynomials and the Kesten-Stigum threshold.
In this article we study the Dyson Bessel process, which describes the evolution of singular values of rectangular matrix Brownian motions, and prove a large deviation principle for its empirical particle density. We then use it to obtain the asymptotics of the so-called rectangular spherical integrals as $m,n$ go to infinity while $m/n$ converges.
We substantially refine asymptotic logarithmic upper bounds produced by Svante Janson (2015) on the right tail of the limiting QuickSort distribution function $F$ and by Fill and Hung (2018) on the right tails of the corresponding density $f$ and of the absolute derivatives of $f$ of each order. For example, we establish an upper bound on $log[1 - F(x)]$ that matches conjectured asymptotics of Knessl and Szpankowski (1999) through terms of order $(log x)^2$; the corresponding order for the Janson (2015) bound is the lead order, $x log x$. Using the refined asymptotic bounds on $F$, we derive right-tail large deviation (LD) results for the distribution of the number of comparisons required by QuickSort that substantially sharpen the two-sided LD results of McDiarmid and Hayward (1996).
The Painleve-IV equation has two families of rational solutions generated respectively by the generalized Hermite polynomials and the generalized Okamoto polynomials. We apply the isomonodromy method to represent all of these rational solutions by means of two related Riemann-Hilbert problems, each of which involves two integer-valued parameters related to the two parameters in the Painleve-IV equation. We then use the steepest-descent method to analyze the rational solutions in the limit that at least one of the parameters is large. Our analysis provides rigorous justification for formal asymptotic arguments that suggest that in general solutions of Painleve-IV with large parameters behave either as an algebraic function or an elliptic function. Moreover, the results show that the elliptic approximation holds on the union of a curvilinear rectangle and, in the case of the generalized Okamoto rational solutions, four curvilinear triangles each of which shares an edge with the rectangle; the algebraic approximation is valid in the complementary unbounded domain. We compare the theoretical predictions for the locations of the poles and zeros with numerical plots of the actual poles and zeros obtained from the generating polynomials, and find excellent agreement.
We study the problem of characterizing when two memoryless binary asymmetric channels, described by their transition probabilities $(p,q)$ and $(p,q)$, are equivalent from the point of view of maximum likelihood decoding (MLD) when restricted to $n$-block binary codes. This equivalence of channels induces a partition (depending on $n$) on the space of parameters $(p,q)$ into regions associated with the equivalence classes. Explicit expressions for describing these regions, their number and areas are derived. Some perspectives of applications of our results to decoding problems are also presented.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
