On Hitting Times and Fastest Strong Stationary Times for Skip-Free and More General Chains

An (upward) skip-free Markov chain with the set of nonnegative integers as state space is a chain for which upward jumps may be only of unit size; there is no restriction on downward jumps. In a 1987 paper, Brown and Shao determined, for an irreducible continuous-time skip-free chain and any d, the passage time distribution from state 0 to state d. When the nonzero eigenvalues ν _j of the generator on {0,…,d}, with d made absorbing, are all real, their result states that the passage time is distributed as the sum of d independent exponential random variables with rates ν _j . We give another proof of their theorem. In the case of birth-and-death chains, our proof leads to an explicit representation of the passage time as a sum of independent exponential random variables. Diaconis and Miclo recently obtained the first such representation, but our construction is much simpler. We obtain similar (and new) results for a fastest strong stationary time T of an ergodic continuous-time skip-free chain with stochastically monotone time-reversal started in state 0, and we also obtain discrete-time analogs of all our results. In the paper’s final section we present extensions of our results to more general chains. Research supported by NSF grant DMS–0406104, and by The Johns Hopkins University’s Acheson J. Duncan Fund for the Advancement of Research in Statistics.     

Zero-sum problems with congruence conditions

For a finite abelian group G and a positive integer d, let s _dℕ(G) denote the smallest integer ℓ∈ℕ₀ such that every sequence S over G of length |S|≧ℓ has a nonempty zero-sum subsequence T of length |T|≡0 mod d. We determine s _dℕ(G) for all d≧1 when G has rank at most two and, under mild conditions on d, also obtain precise values in the case of p-groups. In the same spirit, we obtain new upper bounds for the Erdős–Ginzburg–Ziv constant provided that, for the p-subgroups G _p of G, the Davenport constant D(G _p ) is bounded above by 2exp  (G _p )−1. This generalizes former results for groups of rank two.     

Bounded Direction–Length Frameworks

A direction–length framework is a pair (G,p) where G=(V;D,L) is a ‘mixed’ graph whose edges are labelled as ‘direction’ or ‘length’ edges and p is a map from V to ℝ ^d for some d. The label of an edge uv represents a direction or length constraint between p(u) and p(v). Let G ⁺ be obtained from G by adding, for each length edge e of G, a direction edge with the same end vertices as e. We show that (G,p) is bounded if and only if (G ⁺,p) is infinitesimally rigid. This gives a characterization of when (G,p) is bounded in terms of the rank of the rigidity matrix of (G ⁺,p). We use this to characterize when a mixed graph is generically bounded in ℝ ^d . As an application we deduce that if (G,p) is a globally rigid generic framework with at least two length edges and e is a length edge of G then (G∖e,p) is bounded.     

On a theorem of Rhemtulla on polycyclic groups

Let H be a subgroup of the polycyclic-by-finite group G and denote the automorphism group of G by Γ. We prove that there exists an integer d such that in the poset {?_γ∈∑H^γ:∑ a subset of Γ} of all intersections of images H^γ of H under Γ, chains have length at most d. In particular the poset satisfies the minimal condition. This extends and improves a theorem of A.H. Rhemtulla. We also provide a very different proof of Rhemtulla’s theorem.     

A central limit theorem for a weighted power variation of a Gaussian process*

Let ρ be a real-valued function on [0, T], and let LSI(ρ) be a class of Gaussian processes over time interval [0, T], which need not have stationary increments but their incremental variance σ(s, t) is close to the values ρ(|t ? s|) as t → s uniformly in s ∈ (0, T]. For a Gaussian processesGfrom LSI(ρ), we consider a power variation V _n corresponding to a regular partition π _n of [0, T] and weighted by values of ρ(·). Under suitable hypotheses on G, we prove that a central limit theorem holds for V _n as the mesh of π _n approaches zero. The proof is based on a general central limit theorem for random variables that admit a Wiener chaos representation. The present result extends the central limit theorem for a power variation of a class of Gaussian processes with stationary increments and for bifractional and subfractional Gaussian processes.     

Strong stationary duality for continuous-time Markov chains. Part I: Theory

LetX(t), 0t<, be an ergodic continuous-time Markov chain with finite or countably infinite state space. We construct astrong stationary dual chainX ^* whose first hitting times yield bounds on the convergence to stationarity forX. The development follows closely the discrete-time theory of Diaconis and Fill.^(2,3) However, for applicability it is important that we formulate our results in terms of infinitesimal rates, and this raises new issues.     

Invariant measures and disintegrations with applications to Palm and related kernels

Consider a locally compact group G acting measurably on some spaces S and T. We prove a general representation of G-invariant measures on S and the existence of invariant disintegrations of jointly invariant measures on S × T. The results are applied to Palm and related kernels associated with a stationary random pair (ξ,η), where ξ is a random measure on S and η is a random element in T. An erratum to this article can be found at     

A low-memory algorithm for finding short product representations in finite groups

We describe a space-efficient algorithm for solving a generalization of the subset sum problem in a finite group G, using a Pollard-ρ approach. Given an element z and a sequence of elements S, our algorithm attempts to find a subsequence of S whose product in G is equal to z. For a random sequence S of length d log₂ n, where n = #G and d ≥ 2 is a constant, we find that its expected running time is O(?n log n){O(\sqrt{n}\,{\rm log}\,n)} group operations (we give a rigorous proof for d > 4), and it only needs to store O(1) group elements. We consider applications to class groups of imaginary quadratic fields, and to finding isogenies between elliptic curves over a finite field.     

Hyperfinite construction of G-expectation

The hyperfinite G-expectation is a nonstandard discrete analogue of G-expectation (in the sense of Robinsonian nonstandard analysis). A lifting of a continuous-time G-expectation operator is defined as a hyperfinite G-expectation which is infinitely close, in the sense of nonstandard topology, to the continuous-time G-expectation. We develop the basic theory for hyperfinite G-expectations and prove an existence theorem for liftings of (continuous-time) G-expectation. For the proof of the lifting theorem, we use a new discretization theorem for the G-expectation (also established in this paper, based on the work of Dolinsky et al. [Weak approximation of G-expectations, Stoch. Process. Appl. 122(2) (2012), pp. 664–675]).     

On aschbacher’s localC(G; T) theorem

Aschbacher’s localC(G; T) theorem asserts that ifG is a finite group withF*(G)=O ₂(G), andTεSyl₂(G), thenG=C(G; T)K(G), whereC(G; T)=〈N _G (T ₀)|1≠T ₀ charT〉 andK(G) is the product of all near components ofG of typeL ₂(2 ⁿ ) orA ₂ ⁿ ₊₁. Near components are also known asχ-blocks or Aschbacher blocks. In this paper we give a proof of Aschbacher’s theorem in the case thatG is aK-group, i.e., in the case that every simple section ofG is isomorphic to one of the known simple groups. Our proof relies on a result of Meierfrankenfeld and Stroth [MS] on quadratic four-groups and on the Baumann-Glauberman-Niles theorem, for which Stellmacher [St2] has given an amalgam-theoretic proof. Apart from those results, our proof is essentially self-contained. For John Thompson Supported in part by NSF grant #DMS 89-03124, by DIMACS, an NSF Science and Technology Center, funded under contract STC-88-09648, and by NSA grant #MDA-904-91-H-0043. Prof. Gorenstein died on August 26, 1992.     

Trace formulas for a class of Toeplitz-like operators

LetP _T denote projection onto the space of entire functions of exponential type ≦T which are square summable on the line relative to a measuredΔ and letG denote multiplication by a suitably restricted complex valued function,g. For a reasonably large class of measuresdΔ, which includes Lebesgue measuredγ, it is shown that trace {(P _TGP_T)ⁿ−P_TGⁿP_T} tends boundedly to a limit asT↑∞ and that the limit isindependent of the choice ofdΔ within the permitted class. This extends the range of validity of a formula due to Mark Kac who evaluated this limit in the special casedΔ=dγ using a different formalism.     

On the probabilistic min spanning tree Problem

We study a probabilistic optimization model for min spanning tree, where any vertex v _i of the input-graph G(V, E) has some presence probability p _i in the final instance G′ ⊂ G that will effectively be optimized. Suppose that when this “real” instance G′ becomes known, a spanning tree T, called anticipatory or a priori spanning tree, has already been computed in G and one can run a quick algorithm (quicker than one that recomputes from scratch), called modification strategy, that modifies the anticipatory tree T in order to fit G′. The goal is to compute an anticipatory spanning tree of G such that, its modification for any G￠ í GG' \subseteq G is optimal for G′. This is what we call probabilistic min spanning tree problem. In this paper we study complexity and approximation of probabilistic min spanning tree in complete graphs under two distinct modification strategies leading to different complexity results for the problem. For the first of the strategies developed, we also study two natural subproblems of probabilistic min spanning tree, namely, the probabilistic metric min spanning tree and the probabilistic min spanning tree 1,2 that deal with metric complete graphs and complete graphs with edge-weights either 1, or 2, respectively.     

Set Partition Complexes

The Hom complexes were introduced by Lovász to study topological obstructions to graph colorings. The vertices of Hom(G,K _n ) are the n-colorings of the graph G, and a graph coloring is a partition of the vertex set into independent sets. Replacing the independence condition with any hereditary condition defines a set partition complex. We show how coloring questions arising from, for example, Ramsey theory can be formulated with set partition complexes. It was conjectured by Babson and Kozlov, and proved by Čukić and Kozlov, that Hom(G,K _n ) is (n−d−2)-connected, where d is the maximal degree of a vertex of G. We generalize this to set partition complexes.     

Quasi-randomness and the distribution of copies of a fixed graph

We show that if a graph G has the property that all subsets of vertices of size n/4 contain the “correct” number of triangles one would expect to find in a random graph G(n, 1/2), then G behaves like a random graph, that is, it is quasi-random in the sense of Chung, Graham, and Wilson [6]. This answers positively an open problem of Simonovits and Sós [10], who showed that in order to deduce that G is quasi-random one needs to assume that all sets of vertices have the correct number of triangles. A similar improvement of [10] is also obtained for any fixed graph other than the triangle, and for any edge density other than 1/2. The proof relies on a theorem of Gottlieb [7] in algebraic combinatorics, concerning the rank of set inclusion matrices.     

On Optimal Orientations of Cartesian Products of Trees

. Let d(D) (resp., d(G)) denote the diameter and r(D) (resp., r(G)) the radius of a digraph D (resp., graph G). Let G×H denote the cartesian product of two graphs G and H. An orientation D of G is said to be (r, d)-invariant if r(D)=r(G) and d(D)=d(G). Let {T _i }, i=1,…,n, where n≥2, be a family of trees. In this paper, we show that the graph ∏ _{i =1} ⁿ T _i admits an (r, d)-invariant orientation provided that d(T ₁)≥d(T ₂)≥4 for n=2, and d(T ₁)≥5 and d(T ₂)≥4 for n≥3. Received: July 30, 1997 Final version received: April 20, 1998     

On the Almost Sure Central Limit Theorem for a Class of Z d -Actions

As an extension of earlier papers on stationary sequences, a concept of weak dependence for strictly stationary random fields is introduced in terms of so-called homoclinic transformations. Under assumptions made within the framework of this concept a form of the almost sure central limit theorem (ASCLT) is established for random fields arising from a class of algebraic Z ^d -actions on compact abelian groups. As an auxillary result, the central limit theorem is proved via Ch. Stein's method. The next stage of the proof includes some estimates which are specific for ASCLT. Both steps are based on making use of homoclinic transformations.     

Perfect Matchings in ε-Regular Graphs and the Blow-Up Lemma

G on vertex set , , with density d>2ε and all vertex degrees not too far from d, has about as many perfect matchings as a corresponding random bipartite graph, i.e. about . In this paper we utilize that result to prove that with probability quickly approaching one, a perfect matching drawn randomly from G is spread evenly, in the sense that for any large subsets of vertices and , the number of edges of the matching spanned between S and T is close to |S||T|/n (c.f. Lemma 1). As an application we give an alternative proof of the Blow-up Lemma of Komlós, Sárk?zy and Szemerédi [10]. Received: December 5, 1997     

A randomized embedding algorithm for trees

In this paper, we propose a simple and natural randomized algorithm to embed a tree T in a given graph G. The algorithm can be viewed as a “self-avoiding tree-indexed random walk“. The order of the tree T can be as large as a constant fraction of the order of the graph G, and the maximum degree of T can be close to the minimum degree of G. We show that our algorithm works in a variety of interesting settings. For example, we prove that any graph of minimum degree d without 4-cycles contains every tree of order εd ² and maximum degree at most d-2εd-2. As there exist d-regular graphs without 4-cycles and with O(d ²) vertices, this result is optimal up to constant factors. We prove similar nearly tight results for graphs of given girth and graphs with no complete bipartite subgraph K _s,t .     

Deducing the multidimensional Szemerédi theorem from an infinitary removal lemma

We offer a new proof of the Furstenberg-Katznelson multiple recurrence theorem for several commuting probability-preserving transformations T ₁, T ₂, …, T _d : ℤ ↷ (X, ∑, μ) ([6]), and so, via the Furstenberg correspondence principle introduced in [5], a new proof of the multi-dimensional Szemerédi Theorem. We bypass the careful manipulation of certain towers of factors of a probability-preserving system that underlies the Furstenberg-Katznelson analysis, instead modifying an approach recently developed in [1] to pass to a large extension of our original system in which this analysis greatly simplifies. The proof is then completed using an adaptation of arguments developed by Tao in [13] for his study of an infinitary analog of the hypergraph removal lemma. In a sense, this addresses the difficulty, highlighted by Tao, of establishing a direct connection between his infinitary, probabilistic approach to the hypergraph removal lemma and the infinitary, ergodic-theoretic approach to Szemerédi’s Theorem set in motion by Furstenberg [5].     

Markov Chain Approximations for Symmetric Jump Processes

Markov chain approximations of reversible jump processes are investigated. Tightness results and a central limit theorem are established. Moreover, given the generator of a reversible jump process with state space ℝ ^d , the approximating Markov chains are constructed explicitly. As a byproduct we obtain a definition of the Sobolev space H ^α/2(ℝ ^d ), α∈(0,2), that is equivalent to the standard one.