Browsing by Author "Fuchs, Michael"

Now showing 1 - 20 of 25

A BINOMIAL SPLITTING PROCESS IN CONNECTION WITH CORNER PARKING PROBLEMS
(2014-12-01)
Fuchs, Michael
;
Hwang, Hsien-Kuei
;
Itoh, Yoshiaki
;
Mahmoud, Hosam H.
;
應用數學系
This paper studies a special type of binomial splitting process. Such a process can be used to model a high dimensional corner parking problem as well as determining the depth of random PATRICIA (practical algorithm to retrieve information coded in alphanumeric) tries, which are a special class of digital tree data structures. The latter also has natural interpretations in terms of distinct values in independent and identically distributed geometric random variables and the occupancy problem in urn models. The corresponding distribution is marked by a logarithmic mean and a bounded variance, which is oscillating, if the binomial parameter p is not equal to 1/2, and asymptotic to one in the unbiased case. Also, the limiting distribution does not exist as a result of the periodic fluctuations.
A General Central Limit Theorem for Shape Parameters of m-ary Tries and PATRICIA Tries
(2014-03-24)
Fuchs, Michael
;
Lee, Chung-Kuei
;
應用數學系
;
Department of Applied Mathematics
Tries and PATRICIA tries are fundamental data structures in computer science with numerous applications. In a recent paper, a general framework for obtaining the mean and variance of additive shape parameters of tries and PATRICIA tries under the Bernoulli model was proposed. In this note, we show that a slight modification of this framework yields a central limit theorem for shape parameters, too. This central limit theorem contains many of the previous central limit theorems from the literature and it can be used to prove recent conjectures and derive new results. As an example, we will consider a refinement of the size of tries and PATRICIA tries, namely, the number of nodes of fixed outdegree and obtain (univariate and bivariate) central limit theorems. Moreover, trivariate central limit theorems for size, internal path length and internal Wiener index of tries and PATRICIA tries are derived as well.
A higher-dimensional Kurzweil theorem for formal Laurent series over finite fields
(2012-11-01)
Chen, Shu-Yi
;
Fuchs, Michael
;
應用數學系
;
Department of Applied Mathematics
In a recent paper, Kim and Nakada proved an analogue of Kurzweil's theorem for inhomogeneous Diophantine approximation of formal Laurent series over finite fields. Their proof used continued fraction theory and thus cannot be easily extended to simultaneous Diophantine approximation. In this note, we give another proof which works for simultaneous Diophantine approximation as well. (C) 2012 Elsevier Inc. All rights reserved.
A note on simultaneous Diophantine approximation in positive characteristic
(2011)
Fuchs, Michael
;
應用數學系
;
Department of Applied Mathematics
A note on the quicksort asymptotics
(2015-07-01)
Fuchs, Michael
;
應用數學系
;
Department of Applied Mathematics
In a recent paper, Bindjeme and Fill obtained a surprisingly easy exact formula for the L-2-distance of the (normalized) number of comparisons of Quicksort under the uniform model to its limit. Shortly afterwards, Neininger proved a central limit theorem for the error. As a consequence, he obtained the asymptotics of the L-3-distance. In this short note, we use the moment transfer approach to re-prove Neininger\'s result. As a consequence, we obtain the asymptotics of the L-p-distance for all 1p
An analytic approach to the asymptotic variance of trie statistics and related structures
(2014-03-27)
Fuchs, Michael
;
Hwang, Hsien-Kuei
;
Zacharovas, Vytas
;
應用數學系
;
Department of Applied Mathematics
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. (C) 2014 Elsevier B.V. All rights reserved.
Dependence and phase changes in random m-ary search trees
(2017-05-01)
Chern, Hua-Huai
;
Fuchs, Michael
;
Hwang, Hsien-Kuei
;
Neininger, Ralph
;
應用數學系
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 m-ary search trees. The covariance turns out to exhibit a change of asymptotic behavior: it is essentially linear when 3m13, but becomes of higher order when m14. Surprisingly, the corresponding asymptotic correlation coefficient tends to zero when 3m26, but is periodically oscillating for larger m, and we also prove asymptotic independence when 3m26. Such a less anticipated phenomenon is not exceptional and our results can be extended 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. (c) 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 353-379, 2017
DEPENDENCE BETWEEN PATH-LENGTH AND SIZE IN RANDOM DIGITAL TREES
(2017-12-01)
Fuchs, Michael
;
Hwang, Hsien-Kuei
;
應用數學系
;
Department of Applied Mathematics
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 on random tries, that the size is totally positively correlated to the internal path length and that both tend to the same normal limit law. These two dependence examples provide concrete instances of bivariate normal distributions (as limit laws) whose components have correlation either zero or one or periodically oscillating. Moreover, the same type of behavior is also clarified for other classes of digital trees such as bucket digital trees and Patricia tries.
Distributional analysis of the extra-clustering model with uniformly generated phylogenetic trees
(2020-01-01)
Fuchs, Michael
;
Lee, Chih-Hong
;
Paningbatan, Ariel R.
;
應用數學系
;
Department of Applied Mathematics
The extra-clustering model for the group formation process of social animals was introduced by Durand, Blum and Francois. The model uses the relatedness of the animals, which is described by phylogenetic trees. If these trees are drawn from the Yule-Harding model, it was analyzed in recent work. Here, we analyze it for the uniform model, which is the other widely-studied model on phylogenetics trees. More precisely, we derive moments and limit laws for the number of groups, the number of groups of fixed size and the largest group size. Our results show that, independent of the probability of extra-clustering, there is on average only a finite number of groups, one of which is very large whereas all others are small. This behavior considerably differs from the Yule-Harding case, where the finiteness of the number of groups is dependent on the extra-clustering probability.
Equality of Shapley value and fair proportion index in phylogenetic trees
(2015-11-01)
Fuchs, Michael
;
Jin, Emma Yu
;
應用數學系
;
Department of Applied Mathematics
The Shapley value and the fair proportion index of phylogenetic trees have been introduced recently for the purpose of making conservation decisions in genetics. Moreover, also very recently, Hartmann (J Math Biol 67:1163-1170, 2013) has presented data which shows that there is a strong correlation between a slightly modified version of the Shapley value (which we call the modified Shapley value) and the fair proportion index. He gave an explanation of this correlation by showing that the contribution of both indices to an edge of the tree becomes identical as the number of taxa tends to infinity. In this note, we show that the Shapley value and the fair proportion index are in fact the same. Moreover, we also consider the modified Shapley value and show that its covariance with the fair proportion index in random phylogenetic trees under the Yule-Harding model and uniform model is indeed close to one.
FROM COIN TOSSING TO ROCK-PAPER-SCISSORS AND BEYOND: A LOG-EXP GAP THEOREM FOR SELECTING A LEADER
(2017-03-01)
Fuchs, Michael
;
Hwang, Hsien-Kuei
;
Itoh, Yoshiaki
;
應用數學系
;
Department of Applied Mathematics
A class of games for finding a leader among a group of candidates is studied in detail. This class covers games based on coin tossing and rock-paper-scissors as special cases and its complexity exhibits similar stochastic behaviors: either of logarithmic mean and bounded variance or of exponential mean and exponential variance. Many applications are also discussed.
Invariance principles for Diophantine approximation of formal Laurent series over a finite base field
(2007-07-01)
Deligero, Eveyth
;
Fuchs, Michael
;
Nakada, Hitoshi
;
應用數學系
;
Department of Applied Mathematics
In a recent paper, the first and third author proved a central limit theorem for the number of coprime solutions of the Diophantine approximation problem for formal Laurent series in the setting of the classical theorem of Khintchine. In this note, we consider a more general setting and show that even an invariance principle holds, thereby improving upon earlier work of the second author. Our result yields two consequences: (i) the functional central limit theorem and (ii) the functional law of the iterated logarithm. The latter is a refinement of Khintchine's theorem for formal Laurent series. Despite a lot of research efforts, the corresponding results for Diophantine approximation of real numbers have not been established yet. (C) 2006 Elsevier Inc. All rights reserved.
LIMIT BEHAVIOR OF MAXIMA IN GEOMETRIC WORDS REPRESENTING SET PARTITIONS
(2015-10-01)
Fuchs, Michael
;
Javanian, Mehri
;
應用數學系
;
Department of Applied Mathematics
We consider geometric words omega(1) ... omega(n) with letters satisfying the restricted growth property omega(k) <= d max{omega(0), ..., omega(k-1)}, where omega(0) := 0 and d >= 1. For d = 1 these words are in 1-to-1 correspondence with set partitions and for this case, we show that the number of left-to-right maxima (suitable centered) does not converge to a fixed limit law as n tends to infinity. This becomes wrong for d >= 2, for which we prove that convergence does occur and the limit law is normal. Moreover, we also consider related quantities such as the value of the maximal letter and the number of maximal letters and show again non-convergence to a fixed limit law.
Limit theorems for patterns in phylogenetic trees
(2010-04-01)
Chang, Huilan
;
Fuchs, Michael
;
應用數學系
;
Department of Applied Mathematics
Studying the shape of phylogenetic trees under different random models is an important issue in evolutionary biology. In this paper, we propose a general framework for deriving detailed statistical results for patterns in phylogenetic trees under the Yule-Harding model and the uniform model, two of the most fundamental random models considered in phylogenetics. Our framework will unify several recent studies which were mainly concerned with the mean value and the variance. Moreover, refined statistical results such as central limit theorems, Berry-Esseen bounds, local limit theorems, etc., are obtainable with our approach as well. A key contribution of the current study is that our results are applicable to the whole range of possible sizes of the pattern.
Limit Theorems for Subtree Size Profiles of Increasing Trees
(2012-05-01)
Fuchs, Michael
;
應用數學系
;
Department of Applied Mathematics
Simple families of increasing trees were introduced by Bergeron, Flajolet and Salvy. They include random binary search trees, random recursive trees and random plane-oriented recursive trees (PORTs) as important special cases. In this paper, we investigate the number of subtrees of size k on the fringe of some classes of increasing trees, namely generalized PORTs and d-ary increasing trees. We use a complex-analytic method to derive precise expansions of mean value and variance as well as a central limit theorem for fixed k. Moreover, we propose an elementary approach to derive limit laws when k is growing with n. Our results have consequences for the occurrence of pattern sizes on the fringe of increasing trees.
Metrical theorems for inhomogeneous Diophantine approximation in positive characteristic
(2010)
Fuchs, Michael
;
應用數學系
;
Department of Applied Mathematics
On Kurzweil\'s 0-1 law in inhomogeneous Diophantine approximation
(2016)
Fuchs, Michael
;
Kim, Dong Han
;
應用數學系
;
Department of Applied Mathematics
On the Moment-Transfer Approach for Random Variables satisfying a One-Sided Distributional Recurrence
(2011-05-10)
Chen, Che-Hao
;
Fuchs, Michael
;
應用數學系
;
Department of Applied Mathematics
The moment-transfer approach is a standard tool for deriving limit laws of sequences of random variables satisfying a distributional recurrence. However, so far the approach could not be applied to certain "one-sided" recurrences with slowly varying moments and normal limit law. In this paper, we propose a modified version of the moment-transfer approach which can be applied to such recurrences. Moreover, we demonstrate the usefulness of our approach by re-deriving several recent results in an almost automatic fashion.
Phase Changes in Random Point Quadtrees
(2007-05-01)
Chern, Hua-Huai
;
Fuchs, Michael
;
Hwang, Hsien-Kuei
;
應用數學系
;
Department of Applied Mathematics
We show that a wide class of linear cost measures (such as the number of leaves) in random d-dimensional point quadtrees undergo a change in limit laws: If the dimension d = 1, ..., 8, then the limit law is normal; if d >= 9 then there is no convergence to a fixed limit law. Stronger approximation results such as convergence rates and local limit theorems are also derived for the number of leaves, additional phase changes being unveiled. Our approach is new and very general, and also applicable to other classes of search trees. A brief discussion of Devroye's grid trees (covering m-ary search trees and quadtrees as special cases) is given. We also propose an efficient numerical procedure for computing the constants involved to high precision.
Profiles of random trees: Limit theorems for random recursive trees and binary search trees
(2006-11-01)
Fuchs, Michael
;
Hwang, Hsien-Kuei
;
Neininger, Ralph
;
應用數學系
;
Department of Applied Mathematics
We prove convergence in distribution for the profile (the number of nodes at each level), normalized by its mean, of random recursive trees when the limit ratio alpha of the level and the logarithm of tree size lies in [0, e). Convergence of all moments is shown to hold only for a E [0, 1] (with only convergence of finite moments when alpha is an element of (1, e)). When the limit ratio is 0 or 1 for which the limit laws are both constant, we prove asymptotic normality for alpha = 0 and a "quicksort type" limit law for alpha = 1, the latter case having additionally a small range where there is no fixed limit law. Our tools are based on the contraction method and method of moments. Similar phenomena also hold for other classes of trees; we apply our tools to binary search trees and give a complete characterization of the profile. The profiles of these random trees represent concrete examples for which the range of convergence in distribution differs from that of convergence of all moments.