Iterations of random and deterministic functions

Letf be a probability generating function on [0, 1]. The convergence of its iteratesf _n to fixed points is studied in this paper. Results include rates forf andf ^-1. Also iterates of independent identically distributed stable processes are studied and a trichotomy based on the order of the stability is established. Dedicated to the memory of Professor K G Ramanathan     

Note on the heights of random recursive trees and random m-ary search trees

A process of growing a random recursive tree T_n is studied. The sequence {T_n} is shown to be a sequence of “snapshots” of a Crump–Mode branching process. This connection and a theorem by Kingman are used to show quickly that the height of T_n is asymptotic, with probability one, to c log n. In particular, c = e = 2.718 … for the uniform recursive tree, and c = (2γ)^?1, where γe^1+γ = 1, for the ordered recursive tree. An analogous reduction provides a short proof of Devroye's limit law for the height of a random m-ary search tree. We show finally a close connection between another Devroye's result, on the height of a random union-find tree, and our theorem on the height of the uniform recursive tree. © 1994 John Wiley & Sons, Inc.     

Random trees under CH

We extend Jensen’s Theorem that Souslin’s Hypothesis is consistent with CH, by showing that the statement Souslin’s Hypothesis holds in any forcing extension by a measure algebra is consistent with CH. We also formulate a variation of the principle (*) (see [AT97], [Tod00]) for closed sets of ordinals, and show its consistency relative to the appropriate large cardinal hypothesis. Its consistency with CH would extend Silver’s Theorem that, assuming the existence of an inaccessible cardinal, the failure of Kurepa’s Hypothesis is consistent with CH, by its implication that the statement Kurepa’s Hypothesis fails in any forcing extension by a measure algebra is consistent with CH.     

Multicolored trees in random graphs

We discuss the existence of multi-colored trees in randomly colored, random graphs. © 1994 John Wiley & Sons, Inc.     

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     

Nonautonomous saddle-node bifurcations: Random and deterministic forcing

We study the effect of external forcing on the saddle-node bifurcation pattern of interval maps. By replacing fixed points of unperturbed maps by invariant graphs, we obtain direct analogues to the classical result both for random forcing by measure-preserving dynamical systems and for deterministic forcing by homeomorphisms of compact metric spaces. Additional assumptions like ergodicity or minimality of the forcing process then yield further information about the dynamics.The main difference to the unforced situation is that at the critical bifurcation parameter, two alternatives exist. In addition to the possibility of a unique neutral invariant graph, corresponding to a neutral fixed point, a pair of so-called pinched invariant graphs may occur. In quasiperiodically forced systems, these are often referred to as ‘strange non-chaotic attractors’. The results on deterministic forcing can be considered as an extension of the work of Novo, Núñez, Obaya and Sanz on nonautonomous convex scalar differential equations. As a by-product, we also give a generalisation of a result by Sturman and Stark on the structure of minimal sets in forced systems.     

Random walks on trees

The classical gambler's ruin problem, i.e., a random walk along a line may be viewed graph theoretically as a random walk along a path with the endpoints as absorbing states. This paper is an investigation of the natural generalization of this problem to that of a particle walking randomly on a tree with the endpoints as absorbing barriers. Expressions in terms of the graph structure are obtained from the probability of absorption at an endpoint e in a walk originating from a vertex v, as well as for the expected length of the walk.     

On random cartesian trees

Cartesian trees are binary search trees in which the nodes exhibit the heap property according to a second (priority) key. If the search key and the priority key are independent, and the trees is built based on n independent copies, Cartesian trees basically behave like ordinary random binary search trees. In this article, we analyze the expected behavior when the keys are dependent: in most cases, the expected search, insertion, and deletion times are Φ(√n). We indicate how these results can be used in the analysis of divide-and-conguer algorithms for maximal vectors and convex hulls. Finally, we look at distributions for which the expected time per operation grows like n^a for a ?[1/2, 1]. © 1994 John Wiley & Sons, Inc.     

Limits of random trees

Local convergence of bounded degree graphs was introduced by Benjamini and Schramm [2]. This result was extended further by Lyons [4] to bounded average degree graphs. In this paper, we study the convergence of a random tree sequence (T _n ), where the probability of a given tree T is proportional to $\prod_{v_{i}\in V(T)}d(v_{i})!$ . We show that this sequence is convergent and describe the limit object, which is a random infinite rooted tree.     

Random trees and general branching processes

We consider a tree that grows randomly in time. Each time a new vertex appears, it chooses exactly one of the existing vertices and attaches to it. The probability that the new vertex chooses vertex x is proportional to w(deg(x)), a weight function of the actual degree of x. The weight function w : ℕ → ℝ₊ is the parameter of the model. In 4 and 11 the authors derive the asymptotic degree distribution for a model that is equivalent to the special case, when the weight function is linear. The proof therein strongly relies on the linear choice of w. Using well‐established results from the theory of general branching processes we give the asymptotical degree distribution for a wide range of weight functions. Moreover, we provide the asymptotic distribution of the tree itself as seen from a randomly selected vertex. The latter approach gives greater insight to the limiting structure of the tree. Our proof is robust and we believe that the method may be used to answer several other questions related to the model. It relies on the fact that considering the evolution of the random tree in continuous time, the process may be viewed as a general branching process, this way classical results can be applied. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Random walk in random groups

((no abstract)) . Submitted: January 2002, Final version: December 2002.     

The norm of polynomials in large random and deterministic matrices

Let ${{\bf X}_N =(X_1^{(N)}, \ldots, X_p^{(N)})}$ be a family of N × N independent, normalized random matrices from the Gaussian Unitary Ensemble. We state sufficient conditions on matrices ${{\bf Y}_N =(Y_1^{(N)}, \ldots, Y_q^{(N)})}$ , possibly random but independent of X _N , for which the operator norm of ${P({\bf X}_N, {\bf Y}_N, {\bf Y}_N^*)}$ converges almost surely for all polynomials P. Limits are described by operator norms of objects from free probability theory. Taking advantage of the choice of the matrices Y _N and of the polynomials P, we get for a large class of matrices the ??no eigenvalues outside a neighborhood of the limiting spectrum?? phenomena. We give examples of diagonal matrices Y _N for which the convergence holds. Convergence of the operator norm is shown to hold for block matrices, even with rectangular Gaussian blocks, a situation including non-white Wishart matrices and some matrices encountered in MIMO systems.     

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