Wojciech Szpankowski, Purdue University

Analytical approach to some problems involving order statistics

Limiting distributions of order statistics such as the maximum or minimum of a sequence of (independent and/or dependent) random variables are mostly studied by probabilistic methods. In this talk we would like to argue that analytical methods (e.g., generating functions, etc.) are well suited to such studies. We first show how to prove the classical extreme distributions (e.g., the double exponential distribution) for i.i.d. random variables. Even for this well studied problem we must resort to Hadamard's product, Rice's formula, and the saddle-point method. As a reward, we obtain a uniform treatment of some extreme statistics for dependent random variables. We apply our analytical approach to derive limiting distributions of some extreme statistics arising in the analysis of algorithms. We discuss such problems as the depth in digital trees, the time to elect a leader, probabilistic counting algorithms, and so forth. In some of these problems we also use analytical poissonization and depoissonization technique. We complete the talk with a list of open problems.