z-logo
open-access-imgOpen Access
Estimating random variables from random sparse observations
Author(s) -
Andrea Montanari
Publication year - 2008
Publication title -
european transactions on telecommunications
Language(s) - English
Resource type - Journals
eISSN - 1541-8251
pISSN - 1124-318X
DOI - 10.1002/ett.1289
Subject(s) - random variable , mathematics , combinatorics , bounded function , discrete mathematics , conditional probability distribution , probability density function , multivariate random variable , random graph , statistics , graph , mathematical analysis
Let X 1 , … , X n , be a collection of iid discrete random variables, and Y 1 , … , Y m , a set of noisy observations of such variables. Assume each observation Y a , to be a random function of a random subset of the X i ,s, and consider the conditional distribution of X i , given the observations, namely µ i ,( x i ,) ≡  ${\cal P}$ { X i , = x i ,| Y } ( a posteriori probability ). We establish a general decoupling principle among the X i ,s, as well as a relation between the distribution of µ i , and the fixed points of the associated density evolution operator. These results hold asymptotically in the large system limit, provided the average number of variables an observation depends on is bounded. We discuss the relevance of our result to a number of applications, ranging from sparse graph codes and multi‐user detection, to group testing. Copyright © 2008 John Wiley & Sons, Ltd.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here