Uniform asymptotics of Poisson approximation to the Poisson-binomial distribution

February 20th, 2008

Hsien-Kuei Hwang and Vytas Zacharovas, Uniform asymptotics of Poisson approximation to the Poisson-binomial distribution, submitted for publication.
pdf (339 KB)

Posted in Uncategorized | Comments Off

Profiles of tries

July 24th, 2006

Gahyun Park, Hsien-Kuei Hwang, Pierre Nicodème, Wojciech Szpankowski. Profiles of tries, submitted for publication (July 23, 2006).

Download: pdf (576 KB)

Posted in Uncategorized | Comments Off

Local limit theorems for finite and infinite urn models

April 19th, 2006

Hsien-Kuei Hwang, Svante Janson. Local limit theorems for finite and infinite urn models, Annals of Probability, 36(3) (2007), 992-1022.

Download: pdf (347KB) | ps.gz (170KB)

Posted in Uncategorized | Comments Off

Phase changes in random point quadtrees

February 28th, 2006

Hua-Huai Chern, Michael Fuchs, Hsien-Kuei Hwang. Phase changes in random point quadtrees, ACM Transactions on Algorithms, 3:2, Article No. 12 (2007), 51 psges. (Dedicated to the memory of Ching-Zong Wei).

Download: pdf (482 KB) | gz (294 KB)

Posted in Uncategorized | Comments Off

Profiles of random trees: plane-oriented recursive trees

February 13th, 2006

Hsien-Kuei Hwang. Profiles of random trees: plane-oriented recursive trees, Random Structures and Algorithms, 30:3 (2007), 380-413. An extended abstract of this paper appeared in the special issue of Discrete Mathematics and Theoretical Computer Science for the 2005 International Conference on the Analysis of Algorithms (Barcelona, June 6-10, 2005).

Download: pdf (327 KB) | gz (228 KB)

Posted in Uncategorized | Comments Off

Width and mode of the profile for random trees of logarithmic height

September 13th, 2005

Luc Devroye, Hsien-Kuei Hwang. Width and mode of the profile for some random trees of logarithmic height, Annals of Applied Probability, 16 (2006), 886-918 (revised version October 22, 2005).

Download: pdf (305 KB) | ps.gz (227 KB)

Posted in Uncategorized | Comments Off

Partial match queries in random k-d trees

July 13th, 2005

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)

Posted in Uncategorized | Comments Off

Profiles of random trees: Limit theorems for random recursive trees and binary search trees

July 13th, 2005

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)

Posted in Uncategorized | Comments Off

Maxima in hypercubes

July 13th, 2005

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)

Posted in Uncategorized | Comments Off

Profiles of random trees: correlation and width of random recursive trees and binary search trees

July 12th, 2005

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)

Posted in Uncategorized | Comments Off

Bimodality and phase transitions in the profile variance of random binary search trees

July 12th, 2005

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)

Posted in Uncategorized | Comments Off

Limit distribution of the number of consecutive records

July 12th, 2005

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)

Posted in Uncategorized | Comments Off

Digital sums and divide-and-conquer recurrences: Fourier expansions and absolute convergence

July 12th, 2005

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)

Posted in Uncategorized | Comments Off

Phase changes in random recursive structures and algorithms

July 12th, 2004

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)

Posted in Uncategorized | Comments Off

Efficient maxima-finding algorithms for random planar samples

July 13th, 2003

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)

Posted in Uncategorized | Comments Off

Berry-Esseen bounds for the number of maxima in planar regions

July 13th, 2003

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)

Posted in Uncategorized | Comments Off

Partial match queries in random quadtrees

July 13th, 2003

Hua-Huai Chern, Hsien-Kuei Hwang. Partial match queries in random quadtrees. SIAM Journal on Computing, 32 (4) (2003), 904–915.

Download: pdf (212 KB) | gz (69 KB)

Posted in Uncategorized | Comments Off

Analysis in distribution of two randomized algorithms for finding the maximum in a broadcast communication model

July 13th, 2003

Wei-Mei Chen, Hsien-Kuei Hwang. Analysis in distribution of two randomized algorithms for finding the maximum in a broadcast communication model. Journal of Algorithms, 46:2 (2003), 140-177.

Download: pdf (334 KB) | gz (169 KB)

Posted in Uncategorized | Comments Off

Second phase changes in random m-ary search trees and generalized quicksort

July 13th, 2003

Hsien-Kuei Hwang. Second phase changes in random m-ary search trees and generalized quicksort: convergence rates. Annals of Probability, 31:2 (2003), 609-629.

Download: pdf (264 KB) | gz (131 KB)

Posted in Uncategorized | Comments Off

An asymptotic theory for recurrence relations based on minimization and maximization

July 12th, 2003

Hsien-Kuei Hwang, Tsung-Hsi Tsai. An asymptotic theory for recurrence relations based on minimization and maximization. Theoretical Computer Science, 290:3 (2003), 1475-1501. MathReview: 1 937 733

Download: pdf (264 KB) | gz (111 KB)

Posted in Uncategorized | Comments Off