Some bounds on the coupon collector problem

This work addresses on the coupon collector problem and its generalization introduced by Flajolet, Gardy, and Thimonier. In our main results, we show a ratio limit theorem for the random time of the generalized coupon collector problem, and, further, we give the leading term and the geometric rate for the distribution of this random time, when the number of throws is large. For the classical coupon collector problem, we give a bound on the conditional second moment for the number of visits to the coupons, relying strongly on a result of Holst on extremal distributions. © 2004 Wiley Periodicals, Inc. Random Struct. Alg. 2004     

Lower bounds for the quadratic assignment problem

We investigate the classical Gilmore-Lawler lower bound for the quadratic assignment problem. We provide evidence of the difficulty of improving the Gilmore-Lawler bound and develop new bounds by means of optimal reduction schemes. Computational results are reported indicating that the new lower bounds have advantages over previous bounds and can be used in a branch-and-bound type algorithm for the quadratic assignment problem.     

Omnibus Sequences, Coupon Collection, and Missing Word Counts

In this paper, we study the properties of k-omnisequences of length n, defined to be strings of length n that contain all strings of smaller length k embedded as (not necessarily contiguous) subsequences. We start by proving an elementary result that relates our problem to the classical coupon collector problem. After a short survey of relevant results in coupon collection, we focus our attention on the number M of strings (or words) of length k that are not found as subsequences of an n string, showing that there is a gap between the probability threshold for the emergence of an omnisequence and the zero-infinity threshold for ${\mathbb E}(M)$ .     

Dynamization of order decomposable set problems

Order decomposable set problems are introduced as a general class of problems concerning sets of multidimensional objects. We give a method of structuring sets such that the answer to an order decomposable set problem can be maintained with low worst-case time bounds, while objects are inserted and deleted in the set. Examples include the maintenance of the two-dimensional Voronoi diagram of a set of points, and of the convex hull of a three-dimensional point set in linear time. We show that there is a strong connection between the general dynamization method given and the well-known technique of divide-and-conquer used for solving many problems concerning static sets of objects. Although the upper bounds obtained are low in order of magnitude, the results do not necessarily imply the existence of fast feasible update routines. Hence the results merely assess theoretical bounds for the various set problems considered.     

A fast approximation algorithm for solving the complete set packing problem

We study the complete set packing problem (CSPP) where the family of feasible subsets may include all possible combinations of objects. This setting arises in applications such as combinatorial auctions (for selecting optimal bids) and cooperative game theory (for finding optimal coalition structures). Although the set packing problem has been well-studied in the literature, where exact and approximation algorithms can solve very large instances with up to hundreds of objects and thousands of feasible subsets, these methods are not extendable to the CSPP since the number of feasible subsets is exponentially large. Formulating the CSPP as an MILP and solving it directly, using CPLEX for example, is impossible for problems with more than 20 objects. We propose a new mathematical formulation for the CSPP that directly leads to an efficient algorithm for finding feasible set packings (upper bounds). We also propose a new formulation for finding tighter lower bounds compared to LP relaxation and develop an efficient method for solving the corresponding large-scale MILP. We test the algorithm with the winner determination problem in spectrum auctions, the coalition structure generation problem in coalitional skill games, and a number of other simulated problems that appear in the literature.     

Decision making and card collecting

^** D.K.Smith{at}exeter.ac.uk Collecting a set of different, yet similar, items is a popularhobby. The "coupon collector's problem" is concerned with thenumber of items which must be obtained, one at a time, in orderto complete the set, assuming that the collector is samplingfrom an infinite population where each item has a known probabilityof being found. In recent years, manufacturers have chosen toproduce the items in sealed packets which contain more thanone item, and possibly items from more than one set. This paperconsiders the problem of collecting items in packets, and thedecision problem faced by a collector who is offered the chanceto buy several packets at a discount. Dynamic programming isused to determine when it is worthwhile to purchase in bulk,for various sets and packets, as a function of the discountrate. Finally, mention is made of the other player in the transaction,the card manufacturer, who is also a decision-maker.     

Primal-dual subgradient methods for convex problems

In this paper we present a new approach for constructing subgradient schemes for different types of nonsmooth problems with convex structure. Our methods are primal-dual since they are always able to generate a feasible approximation to the optimum of an appropriately formulated dual problem. Besides other advantages, this useful feature provides the methods with a reliable stopping criterion. The proposed schemes differ from the classical approaches (divergent series methods, mirror descent methods) by presence of two control sequences. The first sequence is responsible for aggregating the support functions in the dual space, and the second one establishes a dynamically updated scale between the primal and dual spaces. This additional flexibility allows to guarantee a boundedness of the sequence of primal test points even in the case of unbounded feasible set (however, we always assume the uniform boundedness of subgradients). We present the variants of subgradient schemes for nonsmooth convex minimization, minimax problems, saddle point problems, variational inequalities, and stochastic optimization. In all situations our methods are proved to be optimal from the view point of worst-case black-box lower complexity bounds.     

An error analysis of the tau method for a class of singularly perturbed problems for differential equations

By using classical results of Poincaré and Birkhoff we discuss the existence and uniqueness of solution for a class of singularly perturbed problems for differential equations. The Tau method formulation of Ortiz [6] is applied to the construction of approximate solutions of these problems. Sharp error bounds are deduced. These error bounds are applied to the discussions of a model problem, a simple one-dimensional analogue of Navier-Stokes equation, which has been considered recently by several authors (see [2], [3], [8], [10]). Numerical results for this problem [8] show that the Tau method leads to more accurate approximations than specially designed finite difference or finite element schemes.     

The Collector’s Brotherhood Problem using the Newman-Shepp symbolic method

Further computations are made on the traditional coupon collectors problem when the collector shares his harvest with his younger brothers. When the book of the p-th brother of the collector is completed, the books of the younger brothers have certain numbers of empty spots. On the average, how many? Several answers can be brought to that question.To Gian-Carlo Rota, in memoriam     

Semicircular limits on the free Poisson chaos: Counterexamples to a transfer principle

We establish a class of sufficient conditions ensuring that a sequence of multiple integrals with respect to a free Poisson measure converges to a semicircular limit. We use this result to construct a set of explicit counterexamples showing that the transfer principle between classical and free Brownian motions (recently proved by Kemp, Nourdin, Peccati and Speicher (2012)) does not extend to the framework of Poisson measures. Our counterexamples implicitly use kernels appearing in the classical theory of random geometric graphs. Several new results of independent interest are obtained as necessary steps in our analysis, in particular: (i) a multiplication formula for free Poisson multiple integrals, (ii) diagram formulae and spectral bounds for these objects, and (iii) a counterexample to the general universality of the Gaussian Wiener chaos in a classical setting.     

On CP, LP and other piecewise perturbation methods for the numerical solution of the Schr?dinger equation

The piecewise perturbation methods (PPM) have proven to be very efficient for the numerical solution of the linear time-independent Schr?dinger equation. The underlying idea is to replace the potential function piecewisely by simpler approximations and then to solve the approximating problem. The accuracy is improved by adding some perturbation corrections. Two types of approximating potentials were considered in the literature, that is piecewise constant and piecewise linear functions, giving rise to the so-called CP methods (CPM) and LP methods (LPM). Piecewise polynomials of higher degree have not been used since the approximating problem is not easy to integrate analytically. As suggested by Ixaru (Comput Phys Commun 177:897–907, 2007), this problem can be circumvented using another perturbative approach to construct an expression for the solution of the approximating problem. In this paper, we show that there is, however, no need to consider PPM based on higher-order polynomials, since these methods are equivalent to the CPM. Also, LPM is equivalent to CPM, although it was sometimes suggested in the literature that an LP method is more suited for problems with strongly varying potentials. We advocate that CP schemes can (and should) be used in all cases, since it forms the most straightforward way of devising PPM and there is no advantage in considering other piecewise polynomial perturbation methods.     

On CP,LP and other piecewise perturbation methods for the numerical solution of the Schrödinger equation

The piecewise perturbation methods (PPM) have proven to be very efficient for the numerical solution of the linear time-independent Schrödinger equation. The underlying idea is to replace the potential function piecewisely by simpler approximations and then to solve the approximating problem. The accuracy is improved by adding some perturbation corrections. Two types of approximating potentials were considered in the literature, that is piecewise constant and piecewise linear functions, giving rise to the so-called CP methods (CPM) and LP methods (LPM). Piecewise polynomials of higher degree have not been used since the approximating problem is not easy to integrate analytically. As suggested by Ixaru (Comput Phys Commun 177:897–907, 2007), this problem can be circumvented using another perturbative approach to construct an expression for the solution of the approximating problem. In this paper, we show that there is, however, no need to consider PPM based on higher-order polynomials, since these methods are equivalent to the CPM. Also, LPM is equivalent to CPM, although it was sometimes suggested in the literature that an LP method is more suited for problems with strongly varying potentials. We advocate that CP schemes can (and should) be used in all cases, since it forms the most straightforward way of devising PPM and there is no advantage in considering other piecewise polynomial perturbation methods.     

Guaranteed and computable bounds of the limit load for variational problems with linear growth energy functionals

The paper is concerned with guaranteed and computable bounds of the limit (or safety) load, which is one of the most important quantitative characteristics of mathematical models associated with linear growth functionals. We suggest a new method for getting such bounds and illustrate its performance. First, the main ideas are demonstrated with the paradigm of a simple variational problem with a linear growth functional defined on a set of scalar valued functions. Then, the method is extended to classical plasticity models governed by vonMises and Drucker-Prager yield laws. The efficiency of the proposed approach is confirmed by several numerical experiments.     

A generalized coupon collecting model as a parsimonious optimal stochastic assignment model

There is a given set of n boxes, numbered 1 thru n. Coupons are collected one at a time. Each coupon has a binary vector x ₁,…,x _n attached to it, with the interpretation being that the coupon is eligible to be put in box i if x _i =1,i=1…,n. After a coupon is collected, it is put in a box for which it is eligible. Assuming the successive coupon vectors are independent and identically distributed from a specified joint distribution, the initial problem of interest is to decide where to put successive coupons so as to stochastically minimize N, the number of coupons needed until all boxes have at least one coupon. When the coupon vector X ₁,…,X _n is a vector of independent random variables, we show, if P(X _i =1) is nondecreasing in i, that the policy π that always puts an arriving coupon in the smallest numbered empty box for which it is eligible is optimal. Efficient simulation procedures for estimating P _π (N>r) and E _π [N] are presented; and analytic bounds are determined in the independent case. We also consider the problem where rearrangements are allowed.     

Designs in Product Association Schemes

A number of important families of association schemes—such as the Hamming and Johnson schemes—enjoy the property that, in each member of the family, Delsarte t-designs can be characterised combinatorially as designs in a certain partially ordered set attached to the scheme. In this paper, we extend this characterisation to designs in a product association scheme each of whose components admits a characterisation of the above type. As a consequence of our main result, we immediately obtain linear programming bounds for a wide variety of combinatorial objects as well as bounds on the size and degree of such designs analogous to Delsarte's bounds for t-designs in Q-polynomial association schemes.     

Exact algorithms for the bin packing problem with fragile objects

We are given a set of objects, each characterized by a weight and a fragility, and a large number of uncapacitated bins. Our aim is to find the minimum number of bins needed to pack all objects, in such a way that in each bin the sum of the object weights is less than or equal to the smallest fragility of an object in the bin. The problem is known in the literature as the Bin Packing Problem with Fragile Objects, and appears in the telecommunication field, when one has to assign cellular calls to available channels by ensuring that the total noise in a channel does not exceed the noise acceptance limit of a call.We propose a branch-and-bound and several branch-and-price algorithms for the exact solution of the problem, and improve their performance by the use of lower bounds and tailored optimization techniques. In addition we also develop algorithms for the optimal solution of the related knapsack problem with fragile objects. We conduct an extensive computational evaluation on the benchmark set of instances, and show that the proposed algorithms perform very well.     

Error bounds for the clenshaw-curtis quadrature formulas

Davis' method is employed to obtain bounds on the errors of the Clenshaw-Curtis quadrature schemes based on practical as well as classical abscissas. Also, bounds are obtained on the error of the Gauss-Legendre cubature formula applied to analytic functions.     

Coupon Subset Collection Problem with Quotas

Methodology and Computing in Applied Probability - This paper studies the coupon subset collection problem with quotas, which is a variant of the classical coupon-collection problem. Specifically,...     

On Finite Markov Chain Imbedding and Its Applications

The finite Markov Chain Imbedding technique has been successfully applied in various fields for finding the exact or approximate distributions of runs and patterns under independent and identically distributed or Markov dependent trials. In this paper, we derive a new recursive equation for distribution of scan statistic using the finite Markov chain imbedding technique. We also address the problem of obtaining transition probabilities of the imbedded Markov chain by introducing a notion termed Double Finite Markov Chain Imbedding where transition probabilities are obtained by using the finite Markov chain imbedding technique again. Applications for random permutation model in chemistry and coupon collector’s problem are given to illustrate our idea.