Limit theorems for recursive algorithms

AbstractWe study random algorithms arising in multiple access communication problems. We prove asymptotic stability and normality. Numerical analysis of the performance of the algorithms is provided. The general convergence theorems in the paper are based on contraction properties of suitably chosen (ideal) metrics. The approach allows us to prove asymptotic normality under very weak conditions, superseding the results of other authors. Stable and multivariate extensions seem to be analysed for the first time in the literature. Our numerical results show that the Capetanakis—Tsybakov—Mikhailov (CTM) algorithm and the trinomial algorithm have a similar asymptotic behaviour. For a small number of users there are some differences concerning the quality of the normal approximation