BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

Source author record

Hsien-Kuei Hwang

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record
math.PRmath.COData Structures and AlgorithmsDiscrete Mathematicsmath.NTmath.STStatistics Theory

Catalog footprint

Research overview

15works
7topics
4close collaborators

Actions

Is this your work?

Log in to claim
Open graphBrowse papers

Published work

15 publications

preprint2016arXiv

Dependence and phase changes in random mm-ary search trees

We study the joint asymptotic behavior of the space requirement and the total path length (either summing over all root-key distances or over all root-node distances) in random mm-ary search trees. The covariance turns out to exhibit a change of asymptotic behavior: it is essentially linear when 3≤m≤133\le m\le 13 but becomes of higher order when m≥14m\ge14. Surprisingly, the corresponding asymptotic correlation coefficient tends to zero when 3≤m≤263\le m\le 26 but is periodically oscillating for larger mm. Such a less anticipated phenomenon is not exceptional and we extend the results in two directions: one for more general shape parameters, and the other for other classes of random log-trees such as fringe-balanced binary search trees and quadtrees. The methods of proof combine asymptotic transfer for the underlying recurrence relations with the contraction method.

Open access
preprint2016arXiv

Dependence between External Path-Length and Size in Random Tries

We study the size and the external path length of random tries and show that they are asymptotically independent in the asymmetric case but strongly dependent with small periodic fluctuations in the symmetric case. Such an unexpected behavior is in sharp contrast to the previously known results that the internal path length is totally positively correlated to the size and that both tend to the same normal limit law. These two examples provide concrete instances of bivariate normal distributions (as limit laws) whose correlation is 00, 11 and periodically oscillating.

Open access
preprint2014arXiv

Distribution of the sum-of-digits function of random integers: a survey

We review some probabilistic properties of the sum-of-digits function of random integers. New asymptotic approximations to the total variation distance and its refinements are also derived. Four different approaches are used: a classical probability approach, Stein's method, an analytic approach and a new approach based on Krawtchouk polynomials and the Parseval identity. We also extend the study to a simple, general numeration system for which similar approximation theorems are derived.

Open access
preprint2014arXiv

Probabilistic analysis of the (1+1)-evolutionary algorithm

We give a detailed analysis of the cost used by the (1+1)-evolutionary algorithm. The problem has been approached in the evolutionary algorithm literature under various views, formulation and degree of rigor. Our asymptotic approximations for the mean and the variance represent the strongest of their kind. The approach we develop is also applicable to characterize the limit laws and is based on asymptotic resolution of the underlying recurrence. While most approximations have their simple formal nature, we elaborate on the delicate error analysis required for rigorous justifications.

Open access
preprint2013arXiv

A binomial splitting process in connection with corner parking problems

A special type of binomial splitting process is studied. Such a process can be used to model a high-dimensional corner parking problem, as well as the depth of random PATRICIA tries (a special class of digital tree data structures). The later also has natural interpretations in terms of distinct values in iid geometric random variables and the occupancy problem in urn models. The corresponding distribution is marked by logarithmic mean and bounded variance, which is oscillating, if the binomial parameter pp is not equal to 1/2, and asymptotic to 1 in the unbiased case. Also, the limiting distribution does not exist owing to periodic fluctuations.

Open access
preprint2013arXiv

An analytic approach to the asymptotic variance of trie statistics and related structures

We develop analytic tools for the asymptotics of general trie statistics, which are particularly advantageous for clarifying the asymptotic variance. Many concrete examples are discussed for which new Fourier expansions are given. The tools are also useful for other splitting processes with an underlying binomial distribution. We specially highlight Philippe Flajolet's contribution in the analysis of these random structures.

Open access
preprint2013arXiv

Limit laws of the coefficients of polynomials with only unit roots

We consider sequences of random variables whose probability generating functions are polynomials all of whose roots lie on the unit circle. The distribution of such random variables has only been sporadically studied in the literature. We show that the random variables are asymptotically normally distributed if and only if the fourth normalized (by the standard deviation) central moment tends to 3, in contrast to the common scenario for polynomials with only real roots for which a central limit theorem holds if and only if the variance goes unbounded. We also derive a representation theorem for all possible limit laws and apply our results to many concrete examples in the literature, ranging from combinatorial structures to numerical analysis, and from probability to analysis of algorithms.

Open access
preprint2012arXiv

Analysis of an exhaustive search algorithm in random graphs and the n^{c\log n} -asymptotics

We analyze the cost used by a naive exhaustive search algorithm for finding a maximum independent set in random graphs under the usual G_{n,p} -model where each possible edge appears independently with the same probability p. The expected cost turns out to be of the less common asymptotic order n^{c\log n}, which we explore from several different perspectives. Also we collect many instances where such an order appears, from algorithmics to analysis, from probability to algebra. The limiting distribution of the cost required by the algorithm under a purely idealized random model is proved to be normal. The approach we develop is of some generality and is amenable for other graph algorithms.

Open access
preprint2011arXiv

Threshold phenomena in k-dominant skylines of random samples

Skylines emerged as a useful notion in database queries for selecting representative groups in multivariate data samples for further decision making, multi-objective optimization or data processing, and the kk-dominant skylines were naturally introduced to resolve the abundance of skylines when the dimensionality grows or when the coordinates are negatively correlated. We prove in this paper that the expected number of kk-dominant skylines is asymptotically zero for large samples when 1≤k≤d−11\le k\le d-1 under two reasonable (continuous) probability assumptions of the input points, dd being the (finite) dimensionality, in contrast to the asymptotic unboundedness when k=dk=d. In addition to such an asymptotic zero-infinity property, we also establish a sharp threshold phenomenon for the expected (d−1d-1)-dominant skylines when the dimensionality is allowed to grow with nn. Several related issues such as the dominant cycle structures and numerical aspects, are also briefly studied.

Open access
preprint2010arXiv

Asymptotic variance of random symmetric digital search trees

Asymptotics of the variances of many cost measures in random digital search trees are often notoriously messy and involved to obtain. A new approach is proposed to facilitate such an analysis for several shape parameters on random symmetric digital search trees. Our approach starts from a more careful normalization at the level of Poisson generating functions, which then provides an asymptotically equivalent approximation to the variance in question. Several new ingredients are also introduced such as a combined use of the Laplace and Mellin transforms and a simple, mechanical technique for justifying the analytic de-Poissonization procedures involved. The methodology we develop can be easily adapted to many other problems with an underlying binomial distribution. In particular, the less expected and somewhat surprising n(log⁡n)2n(\log n)^2-variance for certain notions of total path-length is also clarified.

Open access
preprint2010arXiv

Multivariate records based on dominance

We consider three types of multivariate records in this paper and derive the mean and the variance of their numbers for independent and uniform random samples from two prototype regions: hypercubes [0,1]d[0,1]^d and dd-dimensional simplex. Central limit theorems with convergence rates are established when the variance tends to infinity. Effective numerical procedures are also provided for computing the variance constants to high degree of precision.

Open access
preprint2010arXiv

Psi-series method in random trees and moments of high orders

An unusual and surprising expansion of the form pn=ρ−n−1(6n+185+3363125n−5+10083125n−6+smaller order terms), p_n = ρ^{-n-1}(6n +\tfrac{18}5+ \tfrac{336}{3125} n^{-5}+\tfrac{1008}{3125} n^{-6} +\text{smaller order terms}), as n→∞n\to\infty, is derived for the probability pnp_n that two randomly chosen binary search trees are identical (in shape and in labels of all corresponding nodes). A quantity arising in the analysis of phylogenetic trees is also proved to have a similar asymptotic expansion. Our method of proof is new in the literature of discrete probability and analysis of algorithms, and based on the psi-series expansions for nonlinear differential equations. Such an approach is very general and applicable to many other problems involving nonlinear differential equations; many examples are discussed and several attractive phenomena are discovered.

Open access

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.