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.     

Graphic sequences with a realization containing a complete multipartite subgraph

A nonincreasing sequence of nonnegative integers π=(d₁,d₂,…,d_n) is graphic if there is a (simple) graph G of order n having degree sequence π. In this case, G is said to realizeπ. For a given graph H, a graphic sequence π is potentiallyH-graphic if there is some realization of π containing H as a (weak) subgraph. Let σ(π) denote the sum of the terms of π. For a graph H and n∈Z⁺, σ(H,n) is defined as the smallest even integer m so that every n-term graphic sequence π with σ(π)≥m is potentially H-graphic. Let denote the complete t partite graph such that each partite set has exactly s vertices. We show that and obtain the exact value of σ(K_j+K_s,s,n) for n sufficiently large. Consequently, we obtain the exact value of for n sufficiently large.     

Polynomials orthogonal on the semicircle,II

Generalizing previous work [2], we study complex polynomials {π _k },π _k (z)=z ^k +?, orthogonal with respect to a complex-valued inner product (f,g)=∫ ₀ ^π f(e ^iθ)g(e ^iθ)w(e ^iθ)dθ. Under suitable assumptions on the “weight function”w, we show that these polynomials exist whenever Re ∫ ₀ ^π w(e ^iθ)dθ≠0, and we express them in terms of the real polynomials orthogonal with respect to the weight functionw(x). We also obtain the basic three-term recurrence relation. A detailed study is made of the polynomials {π _k } in the case of the Jacobi weight functionw(z)=(1?z)^α(1+z)^β, α>?1, and its special case \(\alpha = \beta = \lambda - \tfrac{1}{2}\) (Gegenbauer weight). We show, in particular, that for Gegenbauer weights the zeros ofπ _n are all simple and, ifn≥2, contained in the interior of the upper unit half disc. We strongly suspect that the same holds true for arbitrary Jacobi weights. Finally, for the Gegenbauer weight, we obtain a linear second-order differential equation forπ _n (z). It has regular singular points atz=1, ?1, ∞ (like Gegenbauer's equation) and an additional regular singular point on the negative imaginary axis, which depends onn.     

On approximation by polynomials increasing to the right of the interval

We obtain sufficient conditions on a real valued function ?, continuous on [0, + ∞), to insure that, for some nonnegative integer n, there is a nonnegative number r(n) so that for any r ? r(n), the polynomial of best approximation to ? on [0, r] from π_n is increasing and nonnegative on [r, + ∞). Here, π_n denotes the set of all real polynomials of degree n or less. The proofs of Theorems 1 and 2 use only properties of Lagrange interpolation while that of Theorem 3 employs results on the location of interpolation points in Chebyshev approximation.     

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.     

On a new class of boundary value problems for the Sturm-Liouville operator

We consider the spectral problem generated by the Sturm-Liouville operator with complex-valued potential q(x) ∈ L ₂(0, π) and degenerate boundary conditions. We show that the set of potentials q(x) for which there exist associated functions of arbitrarily high order in the system of root functions is everywhere dense in L ₁(0, π).     

A proof of the q,t-Catalan positivity conjecture

We present here a proof that a certain rational function C_n(q,t) which has come to be known as the “q,t-Catalan” is in fact a polynomial with positive integer coefficients. This has been an open problem since 1994. The precise form of the conjecture is given in Garsia and Haiman (J. Algebraic Combin. 5(3) (1996) 191), where it is further conjectured that C_n(q,t) is the Hilbert series of the diagonal harmonic alternants in the variables (x₁,x₂,…,x_n;y₁,y₂,…,y_n). Since C_n(q,t) evaluates to the Catalan number at t=q=1, it has also been an open problem to find a pair of statistics a(π),b(π) on Dyck paths π in the n×n square yielding C_n(q,t)=∑_πt^a(π)q^b(π). Our proof is based on a recursion for C_n(q,t) suggested by a pair of statistics a(π),b(π) recently proposed by Haglund. Thus, one of the byproducts of our developments is a proof of the validity of Haglund's conjecture. It should also be noted that our arguments rely and expand on the plethystic machinery developed in Bergeron et al. (Methods and Applications of Analysis, Vol. VII(3), 1999, p. 363).     

Some permutation problems

Put Z_n = {1, 2,…, n} and let π denote an arbitrary permutation of Z_n. Problem I. Let π = (π(1), π(2), …, π(n)). π has an up, down, or fixed point at a according as a < π(a), a > π(a), or a = π(a). Let $\text{A}\text{(r, s, t)}$ be the number of π ∈ Z_n with r ups, s downs, and t fixed points. Problem II. Consider the triple π^?1(a), a, π(a). Let R denote an up and F a down of π and let B(n, r, s) denote the number of π ∈ Z_n with r occurrences of π^?1(a)RaRπ(a) and s occurrences of π^?1(a)FaFπ(a). Generating functions are obtained for each enumerant as well as for a refinement of the second. In each case use is made of the cycle structure of permutations.     

Balanced decompositions of a signed graph

The balanced decomposition number (b.d.n.) δ₀(Σ) of a signed graph Σ is the smallest number of balanced subsets into which its edges can be partitioned. (A special case is decomposition of a graph into bipartite subgraphs.) The connected b.d.n. δ₁(Σ) is the same, but the subsets must also be connected. The balanced partition number (b.p.n.) π₀(Σ) is the smallest size of a partition of the vertices into subsets inducing balanced subgraphs; the connected b.p.n. π₁(Σ) is similar but the induced subgraphs must be connected. We use signed graph coloring theory to prove that δ₀ = 1 + ⌈log₂ π₀⌉ and that δ₀ is analogous to a critical exponent in the sense of Crapo and Rota. We deduce bounds on δ₀ and values for special signed graphs. We show that δ₀ is computationally about as complex as the chromatic number. We prove that, for a complete signed graph, δ₁ = δ₀; more strongly, with three exceptions a minimal balanced decomposition exists into connected and spanning edge sets. And we show that, of δ₁ and 1 + ⌈log₂ π₁⌉, neither is always at least as large as the other.     

Asymptotics of the spectrum of the Sturm-Liouville operator with regular boundary conditions

On the interval (0, π), we consider the spectral problem generated by the Sturm-Liouville operator with regular but not strongly regular boundary conditions. For an arbitrary potential q(x) ∈ L ₁ (0, π) [q(x) ∈ L ₂(0, π)], we establish exact asymptotic formulas for the eigenvalues of this problem.     

On a property of plane curves

Let γ:[0,1]→²[0,1] be a continuous curve such that γ(0)=(0,0), γ(1)=(1,1), and γ(t)∈²(0,1) for all t∈(0,1). We prove that, for each n∈N, there exists a sequence of points Ai, 0?i?n+1, on γ such that A₀=(0,0), An+1=(1,1), and the sequences and , 0?i?n, are positive and the same up to order, where π₁, π₂ are projections on the axes.     

On representations of GL(n) distinguished by GL(n − 1) over a p-adic field

For a nonarchimedean local field F, let GL(n):= GL(n, F) and GL(n?1) be embedded in GL(n) via g ? ( _{0 1} ^{g 0} ). Let π be an irreducible admissible representation of GL(n) for n ≥ 3. We prove that π is GL(n ? 1)-distinguished if and only if the Langlands parameter L(π) associated to π by the Local Langlands Correspondence has a subrepresentation L(11 _n?2) of dimension n?2 corresponding to the trivial representation of GL(n?2) such that the two-dimensional quotient L(π)/L(11 _n?2) corresponds either to an infinite-dimensional representation or the one-dimensional representations $\nu ^{ \pm (\tfrac{{n - 2}}{2})} $ of GL(2). We also prove that, for a parabolic subgroup P of GL(n) and an irreducible admissible representation ρ of the Levi subgroup of P, $\dim _\mathbb{C} (Hom_{GL(n - 1)} [ind_P^{GL(n)} (\rho ),\mathbb{I}_{n - 1} ]) \leqslant 2$ . For the standard Borel subgroup B _n of GL(n) and characters x _i of GL(1), we classify all representations ξ of the form $ind_{B_n }^{GL(n)} (\chi _1 \otimes \cdots \otimes \chi _n )$ for which $\dim _\mathbb{C} (Hom_{GL(n - 1)} [\xi ,\mathbb{I}_{n - 1} ]) = 2$ .     

On the basis property of a trigonometric system arising in the Frankl problem

We consider the function system {cos4nθ} _n=0 ^∞ , {sin(4n ? 1)θ} _n=1 ^∞ , which arises in the Frankl problem in the theory of elliptic-hyperbolic equations. We show that this system is a Riesz basis in the space L ₂(0, π/2) and construct the biorthogonal system.     

Approximation of curves by polygons

Let A be a smooth curve in a Euclidean space E given by an arc length parametrization f: [0, 1] → E. Let π_n = {0 = t₀ ≤ t₁ ≤ … ≤ t_n = 1} be a partition of [0, 1] and let P_n be the polygon with vertices f(t₀), f(t₁),…, f(t_n). Let L(A) and L(P_n) denote the lengths of A and P_n, respectively. The paper investigates the behavior of n² |L(A) ? L(P_n)| when the partition π_n is induced by the sequence nθ(mod 1) for some irrational number θ. It turns out that this behavior depends on the partial quotients of the continued fraction expansion of θ.     

On the semiring of cone preserving maps

If K is a proper cone in Rⁿ, then the cone of all linear operators that preserve K, denoted by π(K), forms a semiring under usual operator addition and multiplication. Recently J.G. Horne examined the ideals of this semiring. He proved that if K₁, K₂ are polyhedral cones such that π(K₁) and π(K₂) are isomorphic as semirings, then K₁ and K₂ are linearly isomorphic. The study of this semiring is continued in this paper. In Sec. 3 ideals of π(K) which are also faces are characterized. In Sec. 4 it is shown that π(K) has a unique minimal two-sided ideal, namely, the dual cone of π(K¹), where K¹ is the dual cone of K. Extending Horne's result, it is also proved that the cone K is characterized by this unique minimal two-sided ideal of π(K). The set of all faces of π(K) inherits a quotient semiring structure from π(K). Properties of this face-semiring are given in Sec. 5. In particular, it is proved that this face-semiring admits no nontrivial congruence relation iff the duality operator of π(K) is injective. In Sec. 6 the maximal one-sided and two-sided ideals of π(K) are identified. In Sec. 8 it is shown that π(K) never satisfies the ascending-chain condition on principal one-sided ideals. Some partial results on the question of topological closedness of principal one-sided ideals of π(K) are also given.     

Statistical and structural analysis of the appearance of prime numbers

We examine the distribution of the ratio of addition to multiplication over standard atomic sets of integers. By analyzing the array of conversion ratios and selected sub-arrays, we prove that the reciprocal of the mean of the conversion ratio distribution converges to the prime-counting function π(n). We also show that the modified mean of the sub-array C ⁵, which is obtained from the array of conversion ratios by scaling and translation, converges to π(n) with an accuracy comparable to the Li-function. We go on to numerically show that the relative behaviors of L(n), $1/H_{n}^{5}$ and Li(n) with respect to π(n) are similar, and that π(n)/L(n), $\pi(n)/(1/H_{n}^{5})$ and π(n)/Li(n) provide approximations of competitive accuracy at the center of the distribution.     

Equiconvergence of the trigonometric Fourier series and the expansion in eigenfunctions of the Sturm-Liouville operator with a distribution potential

We consider the Sturm-Liouville operator L = ?d ²/dx ² + q(x) with the Dirichlet boundary conditions in the space L ₂[0, π] under the assumption that the potential q(x) belongs to W ₂ ^?1 [0, π]. We study the problem of uniform equiconvergence on the interval [0, π] of the expansion of a function f(x) in the system of eigenfunctions and associated functions of the operator L and its Fourier sine series expansion. We obtain sufficient conditions on the potential under which this equiconvergence holds for any function f(x) of class L ₁. We also consider the case of potentials belonging to the scale of Sobolev spaces W ₂ ^?θ [0, π] with ½ < θ ≤ 1. We show that if the antiderivative u(x) of the potential belongs to some space W ₂ ^θ [0, π] with 0 < θ < 1/2, then, for any function in the space L ₂[0, π], the rate of equiconvergence can be estimated uniformly in a ball lying in the corresponding space and containing u(x). We also give an explicit estimate for the rate of equiconvergence.     

The Length of the Longest Increasing Subsequence of a Random Mallows Permutation

The Mallows measure on the symmetric group S _n is the probability measure such that each permutation has probability proportional to q raised to the power of the number of inversions, where q is a positive parameter and the number of inversions of π is equal to the number of pairs i<j such that π _i >π _j . We prove a weak law of large numbers for the length of the longest increasing subsequence for Mallows distributed random permutations, in the limit that n→∞ and q→1 in such a way that n(1?q) has a limit in R.     

On a class of relatively prime sequences

For each natural number n, let a₀(n) = n, and if a₀(n),…,a_i(n) have already been defined, let a_i+1(n) > a_i(n) be minimal with (a_i+1(n), a₀(n) … a_i(n)) = 1. Let g(n) be the largest a_i(n) not a prime or the square of a prime. We show that g(n) ～ n and that $\text{g(n) > n + cn}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{log}\text{(n)}$ for some c > 0. The true order of magnitude of g(n) ? n seems to be connected with the fine distribution of prime numbers. We also show that “most” a_i(n) that are not primes or squares of primes are products of two distinct primes. A result of independent interest comes of one of our proofs: For every sufficiently large n there is a prime $\text{p < n}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$ with [$\text{n}\text{p}$] composite.     

On the best approximation by trigonometric polynomials on convolution classes of analytic periodic functions

For a continuous 2π-periodic real-valued function K(t), whose amplitudes decrease as a geometric progression with a denominator q ∈ (0, 1) starting from a given number n ∈ ?, we find sharp upper bounds for q ensuring that K(t) satisfies the Nagy condition N* _n .