Concentration Inequalities and its Application to Ranking Problem

Abstract

In this thesis, we study some basic concentration inequalities and their applications to a ranking problem. Concentration inequalities refer to the phenomenon of concentration of a function of independent random variables around the mean. In this thesis, we mainly study how the sum of independent random variables concentrate around the mean. These inequal- ities are used to study error bounds for estimated ranks in the BTL model [SSD17], which gives a framework to determine the ranks for n objects based on k pair-wise comparisons between pairs of objects. We then study the effect of perturbing the transition matrix of a defined Markov chain on the errors in the estimated rank. In some cases, we obtain an ex- plicit lower bound on the number of comparisons k, in terms of the perturbations, needed to obtain a “good” estimation for the underlying rank. Finally, through simulations, we study what kind of perturbation matrices lead to larger errors.