共查询到20条相似文献,搜索用时 15 毫秒
1.
Consider the Aldous Markov chain on the space of rooted binary trees with n labeled leaves in which at each transition a uniform random leaf is deleted and reattached to a uniform random edge. Now, fix 1 ≤ k< n and project the leaf mass onto the subtree spanned by the first k leaves. This yields a binary tree with edge weights that we call a “decorated k‐tree with total mass n.” We introduce label swapping dynamics for the Aldous chain so that, when it runs in stationarity, the decorated k‐trees evolve as Markov chains themselves, and are projectively consistent over k. The construction of projectively consistent chains is a crucial step in the construction of the Aldous diffusion on continuum trees by the present authors, which is the n→ ∞ continuum analog of the Aldous chain and will be taken up elsewhere. 相似文献
2.
The power of choice is known to change the character of random structures and produce desirable optimization effects. We discuss
generalizations of random recursive trees, grown under the choice to meet optimization criteria. Specifically, we discuss
the random k-minimal ( k-maximal) label recursive tree, where a set of k candidate parents, instead of one as in the usual recursive tree, is selected and the node with minimal (maximal) label among
them is assigned as parent for the next node. These models are proposed as alternatives for D’Souza et al. (Eur Phys J B59:535–543,
2007) minimal and maximal depth models. The advantage of the label models is that they are tractable and at the same time provide
approximations and bounds for the depth models. For the depth of nodes in label models we give the average behavior and exact
distributions involving Stirling’s numbers and derive Gaussian limit laws. 相似文献
3.
A capacitated network is a tree with a non negative number, called capacity, associated to each edge. The maximal flow that can pass through a given path is the minimun capacity on the path. Antal and Krapivski (Phys Rev E 74:051110, 2006) study the distribution for the maximal flow from the root to a leaf in the case of a deterministic binary tree with independent
and identically distributed random capacities. In this paper their result is extended to three classes of trees with a random
number of children and dependent random capacities: binary trees with general capacities distribution, branching trees with
exchangeable capacities and random binary search trees. 相似文献
4.
Suppose an urn contains m distinct balls, numbered 1,..., m, and let τ denote the number of i.i.d. samples required to observe all of the balls in the urn. We generalize the partial fraction expansion
type arguments used by Pólya (Z Angew Math Mech 10:96–97, 1930) for approximating
\mathbb E(t)\mathbb{E}(\tau) in the case of fixed sample sizes to obtain an approximation of
\mathbb E(t)\mathbb{E}(\tau) when the sample sizes are i.i.d. random variables. The approximation agrees with that of Sellke (Ann Appl Probab 5(1):294–309,
1995), who made use of Wald’s equation and a Markov chain coupling argument. We also derive a new approximation of
\mathbb V(t)\mathbb{V}(\tau), provide an (improved) bound on the error in these approximations, derive a recurrence for
\mathbb E(t)\mathbb{E}(\tau), give a new large deviation type result for tail probabilities, and look at some special cases. 相似文献
5.
In this paper we study the covariance structure of the number of nodes k and l steps away from the root in random recursive trees. We give an analytic expression valid for all k, l and tree sizes N. The fraction of nodes k steps away from the root is a random probability distribution in k. The expression for the covariances allows us to show that the total variation distance between this (random) probability distribution and its mean converges in probability to zero. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 20: 519–539, 2002 相似文献
6.
In this lecture notes, we will discuss the classical Aleksandrov-Fenchel inequalities for quermassintegrals on convex domains
and pose the problem of how to extend the inequalities to non-convex domains. We will survey some recent progress on the problem,
then report some of our joint work [ 9] in which we generalize the k-th stage of the inequalities to a class of ( k + 1)-convex domains. Our proof, following the earlier work of Castillion [ 8] for k = 1 case of the inequalities, uses the method of optimal transport. 相似文献
7.
Based on uniform recursive trees, we introduce random trees with the factor of time, which are named Yule recursive trees. The structure and the distance between the vertices in Yule recursive trees are investigated in this paper. For arbitrary time t > 0, we first give the probability that a Yule recursive tree Yt is isomorphic to a given rooted tree γ; and then prove that the asymptotic distribution of ζt,m, the number of the branches of size m, is the Poisson distribution with parameter λ = 1/ m. Finally, two types of distance between vertices in Yule recursive trees are studied, and some limit theorems for them are established.© 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007 相似文献
8.
This paper introduces a new concept: a binary sequence of order ( k, r), which is an extension of a binary sequence of order k and a Markov dependent sequence. The probability functions of the sooner and later waiting time random variables are derived in the binary sequence of order ( k, r). The probability generating functions of the sooner and later waiting time distributions are also obtained. Extensions of these results to binary sequence of order ( g, h) are also presented. 相似文献
9.
For labeled trees, Rényi showed that the probability that an arbitrary point of a random tree has degree k approaches l/e( k?l)!. For unlabeled trees, the answer is different because the number of ways to label a given tree depends on the order of its automorphism group. Using arguments involving combinatorial enumeration and asymptotics, we evaluate the corresponding probabilities for large unlabeled trees. 相似文献
10.
In this work, we introduce the s, k- extremal coefficients for studying the tail dependence between the s-th lower and k-th upper order statistics of a normalized random vector. If its margins have tail dependence then so do their order statistics, with the strength of bivariate tail dependence decreasing as two order statistics become farther apart. Some general properties are derived for these dependence measures which can be expressed via copulas of random vectors. Its relations with other extremal dependence measures used in the literature are discussed, such as multivariate tail dependence coefficients, the coefficient η of tail dependence, coefficients based on tail dependence functions, the extremal coefficient ?, the multivariate extremal index and an extremal coefficient for min-stable distributions. Several examples are presented to illustrate the results, including multivariate exponential and multivariate Gumbel distributions widely used in applications. 相似文献
11.
Starting from a real-valued Markov chain X0, X1,…, Xn with stationary transition probabilities, a random element { Y( t); t[0, 1]} of the function space D[0, 1] is constructed by letting Y( k/ n)= Xk, k= 0,1,…, n, and assuming Y ( t) constant in between. Sample tightness criteria for sequences { Y( t); t[0,1]}; n of such random elements in D[0, 1] are then given in terms of the one-step transition probabilities of the underlying Markov chains. Applications are made to Galton-Watson branching processes. 相似文献
12.
The probabilistic aspects of a queue of particles transiting a trapping field is studied. In particular, the probability that the k-th transiting particle is absorbed, given that there are initially t traps, is obtained in closed form by combinatorial arguments in terms of Gauss polynomials ( q-binomial coefficients). In addition the probability of survival of the k-th transiting particle is also evaluated, again in terms of Gauss polynomials. The analysis is general enough to allow the number of traps t to be a discrete random variable, although numerical calculations (in the form of tables) are confined to t being deterministic.
Zusammenfassung Die wahrscheinlichkeitstheoretischen Aspekte einer Reihe von Teilchen, welche ein Feld von Fallen durchlaufen, werden untersucht. Insbesondere wird die Wahrscheinlichkeit, daß dask-te Teilchen absorbiert wird, wenn anfangst Fallen vorhanden waren, mittels kombinatorischer Argumente durch Gauss-Polynome (q-Binomialkoeffizienten) in geschlossener Form dargestellt. Außerdem wird die Überlebenswahrscheinlichkeit desk-ten das Feld durchlaufenden Teilchens errechnet, ebenfalls in Form von Gauss-Polynomen. Die Allgemeinheit der Untersuchung läßt zu, daß die Anzahlt der Fallen eine diskrete Zufallsvariable sein kann, wobei aber die numerischen Berechnungen (in Form von Tabellen) auf deterministischet-Werte beschränkt wurden. 相似文献
13.
Let k denote one of the families of binary trees, t-aray trees ( t> 2) or ordered trees with nodes labelled monotonically by elements of {1 < 2 < ? < k}. The average height of the j-th leaf of the trees of k with exactly n nodes is shown to converge to a finite limit (depending on k and j) for n → ∞. The limit is determined explicitly for small values of k and its asymptotic behaviour in j and k is investigated. Some recent results on the average shape of rooted tree structures appear as special cases. 相似文献
14.
It has recently been shown by Rootzén and Tajvidi (Bernoulli, 12:917–930, 2006) that modelling exceedances of a random variable over a high threshold (peaks-over-threshold approach [POT]) can also in
the multivariate setup be done rationally only by a multivariate generalized Pareto distribution (GPD). The selection of a
proper threshold is, however, a crucial problem. The contribution of this paper is twofold: We develop first a non asymptotic
and exact level- α test based on the single-sample t-test, which checks whether multivariate data are actually generated by a multivariate GPD. Secondly, this procedure is utilized
for the derivation of a t-test based threshold selection rule in multivariate peaks-over-threshold models. The application to a hydrological data set
illustrates this approach.
相似文献
15.
Evaluating a binary tree in postorder we assume that in one unit of time zero or two nodes are removed from the top of the
stack and one node is stored in the stack. The oscillation of the stack can be described by a function f where f(t) is the number of nodes in the stack after t units of time.
In this paper we shall first derive several new enumeration results concerning planted plane trees. In the second part we
shall prove, that the average number of maxima (MAX-turns) and minima (MIN-turns) of the function f is n/2 and n/2—1, respectively, provided that all binary trees with n leaves are equally likely. Finally, we shall compute for large n and fixed j the average increase (decrease) of the length of the stack between the j-th MIN-turn and ( j+1)-th MAX-turn (between the j-th MAX-turn and the j-th MIN-turn). This result implies that the average oscillation of the stack can be described by the function f(j)=4√ j/π−(−1)
j
+ O(1/√ j) for large n and fixed turn-number j. 相似文献
16.
Let r
k
( n) denote the number of ways n can be expressed as a sum of k squares. Recently, S. Cooper (Ramanujan J. 6:469–490, [ 2002]), conjectured a formula for r
9( t), t≡5 (mod 8), r
11( t), t≡7 (mod 8), where t is a square-free positive integer. In this note we observe that these conjectures follow from the works of Lomadze (Akad.
Nauk Gruz. Tr. Tbil. Mat. Inst. Razmadze 17:281–314, [ 1949]; Acta Arith. 68(3):245–253, [ 1994]). Further we express r
9( t), r
11( t) in terms of certain special values of Dirichlet L-functions. Combining these two results we get expressions for these special values of Dirichlet L-functions involving Jacobi symbols.
相似文献
17.
We present here a new and universal approach for the study of random and/or trees, unifying in one framework many different models, including some novel ones not yet understood in the literature. An and/or tree is a Boolean expression represented in (one of) its tree shapes. Fix an integer k, take a sequence of random (rooted) trees of increasing size, say , and label each of these random trees uniformly at random in order to get a random Boolean expression on k variables. We prove that, under rather weak local conditions on the sequence of random trees , the distribution induced on Boolean functions by this procedure converges as n tends to infinity. In particular, we characterize two different behaviors of this limit distribution depending on the shape of the local limit of : a degenerate case when the local limit has no leaves; and a non‐degenerate case, which we are able to describe in more details under stronger conditions. In this latter case, we provide a relationship between the probability of a given Boolean function and its complexity. The examples covered by this unified framework include trees that interpolate between models with logarithmic typical distances (such as random binary search trees) and other ones with square root typical distances (such as conditioned Galton–Watson trees). 相似文献
18.
The k-th spectral moment Mk(G) of the adjacency matrix of a graph G represents the number of closed walks of length k in G. We study here the partial order ? of graphs, defined by G ? H if Mk(G) ≤ Mk(H) for all k ≥?0, and are interested in the question when is ? a linear order within a specified set of graphs? Our main result is that ? is a linear order on each set of starlike trees with constant number of vertices. Recall that a connected graph G is a starlike tree if it has a vertex u such that the components of G ? u are paths, called the branches of G. It turns out that the ? ordering of starlike trees with constant number of vertices coincides with the shortlex order of sorted sequence of their branch lengths. 相似文献
19.
We consider a { 0,1}-valued m-th order stationary Markov chain. We study the occurrences of runs where two 1’s are separated by at most/exactly/at least k 0’s under the overlapping enumeration scheme where k≥0 and occurrences of scans (at least k
1 successes in a window of length at most k, 1≤ k
1≤ k) under both non-overlapping and overlapping enumeration schemes. We derive the generating function of first two types of
runs. Under the conditions, (1) strong tendency towards success and (2) strong tendency towards reversing the state, we establish
the convergence of waiting times of the r-th occurrence of runs and scans to Poisson type distributions. We establish the central limit theorem and law of the iterated
logarithm for the number of runs and scans up to time n. 相似文献
20.
We show that the without replacement bootstrap of Booth, Butler and Hall ( J. Am. Stat. Assoc.
89, 1282–1289, 1994) provides second order correct approximation to the distribution function of a Studentized U-statistic based on simple random
sample drawn without replacement. In order to achieve similar approximation accuracy for the bootstrap procedure due to Bickel
and Freedman ( Ann. Stat.
12, 470–482, 1984) and Chao and Lo ( Sankhya Ser. A
47, 399–405, 1985) we introduce randomized adjustments to the resampling fraction.
相似文献
|