Chains and anti-chains in the lattice of epigroup varieties

Let ? _n be the variety of all epigroups of index ≤n. We prove that, for an arbitrary natural number n, the interval [? _n ,? _n+1] of the lattice of epigroup varieties contains a chain isomorphic to the chain of real numbers with the usual order and an anti-chain of the cardinality continuum.     

Geometric ergodicity and the spectral gap of non-reversible Markov chains

We argue that the spectral theory of non-reversible Markov chains may often be more effectively cast within the framework of the naturally associated weighted-L _∞ space ${L_\infty^V}$ , instead of the usual Hilbert space L ₂?=?L ₂(π), where π is the invariant measure of the chain. This observation is, in part, based on the following results. A discrete-time Markov chain with values in a general state space is geometrically ergodic if and only if its transition kernel admits a spectral gap in ${L_\infty^V}$ . If the chain is reversible, the same equivalence holds with L ₂ in place of ${L_\infty^V}$ . In the absence of reversibility it fails: There are (necessarily non-reversible, geometrically ergodic) chains that admit a spectral gap in ${L_\infty^V}$ but not in L ₂. Moreover, if a chain admits a spectral gap in L ₂, then for any ${h\in L_2}$ there exists a Lyapunov function ${V_h\in L_1}$ such that V _h dominates h and the chain admits a spectral gap in ${L_\infty^{V_h}}$ . The relationship between the size of the spectral gap in ${L_\infty^V}$ or L ₂, and the rate at which the chain converges to equilibrium is also briefly discussed.     

On the generalization of the Volterra principle of inversion

In this article a linear operator, K, defined on a Hilbert space equipped with a chain of orthoprojectors is considered. It is proved that if K enjoys a particular property with respect to the chain of orthoprojectors, then the series ∑_{n = 0}^∞Kⁿ converges in the uniform operator norm. The proof uses purely algebraic techniques and does not require compactness of K. As such, it is a significant generalization of the well-known Volterra principle of inversion.     

Weight Hierarchies of Linear Codes Satisfying the Chain Condition

The weight hierarchy of a linear [n,k;q] code C over GF(q) is the sequence (d₁,d₂,...,d_k) where d_r is the smallest support of an r–dimensional subcode of C. By explicit construction, it is shown that if a sequence (a₁,a₂,...,a_k) satisfies certain conditions, then it is the weight hierarchy of a code satisfying the chain condition.     

Applications of the symmetric chain decomposition of the lattice of divisors

The symmetric chain decomposition of the lattice of divisors,D _N, is applied to prove results about the strict unimodality of the Whitney numbers ofD _N, about minimum interval covers for the union of consecutive rank-sets ofD _N, and about the distribution of sums of vectors in which each vector can be included several times (an extension of the famous Littlewood-Offord problem)Research supported in part by NSA/MSP GrantMDA904-92H3053.     

The intersection of the powers of the radical in Noetherian P.I. rings

LetR be a ring and J its radical. DefineJ ₁=∩Jⁿ, J₂=∩J ₁ ⁿ ,…,… J_k=∩J _k−1 ⁿ .... It is shown that in a ringR satisfying a polynomial identity and the ascending chain condition on ideals,J _k =0 for some appropriatek. The work of the first author was supported by an NSF grant at the University of Chicago. The work of the second author was supported by an NSF grant at the University of California, San Diego.     

Weak Invariance Principle for the Local Times of Partial Sums of Markov Chains

Let {X _n } be an integer-valued Markov chain with finite state space. Let $S_{n}=\sum_{k=0}^{n}X_{k}$ and let L _n (x) be the number of times S _k hits x∈? up to step n. Define the normalized local time process l _n (t,x) by The subject of this paper is to prove a functional weak invariance principle for the normalized sequence l _n (t,x), i.e., we prove under the assumption of strong aperiodicity of the Markov chain that the normalized local times converge in distribution to the local time of the Brownian motion.     

Rings with divisibility on chains of ideals

We present a generalization of the ascending and descending chain condition on one-sided ideals by means of divisibility on chains. We say that a ring R satisfies ACC_d on right ideals if in every ascending chain of right ideals of R, each right ideal in the chain, except for a finite number of right ideals, is a left multiple of the following one; that is, each right ideal in the chain, except for a finite number, is divisible by the following one. We study these rings and prove some results about them. Dually, we say that a ring R satisfies DCC_d on right ideals if in every descending chain of right ideals of R, each right ideal in the chain, except for a finite number of right ideals, is divisible by the previous one. We study these conditions on rings, in general and in special cases.     

Adaptive estimation of the transition density of a particular hidden Markov chain

We study the following model of hidden Markov chain: with (X_i) a real-valued positive recurrent and stationary Markov chain, and (?_i)_1?i?n+1 a noise independent of the sequence (X_i) having a known distribution. We present an adaptive estimator of the transition density based on the quotient of a deconvolution estimator of the density of X_i and an estimator of the density of (X_i,X_i+1). These estimators are obtained by contrast minimization and model selection. We evaluate the L² risk and its rate of convergence for ordinary smooth and supersmooth noise with regard to ordinary smooth and supersmooth chains. Some examples are also detailed.     

The Key Renewal Theorem for a Transient Markov Chain

We consider a time-homogeneous real-valued Markov chain X _n , n≥0. Suppose that this chain is transient, that is, X _n generates a σ-finite renewal measure. We prove the key renewal theorem under the condition that this chain has jumps that are asymptotically homogeneous at infinity and asymptotically positive drift.     

Lifting problem of the measure algebra

We prove the consistency of “?/I _mz does not split” (see Notation). We write the proof so that with the standard duality, also the consistency of “?/I _tc does not split” (i.e., replacing measure zero by first category, random by generic, etc.) is proved. The method is the oracle chain condition.     

On the limit laws of the second order for additive functionals of Harris recurrent Markov chains

Let {X _n } _{n ≥0} be a Harris recurrent Markov chain with state space E and invariant measure π. The law of the iterated logarithm and the law of weak convergence are given for the additive functionals of the form

On the range of recurrent Markov chains

Let {X_n}₀^∞ be an irreducible recurrent Markov Chain on the nonnegative integers. A result of Chosid and Isaac (1978) gives a sufficient condition for n^?1R_n → 0 w.p.1. where R_n is the range of the chain. We give an alternative proof using Kingman's subadditive ergodic theorem (Kingman, 1973). Some examples are also given.     

A chain of evolution algebras

We introduce a notion of chain of evolution algebras. The sequence of matrices of the structural constants for this chain of evolution algebras satisfies an analogue of Chapman-Kolmogorov equation. We give several examples (time homogenous, time non-homogenous, periodic, etc.) of such chains. For a periodic chain of evolution algebras we construct a continuum set of non-isomorphic evolution algebras and show that the corresponding discrete time chain of evolution algebras is dense in the set. We obtain a criteria for an evolution algebra to be baric and give a concept of a property transition. For several chains of evolution algebras we describe the behavior of the baric property depending on the time. For a chain of evolution algebras given by the matrix of a two-state evolution we define a baric property controller function and under some conditions on this controller we prove that the chain is not baric almost surely (with respect to Lebesgue measure). We also construct examples of the almost surely baric chains of evolution algebras. We show that there are chains of evolution algebras such that if it has a unique (resp. infinitely many) absolute nilpotent element at a fixed time, then it has unique (resp. infinitely many) absolute nilpotent element any time; also there are chains of evolution algebras which have not such property. For an example of two dimensional chain of evolution algebras we give the full set of idempotent elements and show that for some values of parameters the number of idempotent elements does not depend on time, but for other values of parameters there is a critical time t_c such that the chain has only two idempotent elements if time t?t_c and it has four idempotent elements if time t<t_c.     

On the hardness of sampling independent sets beyond the tree threshold

We consider local Markov chain Monte–Carlo algorithms for sampling from the weighted distribution of independent sets with activity λ, where the weight of an independent set I is λ^|I|. A recent result has established that Gibbs sampling is rapidly mixing in sampling the distribution for graphs of maximum degree d and λ < λ _c (d), where λ _c (d) is the critical activity for uniqueness of the Gibbs measure (i.e., for decay of correlations with distance in the weighted distribution over independent sets) on the d-regular infinite tree. We show that for d ≥ 3, λ just above λ _c (d) with high probability over d-regular bipartite graphs, any local Markov chain Monte–Carlo algorithm takes exponential time before getting close to the stationary distribution. Our results provide a rigorous justification for “replica” method heuristics. These heuristics were invented in theoretical physics and are used in order to derive predictions on Gibbs measures on random graphs in terms of Gibbs measures on trees. A major theoretical challenge in recent years is to provide rigorous proofs for the correctness of such predictions. Our results establish such rigorous proofs for the case of hard-core model on bipartite graphs. We conjecture that λ _c is in fact the exact threshold for this computational problem, i.e., that for λ > λ _c it is NP-hard to approximate the above weighted sum over independent sets to within a factor polynomial in the size of the graph.     

Going in Circles: Variations on the Money-Coutts Theorem

Given a polygon A ₁,...,A _n, consider the chain of circles: S ₁ inscribed in the angle A ₁, S ₂ inscribed in the angle A ₂ and tangent to S ₁, S ₃ inscribed in the angle A ₃ and tangent to S ₂, etc. We describe a class of n-gons for which this process is 2n-periodic. We extend the result to the case when the sides of a polygon are arcs of circles. The case of triangles is known as the Money-Coutts theorem.     

On semidirectly closed pseudovarieties of aperiodic semigroups

The aim of this work is to study the unknown intervals of the lattice of aperiodic pseudovarieties which are semidirectly closed and answer questions proposed by Almeida in his book “Finite Semigroups and Universal Algebra”. The main results state that the intervals [V^*(B₂),ER∩LR] and [V^*(B₂¹),ER∩A] are not trivial, and that both contain a chain isomorphic to the chain of real numbers. These results are a consequence of the study of the semidirectly closed pseudovariety generated by the aperiodic Brandt semigroup B₂.     

Chain Blockers and Convoluted Catalan Numbers

We give new interpretations of Catalan and convoluted Catalan numbers in terms of trees and chain blockers. For a poset P we say that a subset A ? P is a chain blocker if it is an inclusionwise minimal subset of P that contains at least one element from every maximal chain. In particular, we study the set of chain blockers for the class of posets P = C _a × C _b where C _i is the chain 1 < ? < i. We show that subclasses of these chain blockers are counted by Catalan and convoluted Catalan numbers.     

Saddlepoint expansions for sums of Markov dependent variables on a continuous state space

Summary Based on the conjugate kernel studied in Iscoe et al. (1985) we derive saddlepoint expansions for either the density or distribution function of a sumf(X ₁)+...+f(X _n ), where theX _i 's constitute a Markov chain. The chain is assumed to satisfy a strong recurrence condition which makes the results here very similar to the classical results for i.i.d. variables. In particular we establish also conditions under which the expansions hold uniformly over the range of the saddlepoint. Expansions are also derived for sums of the formf(X ₁,X ₀)+f(X ₂,X ₁)+...+f(X _n ,X _n–1) although the uniformity result just mentioned does not generalize.