Partial match queries in random k-d trees
Hua-Huai Chern, Hsien-Kuei Hwang. Partial match queries in random k-d trees, SIAM Journal on Computing, 35:6 (2006) 1440-1466.
Download: pdf (243 KB) | gz (170 KB)
Profiles of random trees: Limit theorems for random recursive trees and binary search trees
Michael Fuchs, Hsien-Kuei Hwang, Ralph Neininger. Profiles of random trees: Limit theorems for random recursive trees and binary search trees, Algorithmica, 46:3-4 (2006), 367-407. (This revised version largely simplifies the calculations of the moments in the previous version, using the approach introduced in this paper. )
Download: pdf (328 KB) | gz (213 KB)
Maxima in hypercubes
Zhi-Dong Bai, Luc Devroye, Hsien-Kuei Hwang, Tsung-Hsi Tsai. Maxima in hypercubes, Random Structures and Algorithms, 27(3) (2005), 290-309.
Download: pdf (202 KB) | gz (147 KB)
Profiles of random trees: correlation and width of random recursive trees and binary search trees
Michael Drmota, Hsien-Kuei Hwang. Profiles of random trees: correlation and width of random recursive trees and binary search trees, Advances in Applied Probability, 37:2 (2005), 321–341. (Corrigendum: Page 323, Corollary 1.2, case (ii): add the condition sign(s＿{n,k}) = sign(t＿{n,h}).)
Download: pdf (559 KB) | gz (355 KB)
Bimodality and phase transitions in the profile variance of random binary search trees
Michael Drmota, Hsien-Kuei Hwang. Bimodality and phase transitions in the profile variance of random binary search trees, SIAM Journal on Discrete Mathematics, 19:1 (2005), 19-45.
Download: pdf (302 KB) | gz (182 KB)
Limit distribution of the number of consecutive records
Hua-Huai Chern, Hsien-Kuei Hwang. Limit distribution of the number of consecutive records, Random Structures and Algorithms, 26:4 (2005), 404-417.
Download: pdf (164 KB) | gz (96 KB)
Digital sums and divide-and-conquer recurrences: Fourier expansions and absolute convergence
Peter J. Grabner, Hsien-Kuei Hwang. Digital sums and divide-and-conquer recurrences: Fourier expansions and absolute convergence, Constructive Approximation, 21:2 (2005), 149-179.
Download: pdf (343 KB) | gz (210 KB)
Phase changes in random recursive structures and algorithms
Hsien-Kuei Hwang. Phase changes in random recursive structures and algorithms (a brief survey), Proceedings of the Workshop on Probability with Applications to Finance and Insurance, edited by T. L. Lai, H. Yang and S. P. Yung, World Scientific, pp. 82--97, June 2004. (An English translation based mainly on my Chinese paper published in NSC Natural Science Newsletter, 14(3)(2002), 74-80.)
Download: pdf (218 KB) | gz (98 KB)
Efficient maxima-finding algorithms for random planar samples
Wei-Mei Chen, Hsien-Kuei Hwang, Tsung-Hsi Tsai. Efficient maxima-finding algorithms for random planar samples, Discrete Mathematics and Theoretical Computer Science, 6 (2003), 107--122.
Download: pdf (197 KB) | gz (67 KB)
Berry-Esseen bounds for the number of maxima in planar regions
Zhi-Dong Bai, Hsien-Kuei Hwang, Tsung-Hsi Tsai. Berry-Esseen bounds for the number of maxima in planar regions, Electronic Journal of Probability, 8 (2003), Paper 9, 26 pages. (Errata: Page 4, line 6 (and page 6, line 9): $phi_n(y)$ should be defined
as $phi_n(y) := E(e^{M_ny})/E(e^{N(mu_n,sigma_n^2)y})$; Page 4, line 7 should read $|phi_n^{(m)}(0)| le m! A^m n^{m/6}$.)
Download: pdf (223 KB) | gz (176 KB)