Concentration of multivariate random recursive sequences arising in the analysis of algorithms [Elektronische Ressource] / von Tämur Ali Khan

Concentration ofMultivariate Random Recursive Sequencesarising in the Analysis of AlgorithmsDissertationzur Erlangung des Doktorgrades derNaturwissenschaftenvorgelegt beim Fachbereich Informatik und Mathematikder Johann Wolfgang Goethe-Universit¨atFrankfurt am MainvonT¨amur Ali Khanaus Frankfurt am MainFrankfurt am Main 2006(D30)vom Fachbereich Informatik und Mathematikder Johann Wolfgang Goethe-Universit¨at als Dissertation angenommen.Dekan: Prof. Dr.-Ing. Detlef Kr¨omkerGutachter: Prof. Dr. Ralph NeiningerProf. Dr. G´abor LugosiDatum der Disputation: 19.03.2007ContentsIntroduction v1 Probabilistic Analysis for Minimax Trees and Minimax Tree Eval-uation 11.1 Survey of Game Trees . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Probabilistic Analysis for Randomized Boolean Decision Tree Evalu-ation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.2.1 Worst case input . . . . . . . . . . . . . . . . . . . . . . . . . 101.2.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.2.3 Karp and Zhang’s 2-type branching process . . . . . . . . . . 141.2.4 The recursive point of view . . . . . . . . . . . . . . . . . . . 151.2.5 Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151.2.6 d-ary Boolean decision trees . . . . . . . . . . . . . . . . . . . 201.3 A Limit Law for the Root Value of Minimax Trees . . . . . . . . . . 221.3.1 Technical preliminaries . . . . . . . . . . .