Analysis of Bin models with applications in coding theory

Bin models represent one of the most frequently used descriptive representations of phenomena as diverse as spreading of disease, financial market fluctuation, error burst generation in communication channels, or learning in neurological systems. When analyzing randomized bin models, it is usually of interest to evaluate some statistic depending on the characteristics of the distribution of objects (balls) into bins. Due to the inherent mutual dependence of the occupancy variables, determining this statistic may represent a challenging analytical task. In this paper, we describe a class of invertible probabilistic transforms that result in mapping dependent bin occupancies into independent random variables. The statistics of interest can be evaluated in the transform domain and then appropriately inverted to obtain an exact solution. Or, for problems with large values for the parameters, the asymptotic behavior of the statistics can be deduced from the transform itself. Possible analytical applications of these new transform techniques in coding theory include the binning schemes related to Luby transform (LT), Slepian-Wolf, and deletion-error correcting coding.