k-regular factors and semi-k-regular factors in bipartite graphs

LetG be a graph, andk1 an integer. LetU be a subset ofV(G), and letF be a spanning subgraph ofG such that deg _F (x)=k for allx V(G)–U. If deg _F (x)k for allxU, thenF is called an upper semi-k-regular factor with defect setU, and if deg _F (x)k for allxU, thenF is called a lower semi-k-regular factor with defect setU. Now letG=(X, Y;E(G)) be a bipartite graph with bipartition (X,Y) such that X=Yk+2. We prove the following two results.(1) Suppose that for each subsetU ₁X such that U ₁=max{k+1, X+1/2},G has an upper semi-k-regular factor with defect setU ₁Y, and for each subsetU ₂Y such that U ₂=max{k+1, X+1/2},G has an upper semi-k-regular factor with defect setXU ₂. ThenG has ak-factor.(2) Suppose that for each subsetU ₁X such that U ₁=X–1/k+1,G has a lower semi-k-regular factor with defect setU ₁Y, and for each subsetU ₂Y such that U ₂=X–1/k+1,G has a lower semi-k-regular factor with defect setXU ₂. ThenG has ak-factor.     

A bounded law of the iterated logarithm for Hilbert space valued martingales and its application to U-statistics

Summary A bounded law of the iterated logarithm for martingales with values in a separable Hilbert space H is proved. It is then applied to prove invariance principles for U-statistics for independent identically distributed (-valued) random variables {X _j , j1} and a kernel h: ^m H, m2, which is degenerate for the common distribution function of X _j , j1. This extends to general m results of an earlier paper on this subject and even gives new results in the case H=.     

Exchangeable random variables and the subsequence principle

Summary Call a sequence {X _n } of r.v.'s -exchangeable if on the same probability space there exists an exchangeable sequence {Y _n } such thatP(|X _n –Y _n |) for alln. We prove that any tight sequence {X _n } defined on a rich enough probability space contains -exchangeable subsequences for every >0. The distribution of the approximating exchangeable sequences is also described in terms of {X _n }. Our results give a convenient way to prove limit theorems for subsequences of general r.v. sequences. In particular, they provide a simplified way to prove the subsequence theorems of Aldous [1] and lead also to various extensions.     

Extension of the Zorn lemma to general nontransitive binary relations

Let be an irreflexive (strict) binary relation on a nonempty setX. Denote the completion of by , i.e.,yx ifxy does not hold. An elementx ^* X is said to be a maximal element of onX ifx ^* x, xX. In this paper, an extension of the Zorn lemma to general nontrasitive binary relations (may lack antisymmetry) is established and is applied to prove existence of maximal elements for general nontrasitive (reflexive or irreflexive) binary relations on nonempty sets without assuming any topological conditions or linear structures. A necessary and sufficient condition has been also established to completely characterize the existence of maximal elements for general irreflexive nontrasitive binary relations. This is the first such result available in the literature to the best of our knowledge. Many recent known existence sults in the literature for vector optimization are shown to be special cases of our result.This work was supported in part by AFSOR Grant 91-0097.The author is grateful to the referees and Professor P. L. Yu for their comments and suggestions that led to this improved paper.     

On the Skitovich–Darmois Theorem for Compact Abelian Groups

Let X be a separable compact Abelian group, Aut(X) the group of topological automorphisms of X, f _n: XX a homomorphism f _n(x)=nx, and X ⁽ⁿ⁾=Im f _n. Denote by I(X) the set of idempotent distributions on X and by (X) the set of Gaussian distributions on X. Consider linear statistics L ₁= ₁( ₁)+ ₂( ₂) and L ₂= ₁( ₁)+ ₂( ₂), where _j are independent random variables taking on values in X and with distributions _j, and _j, _jAut(X). The following results are obtained. Let X be a totally disconnected group. Then the independence of L ₁ and L ₂ implies that ₁, ₂I(X) if and only if X possesses the property: for each prime p the factor-group X/X ^(p) is finite. If X is connected, then there exist independent random variables _j taking on values in X and with distributions _j, and _j, _jAut(X) such that L ₁ and L ₂ are independent, whereas ₁, ₂(X) * I(X).     

Continuity of the eigenvalues of self-adjoint operators with respect to the strong operator topology

Let T_n, T, and S be self-adjoint operators such that T_n converges to T in the sense of strong resolvent convergence. If S is bounded from below, _e(S) (–,O) = Ø, and T_n S for all n, then the negative eigenvalues of T_n converge to the negative eigenvalues of T. The corresponding eigenfunctions converge in norm. This generalizes a result due to T. Kato, where T_n T is assumed, and a recent result of the author for the case T_n T_n+1.     

Monotonie bei den Quadraturverfahren von Gauß und Newton-Cotes

Summary LetQ _n be the quadrature rule of Gauss or Newton-Cotes withn abscissas. It is proven here, thatf ⁽²ⁿ⁾0 impliesQ _n ^G [f]Q _m ^G [f] (for allm>n) andQ _2n–1 ^NC [f]Q _2n ^NC [f]Q _2n+1 ^NC [f]. It follows that the sequenceQ _n[f] (n=1, 2, ...) is monotone, if all derivatives off are positive.

     

Stochastically monotone Markov Chains

Summary A real-valued discrete time Markov Chain {X _n} is defined to be stochastically monotone when its one-step transition probability function pr {X _n+1y¦ X _n=x} is non-increasing in x for every fixed y. This class of Markov Chains arises in a natural way when it is sought to bound (stochastically speaking) the process {X _n} by means of a smaller or larger process with the same transition probabilities; the class includes many simple models of applied probability theory. Further, a given stochastically monotone Markov Chain can readily be bounded by another chain {Y _n}, with possibly different transition probabilities and not necessarily stochastically monotone, and this is of particular value when the latter process leads to simpler algebraic manipulations. A stationary stochastically monotone Markov Chain {X _n} has cov(f(X ₀), f(X _n)) cov(f(X ₀), f(X _n+1))0 (n =1, 2,...) for any monotonic function f(·). The paper also investigates the definition of stochastic monotonicity on a more general state space, and the properties of integer-valued stochastically monotone Markov Chains.     

Birth times,death times and time substitutions in Markov chains

Summary Given a Markov chain (X _n ) _n0, random times are studied which are birth times or death times in the sense that the post- and pre- processes are independent given the present (X _–1, X ) at time and the conditional post- process (birth times) or the conditional pre- process (death times) is again Markovian. The main result for birth times characterizes all time substitutions through homogeneous random sets with the property that all points in the set are birth times. The main result for death times is the dual of this and appears as the birth time theorem with the direction of time reversed.Part of this work was done while the author was visiting the Department of Mathematics, University of California at San DiegoThe support of The Danish Natural Science Research Council is gratefully acknowledged     

Majorizing provably recursive functions in fragments of PA

We prove an interpretation or majorization theorem for PA _n (n1), the fragment of Peano Arithmetic based on _n ⁰ -induction. The theorem relies upon an asymmetric treatment of quantifiers, inspired by Girard's asymmetric rules for ID₁, and it implies the well-known classification of provably recursive functions of PA _n .A first version of this paper was prepared while the author held a CNR-Nato Junior Fellowship at Ludwig-Maximilians-Universität München in Winter-Semester 1982–83. The present version differs from the previous one because of some simplifications and corrections; Section 4 has been rewritten. We gratefully acknowledge the criticism of the referee.     

On a problem of Erdös and Alladi

We give an estimate for the quantity {f(n):nx, p(n)y}, wherep(n) denotes the greatest prime factor ofn andf belongs to a certain class of multiplicative functions. As an application, we show that for the Moebius function, ({(n):nx, p(n)y}) ({1:nx, p(n)y})^–1 tends to zero, asx, uniformly iny2, and thus settle a conjecture of Erdös.Supported by a grant from the Deutsche Forschungsgesellschaft.     

The Berry-Esseén theorem for strongly mixing Harris recurrent Markov chains

Summary Let ₀, ₁,... be a stationary Harris recurrent Markov chain with state space (E,), and let f E IR, X _i=f(_i). It is known that the sequence X _i, i0, is strongly mixing, i.e. (n)>0 where (n) are the strong (or Rosenblatt) mixing coefficients. If (n) decreases at a sufficiently fast rate and f is suitable, then a central limit holds for the partial sums . The present paper gives conditions in order that the convergence rates are O(n ^–1/2).     

Brownian charges around loops

Summary Let (X _t ⁿ ) be a Poisson sequence of independent Brownian motions in ^d ,d3; Let be a compact oriented submanifold of d, of dimensiond–2 and volume ; let t be the sum of the windings of (X _s ⁿ , 0st) around ; then t/t converges in law towards a Cauchy variable of parameter /2. A similar result is valid when the winding is replaced by the integral of a harmonic 1-form in ^d .     

Necessary and sufficient conditions for the convergence of convolution products of non-identical distributions on finite abelian semigroups

Given a sequence of probability measures ( _n ) on a finite abelian semigroup, we present necessary and sufficient conditions which guarantee the weak convergence of the convolution products _{k,n k+1}*···* _n (k<n), asn for allk0. These conditions are verifiable in the sense that they are based entirely on the individual measures in the sequence ( _n ).     

Some Conditions for a C0-Semigroup to Be Asymptotically Finite-Dimensional

We study the class of bounded C ₀-semigroups T=(T _t ) _t0 on a Banach space X satisfying the asymptotic finite dimensionality condition: codim X ₀(T)<, where X ₀(T):={x X:lim_t T _t x=0}. We prove a theorem which provides some necessary and sufficient conditions for asymptotic finite dimensionality.     

A decision theoretical characterization of weak ergodicity

Summary The relation between the ergodic coefficient and deficiency relative to the least informative experiment is investigated. The result is applied to nonhomogeneous Markov chains (NMC's). Our main result can be described as follows: Given an NMC, define the experiments _n ^(j) for n1 consisting in observing the (n+j)-th state of the chain, the j-th state being the unknown parameter. Then the chain is weakly ergodic if and only if for any j, _n ^(j) converges as n (with respect to deficiencies) to the least informative experiment. It is finally shown that in the homogeneous case, the rate of convergence is always exponential.     

On the asymptotic behaviour of first passage times for transient random walk

Summary Let _x denote the time at which a random walk with finite positive mean first passes into (x, ), wherex0. This paper establishes the asymptotic behaviour of Pr { _x >n} asn for fixedx in two cases. In the first case the left hand tail of the step-distribution is regularly varying, and in the second the step-distribution satisfies a one-sided Cramér type condition. As a corollary, it follows that in the first case Pr { _x >n}/Pr{ ₀ >n} coincides with the limit of the same quantity for recurrent random walk satisfying Spitzer's condition, but in the second case the limit is more complicated.     

Semilinear Perturbations of Harmonic Spaces,Liouville Property and a Boundary Value Problem

Let (X,) be a P-harmonic Bauer space and let be a Borel measurable function on X×R satisfying conditions (A) through (D) of Section 2 (e.g., (x,t)=t|t|^–1 where >1). For every Kato family M of potential kernels on X let ^M U(X) denote the set of all real continuous functions on X such that u+K ^M _D (,u)(D) for every open relatively compact subset D of X. We study the existence of a non-trivial function in ^M U(X) which is dominated by a given positive harmonic function on X. If X is a domain of R ^d , is a positive Kato measure on X and L is a second-order differential operator in R ^d , we apply our study to derive a characterization of finite positive measures on the minimal Martin boundary ^M ₁ X for which the boundary value problem Lu=(,u) in X and u= on ^M ₁ X is solvable.     

On characterizations of distributions via moments of record values

Summary Let {X _n } _n ⁼¹ be a sequence of i.i.d. random variables having continuous distribution F(x) with E|X| ^l+< for some positive integer l and for some >0. It is shown that for any fixed integer N0 the sequence of moments of record values {E(X _L(n) ) ^l } _n=N characterizes F. Furthermore, this result is applied to the weak convergence of continuous distributions.     

Darstellung einer Ordnung von Maßen durch Stoppzeiten

Summary Given a stochastic matrixP on the state spaceI an ordering for measures inI can be defined in the following way: iff(f)(f) for allf in a sufficiently rich subcone of the cone of positiveP-subharmonic functions. It is shown that, if, are probability measures with , then in theP-process (X _n)_n0 having as initial distribution there exists a stopping time such thatX is distributed according to. In addition, can be chosen in such a way, that for every positive subharmonicf with(f)< the submartingale (f(X _n))_n0 is uniformly integrable.