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     

Oscillations in the height of the Yule tree and application to the binary search tree

For a particular case of a branching random walk with lattice support, namely the Yule branching random walk, we prove that the distribution of the centred maximum oscillates around a distribution corresponding to a critical travelling wave in the following sense: there exist continuous functions and such that: where and is the height of the Yule tree. We also shows that similar oscillations occur for , when f is in a large class of functions. This process is classically related to the binary search tree, thus yielding analogous results for the height and for the saturation level of the binary search tree. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 51, 90–120, 2017     

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     

Arboricity and spanning‐tree packing in random graphs

We study the arboricity and the maximum number of edge‐disjoint spanning trees of the classical random graph . For all , we show that, with high probability, is precisely the minimum of and , where is the minimum degree of the graph and denotes the number of edges. Moreover, we explicitly determine a sharp threshold value for such that the following holds. Above this threshold, equals and equals . Below this threshold, equals , and we give a two‐value concentration result for the arboricity in that range. Finally, we include a stronger version of these results in the context of the random graph process where the edges are randomly added one by one. A direct application of our result gives a sharp threshold for the maximum load being at most in the two‐choice load balancing problem, where .     

The suffix binary search tree and suffix AVL tree

Suffix trees and suffix arrays are classical data structures that are used to represent the set of suffixes of a given string, and thereby facilitate the efficient solution of various string processing problems—in particular on-line string searching. Here we investigate the potential of suitably adapted binary search trees as competitors in this context. The suffix binary search tree (SBST) and its balanced counterpart, the suffix AVL-tree, are conceptually simple, relatively easy to implement, and offer time and space efficiency to rival suffix trees and suffix arrays, with distinct advantages in some circumstances—for instance in cases where only a subset of the suffixes need be represented.

Construction of a suffix BST for an n-long string can be achieved in O(nh) time, where h is the height of the tree. In the case of a suffix AVL-tree this will be O(nlogn) in the worst case. Searching for an m-long substring requires O(m+l) time, where l is the length of the search path. In the suffix AVL-tree this is O(m+logn) in the worst case. The space requirements are linear in n, generally intermediate between those for a suffix tree and a suffix array.

Empirical evidence, illustrating the competitiveness of suffix BSTs, is presented.     

Random near-regular graphs and the node packing problem

Nemhauser and Trotter [12] proposed a certain easily-solved linear program as a relaxation of the node packing problem. They showed that any variables receiving integer values in an optimal solution to this linear program also take on the same values in an optimal solution to the (integer) node packing problem. Let π be the property of graphs defined as follows: a graph G has property π if and only if there is a unique optimal solution to the linear-relaxation problem, and this solution is completely fractional. If a graph G has property π then no information about the node packing problem on G is gained by solving the linear relaxation. We calculate the asymptotic probability that a certain type of ‘sparse’ random graph has property π, as the number of its nodes tends to infinity. Let m be a fixed positive integer, and consider the following random graph on the node set {1,2 …, n}). We join each node, j say, to exactly m other nodes chosen randomly with replacement, by edges oriented away from j; we denote by G_n(m) the undirected graph obtained by deleting all orientations and allowing all parallel edges to coalesce. We show that, as n → ∞,

$\text{P(G}{}_{\mathrm{n}}\text{(m)}\text{has property}\text{π)→}\text{0}\text{if}\text{m = 1,}\text{1}\text{if}\text{m ? 3,}$

and we conjecture that $\text{P(G}{}_{\mathrm{n}}\text{(2)}\text{has property}\text{π)→ (1–2e}{}^{\mathrm{?2}}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$.     

不连续随机算子随机不动点定理及其应用

该文利用半序理论和随机压缩映象原理,得到了一类不连续随机增算子随机不动点的唯一存在定理.作为应用,考虑了R~n中含间断项的一阶随机微分积分方程初值问题.     

Random coincidence theorems and applications

In this article we state conditions under which the existence of deterministic coincidence points of two multivalued random functions implies the existence of random coincidence points. Moreover, two existence results of measurable selections are obtained for the intersection of the multivalued function evaluated at the random coincidence point. Our results extend or improve some theorems in the literature.     

Entropy for Random Partitions and Its Applications

Asymptotic properties of partitions of the unit interval are studied through the entropy for random partition

二叉树上分枝马氏链的强大数定理

首先给出了在可列状态空间取值的二叉树上分枝马氏链定义的离散形式,然后建立了二叉树上分枝马氏链的若干强极限定理,最后研究了二叉树上有限状态分枝马氏链的强大数定理．     

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.     

Boundaries and Harmonic Functions for Random Walks with Random Transition Probabilities

The usual random walk on a group (homogeneous both in time and in space) is determined by a probability measure on the group. In a random walk with random transition probabilities this single measure is replaced with a stationary sequence of measures, so that the resulting (random) Markov chains are still space homogeneous, but no longer time homogeneous. We study various notions of measure theoretical boundaries associated with this model and establish an analogue of the Poisson formula for (random) bounded harmonic functions. Under natural conditions on transition probabilities we identify these boundaries for several classes of groups with hyperbolic properties and prove the boundary triviality (i.e., the absence of non-constant random bounded harmonic functions) for groups of subexponential growth, in particular, for nilpotent groups.     

随机泛函分析中的锐角原理及应用(英文)

在随机泛函分析中证明了著名的锐角原理和随机一一映射定理,并且得到了若干新的结果．     

On Sums of Products of Bernoulli Variables and Random Permutations

Let {X _k } _k1 be independent Bernoulli random variables with parameters p _k . We study the distribution of the number or runs of length 2: that is . Let S=lim _n S _n . For the particular case p _k =1/(k+B), B being given, we show that the distribution of S is a Beta mixture of Poisson distributions. When B=0 this is a Poisson(1) distribution. For the particular case p _k =p for all k we obtain the generating function of S _n and the limiting distribution of S _n for .     

Random Probability Measures with Given Mean and Variance

This article describes several natural methods of constructing random probability measures with prescribed mean and variance, and focuses mainly on a technique which constructs a sequence of simple (purely discrete, finite number of atoms) distributions with the prescribed mean and with variances which increase to the desired variance. Basic properties of the construction are established, including conditions guaranteeing full support of the generated measures, and conditions guaranteeing that the final measure is discrete. Finally, applications of the construction method to optimization problems such as Plackett's Problem are mentioned, and to experimental determination of average-optimal solutions of certain control problems.     

Martingales and large deviations for binary search trees

We establish an almost sure large deviations theorem for the depth of the external nodes of binary search trees (BSTs). To achieve this, a parametric family of martingales is introduced. This family also allows us to get asymptotic results on the number of external nodes at deepest level. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 112–127, 2001     

随机赔偿,随机折现下的保险概率模型及若干结果

本文首先构造了保险的随机过程模型，即随机赔偿和随机折现的双随机模型．运用测度扩张理论将赔偿过程发展为随机赔偿恻度，在模型的基本假定之下研究赔偿过程的性质，给出保险和年金的测度表示以及诸多精算公式．最后针对随机利率的Gauss过程模型得到Hoem模型随机赔偿测度的现值矩发展了［7］中的主要结果．     

Random Tours in the Traveling Salesman Problem: Analysis and Application

Random solutions to the traveling salesman problem (TSP) exhibit statistical regularities across problem instances. These patterns can assist heuristic search for good solutions by providing easy estimates of the length of the optimal tour.