Limiting distributions of functionals of Markov chains

Let \s{X_n, n ? 0\s} and \s{Y_n, n ? 0\s} be two stochastic processes such that Y_n depends on X_n in a stationary manner, i.e. P(Y_n ? A\vbX_n) does not depend on n. Sufficient conditions are derived for Y_n to have a limiting distribution. If X_n is a Markov chain with stationary transition probabilities and Y_n = f(X_n,..., X_n+k) then Y_n depends on X_n is a stationary way. Two situations are considered: (i) \s{X_n, n ? 0\s} has a limiting distribution (ii) \s{X_n, n ? 0\s} does not have a limiting distribution and exits every finite set with probability 1. Several examples are considered including that of a non-homogeneous Poisson process with periodic rate function where we obtain the limiting distribution of the interevent times.     

Augmented truncation approximations of discrete-time Markov chains

Let P be a positive recurrent infinite transition matrix with invariant distribution π and be a truncated and arbitrarily augmented stochastic matrix with invariant distribution _(n)π. We investigate the convergence ‖_(n)π−π‖→0, as n→∞, and derive a widely applicable sufficient criterion. Moreover, computable bounds on the error ‖_(n)π−π‖ are obtained for polynomially and geometrically ergodic chains. The bounds become rather explicit when the chains are stochastically monotone.     

Length laws for random subdivision of longest intervals

[0, 1] is partitioned by randomly splitting the longest subinterval, of length L, into two intervals of lengths LV and L(1 − V). V is independent of the past with a fixed distribution on (0, 1) If there are n subintervals and L_n is the length of a randomly chosen subinterval, then P(nL_n ∈ dy) ≅ y⁻¹P(K exp(−T₀) ∈ dy) where K = E(exp(T₀)) and T₀ is the first renewal in a stationary renewa process constructed from V.     

The rate of convergence for backwards products of a convergent sequence of finite Markov matrices

Recent papers have shown that Π^∞_{k = 1}P(k) = lim_m→∞ (P(m) ? P(1)) exists whenever the sequence of stochastic matrices {P(k)}^∞_{k = 1} exhibits convergence to an aperiodic matrix P with a single subchain (closed, irreducible set of states). We show how the limit matrix depends upon P(1).In addition, we prove that lim_m→∞lim_n→∞ (P(n + m) ? P(m + 1)) exists and equals the invariant probability matrix associated with P. The convergence rate is determined by the rate of convergence of {P(k)}^∞_{k = 1} towards P.Examples are given which show how these results break down in case the limiting matrix P has multiple subchains, with {P(k)}^∞_{k = 1} approaching the latter at a less than geometric rate.     

On entropy-preserving stochastic averages

When an n×n doubly stochastic matrix A acts on Rⁿ on the left as a linear transformation and P is an n-long probability vector, we refer to the new probability vector AP as the stochastic average of the pair (A,P). Let Γ_n denote the set of pairs (A,P) whose stochastic average preserves the entropy of P:H(AP)=H(P). Γ_n is a subset of B_n×Σ_n where B_n is the Birkhoff polytope and Σ_n is the probability simplex.We characterize Γ_n and determine its geometry, topology,and combinatorial structure. For example, we find that (A,P)∈Γ_n if and only if A^tAP=P. We show that for any n, Γ_n is a connected set, and is in fact piecewise-linearly contractible in B_n×Σ_n. We write Γ_n as a finite union of product subspaces, in two distinct ways. We derive the geometry of the fibers (A,·) and (·,P) of Γ_n. Γ₃ is worked out in detail. Our analysis exploits the convexity of xlogx and the structure of an efficiently computable bipartite graph that we associate to each ds-matrix. This graph also lets us represent such a matrix in a permutation-equivalent, block diagonal form where each block is doubly stochastic and fully indecomposable.     

On the polynomial of a path

Let A(P_n) be the adjacency matrix of the path on n vertices. Suppose that r(λ) is a polynomial of degree less than n, and consider the matrix M = r(A>/(P_n)). We determine all polynomials for which M is the adjacency matrix of a graph.     

Cells in any simple polygon formed by a planar point set

Let P be a finite point set in general position in the plane. We consider empty convex subsets of P such that the union of the subsets constitute a simple polygon S whose dual graph is a path, and every point in P is on the boundary of S. Denote the minimum number of the subsets in the simple polygons S's formed by P by f_p(P), and define the maximum value of f_p(P) by F_p(n) over all P with n points. We show that ⌈(4n-17)/15⌉?F_p(n)?⌊n/2⌋.     

Connected graphs with maximal Q-index: The one-dominating-vertex case

By the signless Laplacian of a (simple) graph G we mean the matrix Q(G)=D(G)+A(G), where A(G),D(G) denote respectively the adjacency matrix and the diagonal matrix of vertex degrees of G. For every pair of positive integers n,k, it is proved that if 3?k?n-3, then H_n,k, the graph obtained from the star K_1,n-1 by joining a vertex of degree 1 to k+1 other vertices of degree 1, is the unique connected graph that maximizes the largest signless Laplacian eigenvalue over all connected graphs with n vertices and n+k edges.     

Doubly stochastic matrices with equal subpermanents

It has been conjectured that if A is a doubly stochastic n>× n matrix such that per A(i, j)≥perA for all i, j, then either A = J_n, then n × n matrix with each entry equal to $\text{1}\text{n}$, or, up to permutations of rows and columns, $\text{A =}\text{1}\text{2}\text{(I}{}_{\mathrm{n}}\text{+ P}{}_{\mathrm{n}}\text{)}$, where P_n is a full cycle permutation matrix. This conjecture is proved.     

Irreducibility of associated matrices

For an n by n matrix A, let K(A) be the associated matrix corresponding to a permutation group (of degree m) and one of its characters. Let D_r(A) be the coefficient of x^m?r in K(A+xI). If A is reducible, then D_r(A) is reducible. If A is irreducible and the character is identically one, then D₁(A) is irreducible. If A is row stochastic and the character is identically one, then D_r(A) is essentially row stochastic. Finally, the results motivate the definition of group induced diagraphs.     

On representations by determinants of P(n) and Pm(n)

P(n) and P_m(n) denote the number of (unordered) partitions of n and the number of partitions of n into m parts, respectively. For P(n), there exists a recursion formula which is shown in Eq. (3) and a complicated formula indicated in J. L. Doob et al. (“Hans Rademacher: Topic Analytic Number Theory,” Springer-Verlag, Berlin/New York, 1973, p. 275, which is accompanied with the error term. For P_m(n), there is no general rule known covering all m (Doob et al., p. 222). In this article, P(n) and P_m(n) are represented by determinants. Note that the determinant of the former agrees with the above recursion formula and the finite product of binomials analogous to Euler identity, which is indicated in (5), leads to the representation of the latter. The computation of determinant is a little troublesome, but it is very important that the representations themselves of the number of partitions are simple, if we make use of the determinant.     

Groups with the same prime graph as the orthogonal group B n (3)

Let G be a finite group. The prime graph of G is denoted by Γ(G). It is proved in [1] that if G is a finite group such that Γ(G) = Γ(B _p (3)), where p > 3 is an odd prime, then G ? B _p (3) or C _p (3). In this paper we prove the main result that if G is a finite group such that Γ(G) = Γ(B _n (3)), where n ≥ 6, then G has a unique nonabelian composition factor isomorphic to B _n (3) or C _n (3). Also if Γ(G) = Γ(B ₄(3)), then G has a unique nonabelian composition factor isomorphic to B ₄(3), C ₄(3), or ² D ₄(3). It is proved in [2] that if p is an odd prime, then B _p (3) is recognizable by element orders. We give a corollary of our result, generalize the result of [2], and prove that B _2k+1(3) is recognizable by the set of element orders. Also the quasirecognition of B _2k (3) by the set of element orders is obtained.     

Graphs with bounded valency that do not embed in the projective plane

In 1930 Kuratowski proved that a graph does not embed in the real plane R² if and only if it contains a subgraph homeomorphic to one of two graphs, K₅ or K₃₃. Let I_n(P) denote the minimal set of graphs whose vertices have miximal valency n such that any graph which does not embed in the real projective plane (or equivalently, does not embed in the Möbius band) contains a subgraph homeomorphic to a graph in I_n(P) for some positive integer n. Glover and Huneke and Milgram proved that there are only 6 graphs in I₃(P). This note proves that for each n, I_n(P) is finite.     

The inverse of a matrix polynomial

An explicit representation is obtained for P(z)^?1 when P(z) is a complex n×n matrix polynomial in z whose coefficient of the highest power of z is the identity matrix. The representation is a sum of terms involving negative powers of z?λ for each λ such that P(λ) is singular. The coefficients of these terms are generated by sequences u_k, v_k of 1×n and n×1 vectors, respectively, which satisfy u₁≠0, v₁≠0, ∑^k?1_h=0(1?h!)u_k?hP^(h)(λ)=0, ∑^k?1_h=0(1?h!)P^(h)(λ)v_k?h=0, and certain orthogonality relations. In more general cases, including that when P(z) is analytic at λ but not necessarily a polynomial, the terms in the representation involving negative powers of z?λ provide the principal part of the Laurent expansion for P(z)^?1 in a punctured neighborhood of z=λ.     

Periodic regeneration

We consider stochastic processes Z = (Z_t)_[0,∞), on a general state space, having a certain periodic regeneration property: there is an increasing sequence of random times (S_n)^∞₀ such that the post-S_n process is conditionally independent of S₀,…,S_n given (S_n mod 1) and the conditional distribution does not depend on n. Our basic condition is that the distributions $\text{P}{}_{\mathrm{s}}\text{(A) =}\text{P}\text{(S}{}_{\mathrm{n+1}}\text{? S}{}_{\mathrm{n}}\text{∈ A|S}{}_{\mathrm{n}}\text{= s), s ∈[0, 1)}$, have a common component that is absolutely continuous w.r.t. Lebesgue measure. Then Z has the following time-homogeneous regeneration property: there exists a discrete aperiodic renewal process T = (T_n)^∞₀ such that the post-T_n process is independent of T₀,…,T_n and its distribution does not depend on n; this yields weak ergodicity. Further, the Markov chain (S_nmod 1)^∞₀ has an invariant distribution π_[0,1) and it holds that T_n+1 ? T_n has finite first moment if and only if m = ∫ m(P_s)π_[0,1)(ds) < ∞ where m(P_s) is the first moment of P_s; this yields periodic ergodicity. Also, some distributional properties of T₀ and T_n+1 ? T_n are established leading to improved ergodic regults. Finally, a uniform key periodic renewal theorem is derived.     

Localization of André-Quillen-Goodwillie towers, and the periodic homology of infinite loopspaces

Let K(n) be the nth Morava K-theory at a prime p, and let T(n) be the telescope of a v_n-self map of a finite complex of type n. In this paper we study the K(n)_*-homology of Ω^∞X, the 0th space of a spectrum X, and many related matters.We give a sampling of our results.Let PX be the free commutative S-algebra generated by X: it is weakly equivalent to the wedge of all the extended powers of X. We construct a natural map

s_n(X):L_T(n)P(X)→L_T(n)Σ^∞(Ω^∞X)₊     

A method in graph theory

A unified approach to a variety of graph-theoretic problems is introduced. The k-closure C_k(G) of a simple graph G of order n is the graph obtained from G by recursively joining pairs of nonadjacent vertices with degree-sum at least k. It is shown that, for many properties P, one can find a suitable value of k (depending on P and n) such that if C_k(G) has P, then so does G. For instance, if P is the hamiltonian property, one may take k = n. Thus if C_n(G) is hamiltonian, then so is G; in particular, if n ? 3 and C_n(G) is complete, then G is hamiltonian. This condition for a graph to be hamiltonian is shown to imply the well-known conditions of Chvátal and Las Vergnas. The same method, applied to other properties, yields many new theorems of a similar nature.     

On two discrete-time system stability concepts and supermartingales

A random discrete-time system {x_n}, n = 0, 1, 2, … is called stochastically stable if for every ? > 0 there exists a λ > 0 such that the probability P[(sup_n ∥ x_n ∥) > ?] < ? whenever P[∥ x₀ ∥ > λ] < λ. A system is shown stochastically stable if some local Lyapunov function V(·) satisfies the supermartingale definition on {V(x_n)} in a neighborhood of the origin; earlier proofs of stochastic stability require additional restrictions. A criterion for x_n → 0 almost surely is developed. It consists of a global inequality on {U(x_n)} stronger than the supermartingale defining inequality, but applied to a U(·) that need not be a Lyapunov function. The existence of such a U(·) is exhibited for a stochastically unstable nontrivial stochastic system. This indicates that our criterion for x_n → 0 is “tight,” and that the two stability concepts studied are substantially distinct.