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.     

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.     

D λ -cycles in 3-cyclable graphs

Letk and be positive integers, andG a 2-connected graph of ordern with minimum degree and independence number. A cycleC ofG is called aD -cycle if every component ofG – V(C) has order smaller than. The graphG isk-cyclable if anyk vertices ofG lie on a common cycle. A previous result of the author is that if k 2, G isk-connected and every connected subgraphH ofG of order has at leastn +k ² + 1/k + 1 – vertices outsideH adjacent to at least one vertex ofH, thenG contains aD -cycle. Here it is conjectured that k-connected can be replaced by k-cyclable, and this is proved fork = 3. As a consequence it is shown that ifn 4 – 6, or ifG is triangle-free andn 8 – 10, thenG contains aD ₃-cycle orG , where denotes a well-known class of nonhamiltonian graphs of connectivity 2. As an analogue of a result of Nash-Williams it follows that ifn 4 – 6 and – 1, thenG is hamiltonian orG . The results are all best possible and compare favorably with recent results on hamiltonicity of graphs which are close to claw-free.     

Generalized sentinels defined via least squares

We address the problem of monitoring a linear functional (c, x)_Eof an unknown vectorx of a Hilbert spaceE, the available data being the observationz, in a Hilbert spaceF, of a vectorAx depending linearly onx through some known operatorA(E; F). WhenE=E ₁×E ₂,c=(c ₁ 0), andA is injective and defined through the solution of a partial differential equation, Lions ([6]–[8]) introduced sentinelssF such that (s, Ax)_Fis sensitive to x₁ E ₁ but insensitive to x₂ E₂. In this paper we prove the existence, in the general case, of (i) a generalized sentinel (s, ) ×E, where F withF dense in 80, such that for anya priori guess x₀ ofx, we have s, Ax + (, x₀)_E=(c, x)_E, where x is the least-squares estimate ofx closest tox ₀, and (ii) a family of regularized sentinels (s _n , _n ) F×E which converge to (s, ). Generalized sentinels unify the least-squares approach (by construction !) and the sentinel approach (whenA is injective), and provide a general framework for the construction of sentinels with special sensitivity in the sense of Lions [8]).     

Set systems with no union of cardinality 0 modulom

Letq be a prime power. It is shown that for any hypergraph = {F ₁,...,F _d(q–1)+1} whose maximal degree isd, there exists Ø ₀ , such that 0 (modq).     

Decomposition of large uniform hypergraphs

We determine a minimum cardinality family _{n, k} (resp. _{n, k} ) ofn-uniform,k-edge hypergraphs satisfying the following property: all, except for finitely many,n-uniform hypergraphs satisfying the divisibility condition have an _{n, k} -decomposition (resp. vertex _{n, k} -decomposition).     

On generalized gamma functions related to the Laurent coefficients of the Riemann zeta function

Summary We study a class of generalized gamma functions _k (z) which relate to the generalized Euler constants _k (basically the Laurent coefficients of(s)) as (z) does to the Euler constant. A new series expansion for _k is derived, and the constant term in the asymptotic expansion for log _k (z) is studied in detail. These and related constants are numerically computed for 1 k 15.     

A Second Descent Problem for Quadratic Forms

Let F be a field of characteristic different from 2. We discuss a new descent problem for quadratic forms, complementing the one studied by Kahn and Laghribi. More precisely, we conjecture that for any quadratic form q over F and any Im(W(F) W(F(q))), there exists a quadratic form W(F) such that dim 2 dim and _F(q), where F(q) is the function field of the projective quadric defined by q = 0. We prove this conjecture for dim 3 and any q, and get partial results for dim {4, 5,6}. We also give other related results.     

On the kernel of intersecting families

Let be at-wises-intersecting family, i.e.,|F ₁ ... F _t | s holds for everyt members of. Then there exists a setY such that|F ₁ ... F _t Y| s still holds for everyF ₁,...,F _t . Here exponential lower and upper bounds are proven for the possible sizes ofY. This work was done while the authors visited Bell Communication Research, NJ 07960, and AT&T Bell Laboratories, Murray Hill, NJ 07974, USA, respectively.Research supported in part by Allon Fellowship and by Bat Sheva de Rothschild Foundation.     

On spaces of Baire I functions over K-analytic spaces

Suppose that is a relatively countably compact subset of B₁(X), the space of Baire I functions over a K-analytic space X equipped with the pointwise convergence topology. It is proved that (1) the closure of is a strongly countably compact Frechét-Urysohn space; (2) if is ₁ -compact, is a bicompactum; (3) if X is a paracompact space, the closure of is a bicompactum.Translated from Matematicheskie Zametki, Vol. 52, No. 3, pp. 108–116, September, 1992.     

An intersection property for starshaped sets in the plane

Let be a family of compact starshaped sets in the plane. If every three and every two members of have a union which is connected and simply connected, then {F:F in } is simply connected and nonempty. Of course, if every three and every two members of have a starshaped union, the same result holds.Supported in part by NSF grants DMS-8705336, DMS-8908717 and by a Senior Faculty Summer Research Fellowship, Research Council, University of Oklahoma.     

A bijective proof of Kadell's conjecture on plane partitions

We give a weight-preserving bijection from _{r, µ} ^m to, where _{r, µ} ^m is the set of all plane partitions whose entries are m and whose entries below ther-th row form a column strict plane partition of type, and _µ ^m the set of all column strict plane partitions of type whose entries are m, and the set of all plane partitions with at mostr rows, whose entries are m. This confirms a conjecture of Kadell.     

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.     

New lower semicontinuity results for polyconvex integrals

Summary We study integral functionals of the formF(u, )= f(u)dx, defined foru C¹(;R ^k), R ⁿ . The functionf is assumed to be polyconvex and to satisfy the inequalityf(A) c₀¦(A)¦ for a suitable constant c₀ > 0, where (A) is then-vector whose components are the determinants of all minors of thek×n matrixA. We prove thatF is lower semicontinuous onC ¹(;R ^k) with respect to the strong topology ofL ¹(;R ^k). Then we consider the relaxed functional , defined as the greatest lower semicontinuous functional onL ¹(;R ^k ) which is less than or equal toF on C¹(;R ^k). For everyu BV(;R ^k) we prove that (u,) f(u)dx+c₀¦D^su¦(), whereDu=u dx+D^su is the Lebesgue decomposition of the Radon measureDu. Moreover, under suitable growth conditions onf, we show that (u,)= f(u)dx for everyu W^1,p(;R ^k), withp min{n,k}. We prove also that the functional (u, ) can not be represented by an inte- gral for an arbitrary functionu BV_loc(R ⁿ;R ^k). In fact, two examples show that, in general, the set function (u, ) is not subadditive whenu BV_loc(R ⁿ;R ^k), even ifu W _loc ^1,p (R ⁿ;R ^k) for everyp < min{n,k}. Finally, we examine in detail the properties of the functionsu BV(;R ^k) such that (u, )= f(u)dx, particularly in the model casef(A)=¦(A)¦.     

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.     

Existence of compatible families of proper regular conditional probabilities

Summary Let (, , ) be a perfect probability space with countably generated, and let IB be a family of sub--fields of . Under a countability condition on the family IB, I show that there exists a family {}_IB of regular conditional probabilities which are everywhere compatible. Under a more stringent condition on IB, I show that the can furthermore be chosen to be everywhere proper. It follows that in the Dobrushin-Lanford-Ruelle formulation of the statistical mechanics of classical lattice systems, every (perfect) probability measure is a Gibbs measure for some specification.Research supported in part by NSF PHY-78-23952NSF Predoctoral Fellow (1976–79) and Danforth Fellow (1979–81).     

Flowchart machines

Let denote a conventional flowchart. Any algorithm can be represented by a flowchart. If action nodes in call then is a recursive flowchart. We show how to decompose arbitrary non-self-modifying programs into structure and atomic parts. We specifically give the synthesis procedure for a controller . can serve as the only sequencer in an execution of . If is recursive then is a pushdown machine, otherwise is a finite state machine. The next-state functionf and the output functiong of represent respectively all of the structure-, i.e. the programmer-oriented-, and all of the atomic-, i.e. the data-oriented-, parts of .f defines the flow or pattern of computations andg the actual transformations or operations on data. Thus we construct and analyze programs by constructing and analyzing their sequencers .     

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.     

Regular (2, 2)-systems

Let (E,I) be an independence system over the finite setE = {e ₁, ,e _n }, whose elements are orderede ₁ e _n . (E,I) is called regular, if the independence of {e _l , ,e _{l k} },l ₁ < <l _k , implies that of {e _{m l} , ,e _{m k} }, wherem _l < ··· <m _k andl ₁ m ₁, ,l _k m _k . (E,I) is called a 2-system, if for anyI I,e E I the setI {e } contains at most 2 distinct circuitsC, C I and the number 2 is minimal with respect to this property. If, in addition, for any two independent setsI andJ the family (C J, C C (J, I)), whereC(J, I) denotes {C C:e J I C {e}}, can be partitioned into 2 subfamilies each of which possesses a transversal, then (E,I) is called a (2, 2)-system. In this paper we characterize regular 2-systems and we show that the classes of regular 2-systems resp. regular (2, 2)-systems are identical.     

Cutting disjoint disks by straight lines

Fork>0 letf(k) denote the minimum integerf such that, for any family ofk pairwise disjoint congruent disks in the plane, there is a direction such that any line having direction intersects at mostf of the disks. We determine the exact asymptotic behavior off(k) by proving that there are two positive constantsd ₁,d ₂ such thatd ₁k logkf(k)d ₂k logk. This result has been motivated by problems dealing with the separation of convex sets by straight lines.The work of the first author was supported in part by the Allon Fellowship, by the Bat Sheva de Rothschild Foundation, by the Fund for Basic Research administered by the Israel Academy of Sciences, and by the Center for Absorbtion in Science. Work by the second author was supported by the Technion V. P.R. Fund, Grant No. 100-0679. The third author's work was supported by the Natural Sciences and Engineering Research Council, Canada, and the joint project Combinatorial Optimization of the Natural Science and Engineering Research Council (NSERC), Canada, and the German Research Association (Deutsche Forschungsgemeinschaft, SFB 303).