共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
3.
4.
K. B. Athreya 《Proceedings Mathematical Sciences》1994,104(1):263-267
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 相似文献
5.
6.
7.
8.
Boris Pittel 《Random Structures and Algorithms》1994,5(2):337-347
A process of growing a random recursive tree Tn is studied. The sequence {Tn} 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 Tn 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 γe1+γ = 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. 相似文献
9.
James Hirschorn 《Israel Journal of Mathematics》2007,157(1):123-153
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. 相似文献
10.
We discuss the existence of multi-colored trees in randomly colored, random graphs. © 1994 John Wiley & Sons, Inc. 相似文献
11.
A random suffix search tree is a binary search tree constructed for the suffixes Xi = 0 · BiBi+1Bi+2… of a sequence B1, B2, B3, … of independent identically distributed random b‐ary digits Bj. Let Dn denote the depth of the node for Xn in this tree when B1 is uniform on ?b. We show that for any value of b > 1, ??Dn = 2 log n + O(log2log n), just as for the random binary search tree. We also show that Dn/??Dn → 1 in probability. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2003 相似文献
12.
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. 相似文献
13.
Lynn Hauser Pearce 《Discrete Mathematics》1980,30(3):269-276
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. 相似文献
14.
Luc Devroye 《Random Structures and Algorithms》1994,5(2):305-327
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 na for a ?[1/2, 1]. © 1994 John Wiley & Sons, Inc. 相似文献
15.
Attila Deák 《Acta Mathematica Hungarica》2013,141(1-2):185-201
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. 相似文献
16.
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 相似文献
17.
M. Gromov 《Geometric And Functional Analysis》2003,13(1):73-146
((no abstract)) .
Submitted: January 2002, Final version: December 2002. 相似文献
18.
Camille Male 《Probability Theory and Related Fields》2012,154(3-4):477-532
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. 相似文献
20.
Philippe Flajolet Xavier Gourdon Conrado Martínez 《Random Structures and Algorithms》1997,11(3):223-244
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 相似文献