Randomly Weighted Sums of Subexponential Random Variables with Application to Ruin Theory

Let {X _k , 1 k n} be n independent and real-valued random variables with common subexponential distribution function, and let {k, 1 k n} be other n random variables independent of {X _k , 1 k n} and satisfying a _k b for some 0 < a b < for all 1 k n. This paper proves that the asymptotic relations P (max_{1 m n k=1} ^m _k X _k > x) P (sum _k=1 ⁿ _k X _k > x) sum _k=1 ⁿ P ( _k X _k > x) hold as x . In doing so, no any assumption is made on the dependence structure of the sequence { _k , 1 k n}. An application to ruin theory is proposed.     

Triple Positive Solutions for Multipoint Conjugate Boundary Value Problems

For the nth order nonlinear differential equation y ⁽ⁿ⁾(t)=f(y(t)), t [0,1], satisfying the multipoint conjugate boundary conditions, y ^(j)(a_i) = 0,1 i k, 0 j n _i - 1, 0 =a ₁ < a ₂ < < a _k = 1, and _i=1 ^k n _i =n, where f: [0, ) is continuous, growth condtions are imposed on f which yield the existence of at least three solutions that belong to a cone.     

On convergence subsystems of orthonormal systems

It is proved that for any sequence {R _k} _k=1 of real numbers satisfyingR _kk (k1) andR _k=o(k log₂ k),k, there exists an orthonormal system {n _k(x)} _n=1 ,x (0;1), such that none of its subsystems {n _k(x)} _k=1 withn _kR_k (k1) is a convergence subsystem.     

Partitioning arrangements of lines II: Applications

In this paper we present efficient deterministic algorithms for various problems involving lines or segments in the plane, using the partitioning algorithm described in a companion paper [A3]. These applications include: (i) anO(m ^2/3 n ^2/3 · log^2/3 n · log^/3 (m/n)+(m+n) logn) algorithm to compute all incidences betweenm points andn lines, where is a constant <3.33; (ii) anO(m ^2/3 n ^2/3 · log^5/3 n · log^/3 (m/n)+(m+n) logn) algorithm to computem faces in an arrangement ofn lines; (iii) anO(n ^4/3 log^(+2)/3 n) algorithm to count the number of intersections in a set ofn segments; (iv) anO(n ^4/3 log^{( + 2)/3} n) algorithm to count red-blue intersections between two sets of segments, and (v) anO(n ^3/2 log^/3 n) algorithm to compute spanning trees with low stabbing number for a set ofn points. We also present an algorithm that, given set ofn points in the plane, preprocesses it, in timeO(nm log^+1/2 n), into a data structure of sizeO(m) forn lognmn ², so that the number of points ofS lying inside a query triangle can be computed inO((n/m) log^3/2 n) time.Work on this paper has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant DCR-83-20085, and by grants from the Digital Equipment Corporation and the IBM Corporation. A preliminary version of this paper appears in theProceedings of the 5th ACM Symposium on Computational Geometry, 1989, pp. 11–22.     

A Comparison Theorem on Moment Inequalities Between Negatively Associated and Independent Random Variables

Let {X _i, 1in} be a negatively associated sequence, and let {X* _i , 1in} be a sequence of independent random variables such that X* _i and X _i have the same distribution for each i=1, 2,..., n. It is shown in this paper that Ef( ⁿ _i=1 X _i)Ef( ⁿ _i=1 X* _i ) for any convex function f on R ¹ and that Ef(max_1kn ⁿ _i=k X _i)Ef(max_1kn ^k _i=1 X* _i ) for any increasing convex function. Hence, most of the well-known inequalities, such as the Rosenthal maximal inequality and the Kolmogorov exponential inequality, remain true for negatively associated random variables. In particular, the comparison theorem on moment inequalities between negatively associated and independent random variables extends the Hoeffding inequality on the probability bounds for the sum of a random sample without replacement from a finite population.     

Random Lazy Random Walks on Arbitrary Finite Groups

This paper considers lazy random walks supported on a random subset of k elements of a finite group G with order n. If k=a log₂ n where a>1 is constant, then most such walks take no more than a multiple of log₂ n steps to get close to uniformly distributed on G. If k=log₂ n+f(n) where f(n) and f(n)/log₂ n0 as n, then most such walks take no more than a multiple of (log₂ n) ln(log₂ n) steps to get close to uniformly distributed. To get these results, this paper extends techniques of Erdös and Rényi and of Pak.     

Asymptotic behavior of the dwell time distribution for a random walk on a positive semi-axis

Let ₁, ₂, ... be a sequence of independent identically distributed random variables with zero means. We consider the functional _n = _k=o ⁿ (S _k ) where S₁=0, S_k= _i=1 ^k _i (k1) and(x)=1 for x0,(x) = 0 for x<0. It is readily seen that _n is the time spent by the random walk S_n, n0, on the positive semi-axis after n steps. For the simplest walk the asymptotics of the distribution P (_n = k) for n and k, as well as for k = O(n) and k/n<1, was studied in [1]. In this paper we obtain the asymptotic expansions in powers of n^–1 of the probabilities P(h_n = nx) and P(nx_{1 n} nx₂) for 0<₁, x = k/n ₂<1, 0<₁x₁2₂<1.Translated from Matematicheskie Zametki, Vol. 15, No. 4, pp. 613–620, April, 1974.The author wishes to thank B. A. Rogozin for valuable discussions in the course of his work.     

New applications of random sampling in computational geometry

This paper gives several new demonstrations of the usefulness of random sampling techniques in computational geometry. One new algorithm creates a search structure for arrangements of hyperplanes by sampling the hyperplanes and using information from the resulting arrangement to divide and conquer. This algorithm requiresO(s ^d+ ) expected preprocessing time to build a search structure for an arrangement ofs hyperplanes ind dimensions. The expectation, as with all expected times reported here, is with respect to the random behavior of the algorithm, and holds for any input. Given the data structure, and a query pointp, the cell of the arrangement containingp can be found inO(logs) worst-case time. (The bound holds for any fixed >0, with the constant factors dependent ond and .) Using point-plane duality, the algorithm may be used for answering halfspace range queries. Another algorithm finds random samples of simplices to determine the separation distance of two polytopes. The algorithm uses expectedO(n ^[d/2]) time, wheren is the total number of vertices of the two polytopes. This matches previous results [10] for the cased = 3 and extends them. Another algorithm samples points in the plane to determine their orderk Voronoi diagram, and requires expectedO(s ¹⁺ k) time fors points. (It is assumed that no four of the points are cocircular.) This sharpens the boundO(sk ² logs) for Lee's algorithm [21], andO(s ² logs+k(s–k) log² s) for Chazelle and Edelsbrunner's algorithm [4]. Finally, random sampling is used to show that any set ofs points inE ³ hasO(sk ² log⁸ s/(log logs)⁶) distinctj-sets withjk. (ForS E ^d , a setS S with |S| =j is aj-set ofS if there is a half-spaceh ⁺ withS =S h ⁺.) This sharpens with respect tok the previous boundO(sk ⁵) [5]. The proof of the bound given here is an instance of a probabilistic method [15].A preliminary version of this paper appeared in theProceedings of the 18th Annual ACM Symposium on Theory of Computing, Berkeley, CA, 1986.     

Embeddings of graphs in euclidean spaces

The dimension of a graphG=(V, E) is the minimum numberd such that there exists a representation and a thresholdt such thatxy E iff . We prove that d(G)n–x(G) and wheren=|V| andx(G) is the chromatic number ofG; we present upper bounds for the dimension of graphs with a large girth and we show that the complement of a forest can be represented by unit vectors inR ⁶. We prove that d(G)1/15n for most graphs and that there are 3-regular graphs with d(G)c logn/log logn.     

A superfast algorithm for multi-dimensional Padé systems

For a vector ofk+1 matrix power series, a superfast algorithm is given for the computation of multi-dimensional Padé systems. The algorithm provides a method for obtaining matrix Padé, matrix Hermite Padé and matrix simultaneous Padé approximants. When the matrix power series is normal or perfect, the algorithm is shown to calculate multi-dimensional matrix Padé systems of type (n ₀,...,n _k ) inO(n · log²n) block-matrix operations, where n=n ₀+...+n _k . Whenk=1 and the power series is scalar, this is the same complexity as that of other superfast algorithms for computing Padé systems. Whenk>1, the fastest methods presently compute these matrix Padé approximants with a complexity ofO(n²). The algorithm succeeds also in the non-normal and non-perfect case, but with a possibility of an increase in the cost complexity.Supported in part by NSERC grant No. A8035.Partially supported by NSERC operating grant No. 6194.     

Probabilistic analysis of an algorithm for solving thek-dimensional all-nearest-neighbors problem by projection

A well-known simple heuristic algorithm for solving the all-nearest-neighbors problem in thek-dimensional Euclidean spaceE ^k ,k>1, projects the given point setS onto thex-axis. For each pointq S a nearest neighbor inS under anyL _p -metric (1 p ) is found by sweeping fromq into two opposite directions along thex-axis. If _q denotes the distance betweenq and its nearest neighbor inS the sweep process stops after all points in a vertical 2 _q -slice centered aroundq have been examined. We show that this algorithm solves the all-nearest-neighbors problem forn independent and uniformly distributed points in the unit cube [0,1] ^k in (n ^2–1/k ) expected time, while its worst-case performance is (n ²).     

Krasnosel'skii numbers for bounded finitely starlike sets inR d

For eachk andd, 1kd, definef(d, d)=d+1 andf(d, k)=2d if 1kd–1. The following results are established:Let be a uniformly bounded collection of compact, convex sets inR ^d . For a fixedk, 1kd, dim {MM in }k if and only if for some > 0, everyf(d, k) members of contain a commonk-dimensional set of measure (volume) at least.LetS be a bounded subset ofR ^d . Assume that for some fixedk, 1kd, there exists a countable family of (k–l)-flats {H _i :i1} inR ^d such that clS S {H_i i 1 } and for eachi1, (clS S) H _i has (k–1) dimensional measure zero. Every finite subset ofS sees viaS a set of positivek-dimensional measure if and only if for some>0, everyf(d,k) points ofS see viaS a set ofk-dimensional measure at least .The numbers off(d,d) andf(d, 1) above are best possible.Supported in part by NSF grant DMS-8705336.     

Primes in short intervals

Let (x) stand for the number of primes not exceedingx. In the present work it is shown that if 23/421,yx andx>x() then (x)–(x–y)>y/(100 logx). This implies for the difference between consecutive primes the inequalityp _n+1–p _n p _n ^23/42 .     

On elementary equivalence and isomorphism of clone segments

The principal application of a general theorem proved here shows that for any choice 1mnp of integers there exist metric spacesX andY such that the initialk-segments of their clones of continuous maps coincide exactly whenkm, are isomorphic exactly whenkn, and are elementarily equivalent exactly whenkp.Dedicated to Prof. László Fuchs on the occasion of his 70th birthday     

Sub-Ramsey numbers for arithmetic progressions

Letm 3 andk 1 be two given integers. Asub-k-coloring of [n] = {1, 2,...,n} is an assignment of colors to the numbers of [n] in which each color is used at mostk times. Call an arainbow set if no two of its elements have the same color. Thesub-k-Ramsey number sr(m, k) is defined as the minimumn such that every sub-k-coloring of [n] contains a rainbow arithmetic progression ofm terms. We prove that((k – 1)m ²/logmk) sr(m, k) O((k – 1)m ² logmk) asm , and apply the same method to improve a previously known upper bound for a problem concerning mappings from [n] to [n] without fixed points.Research supported in part by Allon Fellowship and by a Bat Sheva de-Rothschild grant.Research supported in part by the AKA Research Fund of the Hungarian Academy of Sciences, grant No. 1-3-86-264.     

Random Walks Crossing High Level Curved Boundaries

Let {S _n} be a random walk, generated by i.i.d. increments X _i which drifts weakly to in the sense that as n . Suppose k0, k1, and E|X ₁|^1\k = if k>1. Then we show that the probability that S. crosses the curve nan ^K before it crosses the curve n –an ^k tends to 1 as a . This intuitively plausible result is not true for k = 1, however, and for 1/2 <k<1, the converse results are not true in general, either. More general boundaries g(n) than g(n) = n ^k are also considered, and we also prove similar results for first passages out of regions like { (n, y): n1, |y| (a + n) ^k } as a .     

An explicit calculation of the mean of the perimeter of the convex hull of a plane random walk

If (X _n ) _n ⁼¹ is a sequence of i.i.d. random variables in the Euclidean plane such that we compute the mean of the perimeter of theconvex hull ofX ₁++X _k; 0kn}.     

Minimal Fine Limits for a Class of Potentials

We consider potentials G _k associated with the Weinstein equation with parameter k in , _j=1 ⁿ (² u/ x ² _j ) + (k/x _n ) ( u/ x _n ) = 0, on the upper half space in ⁿ . We show that if the representing measure satisfies the growth condition y _n /(1+|y|) ^n-k < , where max(k, 2 – n) < 1, then G _k has a minimal fine limit of 0 at every boundary point except for a subset of vanishing (n – 2 + ) dimensional Hausdorff measure. We also prove this exceptional set is best possible.     

∑II∑ threshold formulas

A II formula has the form, where eachL is either a variable or a negated variable. In this paper we study the computation of threshold functions by II formulas. By combining the proof of the Fredman-Komlós bound [5, 10] and a counting argument, we show that fork andn large andkn/2, every II formula computing the threshold functionT _k ⁿ has size at least exp . Fork andn large andkn ^2/3, we show that there exist II formulas for computingT _k ⁿ with size at most exp .     

Minimal Degree and (k, m)-Pancyclic Ordered Graphs

Given positive integers k m n, a graph G of order n is (k, m)-pancyclic ordered if for any set of k vertices of G and any integer r with m r n, there is a cycle of length r encountering the k vertices in a specified order. Minimum degree conditions that imply a graph of sufficiently large order n is (k, m)-pancylic ordered are proved. Examples showing that these constraints are best possible are also provided.