統計学輪講（第11回）

日時	  2002年 6月 4日(火)    15時〜16時40分
場所	  経済学部新棟３階第３教室
講演者    Prof. Hosam Mahmoud(George Washington Univ.)
演題      A study of an algorithm for finding order statistics via
          analytic probability

概要
    Certain analytic techniques have proved effective in the study of
averages for random discrete structures and algorithms. Typically one 
considers a generating function for the sequence of averages. One then 
sets up a functional equation (usually arising from a recurrence) and 
solves it asymptotically by a tool-kit that involves a variety of 
integral transforms (such as the Mellin transform). The behavior of 
the generating function near its dominant singularities captures the 
asymptotic nature of the averages. (Typically, non-dominant 
singularities contribute periodic oscillations.)

    To address distributions instead of only average-case analysis, 
these methods are extended to bivariate generating functions. One 
still considers dominant singularities, which are now functions of 
a second variable. The analysis is most informative in the 
neighborhood of certain values for this second variable. The analysis 
therefore is viewed as a perturbation. We illustrate this route by 
a problem that arises in sorting algorithms. To find the limit 
distribution of a sum of dependent random variables, the analysis 
involves perturbation of Rice's integration method which will be 
explained in a tutorial introduction.