On the Wiener index of random trees

By a theorem of Janson, the Wiener index of a random tree from a simply generated family of trees converges in distribution to a limit law that can be described in terms of the Brownian excursion. The family of unlabelled trees (rooted or unrooted), which is perhaps the most natural one from a graph-theoretical point of view, since isomorphisms are taken into account, is not covered directly by this theorem though. The aim of this paper is to show how one can prove the same limit law for unlabelled trees by means of generating functions and the method of moments.     

On Weighted Depths in Random Binary Search Trees

Following the model introduced by Aguech et al. (Probab Eng Inf Sci 21:133–141, 2007), the weighted depth of a node in a labelled rooted tree is the sum of all labels on the path connecting the node to the root. We analyse weighted depths of nodes with given labels, the last inserted node, nodes ordered as visited by the depth first search process, the weighted path length and the weighted Wiener index in a random binary search tree. We establish three regimes of nodes depending on whether the second-order behaviour of their weighted depths follows from fluctuations of the keys on the path, the depth of the nodes or both. Finally, we investigate a random distribution function on the unit interval arising as scaling limit for weighted depths of nodes with at most one child.     

A general estimate in the invariance principle

We obtain estimates for the accuracy with which a random broken line constructed from sums of independent nonidentically distributed random variables can be approximated by a Wiener process. All estimates depend explicitly on the moments of the random variables; meanwhile, these moments can be of a rather general form. In the case of identically distributed random variables we succeed for the first time in constructing an estimate depending explicitly on the common distribution of the summands and directly implying all results of the famous articles by Komlós, Major, and Tusnády which are devoted to estimates in the invariance principle.     

Hitting Times,Cover Cost,and the Wiener Index of a Tree

We exhibit a close connection between hitting times of the simple random walk on a graph, the Wiener index, and related graph invariants. In the case of trees, we obtain a simple identity relating hitting times to the Wiener index. It is well known that the vertices of any graph can be put in a linear preorder so that vertices appearing earlier in the preorder are “easier to reach” by a random walk, but “more difficult to get out of.” We define various other natural preorders and study their relationships. These preorders coincide when the graph is a tree, but not necessarily otherwise. Our treatise is self‐contained, and puts some known results relating the behavior or random walk on a graph to its eigenvalues in a new perspective.     

On the internal path length of d‐dimensional quad trees

It is proved that the internal path length of a d‐dimensional quad tree after normalization converges in distribution. The limiting distribution is characterized as a fixed point of a random affine operator. We obtain convergence of all moments and of the Laplace transforms. The moments of the limiting distribution can be evaluated from the recursion and lead to first order asymptotics for the moments of the internal path lengths. The analysis is based on the contraction method. In the final part of the paper we state similar results for general split tree models if the expectation of the path length has a similar expansion as in the case of quad trees. This applies in particular to the m‐ary search trees. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 5: 25–41, 1999     

Numerical solutions of Burgers’ equation with random initial conditions using the Wiener chaos expansion and the Lax–Wendroff scheme

The work is concerned with efficient computation of statistical moments of solutions to Burgers’ equation with random initial conditions. When the Lax–Wendroff scheme is expanded using the Wiener chaos expansion (WCE), it introduces an infinite system of deterministic equations with respect to non-random Hermite–Fourier coefficients. One of important properties of the system is that all the statistical moments of the solution can be computed using simple formulae that involve only the solution of the system. The stability, accuracy, and efficiency of the WCE approach to computing statistical moments have been numerically tested and compared to those for the Monte Carlo (MC) method. Strong evidence has been given that the WCE approach is as accurate as but substantially faster than the MC method, at least for certain classes of initial conditions.     

Enumeration of Wiener indices in random polygonal chains

The Wiener index of a connected graph (molecule graph) G is the sum of the distances between all pairs of vertices of G, which was reported by Wiener in 1947 and is the oldest topological index related to molecular branching. In this paper, simple formulae of the expected value of the Wiener index in a random polygonal chain and the asymptotic behavior of this expectation are established by solving a difference equation. Based on the results above, we obtain the average value of the Wiener index of all polygonal chains with n polygons. As applications, we use the unified formulae to obtain the expected values of the Wiener indices of some special random polygonal chains which were deeply discussed in the context of organic chemistry or statistical physics.     

Large Deviations from the Almost Everywhere Central Limit Theorem

We prove large deviation principles for the almost everywhere central limit theorem, assuming that the i.i.d. summands have finite moments of all orders. The level 3 rate function is a specific entropy relative to Wiener measure and the level 2 rate the Donsker-Varadhan entropy of the Ornstein-Uhlenbeck process. In particular, the rate functions are independent of the particular distribution of the i.i.d. process under study. We deduce these results from a large deviation theory for Brownian motion via Skorokhod's representation of random walk as Brownian motion evaluated at random times. The results for Brownian motion come from the well-known large deviation theory of the Ornstein-Uhlenbeck process, by a mapping between the two processes.     

On the M/G/2 queeing model

The M/G/2 queueing model with service time distribution a mixture of m negative exponential distributions is analysed. The starting point is the functional relation for the Laplace–Stieltjes transform of the stationary joint distribution of the workloads of the two servers. By means of Wiener–Hopf decompositions the solution is constructed and reduced to the solution of m linear equations of which the coefficients depend on the zeros of a polynome. Once this set of equations has been solved the moments of the waiting time distribution can be easily obtained. The Laplace–Stieltjes transform of the stationary waiting time distribution has been derived, it is an intricate expression.     

Random cutting and records in deterministic and random trees

We study random cutting down of a rooted tree and show that the number of cuts is equal (in distribution) to the number of records in the tree when edges (or vertices) are assigned random labels. Limit theorems are given for this number, in particular when the tree is a random conditioned Galton–Watson tree. We consider both the distribution when both the tree and the cutting (or labels) are random and the case when we condition on the tree. The proofs are based on Aldous' theory of the continuum random tree. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Wiener Index of Trees: Theory and Applications

The Wiener index W is the sum of distances between all pairs of vertices of a (connected) graph. The paper outlines the results known for W of trees: methods for computation of W and combinatorial expressions for W for various classes of trees, the isomorphism–discriminating power of W, connections between W and the center and centroid of a tree, as well as between W and the Laplacian eigenvalues, results on the Wiener indices of the line graphs of trees, on trees extremal w.r.t. W, and on integers which cannot be Wiener indices of trees. A few conjectures and open problems are mentioned, as well as the applications of W in chemistry, communication theory and elsewhere.     

Estimates in the invariance principle in terms of truncated power moments

We obtain estimates for the distributions of errors which arise in approximation of a random polygonal line by a Wiener process on the same probability space. The polygonal line is constructed on the whole axis for sums of independent nonidentically distributed random variables and the distance between it and the Wiener process is taken to be the uniform distance with an increasing weight. All estimates depend explicitly on truncated power moments of the random variables which is an advantage over the earlier estimates of Komlos, Major, and Tusnady where this dependence was implicit.     

Moments, continuité, et analyse multifractale des martingales de Mandelbrot

Here, a Mandelbrot measure is a statistically self-similar measure μ on the boundary of a c-ary tree, obtained by multiplying random weights indexed by the nodes of the tree. We take a particular interest in the random variable Y = ‖μ‖: we study the existence of finite moments of negative orders for Y, conditionally to Y > 0, and the continuity properties of Y with respect to the weights. Our results on moments make possible to study, with probability one, the existence of a local Hölder exponent for μ, almost everywhere with respect to another Mandelbrot measure, as well as to perform the multifractal analysis of μ, under hypotheses that are weaker than those usually assumed.     

Convergence rate estimates in some limit theorems for maximum random sums

Some estimates of the accuracy of the approximation of the distribution of maximum partial random sums by the distribution of the maximum of the standard Wiener process are given in the case of an asymptotically degenerate index. Proceedings of the Seminar on Stability Problems for Stochastic Models, Moscow, 1993.     

具有随机效应的Wiener加速退化模型的可靠性研究

研究了有随机效应的Wiener退化模型基于加速退化数据的统计推断问题.利用广义枢轴量方法得到了模型参数和感兴趣可靠性指标的广义置信区间.说明了不含随机效应的Wiener退化模型的统计推断问题是有随机效应的Wiener退化模型的特殊情况.蒙特卡罗模拟结果显示文中提出的区间估计有较好的覆盖比例.最后利用LED加速退化数据说...     

Behaviour of queueing approximations based on sample moments

We investigate moment–based queueing approximations in the presence of sampling error. Let L be the steady–state mean number in the system for a GI/M/1 queue. We focus on the estimation of L under the assumption that only sample moments of the interarrival–time distribution are known. A simulation experiment is carried out for several interarrival–time distributions. For each case, sample moments from the interarrival–time distribution are matched to an approximating phase–type distribution and the corresponding estimate L is obtained. We show that the sampling error in the moments induces bias as well as variability in L. Based on our simulation experiment, we suggest matching only two moments when the sample coefficient of variation is low or when sample size is low; otherwise, matching three moments is preferable.     

Precise Logarithmic Asymptotics for the Right Tails of Some Limit Random Variables for Random Trees

For certain random variables that arise as limits of functionals of random finite trees, we obtain precise asymptotics for the logarithm of the right-hand tail. Our results are based on the facts (i) that the random variables we study can be represented as functionals of a Brownian excursion and (ii) that a large deviation principle with good rate function is known explicitly for Brownian excursion. Examples include limit distributions of the total path length and of the Wiener index in conditioned Galton-Watson trees (also known as simply generated trees). In the case of Wiener index (where we recover results proved by Svante Janson and Philippe Chassaing by a different method) and for some other examples, a key constant is expressed as the solution to a certain optimization problem, but the constant’s precise value remains unknown. Research supported by NSF grants DMS-0104167 and DMS-0406104 and by The Johns Hopkins University’s Acheson J. Duncan Fund for the Advancement of Research in Statistics.     

固定直径的树的Wiener指数

图G的wiener指数定义为图中所有点对u,v的距离之和∑d（u,v）. 在这篇文章中,我们刻画了在n个顶点直径为d的所有树中具有第三小wiener指数的树的特征以及介绍了得到这类树的wiener指数排序的方法.