Hypergroup deformations and Markov chains

Persi Diaconis and Phil Hanlon in their interesting paper⁽⁴⁾ give the rates of convergence of some Metropolis Markov chains on the cubeZ ^d (2). Markov chains on finite groups that are actually random walks are easier to analyze because the machinery of harmonic analysis is available. Unfortunately, Metropolis Markov chains are, in general, not random walks on group structure. In attempting to understand Diaconis and Hanlon's work, the authors were led to the idea of a hypergroup deformation of a finite groupG, i.e., a continuous family of hypergroups whose underlying space isG and whose structure is naturally related to that ofG. Such a deformation is provided forZ ^d (2), and it is shown that the Metropolis Markov chains studied by Diaconis and Hanlon can be viewed as random walks on the deformation. A direct application of the Diaconis-Shahshahani Upper Bound Lemma, which applies to random walks on hypergroups, is used to obtain the rate of convergence of the Metropolis chains starting at any point. When the Markov chains start at 0, a result in Diaconis and Hanlon⁽⁴⁾ is obtained with exactly the same rate of convergence. These results are extended toZ ^d (3).Research supported in part by the Office of Research and Sponsored Programs, University of Oregon.     

Boundaries of random walks on graphs and groups with infinitely many ends

Consider an irreducible random walk {Z _n} on a locally finite graphG with infinitely many ends, and assume that its transition probabilities are invariant under a closed group Γ of automorphisms ofG which acts transitively on the vertex set. We study the limiting behaviour of {Z _n} on the spaceΩ of ends ofG. With the exception of a degenerate case,Ω always constitutes a boundary of Γ in the sense of Furstenberg, and {Z _n} converges a.s. to a random end. In this case, the Dirichlet problem for harmonic functions is solvable with respect toΩ. The degenerate case may arise when Γ is amenable; it then fixes a unique end, and it may happen that {Z _n} converges to this end. If {Z _n} is symmetric and has finite range, this may be excluded. A decomposition theorem forΩ, which may also be of some purely graph-theoretical interest, is derived and applied to show thatΩ can be identified with the Poisson boundary, if the random walk has finite range. Under this assumption, the ends with finite diameter constitute a dense subset in the minimal Martin boundary. These results are then applied to random walks on discrete groups with infinitely many ends.     

General shock models with random threshold

A general shock model associated with a correlated pair (X _n ,Y _n ) of renewal sequences is considered. The system fails when the magnitude of the shock exceeds a random threshold Zfollowing exponential law. The distribution of the system failure time T _Z is found and first two moments of T _Z are derived. A class of correlated cumulative shock models is also studied. As an application stochastic clearing system is studied in detail.     

Convergence of two-dimensional branching recursions

The asymptotic distribution of branching type recursions (L_n) of the form is investigated in the two-dimensional case. Here is an independent copy of L_n−1 and A,B are random matrices jointly independent of . The asymptotics of L_n after normalization are derived by a contraction method. The limiting distribution is characterized by a fixed point equation. The assumptions of the convergence theorem are checked in some examples using eigenvalue decompositions and computer algebra.     

Large deviations for random walks on Galton–Watson trees: averaging and uncertainty

 In the study of large deviations for random walks in random environment, a key distinction has emerged between quenched asymptotics, conditional on the environment, and annealed asymptotics, obtained from averaging over environments. In this paper we consider a simple random walk {X _n } on a Galton–Watson tree T, i.e., on the family tree arising from a supercritical branching process. Denote by |X _n | the distance between the node X _n and the root of T. Our main result is the almost sure equality of the large deviation rate function for |X _n |/n under the “quenched measure” (conditional upon T), and the rate function for the same ratio under the “annealed measure” (averaging on T according to the Galton–Watson distribution). This equality hinges on a concentration of measure phenomenon for the momentum of the walk. (The momentum at level n, for a specific tree T, is the average, over random walk paths, of the forward drift at the hitting point of that level). This concentration, or certainty, is a consequence of the uncertainty in the location of the hitting point. We also obtain similar results when {X _n } is a λ-biased walk on a Galton–Watson tree, even though in that case there is no known formula for the asymptotic speed. Our arguments rely at several points on a “ubiquity” lemma for Galton–Watson trees, due to Grimmett and Kesten (1984). Received: 15 November 2000 / Revised version: 27 February 2001 / Published online: 19 December 2001     

Collision probability for random trajectories in two dimensions

We give a lower bound for the non-collision probability up to a long time T$T$ in a system of n$n$ independent random walks with fixed obstacles on Z²${\mathbb{Z}}^2$. By ‘collision’ we mean collision between the random walks as well as collision with the fixed obstacles. We give an analogous result for Brownian particles on the plane. As a corollary we show that the non-collision request leads only to logarithmic corrections for a spread-out property of the independent random walk system.     

Minimum Manhattan Network is NP-Complete

Given a set T of n points in ℝ², a Manhattan network on T is a graph G with the property that for each pair of points in T, G contains a rectilinear path between them of length equal to their distance in the L ₁-metric. The minimum Manhattan network problem is to find a Manhattan network of minimum length, i.e., minimizing the total length of the line segments in the network.     

A note on the Poisson boundary of lamplighter random walks

The main goal of this paper is to determine the Poisson boundary of lamplighter random walks over a general class of discrete groups Γ endowed with a “rich” boundary. The starting point is the Strip Criterion of identification of the Poisson boundary for random walks on discrete groups due to Kaimanovich (Ann. Math. 152:659–692, 2000). A geometrical method for constructing the strip as a subset of the lamplighter group \mathbb Z₂\wr G{\mathbb {Z}_{2}\wr \Gamma} starting with a “smaller” strip in the group Γ is developed. Then, this method is applied to several classes of base groups Γ: groups with infinitely many ends, hyperbolic groups in the sense of Gromov, and Euclidean lattices. We show that under suitable hypothesis the Poisson boundary for a class of random walks on lamplighter groups is the space of infinite limit configurations.     

The Arcsine Law

Let N _n denote the number of positive sums in the first n trials in a random walk (S _i) and let L _n denote the first time we obtain the maximum in S ₀,..., S _n. Then the classical equivalence principle states that N _n and L _n have the same distribution and the classical arcsine law gives necessary and sufficient condition for (1/n) L _n or (1/n) N _n to converge in law to the arcsine distribution. The objective of this note is to provide a simple and elementary proof of the arcsine law for a general class of integer valued random variables (T _n) and to provide a simple an elementary proof of the equivalence principle for a general class of integer valued random vectors (N _n, L _n).     

Limit theorems for monochromatic stars

Let T(K_1,r,G_n) be the number of monochromatic copies of the r‐star K_1,r in a uniformly random coloring of the vertices of the graph G_n. In this paper we provide a complete characterization of the limiting distribution of T(K_1,r,G_n), in the regime where is bounded, for any growing sequence of graphs G_n. The asymptotic distribution is a sum of mutually independent components, each term of which is a polynomial of a single Poisson random variable of degree at most r. Conversely, any limiting distribution of T(K_1,r,G_n) has a representation of this form. Examples and connections to the birthday problem are discussed.     

List Point Arboricity of Dense Graphs

Let G be a simple graph. The point arboricity ρ(G) of G is defined as the minimum number of subsets in a partition of the point set of G so that each subset induces an acyclic subgraph. The list point arboricity ρ _l (G) is the minimum k so that there is an acyclic L-coloring for any list assignment L of G which |L(v)| ≥ k. So ρ(G) ≤ ρ _l (G) for any graph G. Xue and Wu proved that the list point arboricity of bipartite graphs can be arbitrarily large. As an analogue to the well-known theorem of Ohba for list chromatic number, we obtain ρ _l (G + K _n ) = ρ(G + K _n ) for any fixed graph G when n is sufficiently large. As a consequence, if ρ(G) is close enough to half of the number of vertices in G, then ρ _l (G) = ρ(G). Particularly, we determine that , where K _2(n) is the complete n-partite graph with each partite set containing exactly two vertices. We also conjecture that for a graph G with n vertices, if then ρ _l (G) = ρ(G). Research supported by NSFC (No.10601044) and XJEDU2006S05.     

Optical local Gaussian approximation of an exponential family

Summary Under certain regularity conditions products E ⁿ of an experiment E can be locally approximated by homoschedastic Gaussian experiments G _n. G _n can be defined such that the square roots of the densities have nearly the same structure with respect to the L ²-geometry as in E ⁿ. The main result of this paper is that this choice of G _n is asymptotically optimal in the sense of minimizing the deficiency distance between E ⁿ and G if E is a one-dimensional exponential family. This work has been supported by the Deutsche Forschungsgemeinschaft     

The average Steiner distance of a graph

The average distance μ(G) of a graph G is the average among the distances between all pairs of vertices in G. For n ≥ 2, the average Steiner n-distance μ_n(G) of a connected graph G is the average Steiner distance over all sets of n vertices in G. It is shown that for a connected weighted graph G, μ_n(G) ≤ μ_k(G) + μ_n+1−k(G) where 2 ≤ k ≤ n − 1. The range for the average Steiner n-distance of a connected graph G in terms of n and |V(G)| is established. Moreover, for a tree T and integer k, 2 ≤ k ≤ n − 1, it is shown that μ_n(T) ≤ (n/k)μ_k(T) and the range for μ_n(T) in terms of n and |V(T)| is established. Two efficient algorithms for finding the average Steiner n-distance of a tree are outlined. © 1996 John Wiley & Sons, Inc.     

The ratio of the distance irredundance and domination numbers of a graph

Let n ≥ 1 be an integer and let G be a graph. A set D of vertices in G is defined to be an n-dominating set of G if every vertex of G is within distance n from some vertex of D. The minimum cardinality among all n-dominating sets of G is called the n-domination number of G and is denoted by γ_n(G). A set / of vertices in G is n-irredundant if for every vertex x ∈ / there exists a vertex y that is within distance n from x but at distance greater than n from every vertex of / - {x}. The n-irredundance number of G, denoted by ir_n(G), is the minimum cardinality taken over all maximal n-irredundant sets of vertices of G. We show that inf{ir_n(G)/γ_n(G) | G is an arbitrary finite undirected graph with neither loops nor multiple edges} = 1/2 with the infimum not being attained. Subsequently, we show that 2/3 is a lower bound on all quotients ir_n(T)/γ_n(T) in which T is a tree. Furthermore, we show that, for n ≥ 2, this bound is sharp. These results extend those of R. B. Allan and R.C. Laskar [“On Domination and Some Related Concepts in Graph Theory,” Utilitas Mathematica, Vol. 21 (1978), pp. 43–56], B. Bollobás and E. J. Cockayne [“Graph-Theoretic Parameters Concerning Domination, Independence and Irredundance,” Journal of Graph Theory, Vol. 3 (1979), pp. 241–249], and P. Damaschke [Irredundance Number versus Domination Number, Discrete Mathematics, Vol. 89 (1991), pp. 101–104].     

On galois groups and their maximal 2-subgroups

LetG be a finite group of even order, having a central element of order 2 which we denote by −1. IfG is a 2-group, letG be a maximal subgroup ofG containing −1, otherwise letG be a 2-Sylow subgroup ofG. LetH=G/{±1} andH=G/{±1}. Suppose there exists a regular extensionL ₁ of ℚ(T) with Galois groupG. LetL be the subfield ofL ₁ fixed byH. We make the hypothesis thatL ₁ admits a quadratic extensionL ₂ which is Galois overL of Galois groupG. IfG is not a 2-group we show thatL ₁ then admits a quadratic extension which is Galois over ℚ(T) of Galois groupG and which can be given explicitly in terms ofL ₂. IfG is a 2-group, we show that there exists an element α ε ℚ(T) such thatL ₁ admits a quadratic extension which is Galois over ℚ(T) of Galois groupG if and only if the cyclic algebra (L/ℚ(T).a) splits. As an application of these results we explicitly construct several 2-groups as Galois groups of regular extensions of ℚ(T).     

NP-completeness for minimizing maximum edge length in grid embeddings

Given an embedding f: G →$\text{Z}$² of a graph G in the two-dimensional lattice, let |f| be the maximum L₁ distance between points f(x) and f(y) where xy is an edge of G. Let B₂(G) be the minimum |f| over all embeddings f. It is shown that the determination of B₂(G) for arbitrary G is NP-complete. Essentially the same proof can be used in showing the NP-completeness of minimizing |f| over all embeddings f: G → $\text{Z}$ⁿ of G into the n-dimensional integer lattice for any fixed n ≥ 2.     

On the computation of the projective surgery obstruction groups

The computation of the projective surgery obstruction groupsL _n ^p (ZG), forG a hyperelementary finite group, is reduced to standard calculations in number theory, mostly involving class groups. Both the exponent of the torsion subgroup and the precise divisibility of the signatures are determined. ForG a 2-hyperelementary group, theL _n ^p (ZG) are detected by restriction to certain subquotients ofG, and a complete set of invariants is given for oriented surgery obstructions.Partially supported by NSERC grant A4000.Partially supported by NSF grant DMS-8610730(1) and the Danish Research Council.     

Automorphism groups of finite distributive lattices with a given sublattice of fixed points

For a latticeL, aL is a fixed point ofL if and only iff(a)=a for every automorphismf ofL. Let Aut (L) andS (L) denote the group of automorphisms ofL and the sublattice of fixed points ofL, respectively. It is shown that ifG is a finite group other thanZ ₂ ² ,Z ₂ ³ ,Z ₂ ⁴ ,Z ₃ ² or the quaternion group of order 8 andL is a finite automorphism free distributive lattice that is not near Boolean then there is a finite distributive latticeL such that Aut (L)G andS(L)L.The support of the National Research Council of Canada is gratefully acknowledged.     

The continuum limit of critical random graphs

We consider the Erd?s–Rényi random graph G(n, p) inside the critical window, that is when p?=?1/n?+?λn ^?4/3, for some fixed ${\lambda \in \mathbb{R}}$ . We prove that the sequence of connected components of G(n, p), considered as metric spaces using the graph distance rescaled by n ^?1/3, converges towards a sequence of continuous compact metric spaces. The result relies on a bijection between graphs and certain marked random walks, and the theory of continuum random trees. Our result gives access to the answers to a great many questions about distances in critical random graphs. In particular, we deduce that the diameter of G(n, p) rescaled by n ^?1/3 converges in distribution to an absolutely continuous random variable with finite mean.     

Averaging sequences and modulated ergodic theorems for weakly almost periodic group representations

LetT be a weakly almost periodic (WAP) representation of a locally compact Σ-compact groupG by linear operators in a Banach spaceX, and letM = M(T) be its ergodic projection onto the space of fixed points (i.e.,Mx is the unique fixed point in the closed convex hull of the orbit ofx). A sequence of probabilities Μ_n is said toaverage T [weakly] if ∫T(t)x dΜ _n converges [weakly] toM(T)x for eachx ∃X. We callΜ _n [weakly]unitarily averaging if it averages [weakly] every unitary representation in a Hilbert space, and [weakly]WAPRaveraging if it averages [weakly] every WAP representation. We investigate some of the relationships of these notions, and connect them with properties of the regular representation (by translations) in the spaceWAP(G). Research partially supported by the Israel Science Foundation.