Limit laws for local counters in random binary search trees

Limit laws for several quantities in random binary search trees that are related to the local shape of a tree around each node can be obtained very simply by applying central limit theorems for w-dependent random variables. Examples include: the number of leaves (L_n), the number of nodes with k descendants (k fixed), the number of nodes with no left child, the number of nodes with k left descendants. Some of these results can also be obtained via the theory of urn models, but the present method seems easier to apply.     

Patterns in random binary search trees

In a randomly grown binary search tree (BST) of size n, any fixed pattern occurs with a frequency that is on average proportional to n. Deviations from the average case are highly unlikely and well quantified by a Gaussian law. Trees with forbidden patterns occur with an exponentially small probability that is characterized in terms of Bessel functions. The results obtained extend to BSTs a type of property otherwise known for strings and combinatorial tree models. They apply to paged trees or to quicksort with halting on short subfiles. As a consequence, various pointer saving strategies for maintaining trees obeying the random BST model can be precisely quantified. The methods used are based on analytic models, especially bivariate generating function subjected to singularity perturbation asymptotics. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 : 223–244, 1997     

Limiting theorems for the nodes in binary search trees

We consider three random variables X_n, Y_n and Z_n, which represent the numbers of the nodes with 0, 1, and 2 children, in the binary search trees of size n. The expectation and variance of the three above random variables are got, and it is also shown that X_n, Y_n and Z_n are all asymptotically normal as n→∞by applying the contraction method.     

Optimal binary search methods

The ordinary binary search method is shown to be one of a class of optimal binary search methods, supposing equiprobable search keys. For certain values of the numbern of records this class may be rather large. Thus forn=2 ^K +2 ^K–1–1 the number of optimal methods is of order 2^2n/3.     

A unified approach to the large deviations for small perturbations of random evolution equations

LetX ^ɛ = {X ^ɛ (t ; 0 ⩽t ⩽ 1 } (ɛ > 0) be the processes governed by the following stochastic differential equations:

关于重尾随机和大偏差的一个注记

设｛Xκ，κ≥1｝为一列独立同分布的非随机变量，且具有共同的分布函数F。记Sn为序列｛Xκ，κ≥1｝的前n项部分和。在F属于ERV分布族的假定下，文中证明了关于随机和SN(t)的随机中心化的精细大偏差结果。这里N（t）为一个与｛Xκ，κ≥1｝独立的非负整数值的随机过程。     

On replica symmetry of large deviations in random graphs

The following question is due to Chatterjee and Varadhan (2011). Fix and take , the Erd?s‐Rényi random graph with edge density p, conditioned to have at least as many triangles as the typical . Is G close in cut‐distance to a typical ? Via a beautiful new framework for large deviation principles in , Chatterjee and Varadhan gave bounds on the replica symmetric phase, the region of where the answer is positive. They further showed that for any small enough p there are at least two phase transitions as r varies. We settle this question by identifying the replica symmetric phase for triangles and more generally for any fixed d‐regular graph. By analyzing the variational problem arising from the framework of Chatterjee and Varadhan we show that the replica symmetry phase consists of all such that lies on the convex minorant of where is the rate function of a binomial with parameter p. In particular, the answer for triangles involves rather than the natural guess of where symmetry was previously known. Analogous results are obtained for linear hypergraphs as well as the setting where the largest eigenvalue of is conditioned to exceed the typical value of the largest eigenvalue of . Building on the work of Chatterjee and Diaconis (2012) we obtain additional results on a class of exponential random graphs including a new range of parameters where symmetry breaking occurs. En route we give a short alternative proof of a graph homomorphism inequality due to Kahn (2001) and Galvin and Tetali (2004). © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 109–146, 2015     

LARGE DEVIATIONS AND MODERATE DEVIATIONS FOR m-NEGATIVELY ASSOCIATED RANDOM VARIABLES

M-negatively associated random variables,which generalizes the classical one of negatively associated random variables and includes m-dependent sequences as its par- ticular case,are introduced and studied.Large deviation principles and moderate devi- ation upper bounds for stationary m-negatively associated random variables are proved. Kolmogorov-type and Marcinkiewicz-type strong laws of large numbers as well as the three series theorem for m-negatively associated random variables are also given.     

Random suffix search trees

A random suffix search tree is a binary search tree constructed for the suffixes X_i = 0 · B_iB_i+1B_i+2… of a sequence B₁, B₂, B₃, … 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₁ is uniform on ?_b. We show that for any value of b > 1, ??D_n = 2 log n + O(log²log n), just as for the random binary search tree. We also show that D_n/??D_n → 1 in probability. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2003     

Self-normalized large deviations for stationary sequences

In this note, we prove the large deviation principle for self-normalized partial sums of a stationary weakly dependent random sequence. This revised version was published online in June 2006 with corrections to the Cover Date.     

A new genetic approach to construct near-optimal binary search trees

Many definitive and approximate methods have been so far proposed for the construction of an optimal binary search tree. One such method is the use of evolutionary algorithms with satisfactorily improved cost efficiencies. This paper will propose a new genetic algorithm for making a near-optimal binary search tree. In this algorithm, a new greedy method is used for the crossover of chromosomes while a new way is also developed for inducing mutation in them. Practical results show a rapid and desirable convergence towards the near-optimal solution. The use of a heuristic to create not so costly chromosomes as the first offspring, the greediness of the crossover, and the application of elitism in the selection of future generation chromosomes are the most important factors leading to near-optimal solutions by the algorithm at desirably high speeds. Due to the practical results, increasing problem size does not cause any considerable difference between the solution obtained from the algorithm and exact solution.     

关于大偏差概率的一个界

研究得到了关于随机和S(t)=∑N(t)i=1Xi,t≥0大偏差的幂的一个界,其中(N(t))t≥0是一族非负整值随机变量,(Xn)n∈N是独立同分布的随机变量,其共同的分布函数是F与(N(t))t≥0独立.本结论是在假设分布函数F的右尾属于ERV族的情况下得到的.     

Wiener indices of balanced binary trees

We study a new family of trees for computation of the Wiener indices. We introduce general tree transformations and derive formulas for computing the Wiener indices when a tree is modified. We present several algorithms to explore the Wiener indices of our family of trees. The experiments support new conjectures about the Wiener indices.     

次线性期望下独立随机变量列的大偏差和中偏差

本文研究在次线性期望下的独立随机变量列的大偏差和中偏差原理. 利用次可加方法, 我们得 到次线性期望下的大偏差原理. 与次线性期望下的中心极限定理相应的中偏差原理也被建立.     

An application of berezin integration to large deviations

We apply a method invented by Luttinger to obtain an asymptotic expansion in powers of 1/T forE[e ^–TF()]. is theproportion of local time andE is the expectation for a time-homogeneous Markov process withN states. The result extends the large-deviation result of Donsker and Varadhan by providing a complete expansion as opposed to only the leading term.     

Nonlinear filtering and large deviations:a pde-control theoretic approach

We consider the asymptotic nonlinear filtering problem dx=f(x)dt + ?^1/2 dw,dy=h(x) dt + ? dv and obtain lim_?→0 ? log q ²(x,t) = -W(x,t) for unnormalized conditional densities q ²(x,t) using PDE methods. HereW(x,t) is the value function for a deterministic optimal control problem arising in Mortensen's deterministic estimation, and is the unique viscosity solution of a Hamilton-Jacobi-Bellman equation. ijab has also studied this filtering problem, and we extend his large deviation result for certain unnormalized conditional measures. The resulting variational problem corresponds to the above control problem     

The missing log in large deviations for triangle counts

This paper solves the problem of sharp large deviation estimates for the upper tail of the number of triangles in an Erd?s‐Rényi random graph, by establishing a logarithmic factor in the exponent that was missing till now. It is possible that the method of proof may extend to general subgraph counts. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 40, 437–451, 2012     

Sample path large deviations and intree networks

Using the contraction principle, in this paper we derive a set of closure properties for sample path large deviations. These properties include sum, reduction, composition and reflection mapping. Using these properties, we show that the exponential decay rates of the steady state queue length distributions in an intree network with routing can be derived by a set of recursive equations. The solution of this set of equations is related to the recently developed theory of effective bandwidth for high speed digital networks, especially ATM networks. We also prove a conditional limit theorem that illustrates how a queue builds up in an intree network.     

Large deviations and moderate deviations for kernel density estimators of directional data

Let fn be the non-parametric kernel density estimator of directional data based on a kernel function K and a sequence of independent and identically distributed random variables taking values in d-dimensional unit sphere Sd-1. It is proved that if the kernel function is a function with bounded variation and the density function f of the random variables is continuous, then large deviation principle and moderate deviation principle for {sup x∈sd-1 ｜fn（x） - E（fn（x））｜, n ≥ 1} hold.