Variable length path coupling

We present a new technique for constructing and analyzing couplings to bound the convergence rate of finite Markov chains. Our main theorem is a generalization of the path coupling theorem of Bubley and Dyer, allowing the defining partial couplings to have length determined by a random stopping time. Unlike the original path coupling theorem, our version can produce multistep (non‐Markovian) couplings. Using our variable length path coupling theorem, we improve the upper bound on the mixing time of the Glauber dynamics for randomly sampling colorings. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

The average path length of scale free networks

In this paper, the exact solution of average path length in Barabási–Albert model is given. The average path length is an important property of networks and attracts much attention in many areas. The Barabási–Albert model, also called scale free model, is a popular model used in modeling real systems. Hence it is valuable for us to examine the average path length of scale free model. There are two answers, regarding the exact solution for the average path length of scale free networks, already provided by Newman and Bollobas respectively. As Newman proposed, the average path length grows as log(n) with the network size n. However, Bollobas suggested that while it was true when m = 1, the answer changed to log(n)/log(log(n)) when m > 1. In this paper, as we propose, the exact solution of average path length of BA model should approach log(n)/log(log(n)) regardless the value of m. Finally, the simulation is presented to show the validity of our result.     

The chance constrained critical path with location-scale distributions

The Chance Constrained Critical Path (CCCP) generally depends on the preassigned minimum probability level. It is shown that for a wide class of probability distributions there always exists a probability value for which the CCCP remains unchanged for all probabilities greater than or equal to that value. This probability value is easily obtained from an optimal solution of a simple network problem. In addition, necessary and sufficient conditions for the CCCP to be unconditionally independent of the minimum probability level are given for that class of probability distributions.     

Proper generating trees and their internal path length

We find the generating function counting the total internal path length of any proper generating tree. This function is expressed in terms of the functions (d(t),h(t)) defining the associated proper Riordan array. This result is important in the theory of Riordan arrays and has several combinatorial interpretations.     

The weight distributions of irreducible cyclic codes of length

Let m be a positive integer and q be an odd prime power. In this paper, the weight distributions of all the irreducible cyclic codes of length 2^m over F_q are determined explicitly.     

Digraphs without directed path of length two or three

We characterize digraphs without any path of length two or of length three.     

Proximity between life distributions and exponential distributions (I)

Many classes of life distributions have been introduced into reliability theory. Because of the importance of exponential distributions in reliability theory, it is interesting to study the difference between life distributions and exponential distributions. In this paper, we study the proximity between the life distribution in various classes and the exponential distribution. We shall give some simple upper bounds.This research was partially supported by the National Natural Science Foundation of China.     

Parametrization via secant length and application to path following

Summary A possible way for parametrizing the solution path of the nonlinear systemH(u)=0, H: ^{n+1 n} consists of using the secant length as parameter. This idea leads to a quadratic constraint by which the parameter is introduced. A Newton-like method for computing the solution for a given parameter is proposed where the nonlinear system is linearized at each iterate, but the quadratic parametrizing equation is exactly satisfied. The localQ-quadratic convergence of the method is proved and some hints for implementing the algorithm are givenDedicated to Professor Lothar Collatz on the occasion of his 75th birthday     

Mapping resolutions of length three I

We produce some interesting families of resolutions of length three by describing certain open subsets of the spectrum of the generic ring for such resolutions constructed in [6].     

Cycle length distributions in random permutations with diverging cycle weights

We study the model of random permutations with diverging cycle weights, which was recently considered by Ercolani and Ueltschi, and others. Assuming only regular variation of the cycle weights we obtain a very precise local limit theorem for the size of a typical cycle, and use this to show that the empirical distribution of properly rescaled cycle lengths converges in probability to a gamma distribution.Copyright © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46,635–650, 2015     

Standardization of distributions of the chord length and distance within oval domains

The distributions of the chord length and distance within oval domains are expressed in terms of the distributions of these values in a circle and of some parameters of oval domains. Institute of Mathematics and Informatics, Akademijos 4, 2600 Vilnius, Lithuania. Translated from Lietuvos Matematikos Rinkinys, Vol. 39, No. 4, pp. 469–474, October–December, 1999. Translated by E. Gečiauskas     

On martingale tail sums for the path length in random trees

For a martingale (X_n) converging almost surely to a random variable X, the sequence (X_n– X) is called martingale tail sum. Recently, Neininger (Random Structures Algorithms 46 (2015), 346–361) proved a central limit theorem for the martingale tail sum of Régnier's martingale for the path length in random binary search trees. Grübel and Kabluchko (in press) gave an alternative proof also conjecturing a corresponding law of the iterated logarithm. We prove the central limit theorem with convergence of higher moments and the law of the iterated logarithm for a family of trees containing binary search trees, recursive trees and plane‐oriented recursive trees. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 493–508, 2017     

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     

Modification of particle distributions by MHD instabilities I

The modification of particle distributions by low amplitude magnetohydrodynamic modes is an important topic for magnetically confined plasmas. Low amplitude modes are known to be capable of producing significant modification of injected neutral beam profiles, and the same can be expected in burning plasmas for the alpha particle distributions. Flattening of a distribution due to phase mixing in an island or due to portions of phase space becoming stochastic is a process extremely rapid on the time scale of an experiment but still very long compared to the time scale of guiding center simulations. Thus it is very valuable to be able to locate significant resonances and to predict the final particle distribution produced by a given spectrum of magnetohydrodynamic modes. In this paper we introduce a new method of determining domains of phase space in which good surfaces do not exist and use this method for quickly determining the final state of the particle distribution without carrying out the full time evolution leading to it.     

Discrete -convex extremal distributions: Theory and applications

Given a nondegenerate moment space with s fixed moments, explicit formulas for the discrete s-convex extremal distribution have been derived for s=1,2,3 (see [M. Denuit, Cl. Lefèvre, Some new classes of stochastic order relations among arithmetic random variables, with applications in actuarial sciences, Insurance Math. Econom. 20 (1997) 197–214]). If s=4, only the maximal distribution is known (see [M. Denuit, Cl. Lefèvre, M. Mesfioui, On s-convex stochastic extrema for arithmetic risks, Insurance Math. Econom. 25 (1999) 143–155]). This work goes beyond this limitation and proposes a method for deriving explicit expressions for general nonnegative integer s. In particular, we derive explicitly the discrete 4-convex minimal distribution. For illustration, we show how this theory allows one to bound the probability of extinction in a Galton–Watson branching process. The results are also applied to derive bounds for the probability of ruin in the compound binomial and Poisson insurance risk models.     

On the maximum size of connected hypergraphs without a path of given length

In this note we asymptotically determine the maximum number of hyperedges possible in an $r$-uniform, connected $n$-vertex hypergraph without a Berge path of length $k$, as $n$ and $k$ tend to infinity. We show that, unlike in the graph case, the multiplicative constant is smaller with the assumption of connectivity.     

Comparing different metaheuristic approaches for the median path problem with bounded length

In this paper we consider the Bounded Length Median Path Problem which can be defined as the problem of locating a path-shaped facility that departures from a given origin and arrives at a given destination in a network. The length of the path is assumed to be bounded by a given maximum length. At each vertex of the network (customer-point) the demand for the service is given and the cost to reach the closest service-point is computed. The objective is to minimize the sum of these costs over all the customer-points in the network.     

Conditional limit results for type I polar distributions

Let (S ₁,S ₂) = (R cos(Θ), R sin(Θ)) be a bivariate random vector with associated random radius R which has distribution function F being further independent of the random angle Θ. In this paper we investigate the asymptotic behaviour of the conditional survivor probability when u approaches the upper endpoint of F. On the density function of Θ we impose a certain local asymptotic behaviour at 0, whereas for F we require that it belongs to the Gumbel max-domain of attraction. The main result of this contribution is an asymptotic expansion of , which is then utilised to construct two estimators for the conditional distribution function . Furthermore, we allow Θ to depend on u.