Limit laws are proven by the contraction method for random vectors of a recursive nature as they arise parameters combinatorial structures such trees or algorithms, where we use Zolotarev metric. In comparison to previous applications this method, general transfer theorem is derived which allows us establish limit law on basis structure and asymptotics first second moments sequence. particular, asymptotic normality result obtained typically cannot be handled more common $\ell_2$ metrics. As...

We characterize all limit laws of the quicksort-type random variables defined recursively by ${\cal L}(X_n)= {\cal L}(X_{I_n}+X^*_{n-1-I_n}+T_n)$ when "toll function" Tn varies and satisfies general conditions, where (Xn), (Xn*), (In, Tn) are independent, In is uniformly distributed over {0, . .,n-1}, L}(X_n)={\cal L}(X_n^\ast)$. When (cost needed to partition original problem into smaller subproblems) small (roughly $\limsup_{n\rightarrow\infty}\log E(T_n)/\log n\le 1/2$), Xn asymptotically...

Abstract The contraction method for recursive algorithms is extended to the multivariate analysis of vectors parameters structures and algorithms. We prove a general limit law, which also leads an approach asymptotic covariances correlations parameters. As application, bivariate law number key comparisons exchanges median‐of‐(2 t +1) Quicksort are given. Moreover, programs analyzed by Sedgewick exact order standard deviation follow, considering all counted Sedgewick. © 2001 John Wiley &...

The Wiener index is analysed for random recursive trees and binary search in uniform probabilistic models. We obtain expectations, asymptotics the variances, limit laws this parameter. distributions are characterized as projections of bivariate measures that satisfy certain fixed point equations. Covariances, asymptotic correlations, internal path length given.

We study the profile $X_{n,k}$ of random search trees including binary and $m$-ary trees. Our main result is a functional limit theorem normalized $X_{n,k}/\mathbb{E}X_{n,k}$ for $k=\lfloorα\log n\rfloor$ in certain range $α$. A central feature proof use contraction method to prove convergence distribution analytic functions complex domain. This based on general concerning variables an infinite-dimensional Hilbert space. As part proof, we show that Zolotarev metric complete

We propose an approach to analysing the asymptotic behaviour of Pólya urns based on contraction method. For this, a new combinatorial discrete-time embedding evolution urn into random rooted trees is developed. A decomposition these leads system recursive distributional equations which capture distributions numbers balls each colour. Ideas from method are used study such systems asymptotically. apply our couple concrete that lead limit laws with normal distributions, non-normal and periodic...

Methods for proving functional limit laws are developed sequences of stochastic processes which allow a recursive distributional decomposition either in time or space. Our approach is an extension the so-called contraction method to space $\mathcal{C}[0,1]$ continuous functions endowed with uniform topology and $\mathcal{D}[0,1]$ càdlàg Skorokhod topology. The originated from probabilistic analysis algorithms random trees where characteristics satisfy natural recurrences. It based on...

A class of random recursive sequences (Yn) with slowly varying variances as arising for parameters trees or algorithms leads after normalizations to degenerate limit equations the form $X\stackrel {\mathcal{L}}{=}X$. For nondegenerate contraction method is a main tool establish convergence scaled sequence “unique” solution equation. In this paper we develop an extension which allows us derive theorems and data structures particular, some new tools general scheme, transfers information on...

Nonstationarity of the event rate is a persistent problem in modeling time series events, such as neuronal spike trains. Motivated by variety patterns neurophysiological train recordings, we define general class renewal processes. This used to test null hypothesis stationary versus wide alternative processes with finitely many changes (change points). Our extends ideas from filtered derivative approach using multiple moving windows simultaneously. To adjust rejection threshold test, use...

We investigate random distances in a binary search tree. Two types of distance are considered: the depth node randomly selected from tree, and between pairs nodes. By combination classical methods modern contraction techniques we arrive at Gaussian limit law for normed pairs. The exact forms mean variance this latter first derived by to determine scaling properties, then used norming, variable is shown method have normal arising as fixed-point solution distributional equation. identify rate...

In 2009, Oracle replaced the long-serving sorting algorithm in its Java 7 runtime library by a new dual-pivot Quicksort variant due to Vladimir Yaroslavskiy. The decision was based on strikingly good performance of Yaroslavskiy's implementation running time experiments. At that time, no precise investigations were available explain superior performance—on contrary: previous theoretical studies other variants even discouraged use two pivots. 2012, authors gave an average case analysis...

Abstract The complexity of the Quicksort algorithm is usually measured by number key comparisons used during its execution. When operating on a list n data, permuted uniformly at random, appropriately normalized Y known to converge almost surely non‐degenerate random limit . This assumes natural embedding all one probability space, e.g., via binary search trees. In this note central theorem for error term in latter sure convergence shown:...

For the random binary search tree with n nodes inserted number of ancestors elements ranks k and $\ell$, $1 \le < \ell n$, as well path distance between these in are considered. both quantities, central limit theorems for appropriately rescaled versions derived. distance, condition $\ell-k \to \infty$ $n\to is required. We obtain tail bounds order higher moments distance. The measures complexity finger tree.

An algorithm is developed for exact simulation from distributions that are defined as fixed points of maps between spaces probability measures. The the class under consideration include examples limit random variables studied in probabilistic analysis algorithms. Approximating sequences densities with explicit error bounds constructed. sampling relies on a modified rejection method.

We survey multivariate limit theorems in the framework of contraction method for recursive sequences as arising analysis algorithms, random trees or branching processes. compare and improve various general conditions under which laws can be obtained, state related open problems give applications to algorithms recurrences.

We introduce and analyze a random tree model associated to Hoppe's urn. The is built successively by adding nodes the existing when starting with single root node. In each step node added as child of an node, where these parent are chosen randomly probabilities proportional their weights. has weight ϑ&gt;0, given fixed parameter, all other have 1. This resembles stochastic dynamic For ϑ=1, resulting well-studied recursive tree. height, internal path length, number leaves Hoppe n well depth...

The weak limit of the normalized number comparisons needed by Quicksort algorithm to sort n randomly permuted items is known be determined implicitly a distributional fixed-point equation. We give an for perfect random variate generation from this distribution.

Biological movement patterns can sometimes be quasi linear with abrupt changes in direction and speed, as plastids root cells investigated here. For the analysis of such we propose a new stochastic model for along structures. Maximum likelihood estimators are provided, due to serial dependencies increments, classical MOSUM statistic is replaced by moving kernel estimator. Convergence resulting difference process strong consistency variance estimator shown. We estimate change points graphical...