Seminar über Wahrscheinlichkeitstheorie:
Zufällige Bäume

Kontakt

Prof. Dr. R. Neininger
Prof. Dr. A. Wakolbinger
Dipl. Math. C. Boeinghoff
Dipl. Math. H. Sulzbach

Organisatorisches

Termin: Do 14-16 Uhr, Ort: 711 klein, Beginn: n. Vereinb.
Bachelor - Mathematik: Module BaM-SB-1, BaM-WP,
Master - Mathematik: Modul MaM-PR-1,
Lehramt (L3) - Mathematik: Modul L3M-ME.

Vorträge

29. 10. 09: Galton-Watson-Prozesse und Irrfahrten I: Konstruktion von Dwass
Xiaotian Huang


Literatur: Dwass (1969) (nur in der Bibliothek)

05. 11. 09: Galton-Watson-Prozesse und Irrfahrten II: Konstruktion von Bennies / Kersting
Nathalie Urbanska


Literatur: Bennies / Kersting (1999)

12. 11. 09: Binärsuchbäume: Local Counters
Ivan Kulis


Grenzwertsätze für Binärsuchbäume mit kombinatorischen Beobachtungen und klassischen Grenzwertsätzen

Literatur: Devroye (1991)

19. 11. 09: Fortsetzung vom Vortrag GW-Prozesse und Irrfahrten II
Nathalie Urbanska


26. 11. 09: Pfadlänge zufälliger Binärsuchbäume I
Amir Haqshenas


Ein Grenzwertsatz für die Pfadlänge zufällige Binärsuchbäume mit dem Martingalkonvergenzsatz.

Literatur: Regnier (1989), Mahmoud (1991)

03. 12. 09: Pfadlänge zufälliger Binärsuchbäume II
Piravean Chandirakanthan


Charaktersisierung der Grenzverteilung durch eine stochastische Fixpunktgleichung.

Literatur: Rösler (1991)

10. 12. 09: Ahnenlinien und der Kontourprozess
Alexander Hoffmann


Literatur: Bennies / Kersting (1999)

17. 12. 09: Besuch des Frankfurter Weihnachtsmarkts


14. 01. 10: Höhe in Tries und Patricia Tries
Kevin Leckey


Gesetz großer Zahlen und Tail-Ungleichungen der Höhe in Tries und Patricia Tries

Literatur: Devroye (2002b)

21. 01. 10: Immigrierende Yulebäume
Patrick Lahr


Literatur: Tavare (1987)

28. 01. 10: Das Problem der kleinsten Zuweisung
Stephanie Leifheit


Exakter Wert der Erwartung des minimalen assigments in einer quadratischen Matrix mit unabhaengigen, exponentialverteilten Eintraegen.

Literatur: Wästlund (2009)

11. 02. 10: Der Bolthausen-Sznitman-Coalescent
Stephan Gufler


Literatur: Berestycki

Literatur

Bennies, J., Kersting, G. (2000) A random walk approach to Galton Watson Trees Journal of Theoretical Probability 13, 3 777-803.

Berestycki, N. (2009) Recent progress in Coalescent theory.". Lecture notes.

Bertoin, J. (2008) The structure of the allelic partition of the total population for Galton-Watson processes with neutral mutations Preprint, arXiv:0711.3852

Devroye (1991) Limit laws for local counters in random binary search trees. Random Structures Algorithms 2, 303-315.

Devroye (2002a) Limit laws for sums of functions of subtrees of random binary search trees. SIAM J. Comput., 32, 152-171.

Devroye (2002b) Laws of large numbers and tail inequalities for random tries and PATRICIA trees. J. Comput. Appl. Math., 142, 27-37.

Dwass, M. (1969) The total progeny in a branching process and a related random walk J. Appl. Prob. 6, 682-686.

Fill, J.A., Janson, S. (2000) Smoothness and decay properties of the limiting Quicksort density function. Mathematics and computer science (Versailles, 2000), 53-64, Trends Math., Birkhäuser, Basel.

Geiger, J. (1999) Elementary new proofs of classical limit theorems for Galton-Watson Processes J. Appl. Prob. 36, 301-309.

Kennedy, D. P. (1975) The Galton Watson Process conditioned on the total progeny J. Appl. Prob. 12, 800-806.

Mahmoud, H.M. (1991) Limiting distributions for path lengths in recursive trees. Probab. Engrg. Inform. Sci. 5, 53-59.

McDiarmid, C.J.H., Hayward, R.B. (1996) Large deviations for Quicksort. J. Algorithms 21, 476-507.
[Bis einschließlich Abschnitt 2.3.]

Regnier, M. (1989) A limiting distribution for quicksort. RAIRO Inform. Theor. Appl. 23, 335-343.

Rösler, U. (1991) A limit theorem for "Quicksort". RAIRO Inform. Theor. Appl. 25, 85-100.

Steele, J. M. (1987) On Frieze's zeta(3) limit for lengths of minimal spanning trees. Discrete applied mathematics 18, 99-103.

Steele, J. M. (1997) Probability theory and combinatorial optimization. CBMS-NSF Regional Conference Series in Applied Mathematics, 69. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997
[Seiten 4-5, 27-29.]

Tavare, S. (1987) The Birth process with immigration, and the genealogical structure of large populations J. Math. Biol. 25, 161-168.

Wästlund, J. (2009) An easy proof of the zeta(2) limit in the random assignment problem.". Electronic communications in probability 14, 261-269.