Generalizations of Polya's urn Problem

We consider generalizations of the classical Polya urn problem: Given finitely many bins each containing one ball, suppose that additional balls arrive one at a time. For each new ball, with probability p, create a new bin and place the ball in that bin; with probability 1–p, place the ball in an existing bin, such that the probability that the ball is placed in a bin is proportional to $ m^\gamma $, where m is the number of balls in that bin. For p=0, the number of bins is fixed and finite, and the behavior of the process depends on whether is greater than, equal to, or less than 1. We survey the known results and give new proofs for all three cases. We then consider the case p>0. When =1, this is equivalent to the so-called preferential attachment scheme which leads to power law distribution for bin sizes. When >1, we prove that a single bin dominates, i.e., as the number of balls goes to infinity, the probability that any new ball either goes into that bin or creates a new bin converges to 1. When p > 0 and < 1, we show that under the assumption that certain limits exist, the fraction of bins having m balls shrinks exponentially as a function of m. We then discuss further generalizations and pose several open problems.AMS Subject Classification: 05D40, 60C05, 60G20, 68R10, 91C99.     

Coalescing times for IID random variables with applications to population biology

We consider a coalescing particle model where particles move in discrete time. At each time period, each remaining ball is independently put in one of n bins according to a probability distribution p = (p₁, …, p_n), and all balls put into the same bin merge into a single ball. Starting with k balls, we are interested in the properties of E[N( p , k)], the expected time until all balls merge into one. We derive both upper and lower bounds for E[N( p , k)], some asymptotic results, and show that P{N( p , k) > t}, and thus E[N( p , k)], is a Schur concave function of p . Applications to population biology are noted. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 155–166, 2003     

Randomized allocation processes

Many dynamic resource allocation and on‐line load balancing problems can be modeled by processes that sequentially allocate balls into bins. The balls arrive one by one and are to be placed into bins on‐line without using a centralized controller. If n balls are sequentially placed into n bins by placing each ball in a randomly chosen bin, then it is widely known that the maximum load in bins is ln n /ln ln n?(1+o(1)) with high probability. Azar, Broder, Karlin, and Upfal extended this scheme, so that each ball is placed sequentially into the least full of d randomly chosen bins. They showed that the maximum load of the bins reduces exponentially and is ln ln n/In d+Θ(1) with high probability, provided d<2. In this paper we investigate various extensions of these schemes that arise in applications in dynamic resource allocation and on‐line load balancing. Traditionally, the main aim of allocation processes is to place balls into bins to minimize the maximum load in bins. However, in many applications it is equally important to minimize the number of choices performed (the allocation time). We study adaptive allocation schemes that achieve optimal tradeoffs between the maximum load, the maximum allocation time, and the average allocation time. We also investigate allocation processes that may reallocate the balls. We provide a tight analysis of a natural class of processes that each time a ball is placed in one of d randomly chosen bins may move balls among these d bins arbitrarily. Finally, we provide a tight analysis of the maximum load of the off‐line process in which each ball may be placed into one of d randomly chosen bins. We apply this result to competitive analysis of on‐line load balancing processes. ©2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 297–331, 2001     

A Sharp Threshold for k‐Colorability

Let k be a fixed integer and f_k(n, p) denote the probability that the random graph G(n, p) is k‐colorable. We show that for k≥3, there exists d_k(n) such that for any ϵ>0, (1) As a result we conclude that for sufficiently large n the chromatic number of G(n, d/n) is concentrated in one value for all but a small fraction of d>1. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 63–70, 1999     

Balanced allocation on graphs: A random walk approach

We propose algorithms for allocating n sequential balls into n bins that are interconnected as a d‐regular n‐vertex graph G, where d ≥ 3 can be any integer. In general, the algorithms proceeds in n succeeding rounds. Let ? > 0 be an integer, which is given as an input to the algorithms. In each round, ball 1 ≤ t ≤ n picks a node of G uniformly at random and performs a nonbacktracking random walk of length ? from the chosen node and simultaneously collects the load information of a subset of the visited nodes. It then allocates itself to one of them with the minimum load (ties are broken uniformly at random). For graphs with sufficiently large girths, we obtain upper and lower bounds for the maximum number of balls at any bin after allocating all n balls in terms of ?, with high probability.     

Mappings of Finite Distortion of Polynomial Type

Suppose f:? ⁿ →? ⁿ is a mapping of K-bounded p-mean distortion for some p>n?1. We prove the equivalence of the following properties of f: the doubling condition for J(x,f) over big balls centered at the origin, the boundedness of the multiplicity function N(f,? ⁿ ), the polynomial type of f, and the polynomial growth condition for f.     

New Coins from Old, Smoothly

Given a (known) function f:[0,1]→(0,1), we consider the problem of simulating a coin with probability of heads f(p) by tossing a coin with unknown heads probability p, as well as a fair coin, N times each, where N may be random. The work of Keane and O’Brien (ACM Trans. Model. Comput. Simul. 4(2):213–219, 1994) implies that such a simulation scheme with the probability ℙ _p (N<∞) equal to 1 exists if and only if f is continuous. Nacu and Peres (Ann. Appl. Probab. 15(1A):93–115, 2005) proved that f is real analytic in an open set S⊂(0,1) if and only if such a simulation scheme exists with the probability ℙ _p (N>n) decaying exponentially in n for every p∈S. We prove that for α>0 noninteger, f is in the space C ^α [0,1] if and only if a simulation scheme as above exists with ℙ _p (N>n)≤C(Δ _n (p)) ^α , where \varDelta _n(x):=max{?{x(1-x)/n},1/n}\varDelta _{n}(x):=\max\{\sqrt{x(1-x)/n},1/n\}. The key to the proof is a new result in approximation theory: Let B⁺_n\mathcal{B}^{+}_{n} be the cone of univariate polynomials with nonnegative Bernstein coefficients of degree n. We show that a function f:[0,1]→(0,1) is in C ^α [0,1] if and only if f has a series representation ?_n=1^￥F_n\sum_{n=1}^{\infty}F_{n} with F_n ? B⁺_nF_{n}\in \mathcal{B}^{+}_{n} and ∑ _k>n F _k (x)≤C(Δ _n (x)) ^α for all x∈[0,1] and n≥1. We also provide a counterexample to a theorem stated without proof by Lorentz (Math. Ann. 151:239–251, 1963), who claimed that if some j_n ? B⁺_n\varphi_{n}\in\mathcal{B}^{+}_{n} satisfy |f(x)−φ _n (x)|≤C(Δ _n (x)) ^α for all x∈[0,1] and n≥1, then f∈C ^α [0,1].     

Scale‐free graphs of increasing degree

We study a scale‐free random graph process in which the number of edges added at each step increases. This differs from the standard model in which a fixed number, m, of edges are added at each step. Let f(t) be the number of edges added at step t. In the standard scale‐free model, f(t) = m constant, whereas in this paper we consider f(t) = [t^c],c > 0. Such a graph process, in which the number of edges grows non‐linearly with the number of vertices is said to have accelerating growth. We analyze both an undirected and a directed process. The power law of the degree sequence of these processes exhibits widely differing behavior. For the undirected process, the terminal vertex of each edge is chosen by preferential attachment based on vertex degree. When f(t) = m constant, this is the standard scale‐free model, and the power law of the degree sequence is 3. When f(t) = [t^c],c < 1, the degree sequence of the process exhibits a power law with parameter x = (3 ? c)/(1 ? c). As c → 0, x → 3, which gives a value of x = 3, as in standard scale‐free model. Thus no more slowly growing monotone function f(t) alters the power law of this model away from x = 3. When c = 1, so that f(t) = t, the expected degree of all vertices is t, the vertex degree is concentrated, and the degree sequence does not have a power law. For the directed process, the terminal vertex is chosen proportional to in‐degree plus an additive constant, to allow the selection of vertices of in‐degree zero. For this process when f(t) = m is constant, the power law of the degree sequence is x = 2 + 1/m. When f(t) = [t^c], c > 0, the power law becomes x = 1 + 1/(1 + c), which naturally extends the power law to [1,2]. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 38, 396–421, 2011     

Existence and uniqueness of periodic solutions for a class of nonlinear n ‐th order differential equations with delays

In this paper, we use the coincidence degree theory to establish new results on the existence and uniqueness of T ‐periodic solutions for a class of nonlinear n ‐th order differential equations with delays of the form x⁽ⁿ⁾(t) + f (x^{(n‐ 1)}(t)) + g (t, x (t ‐ τ (t))) = p (t).     

Sharp regularity results on second derivatives of solutions to the Monge‐Ampère equation with VMO type data

We establish interior estimates for L^p‐norms, Orlicz norms, and mean oscillation of second derivatives of solutions to the Monge‐Ampère equation det D²u = f(x) with zero boundary value, where f(x) is strictly positive, bounded, and satisfies a VMO‐type condition. These estimates develop the regularity theory of the Monge‐Ampère equation in VMO‐type spaces. Our Orlicz estimates also sharpen Caffarelli's celebrated W^{2, p}‐estimates. © 2008 Wiley Periodicals, Inc.     

Limiting size index distributions for ball-bin models with Zipf-type frequencies

We consider a random ball-bin model where balls are thrown randomly and sequentially into a set of bins. The frequency of choices of bins follows the Zipf-type (power-law) distribution; that is, the probability with which a ball enters the ith most popular bin is asymptotically proportional to 1/i ^α , α > 0. In this model, we derive the limiting size index distributions to which the empirical distributions of size indices converge almost surely, where the size index of degree k at time t represents the number of bins containing exactly k balls at t. While earlier studies have only treated the case where the power α of the Zipf-type distribution is greater than unity, we here consider the case of α ≤ 1 as well as α > 1. We first investigate the limiting size index distributions for the independent throw models and then extend the derived results to a case where bins are chosen dependently. Simulation experiments demonstrate not only that our analysis is valid but also that the derived limiting distributions well approximate the empirical size index distributions in a relatively short period.     

Unboundedness of the large solutions of some asymmetric oscillators at resonance

In this paper, we consider the unboundedness of solutions of the following differential equation (φ_p(x′))′ + (p ? 1)[αφ_p(x⁺) ? βφ_p(x^?)] = f(x)x′ + g(x) + h(x) + e(t) where φ_p(u) = |u|^{p? 2} u, p > 1, x^± = max {±x, 0}, α and β are positive constants satisfying with m, n ∈ N and (m, n) = 1, f and g are continuous and bounded functions such that lim_x→±∞g(x) ? g(±∞) exists and h has a sublinear primitive, e(t) is 2π_p‐periodic and continuous. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Greedy colorings of uniform hypergraphs

We give a very short proof of an Erd?s conjecture that the number of edges in a non‐2‐colorable n‐uniform hypergraph is at least f(n)2ⁿ, where f(n) goes to infinity. Originally it was solved by József Beck in 1977, showing that f(n) at least clog n. With an ingenious recoloring idea he later proved that f(n) ≥ cn^1/3+o(1). Here we prove a weaker bound on f(n), namely f(n) ≥ cn^1/4. Instead of recoloring a random coloring, we take the ground set in random order and use a greedy algorithm to color. The same technique works for getting bounds on k‐colorability. It is also possible to combine this idea with the Lovász Local Lemma, reproving some known results for sparse hypergraphs (e.g., the n‐uniform, n‐regular hypergraphs are 2‐colorable if n ≥ 8). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

The scaling window of the 2‐SAT transition

We consider the random 2‐satisfiability (2‐SAT) problem, in which each instance is a formula that is the conjunction of m clauses of the form x∨y, chosen uniformly at random from among all 2‐clauses on n Boolean variables and their negations. As m and n tend to infinity in the ratio m/n→α, the problem is known to have a phase transition at α_c=1, below which the probability that the formula is satisfiable tends to one and above which it tends to zero. We determine the finite‐size scaling about this transition, namely the scaling of the maximal window W(n, δ)=(α_?(n,δ), α₊(n,δ)) such that the probability of satisfiability is greater than 1?δ for α<α_? and is less than δ for α>α₊. We show that W(n,δ)=(1?Θ(n^?1/3), 1+Θ(n^?1/3)), where the constants implicit in Θ depend on δ. We also determine the rates at which the probability of satisfiability approaches one and zero at the boundaries of the window. Namely, for m=(1+ε)n, where ε may depend on n as long as |ε| is sufficiently small and |ε|n^1/3 is sufficiently large, we show that the probability of satisfiability decays like exp(?Θ(nε³)) above the window, and goes to one like 1?Θ(n^?1|ε|^?3 below the window. We prove these results by defining an order parameter for the transition and establishing its scaling behavior in n both inside and outside the window. Using this order parameter, we prove that the 2‐SAT phase transition is continuous with an order parameter critical exponent of 1. We also determine the values of two other critical exponents, showing that the exponents of 2‐SAT are identical to those of the random graph. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 201–256 2001     

Convergence of Modified Lagrange Interpolation toLp-Functions Based on the Zeros of Orthonormal Polynomials with Freud Weights

We consider the “Freud weight”W²_Q(x)=exp(−Q(x)). let 1<p<∞, and letL*_n(f) be a modified Lagrange interpolation polynomial to a measurable functionf∈{f; ess sup_x∈ |f(x)| W_Q(x)(1+|x|)^α<∞},α>0. Then we have lim_n→∞ ∫^∞_−∞ [|f(x)−L*_n(f; x)| W_Q(x)(1+|x|)^−Δ]^p dx=0, whereΔis a constant depending onpandα.     

Weighted Weak Behaviour of Fourier-Jacobi Series

Let w(x) = (1 - x)^α (1 + x)^β be a Jacobi weight on the interval [-1, 1] and 1 < p < ∞. If either α > ?1/2 or β > ?1/2 and p is an endpoint of the interval of mean convergence of the associated Fourier-Jacobi series, we show that the partial sum operators S_n are uniformly bounded from L^p,1 to L^p,∞, thus extending a previous result for the case that both α, β > ?1/2. For α, β > ?1/2, we study the weak and restricted weak (p, p)-type of the weighted operators f→uS_n(u^?1f), where u is also Jacobi weight.     

On a dual version of the one-dimensional bin packing problem

The NP-hard problem of packing items from a given set into bins so as to maximize the number of bins used, subject to the constraint that each bin be filled to at least a given threshold, is considered. Approximation algorithms are presented that provide guarantees of , , and the optimal number, at running time costs of O(n), O(nlogn), and O(nlog²n), respectively, and the average case behavior of these algorithms is explored via empirical tests on randomly generated sets of items.     

Solutions with boundary‐layers and spike‐layers to singularly perturbed quasilinear Dirichlet problems

The structure of nontrivial nonnegative solutions to singularly perturbed quasilinear Dirichlet problems of the form –?Δ_pu = f(u) in Ω, u = 0 on ?Ω, Ω ? R ^N a bounded smooth domain, is studied as ? → 0⁺, for a class of nonlinearities f(u) satisfying f(0) = f(z₁) = f(z₂) = 0 with 0 < z₁ < z₂, f < 0 in (0, z₁), f > 0 in (z₁, z₂) and f(u)/u^p–1 = –∞. It is shown that there are many nontrivial nonnegative solutions with spike‐layers. Moreover, the measure of each spike‐layer is estimated as ? → 0⁺. These results are applied to the study of the structure of positive solutions of the same problems with f changing sign many times in (0,∞). Uniqueness of a solution with a boundary‐layer and many positive intermediate solutions with spike‐layers are obtained for ? sufficiently small. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Simultaneous approximation of periodic continuous functions and their derivatives

LetR _n(f; x) be a trigonometric polynomial of ordern satisfying Eqs. (1.1) and (1.2). The object of this note is to obtain sufficient conditions in order that thepth derivative ofR _n(f, x) converges uniformly tof ^(p)(x) on the real line. The sufficient conditions turns out to bef ^(p)(x) ∈ Lipα, α>0 with the restrictions of Eq. (1.3). The author acknowledges financial support for this work from the University of Alberta, Post Doctoral Fellowship 1966–67. The author is extremely grateful to the referee for pointing out some valuable results and suggestions.     

Centres of Convex Sets inLMetrics

It is shown that for each convex bodyARⁿthere exists a naturally defined family _AC(Sⁿ⁻¹) such that for everyg _A, and every convex functionf: R→Rthe mappingy∫_Sⁿ⁻¹ f(g(x)−y, x) dσ(x) has a minimizer which belongs toA. As an application, approximation of convex bodies by balls with respect toL^pmetrics is discussed.