First Hitting Time Analysis of the Independence Metropolis Sampler

In this paper, we study a special case of the Metropolis algorithm, the Independence Metropolis Sampler (IMS), in the finite state space case. The IMS is often used in designing components of more complex Markov Chain Monte Carlo algorithms. We present new results related to the first hitting time of individual states for the IMS. These results are expressed mostly in terms of the eigenvalues of the transition kernel. We derive a simple form formula for the mean first hitting time and we show tight lower and upper bounds on the mean first hitting time with the upper bound being the product of two factors: a “local” factor corresponding to the target state and a “global” factor, common to all the states, which is expressed in terms of the total variation distance between the target and the proposal probabilities. We also briefly discuss properties of the distribution of the first hitting time for the IMS and analyze its variance. We conclude by showing how some non-independence Metropolis–Hastings algorithms can perform better than the IMS and deriving general lower and upper bounds for the mean first hitting times of a Metropolis–Hastings algorithm.     

First‐passage percolation on a ladder graph,and the path cost in a VCG auction

This paper studies the time constant for first‐passage percolation, and the Vickrey‐Clarke‐Groves (VCG) payment, for the shortest path on a ladder graph (a width‐2 strip) with random edge costs, treating both in a unified way based on recursive distributional equations. For first‐passage percolation where the edge costs are independent Bernoulli random variables we find the time constant exactly; it is a rational function of the Bernoulli parameter. For first‐passage percolation where the edge costs are uniform random variables we present a reasonably efficient means for obtaining arbitrarily close upper and lower bounds. Using properties of Harris chains we also show that the incremental cost to advance through the medium has a unique stationary distribution, and we compute stochastic lower and upper bounds. We rely on no special properties of the uniform distribution: the same methods could be applied to any well‐behaved, bounded cost distribution. For the VCG payment, with Bernoulli‐distributed costs the payment for an n‐long ladder, divided by n, tends to an explicit rational function of the Bernoulli parameter. Again, our methods apply more generally. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 38, 350‐364, 2011     

Justifying the small‐world phenomenon via random recursive trees

We present a new technique for proving logarithmic upper bounds for diameters of evolving random graph models, which is based on defining a coupling between random graphs and variants of random recursive trees. The advantage of the technique is three‐fold: it is quite simple and provides short proofs, it is applicable to a broad variety of models including those incorporating preferential attachment, and it provides bounds with small constants. We illustrate this by proving, for the first time, logarithmic upper bounds for the diameters of the following well known models: the forest fire model, the copying model, the PageRank‐based selection model, the Aiello‐Chung‐Lu models, the generalized linear preference model, directed scale‐free graphs, the Cooper‐Frieze model, and random unordered increasing k‐trees. Our results shed light on why the small‐world phenomenon is observed in so many real‐world graphs. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 201–224, 2017     

Range Value-at-Risk bounds for unimodal distributions under partial information

In this paper, we derive upper and lower bounds on the Range Value-at-Risk of the portfolio loss when we only know its mean, variance, and feature of unimodality. In a first step, we use some classic results on stochastic ordering to reduce this optimization problem to a parametric one, which in a second step can be solved using standard methods. The novel approach we propose makes it possible to obtain analytical results for all probability levels and is moreover amendable to other situations of interest. Specifically, we apply our method to obtain risk bounds in the case of a portfolio loss that is non-negative (as is often the case in practice) and whose variance is possibly infinite. Numerical illustrations show that in various cases of interest we obtain bounds that are of practical importance.     

Formal verification of tail distribution bounds in the HOL theorem prover

Tail distribution bounds play a major role in the estimation of failure probabilities in performance and reliability analysis of systems. They are usually estimated using Markov's and Chebyshev's inequalities, which represent tail distribution bounds for a random variable in terms of its mean or variance. This paper presents the formal verification of Markov's and Chebyshev's inequalities for discrete random variables using a higher‐order‐logic theorem prover. The paper also provides the formal verification of mean and variance relations for some of the widely used discrete random variables, such as Uniform(m), Bernoulli(p), Geometric(p) and Binomial(m, p) random variables. This infrastructure allows us to precisely reason about the tail distribution properties and thus turns out to be quite useful for the analysis of systems used in safety‐critical domains, such as space, medicine or transportation. For illustration purposes, we present the performance analysis of the coupon collector's problem, a well‐known commercially used algorithm. Copyright © 2008 John Wiley & Sons, Ltd.     

Height-analysis ofk-dimensional leaf and node height-balanced trees: A new approach

A new general approach is proposed for the height-analysis ofk-dimensional leaf and node height-balanced trees which is expected to be useful for such analysis of other neighbor-supported balanced multidimensional trees as well. The approach leads to upper bounds which are the same as the known upper bounds for the corresponding 1-dimensional trees, to within an additive term.This research is partially supported by a grant from the College of Business Administration, Georgia State University, Atlanta, Georgia.Actually a variant calledalmost 2-dimensional leaf AVL-trees is introduced in order to facilitate the derivation of an upper bound for the height of these trees which is within an additive term to the bound for such 1-dimensional trees.     

On the first passage time of a simple random walk on a tree

We consider a simple random walk on a tree. Exact expressions are obtained for the expectation and the variance of the first passage time, thereby recovering the known result that these are integers. A relationship of the mean first passage matrix with the distance matrix is established and used to derive a formula for the inverse of the mean first passage matrix.     

Moment inequalities for the discrete-time bulk service queue

For the discrete-time bulk service queueing model, the mean and variance of the steady-state queue length can be expressed in terms of moments of the arrival distribution and series of the zeros of a characteristic equation. In this paper we investigate the behaviour of these series. In particular, we derive bounds on the series, from which bounds on the mean and variance of the queue length follow. We pay considerable attention to the case in which the arrivals follow a Poisson distribution. For this case, additional properties of the series are proved leading to even sharper bounds. The Poisson case serves as a pilot study for a broader range of distributions.     

Analysis of three graph parameters for random trees

We consider three basic graph parameters, the node‐independence number, the path node‐covering number, and the size of the kernel, and study their distributional behavior for an important class of random tree models, namely the class of simply generated trees, which contains, e.g., binary trees, rooted labeled trees, and planted plane trees, as special instances. We can show for simply generated tree families that the mean and the variance of each of the three parameters under consideration behave for a randomly chosen tree of size n asymptotically ～μn and ～νn, where the constants μ and ν depend on the tree family and the parameter studied. Furthermore we show for all parameters, suitably normalized, convergence in distribution to a Gaussian distributed random variable. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Upper and Lower Bounds for the Lengths of Steiner Trees in 3-Space

We present a method of determining upper and lower bounds for the length of a Steiner minimal tree in 3-space whose topology is a given full Steiner topology, or a degenerate form of that full Steiner topology. The bounds are tight, in the sense that they are exactly satisfied for some configurations. This represents the first nontrivial lower bound to appear in the literature. The bounds are developed by first studying properties of Simpson lines in both two and three dimensional space, and then introducing a class of easily constructed trees, called midpoint trees, which provide the upper and lower bounds. These bounds can be constructed in quadratic time. Finally, we discuss strategies for improving the lower bound.Supported by a grant from the Australia Research Council.     

Sharp Bounds for Exponential Approximations of NWUE Distributions

Let F be an NWUE distribution with mean 1 and G be the stationary renewal distribution of F. We would expect G to converge in distribution to the unit exponential distribution as its mean goes to 1. In this paper, we derive sharp bounds for the Kolmogorov distance between G and the unit exponential distribution, as well as between G and an exponential distribution with the same mean as G. We apply the bounds to geometric convolutions and to first passage times.     

The expectation and variance of the joint linear complexity of random periodic multisequences

The linear complexity of sequences is one of the important security measures for stream cipher systems. Recently, in the study of vectorized stream cipher systems, the joint linear complexity of multisequences has been investigated. By using the generalized discrete Fourier transform for multisequences, Meidl and Niederreiter determined the expectation of the joint linear complexity of random N-periodic multisequences explicitly. In this paper, we study the expectation and variance of the joint linear complexity of random periodic multisequences. Several new lower bounds on the expectation of the joint linear complexity of random periodic multisequences are given. These new lower bounds improve on the previously known lower bounds on the expectation of the joint linear complexity of random periodic multisequences. By further developing the method of Meidl and Niederreiter, we derive a general formula and a general upper bound for the variance of the joint linear complexity of random N-periodic multisequences. These results generalize the formula and upper bound of Dai and Yang for the variance of the linear complexity of random periodic sequences. Moreover, we determine the variance of the joint linear complexity of random periodic multisequences with certain periods.     

Extrinsic Isoperimetric Analysis on Submanifolds with Curvatures Bounded from Below

We obtain upper bounds for the isoperimetric quotients of extrinsic balls of submanifolds in ambient spaces which have a lower bound on their radial sectional curvatures. The submanifolds are themselves only assumed to have lower bounds on the radial part of the mean curvature vector field and on the radial part of the intrinsic unit normals at the boundaries of the extrinsic spheres, respectively. In the same vein we also establish lower bounds on the mean exit time for Brownian motions in the extrinsic balls, i.e. lower bounds for the time it takes (on average) for Brownian particles to diffuse within the extrinsic ball from a given starting point before they hit the boundary of the extrinsic ball. In those cases, where we may extend our analysis to hold all the way to infinity, we apply a capacity comparison technique to obtain a sufficient condition for the submanifolds to be parabolic, i.e. a condition which will guarantee that any Brownian particle, which is free to move around in the whole submanifold, is bound to eventually revisit any given neighborhood of its starting point with probability 1. The results of this paper are in a rough sense dual to similar results obtained previously by the present authors in complementary settings where we assume that the curvatures are bounded from above.     

Homogenization and Enhancement of the G‐Equation in Random Environments

We study the homogenization of a G‐equation that is advected by a divergence free “small mean” stationary vector field in a general ergodic random environment. We prove that the averaged equation is an anisotropic deterministic G‐equation, and we give necessary and sufficient conditions for enhancement. Since the problem is not assumed to be coercive, it is not possible to have uniform bounds for the solutions. In addition, as we show, the associated minimal (first passage) time function does not satisfy, in general, the uniform integrability condition that is necessary to apply the subadditive ergodic theorem. We overcome these obstacles by (i) establishing a new reachability (controllability) estimate for the minimal function and (ii) constructing, for each direction and almost surely, a random sequence that has both a long‐time averaged limit (due to the subadditive ergodic theorem) and stays asymptotically close to the minimal time. © 2013 Wiley Periodicals, Inc.     

Starshaped hypersurfaces and the mean curvature flow

Under the assumption of two a-priori bounds for the mean curvature, we are able to generalize a recent result due to Huisken and Sinestrari [8], valid for mean convex surfaces, to a much larger class. In particular we will demonstrate that these a-priori bounds are satisfied for a class of surfaces including meanconvex as well as starshaped surfaces and a variety of manifolds that are close to them. This gives a classification of the possible singularities for these surfaces in the casen=2. In addition we prove that under certain initial conditions some of them become mean convex before the first singularity occurs.     

Universal graphs and induced-universal graphs

We construct graphs that contain all bounded-degree trees on n vertices as induced subgraphs and have only cn edges for some constant c depending only on the maximum degree. In general, we consider the problem of determining the graphs, so-called universal graphs (or induced-universal graphs), with as few vertices and edges as possible having the property that all graphs in a specified family are contained as subgraphs (or induced subgraphs). We obtain bounds for the size of universal and induced-universal graphs for many classes of graphs such as trees and planar graphs. These bounds are obtained by establishing relationships between the universal graphs and the induced-universal graphs.     

New bounds for expected delay in FIFO M/G/c queues

Most bounds for expected delay, E[D], in GI/GI/c queues are modifications of bounds for the GI/GI/1 case. In this paper we exploit a new delay recursion for the GI/GI/c queue to produce bounds of a different sort when the traffic intensity p = λ/μ = E[S]/E[T] is less than the integer portion of the number of servers divided by two. (S AND T denote generic service and interarrival times, respectively.) We derive two different families of new bounds for expected delay, both in terms of moments of S AND T. Our first bound is applicable when E[S₂] < ∞. Our second bound for the first time does not require finite variance of S; it only involves terms of the form E[S^β], where 1 < β < 2. We conclude by comparing our bounds to the best known bound of this type, as well as values obtained from simulation. This revised version was published online in June 2006 with corrections to the Cover Date.     

Depth in bucket recursive trees with variable capacities of buckets

We consider bucket recursive trees of sizen consisting of all buckets with variable capacities1,2,...,b and with a specifc stochastic growth rule.This model can be considered as a generalization of random recursive trees like bucket recursive trees introduced by Mahmoud and Smythe where all buckets have the same capacities.In this work,we provide a combinatorial analysis of these trees where the generating function of the total weights satisfes an autonomous frst order diferential equation.We study the depth of the largest label（i.e.,the number of edges from the root node to the node containing label n）and give a closed formula for the probability distribution.Also we prove a limit law for this quantity which is a direct application of quasi power theorem and compute its mean and variance.Our results for b=1 reduce to the previous results for random recursive trees.     

Cyclicity of graphs

The cyclicity of a graph is the largest integer n for which the graph is contractible to the cycle on n vertices. By analyzing the cycle space of a graph, we establish upper and lower bounds on cyclicity. These bounds facilitate the computation of cyclicity for several classes of graphs, including chordal graphs, complete n-partite graphs, n-cubes, products of trees and cycles, and planar graphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 160–170, 1999