On the complexity of branch‐and‐bound search for random trees

Let T_n be a b‐ary tree of height n, which has independent, non‐negative, identically distributed random variables associated with each of its edges, a model previously considered by Karp, Pearl, McDiarmid, and Provan. The value of a node is the sum of all the edge values on its path to the root. Consider the problem of finding the minimum leaf value of T_n. Assume that the edge random variable X is nondegenerate, has E {X^θ}<∞ for some θ>2, and satisfies bP{X=c}<1 where c is the leftmost point of the support of X. We analyze the performance of the standard branch‐and‐bound algorithm for this problem and prove that the number of nodes visited is in probability (β+o(1))ⁿ, where β∈(1, b) is a constant depending only on the distribution of the edge random variables. Explicit expressions for β are derived. We also show that any search algorithm must visit (β+o(1))ⁿ nodes with probability tending to 1, so branch‐and‐bound is asymptotically optimal where first‐order asymptotics are concerned. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14: 309–327, 1999     

MAX k‐CUT and approximating the chromatic number of random graphs

We consider the MAX k‐CUT problem on random graphs G_n,p. First, we bound the probable weight of a MAX k‐CUT using probabilistic counting arguments and by analyzing a simple greedy heuristic. Then, we give an algorithm that approximates MAX k‐CUT in expected polynomial time, with approximation ratio 1 + O((np)^‐1/2). Our main technical tool is a new bound on the probable value of Frieze and Jerrum's semidefinite programming (SDP)‐relaxation of MAX k‐CUT on random graphs. To obtain this bound, we show that the value of the SDP is tightly concentrated. As a further application of our bound on the probable value of the SDP, we obtain an algorithm for approximating the chromatic number of G_n,p, 1/n ≤ p ≤ 0.99, within a factor of O((np)^1/2) in polynomial expected time, thereby answering a question of Krivelevich and Vu. We give similar algorithms for random regular graphs. The techniques for studying the SDP apply to a variety of SDP relaxations of further NP‐hard problems on random structures and may therefore be of independent interest. For instance, to bound the SDP we estimate the eigenvalues of random graphs with given degree sequences. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Probabilistic mean value theorems for conditioned random variables with applications

In this paper, we propose a probabilistic analogue of the mean value theorem for conditional nonnegative random variables ordered in the hazard rate and reversed hazard rate order, upon conditioning on intervals of the form (t,∞) and [0,t]. This result is then specialized within the proportional hazards model and the proportional reversed hazards model with applications to series systems in reliability theory and to absorption random times of linear birth‐death processes. We also study the comparison of residual entropies and discuss some connections to Wasserstein and stop‐loss distances of random variables. A treatment for the additive hazard rate model is finally provided, with an application to life annuities.     

Berry–Esseen Bound for a Sample Sum from a Finite Set of Independent Random Variables

Let {X ₁,...,X _N} be a set of N independent random variables, and let S _n be a sum of n random variables chosen without replacement from the set {X ₁,...,X _N} with equal probabilities. In this paper we give an estimate of the remainder term for the normal approximation of S _n under mild conditions.     

The Passage Time Distribution for a Birth-and-Death Chain: Strong Stationary Duality Gives a First Stochastic Proof

A well-known theorem usually attributed to Keilson states that, for an irreducible continuous-time birth-and-death chain on the nonnegative integers and any d, the passage time from state 0 to state d is distributed as a sum of d independent exponential random variables. Until now, no probabilistic proof of the theorem has been known. In this paper we use the theory of strong stationary duality to give a stochastic proof of a similar result for discrete-time birth-and-death chains and geometric random variables, and the continuous-time result (which can also be given a direct stochastic proof) then follows immediately. In both cases we link the parameters of the distributions to eigenvalue information about the chain. We also discuss how the continuous-time result leads to a proof of the Ray–Knight theorem. Intimately related to the passage-time theorem is a theorem of Fill that any fastest strong stationary time T for an ergodic birth-and-death chain on {0,…,d} in continuous time with generator G, started in state 0, is distributed as a sum of d independent exponential random variables whose rate parameters are the nonzero eigenvalues of −G. Our approach yields the first (sample-path) construction of such a T for which individual such exponentials summing to T can be explicitly identified. Research of J.A. Fill was supported by NSF grant DMS–0406104 and by The Johns Hopkins University’s Acheson J. Duncan Fund for the Advancement of Research in Statistics.     

A strong law of large numbers on the harmonic <Emphasis Type="Italic">p</Emphasis>-combination

In this paper, we establish a strong law of large numbers for the harmonic p-combinations of random star bodies. Starting from this theorem, we prove a strong law of large numbers in L _p space and provide the probabilistic version of dual Brunn-Minkowski inequality.     

Proof of the local REM conjecture for number partitioning. I: Constant energy scales

In this article we consider the number partitioning problem (NPP ) in the following probabilistic version: Given n numbers X₁,…,X_n drawn i.i.d. from some distribution, one is asked to find the partition into two subsets such that the sum of the numbers in one subset is as close as possible to the sum of the numbers in the other set. In this probabilistic version, the NPP is equivalent to a mean‐field antiferromagnetic Ising spin glass, with spin configurations corresponding to partitions, and the energy of a spin configuration corresponding to the weight difference. Although the energy levels of this model are a priori highly correlated, a surprising recent conjecture of Bauke, Franz, and Mertens asserts that the energy spectrum of number partitioning is locally that of a random energy model (REM): the spacings between nearby energy levels are uncorrelated. More precisely, it was conjectured that the properly scaled energies converge to a Poisson process, and that the spin configurations corresponding to nearby energies are asymptotically uncorrelated. In this article, we prove these two claims, collectively known as the local REM conjecture. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Lower-Bound Estimates for Poisson-Type Approximations

Let S = w ₁ S ₁ + w ₂ S ₂ + ⋯ + w _N S _N . Here S _j is a sum of identically distributed random variables with weight w _j > 0. We consider the cases where S _j is a sum of independent random variables, the sum of independent lattice variables, or has the Markov binomial distribution. Apart from the general case, we investigate the case of symmetric random variables. Distribution of S is approximated by a compound Poisson distribution, by a second-order asymptotic expansion, and by a signed exponential measure. Lower bounds for the accuracy of approximations in uniform metric are established. __________ Translated from Lietuvos Matematikos Rinkinys, Vol. 45, No. 4, pp. 501–524, October–December, 2005.     

On the numerical solution of a minimax control problem with a positional functional

The probabilistic analysis of an approximation algorithm for the minimum-weight m-peripatetic salesman problem with different weight functions of their routes (Hamiltonian cycles) is presented. The time complexity of the algorithm is O(mn ²). It is assumed that the elements of the distance matrix are independent equally distributed random variables with values in an upper unbounded domain [a _n , ∞), where a _n > 0. The analysis is carried out for the example of truncated normal and exponential distributions. Estimates for the relative error and failure probability, as well as conditions for the asymptotic exactness of the algorithm, are found.     

A note on the sum of uniform random variables

An inductive procedure is used to obtain distributions and probability densities for the sum S_n of independent, non-equally uniform random variables. Some known results are then shown to follow immediately as special cases. Under the assumption of equally uniform random variables some new formulas are obtained for probabilities and means related to S_n. Finally, some new recursive formulas involving distributions are derived.     

Probabilistic analysis of an approximation algorithm for the traveling salesman problem on unbounded above instances

The probabilistic analysis of a modification of the approximation algorithm “Nearest City” is presented for the traveling salesman minimization problem. The case is considered when the entries of the distance matrix are some independent identically distributed random variables with the values in the range [a _n ,∞), a _n > 0, that are unbounded above and have a truncated normal or exponential distribution. We obtain the estimates of relative errors, the failure probabilities, and also the conditions of asymptotic optimality of the algorithm. The modification of the algorithm allows us to perform analysis so that the obtained results are true for the traveling salesman problems in the cases of both directed and undirected graphs.     

Inequalities in probability theory and turán-type problems for graphs with colored vertices

The “best” inequalities of type P{(ζ, η)? E} ≧f(P{η? D₁}P{η?Dm}) for independent and identically distributed random elements ζ and η can be reduced to Turán-type problems for graphs with colored vertices. In the present work we describe a finite algorithm for obtaining the asymptotical solution for an arbitrary problem of such type. In the case of two colors we obtain the final form of asymptotic solution without using the algorithm.     

A fuzzy bootstrap test for the mean with <Emphasis Type="Italic">D</Emphasis><Subscript><Emphasis Type="Italic">p,q</Emphasis></Subscript>-distance

In this paper, we consider the problem of testing a simple hypothesis about the mean of a fuzzy random variable. For this purpose, we take a distance between the sample mean and the mean in the null hypothesis as a test statistic. An asymptotic test about the fuzzy mean is obtained by using a central limit theorem. The asymptotical distribution is ω ₂-distribution. The ω ₂-distribution is only known for special cases, thus we have considered random LR-fuzzy numbers. In the fuzzy concept, in addition to the existence of several versions of the central limit theorem, there is another practical disadvantage: The limit law is, in most cases, difficult to handle. Therefore, the central limit theorem for fuzzy random variable does not seem to be a very useful tool to make inferences on the mean of fuzzy random variable. Thus we use the bootstrap technique. Finally, by means of a simulation study, we show that the bootstrap method is a powerful tool in the statistical hypothesis testing about the mean of fuzzy random variables.     

Generalized mirror averaging and <Emphasis Type="Italic">D</Emphasis>-convex aggregation

We study the problem of aggregation of estimators. Given a collection of M different estimators, we construct a new estimator, called aggregate, which is nearly as good as the best linear combination over an l ₁-ball of ℝ^M of the initial estimators. The aggregate is obtained by a particular version of the mirror averaging algorithm. We show that our aggregation procedure statisfies sharp oracle inequalities under general assumptions. Then we apply these results to a new aggregation problem: D-convex aggregation. Finally we implement our procedure in a Gaussian regression model with random design and we prove its optimality in a minimax sense up to a logarithmic factor.      

Total variation asymptotics for independent process approximations of logarithmic multisets and selections

Many natural unlabeled combinatorial structures, such as random partitions of the integer n, or random monic polynomials over a finite field of degree n, or unlabeled mapping patterns on n points may be described as multisets. In the usual statistical language, a multiset is an unordered sample in which number of items is variable, but the sum is a fixed value n. For these structures, the process counting the number of components of various sizes is equal in distribution to a process of independent, but not identically distributed random variables, conditioned on the value of a weighted sum. By restricting to the first b coordinates, it is possible to compare the combinatorial process directly to the independent process, and to estimate the total variation distance d_b(n) between these distributions. For a broad class of examples similar to the Ewens sampling formula we give asymptotics for d_b(n) which are valid for b=o(n/log n). The polynomial and random mapping pattern examples are covered by this result, but not the example of partitions. Similar results for selections, which are multisets with no repeated parts, such as square free polynomials, are also derived. The proofs of these results use large deviations bounds and singularity analysis of generating functions. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 51–80, 1997     

The block sphericity test—exact and near‐exact distributions for the likelihood ratio statistic

Using a suitable decomposition of the null hypothesis of the sphericity test for several blocks of variables, into a sequence of conditionally independent null hypotheses, we show that it is possible to obtain the expressions for the likelihood ratio test statistic, for its hth null moment, and for the characteristic function of its logarithm. The exact distribution of the logarithm of the likelihood ratio test statistic is obtained in the form of a sum of a generalized integer gamma distribution with the sum of a given number of independent logbeta distributions, taking the form of a single generalized integer gamma distribution when each set of variables has two variables. The development of near‐exact distributions arises, from the previous decomposition of the null hypothesis and from the consequent‐induced factorization of the characteristic function, as a natural and practical way to approximate the exact distribution of the test statistic. A measure based on the exact and approximating characteristic functions, which gives an upper bound on the distance between the corresponding distribution functions, is used to assess the quality of the near‐exact distributions proposed and to compare them with an asymptotic approximation on the basis of Box's method. Copyright © 2011 John Wiley & Sons, Ltd.     

The queue length in an <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">G</Emphasis>/1 batch arrival retrial queue

An M/G/1 retrial queue with batch arrivals is studied. The queue length K _μ is decomposed into the sum of two independent random variables. One corresponds to the queue length K _∞ of a standard M/G/1 batch arrival queue, and another is compound-Poisson distributed. In the case of the distribution of the batch size being light-tailed, the tail asymptotics of K _μ are investigated through the relation between K _∞ and its service times.     

Entropy and<Emphasis Type="Italic">σ</Emphasis>-algebra equivalence of certain random walks on random sceneries

LetX=X ₀,X ₁,…be a stationary sequence of random variables defining a sequence space Σ with shift mapσ and let (T _t, Ω) be an ergodic flow. Then the endomorphismT _X(x, ω)=(σ(x),T _{x 0}(ω)) is known as a random walk on a random scenery. In [4], Heicklen, Hoffman and Rudolph proved that within the class of random walks on random sceneries whereX is an i.i.d. sequence of Bernoulli-(1/2, 1/2) random variables, the entropy ofT _t is an isomorphism invariant. This paper extends this result to a more general class of random walks, which proves the existence of an uncountable family of smooth maps on a single manifold, no two of which are measurably isomorphic. This research was sustained in part by fellowship support from the National Physical Science Consortium and the National Security Agency.     

On the random 2‐stage minimum spanning tree

It is known [A. M. Frieze, Discrete Appl Math 10 (1985), 47–56] that if the edge costs of the complete graph K_n are independent random variables, uniformly distributed between 0 and 1, then the expected cost of the minimum spanning tree is asymptotically equal to . Here we consider the following stochastic two‐stage version of this optimization problem. There are two sets of edge costs c_M: E → ? and c_T: E → ?, called Monday's prices and Tuesday's prices, respectively. For each edge e, both costs c_M(e) and c_T(e) are independent random variables, uniformly distributed in [0, 1]. The Monday costs are revealed first. The algorithm has to decide on Monday for each edge e whether to buy it at Monday's price c_M(e), or to wait until its Tuesday price c_T(e) appears. The set of edges X_M bought on Monday is then completed by the set of edges X_T bought on Tuesday to form a spanning tree. If both Monday's and Tuesday's prices were revealed simultaneously, then the optimal solution would have expected cost ζ(3)/2 + o(1). We show that, in the case of two‐stage optimization, the expected value of the optimal cost exceeds ζ(3)/2 by an absolute constant ε > 0. We also consider a threshold heuristic, where the algorithm buys on Monday only edges of cost less than α and completes them on Tuesday in an optimal way, and show that the optimal choice for α is α = 1/n with the expected cost ζ(3) ? 1/2 + o(1). The threshold heuristic is shown to be sub‐optimal. Finally we discuss the directed version of the problem, where the task is to construct a spanning out‐arborescence rooted at a fixed vertex r, and show, somewhat surprisingly, that in this case a simple variant of the threshold heuristic gives the asymptotically optimal value 1 ? 1/e + o(1). © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Saddlepoint approximation for moments of random variables

In this paper, we introduce a saddlepoint approximation method for higher-order moments like E(S − a)₊ ^m , a>0, where the random variable S in these expectations could be a single random variable as well as the average or sum of some i.i.d random variables, and a > 0 is a constant. Numerical results are given to show the accuracy of this approximation method.