检索结果-内蒙古大学图书馆

RANDOM STRUCTURES & algorithms 2003年第4期23卷 357-396页

作者： Devroye, L Neininger, R McGill Univ Sch Comp Sci Montreal PQ H3A 2K6 Canada

A random suffix search tree is a binary search tree constructed for the suffixes X(i) = 0 (.) B(i)B(i+1)B(i+2)... of a sequence B(1), B(2), B(3),... of independent identically distributed random b-ary digits B(j). Let D(n) denote the depth of the node for X(n) in this tree when B(1) is uniform on Z(b). We show that for any value of b > 1, ED(n) = 2 log n + O(log(2)log n), just as for the random binary search tree. We also show that D(n)/ED(n) --> 1 in probability. (C) 2003 Wiley Periodicals, Inc.

关键词： random binary search tree suffix tree Lacunary sequences random spacings probabilistic analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Euclidean algorithms are Gaussian

引用

JOURNAL OF NUMBER THEORY 2005年第2期110卷 331-386页

作者： Baladi, V Vallée, B Univ Paris 07 CNRS Inst Math Jussieu UMR 7586 F-75251 Paris 05 France Univ Caen CNRS UMR 6072 F-14032 Caen France

We obtain a central limit theorem for a general class of additive parameters (costs, observables) associated to three standard Euclidean algorithms, with optimal speed of convergence. We also provide very precise asymptotic estimates and error terms for the mean and variance of such parameters. For costs that are lattice (including the number of steps), we go further and establish a local limit theorem, with optimal speed of convergence. We view an algorithm as a dynamical system restricted to rational inputs, and combine tools imported from dynamics, such as transfer operators, with various other techniques: Dirichlet series, Perron's formula, quasi-powers theorems, and the saddle-point method. Such dynamical analyses had previously been used to perform the average-case analysis of algorithms. For the present (dynamical) analysis in distribution, we require estimates on transfer operators when a parameter varies along vertical lines in the complex plane. To prove them, we adapt techniques introduced recently by Dolgopyat in the context of continuous-time dynamics (Ann. Math. 147 (1998) 357). (C) 2004 Elsevier Inc. All rights reserved.

关键词： probabilistic analysis of algorithms dynamical systems transfer operator Dirichlet series Perron's formula central limit theorem local limit theorem

来源：评论

学校读者我要写书评

暂无评论

Multiple Choice Tries and Distributed Hash Tables

引用

RANDOM STRUCTURES & algorithms 2009年第3期34卷 337-367页

作者： Devroye, Luc Lugosi, Gabor Park, Gahyun Szpankowski, Wojciech McGill Univ Sch Comp Sci Montreal PQ H3A 2K6 Canada Univ Pompeu Fabra ICREA Barcelona Spain Univ Pompeu Fabra Dept Econ Barcelona Spain Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

In this article we consider tries built from n strings such that each string can be chosen from a pool of k strings, each of them generated by a discrete i.i.d. source. Three cases are considered: k = 2, k is large but fixed, and k similar to c log n. The goal in each case is to obtain tries as balanced as possible. Various parameters such as height and fill-up level are analyzed. It is shown that for two-choice tries a 50% reduction in height is achieved when compared with ordinary tries. In a greedy online construction when the string that minimizes the depth of insertion for every pair is inserted, the height is only reduced by 25%. To further reduce the height by another 25%, we design a more refined online algorithm. The total computation time of the algorithm is O(n log n). Furthermore, when we choose the best among k >= 2 strings, then for large but fixed k the height is asymptotically equal to the typical depth in a trie. Finally, we show that further improvement can be achieved if the number of choices for each string is proportional to log n. In this case highly balanced trees can be constructed by a simple greedy algorithm for which the difference between the height and the fill-up level is bounded by a constant with high probability. This, in turn, has implications for distributed hash tables, leading to a randomized ID management algorithm in peer-to-peer networks such that, with high probability, the ratio between the maximum and the minimum load of a processor is O(1). (C) 2008 Wiley Periodicals, Inc. Random Struct. Mg.. 34, 337-367, 2009

关键词： random tries random data structures probabilistic analysis of algorithms algorithms on sequences distributed hash tables

来源：评论

学校读者我要写书评

暂无评论

ON TAIL BOUNDS FOR RANDOM RECURSIVE TREES

引用

JOURNAL OF APPLIED PROBABILITY 2012年第2期49卷 566-581页

作者： Munsonius, Goetz Olaf Goethe Univ Frankfurt Inst Math D-60054 Frankfurt Germany

We consider a multivariate distributional recursion of sum type, as arises in the probabilistic analysis of algorithms and random trees. We prove an upper tail bound for the solution using Chernoff's bounding technique by estimating the Laplace transform. The problem is traced back to the corresponding problem for binary search trees by stochastic domination. The result obtained is applied to the internal path length and Wiener index of random b-ary recursive trees with weighted edges and random linear recursive trees. Finally, lower tail bounds for the Wiener index of these trees are given.

关键词： Random tree probabilistic analysis of algorithms tail bound path length Wiener index

来源：评论

学校读者我要写书评

暂无评论

ON THE AVERAGE NUMBER OF MAXIMA IN A SET OF VECTORS

引用

INFORMATION PROCESSING LETTERS 1989年第2期33卷 63-65页

作者： BUCHTA, C Institut für Analysis Technische Mathematik und Versicherungsmathematik Technische Universität Wien Wiedner Hauptstrasse 8-10 A-1040 Wien Austria

Any of n vectors in d -space is called maximal if none of the remaining vectors dominates it in every component. Assuming that n vectors are distributed identically and that the d components of each vector are distributed independently and continuously, we determine the expected number of maximal vectors explicitly for any n and d . The asymptotic behaviour of this quantity as n tends to infinity, which was investigated by Bentley, Kung, Schkolnick, Thompson and Devroye, follows immediately from our result.

关键词： Average number of maxima geometric probability maxima of a set of vectors probabilistic analysis of algorithms random points

来源：评论

学校读者我要写书评

暂无评论

A PARTITIONING ALGORITHM FOR MINIMUM WEIGHTED EUCLIDEAN MATCHING

引用

INFORMATION PROCESSING LETTERS 1984年第2期18卷 59-62页

作者： DYER, ME FRIEZE, AM UNIV LONDON QUEEN MARY COLLDEPT COMP SCI & STATLONDON WC1E 7HUENGLAND

The Euclidean matching problem is described, and the usual Euclidean metric is given. The objective is to pair the points into m pairs so that the sum of the lengths of the lines joining the pairs is as small as possible. An algorithm is described which finds a matching of points in the unit square. It is proven that, under the assumption that the points are uniformly distributed in the square, the algorithm has a fast anticipated running time, and it yields a matching with value close to the optimum. This algorithm is almost identical to Supowit and Reingold's (1983), except that they concentrated on a worst-case analysis, while the present algorithm uses a probabilistic analysis.

关键词： Euclidean matching heuristics probabilistic analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Exponential tail bounds for max-recursive sequences

引用

ELECTRONIC COMMUNICATIONS IN PROBABILITY 2006年第none期11卷 266-277页

作者： Rueschendorf, Ludger Schopp, Eva-Maria Univ Freiburg Dept Math Stochast D-79104 Freiburg Germany

Exponential tail bounds are derived for solutions of max-recursive equations and for max-recursive random sequences, which typically arise as functionals of recursive structures, of random trees or in recursive algorithms. In particular they arise in the worst case analysis of divide and conquer algorithms, in parallel search algorithms or in the height of random tree models. For the proof we determine asymptotic bounds for the moments or for the Laplace transforms and apply a characterization of exponential tail bounds due to Kasahara (1978).

关键词： recursive algorithm exponential bounds divide and conquer algorithm probabilistic analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

A survey of Max-type recursive distributional equations

引用

ANNALS OF APPLIED PROBABILITY 2005年第2期15卷 1047-1110页

作者： Aldous, DJ Bandyopadhyay, A Univ Calif Berkeley Dept Stat Berkeley CA 94720 USA Univ Minnesota Inst Math & Applicat Minneapolis MN 55414 USA

In certain problems in a variety of applied probability settings (from probabilistic analysis of algorithms to statistical physics), the central requirement is to solve a recursive distributional equation of the form X-d = g((xi(i), X-i), i >= 1). Here (xi(i)) and g((.)) are given and the X-i are independent copies of the unknown distribution X. We survey this area, emphasizing examples where the function g((.)) is essentially a "maximum" or "minimum" function. We draw attention to the theoretical question of endogeny: in the associated recursive tree process X-i, are the X-i measurable functions of the innovations process (xi(i))?

关键词： branching process branching random walk cavity method coupling from the past fixed point equation frozen percolation mean-field model of distance metric contraction probabilistic analysis of algorithms probability distribution probability on trees random matching

来源：评论

学校读者我要写书评

暂无评论

AN ASYMPTOTICALLY OPTIMAL ALGORITHM FOR THE DUTCH NATIONAL FLAG PROBLEM

引用

SIAM JOURNAL ON COMPUTING 1982年第2期11卷 243-262页

作者： BITNER, JR

We develop an algorithm for the Dutch National Flag problem that has an adjustable integer parameter smax≧0smax≧0\operatorname{smax} \geqq 0 allowing a time/space tradeoff. (Let n be the length of the input to be or... 详细信息

We develop an algorithm for the Dutch National Flag problem that has an adjustable integer parameter

smax ≧ 0

$\operatorname{smax} \geqq 0$ allowing a time/space tradeoff. (Let n be the length of the input to be ordered.) The space required is proportional to smax (but independent of n), and the average number of swaps required is

关键词： Dutch National Flag problem eulerian digraphs algorithm design loop invariant stepwise refinement probabilistic analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

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

引用

ALGORITHMICA 2006年第3-4期46卷 367-407页

作者： Fuchs, Michael Hwang, Hsien-Kuei Neininger, Ralph Natl Chiao Tung Univ Dept Appl Math Hsinchu 300 Taiwan Acad Sinica Inst Stat Sci Taipei 115 Taiwan Goethe Univ Frankfurt Dept Math D-60325 Frankfurt AM Germany

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.

关键词： random recursive tree random binary search tree profile of trees probabilistic analysis of algorithms weak convergence

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：