Self-adjusting stochastic processes

Let A_t(i, j) be the transition matrix at time t of a process with n states. Such a process may be called self-adjusting if the occurrence of the transition from state h to state k at time t results in a change in the hth row such that A_t+1(h, k) ? A_t(h, k). If the self-adjustment (due to transition h → kx) is A_{t + 1}(h, j) = λA_t(h, j) + (1 ? λ)δ_jk (0 < λ < 1), then with probability 1 the process is eventually periodic. If A₀(i, j) < 1 for all i, j and if the self-adjustment satisfies A_{t + 1}(h, k) = ?(A_t(h, k)) with ?(x) twice differentiable and increasing, x < ?(x) < 1 for 0 ? x < 1,?(1) = ?′(1) = 1, then, with probability 1, lim A_t does not exist.     

A matrix of permanents

If A is a matrix of order n×(n?2), n?3, denote by ā the n×n matrix whose (i,j)th entry is zero if i=j, and if i≠j, is the permanent of the submatrix of A obtained by deleting its ith and jth rows. It is shown that if A is a nonnegative n×(n?2) matrix, then ā is nonsingular if and only if A has no zero submatrix of n?1 lines. This is used to give precise consequences of the occurrence of equality in Alexandroff's inequality.     

On a class of martingale inequalities

Let Z = {Z₀, Z₁, Z₂,…} be a martingale, with difference sequence X₀ = Z₀, X_i = Z_i ? Z_{i ? 1}, i ≥ 1. The principal purpose of this paper is to prove that the best constant in the inequality λP(sup_i |X_i| ≥ λ) ≤ C sup_iE |Z_i|, for λ > 0, is C = (log 2)^?1. If Z is finite of length n, it is proved that the best constant is $\text{C}{}_{\mathrm{n}}\text{= [n(2}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}\text{? 1)]}{}^{\mathrm{?1}}$. The analogous best constant C_n(z) when Z₀ ≡ z is also determined. For these finite cases, examples of martingales attaining equality are constructed. The results follow from an explicit determination of the quantity G_n(z, E) = sup_zP(max_i=1,…,n |X_i| ≥ 1), the supremum being taken over all martingales Z with Z₀ ≡ z and E|Z_n| = E. The expression for G_n(z,E) is derived by induction, using methods from the theory of moments.     

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.     

Upper triangular operator matrices with the single-valued extension property

If A=(Aij)_1?i,j?n∈B(X) is an upper triangular Banach space operator such that AiiAij=AijAjj for all 1?i?j?n, then A has SVEP or satisfies (Dunford's) condition (C) or (Bishop's) property (β) or (the decomposition) property (δ) if and only if Aii, 1?i?n, has the corresponding property.     

Fast canonization of circular strings

A circular string A = (a₁,…,a_n) is a string that has n equivalent linear representations A_i = a_i,…,a_n,a₁,…,a_i?1 for i = 1,…,n. The a_i's are assumed to be well ordered. We say that A_i < A_j if the word a_i…a_na₁…a_i?1 precedes the word a_j…a_na₁…a_j?1 in the lexicographic order, A_i ? A_j if either A_i < A_j or A_i = A_j. A_i0 is a minimal representation of A if A_i0 ? A_i for all 1 ≤ i ≤ n. The index i₀ is called a minimal starting point (m.s.p.). In this paper we discuss the problem of finding m.s.p. of a given circular string. Our algorithm finds, in fact, all the m.s.p.'s of a given circular string A of length n by using at most $\text{n + ?}\text{d}\text{2}\text{?}$ comparisons. The number d denotes the difference between two successive m.s.p.'s (see Lemma 1.1) and is equal to n if A has a unique m.s.p. Our algorithm improves the result of 3n comparisons given by K. S. Booth. Only constant auxiliary storage is used.     

Some explicit formulae in simultaneous padé approximation

Using old results on the explicit calculation of determinants, formulae are given for the coefficients of P₀(z) and P₀(z)f_i(z) ? P_i(z), where P_i(z) are polynomials of degree σ ? ρ_i (i=0,1,…,n), P₀(z)f_i(z) ? P_i(z) are power series in which the terms with z^k, 0?k?σ, vanish (i=1,2,…,n), (ρ₀,ρ₁,…,ρ_n) is an (n+1)-tuple of nonnegative integers, σ=ρ₀+ρ₁+?+ρ_n, and {f_i}ⁿ_i=1 is the set of hypergeometric functions {₁F₁(1;c_i;z)}ⁿ_i=1$\text{(c}{}_{\mathrm{i}}\text{?}\text{Z}\text{z.drule;}\text{N}\text{, c}{}_{\mathrm{i}}\text{? c}{}_{\mathrm{j}}\text{?}\text{Z}\text{)}$ or {₂F₀(a_i,1;z)}ⁿ_i=1$\text{(a}{}_{\mathrm{i}}\text{?}\text{Z}\text{?}\text{N}\text{, a}{}_{\mathrm{i}}\text{? a}{}_{\mathrm{j}}\text{?}\text{Z}\text{)}$ under the condition ρ₀?ρ_i ? 1 (i=1,2,…,n).     

The complexity of generalized clique packing

The K_i - j packing problem P_{i, j} is defined as follows: Given a graph G and integer k does there exist a set of at least kK_i's in G such that no two of these K_i's intersect in more than j nodes. This problem includes such problems as matching, vertex partitioning into complete subgraphs and edge partitioning into complete subgraphs. In this paper it is shown thhat for i ? 3 and 0?j?i ?2 the P_{i, j} problems is NP-complete. Furthermore, the problems remains NP-complete for i?3 and 1?j?i ?2 for chordal graphs.     

Davenport constant with weights and some related questions, II

Let G be a finite abelian group of order n and let A⊆Z be non-empty. Generalizing a well-known constant, we define the Davenport constant of G with weight A, denoted by DA(G), to be the least natural number k such that for any sequence (x₁,…,xk) with xi∈G, there exists a non-empty subsequence (xj₁,…,xjl) and a₁,…,al∈A such that . Similarly, for any such set A, EA(G) is defined to be the least t∈N such that for all sequences (x₁,…,xt) with xi∈G, there exist indices j₁,…,jn∈N,1?j₁<?<jn?t, and ?₁,…,?n∈A with . In the present paper, we establish a relation between the constants DA(G) and EA(G) under certain conditions. Our definitions are compatible with the previous generalizations for the particular group G=Z/nZ and the relation we establish had been conjectured in that particular case.     

Maximum principle and propagation for intrinsicly regular solutions of differential inequalities structured on vector fields

We prove suitable versions of the weak maximum principle and of the maximum propagation for solutions u of a differential inequality Hu?0. Here H=_∑i,jai,j(z)ZiZj+Z₀ is a differential operator structured on the vector fields Zj's, whereas u belongs to an appropriate intrinsic class of regularity modelled on the Zj's.     

Effective Fast Algorithms for Polynomial Spectral Factorization

Let p(z) be a polynomial of degree n having zeros |ξ₁|≤???≤|ξ _m |<1<|ξ _m+1|≤???≤|ξ _n |. This paper is concerned with the problem of efficiently computing the coefficients of the factors u(z)=∏ _i=1 ^m (z?ξ _i ) and l(z)=∏ _i=m+1 ⁿ (z?ξ _i ) of p(z) such that a(z)=z ^?m p(z)=(z ^?m u(z))l(z) is the spectral factorization of a(z). To perform this task the following two-stage approach is considered: first we approximate the central coefficients x _?n+1,. . .x _n?1 of the Laurent series x(z)=∑ _i=?∞ ^+∞ x _i z ⁱ satisfying x(z)a(z)=1; then we determine the entries in the first column and in the first row of the inverse of the Toeplitz matrix T=(x _i?j ) _i,j=?n+1,n?1 which provide the sought coefficients of u(z) and l(z). Two different algorithms are analyzed for the reciprocation of Laurent polynomials. One algorithm makes use of Graeffe's iteration which is quadratically convergent. Differently, the second algorithm directly employs evaluation/interpolation techniques at the roots of 1 and it is linearly convergent only. Algorithmic issues and numerical experiments are discussed.     

A new inequality for symmetric functions

Let x_i ≥ 0, y_i ≥ 0 for i = 1,…, n; and let a_j(x) be the elementary symmetric function of n variables given by a_j(x) = ∑_{1 ≤ ii < … <ij ≤ n}x_ii … x_ij. Define the partical ordering x <y if a_j(x) ≤ a_j(y), j = 1,… n. We show that $\text{x}\text{\$}\text{?}\text{y ? x}{}^{\mathrm{\alpha }}\text{\$}\text{?}\text{y}{}^{\mathrm{\alpha }}\text{, 0}\text{\$}\text{?}\text{α ≤ 1}$, where {x^α}_i = x^α_i. We also give a necessary and sufficient condition on a function f(t) such that x <y ? f(x) <f(y). Both results depend crucially on the following: If x <y there exists a piecewise differentiable path z(t), with z_i(t) ≥ 0, such that z(0) = x, z(1) = y, and z(s) <z(t) if 0 ≤ s ≤ t ≤ 1.     

On Kendall's Process

LetZ₁, …, Z_nbe a random sample of sizen?2 from ad-variate continuous distribution functionH, and letV_i, nstand for the proportion of observationsZ_j,j≠i, such thatZ_j?Z_icomponentwise. The purpose of this paper is to examine the limiting behavior of the empirical distribution functionK_nderived from the (dependent) pseudo-observationsV_i, n. This random quantity is a natural nonparametric estimator ofK, the distribution function of the random variableV=H(Z), whose expectation is an affine transformation of the population version of Kendall's tau in the cased=2. Since the sample version ofτis related in the same way to the mean ofK_n, Genest and Rivest (1993,J. Amer. Statist. Assoc.) suggested that[formula]be referred to as Kendall's process. Weak regularity conditions onKandHare found under which this centered process is asymptotically Gaussian, and an explicit expression for its limiting covariance function is given. These conditions, which are fairly easy to check, are seen to apply to large classes of multivariate distributions.     

A note on bideterminants for Schur superalgebras

Let S(m|n,r)_Z be a Z-form of a Schur superalgebra S(m|n,r) generated by elements ξ_i,j. We solve a problem of Muir and describe a Z-form of a simple S(m|n,r)-module D_λ,Q over the field Q of rational numbers, under the action of S(m|n,r)_Z. This Z-form is the Z-span of modified bideterminants [T_?:T_i] defined in this work. We also prove that each [T_?:T_i] is a Z-linear combination of modified bideterminants corresponding to (m|n)-semistandard tableaux T_i.     

Conditional ordering of order statistics

For any positive integers m and n, let X₁,X₂,…,X_m∨n be independent random variables with possibly nonidentical distributions. Let X_1:n≤X_2:n≤?≤X_n:n be order statistics of random variables X₁,X₂,…,X_n, and let X_1:m≤X_2:m≤?≤X_m:m be order statistics of random variables X₁,X₂,…,X_m. It is shown that (X_j:n,X_j+1:n,…,X_n:n) given X_i:m>y for j−i≥max{n−m,0}, and (X_1:n,X_2:n,…,X_j:n) given X_i:m≤y for j−i≤min{n−m,0} are all increasing in y with respect to the usual multivariate stochastic order. We thus extend the main results in Dubhashi and Häggström (2008) [1] and Hu and Chen (2008) [2].     

A stochastic permutation-flowshop scheduling problem minimizing in distribution the schedule length

Consider n jobs (J₁,J₂,…,J_n) and m machines (M₁,M₂…,M_m). Upon completion of processing of J_i, 1 ? i ? n, on M_j 1 ? j ? m ? 1, it departs with probability p_i or moves to M_j+1 with the complementary probability, 1?p_i. A job completing service on M_m departs. The processing time of j_i on M_j possesses a distribution function F_j. It is proved that sequencing the jobs in a nondecreasing order of p_i minimizes in distribution the schedule length.     

Transition matrices for well-conditioned Markov chains

Let T∈R^n×n be an irreducible stochastic matrix with stationary distribution vector π. Set A = I − T, and define the quantity , where A_j, j = 1, … , n, are the (n − 1) × (n − 1) principal submatrices of A obtained by deleting the jth row and column of A. Results of Cho and Meyer, and of Kirkland show that κ₃ provides a sensitive measure of the conditioning of π under perturbation of T. Moreover, it is known that .In this paper, we investigate the class of irreducible stochastic matrices T of order n such that , for such matrices correspond to Markov chains with desirable conditioning properties. We identify some restrictions on the zero-nonzero patterns of such matrices, and construct several infinite classes of matrices for which κ₃ is as small as possible.     

Asymptotic separation for independent trajectories of Markov processes

We say that n independent trajectories ξ₁(t),…,ξ _n (t) of a stochastic process ξ(t)on a metric space are asymptotically separated if, for some ɛ > 0, the distance between ξ _i (t _i ) and ξ _j (t _j ) is at least ɛ, for some indices i, j and for all large enough t ₁,…,t _n , with probability 1. We prove sufficient conitions for asymptotic separationin terms of the Green function and the transition function, for a wide class of Markov processes. In particular,if ξ is the diffusion on a Riemannian manifold generated by the Laplace operator Δ, and the heat kernel p(t, x, y) satisfies the inequality p(t, x, x) ≤ Ct ^−ν/2 then n trajectories of ξ are asymptotically separated provided . Moreover, if for some α∈(0, 2)then n trajectories of ξ^(α) are asymptotically separated, where ξ^(α) is the α-process generated by −(−Δ)^α/2. Received: 10 June 1999 / Revised version: 20 April 2000 / Published online: 14 December 2000 RID="*" ID="*" Supported by the EPSRC Research Fellowship B/94/AF/1782 RID="**" ID="**" Partially supported by the EPSRC Visiting Fellowship GR/M61573     

On Ochoa's special matrices in matrix classes

It is well known that the ideal classes of an order Z[μ], generated over Z by the integral algebraic number μ, are in a bijective correspondence with certain matrix classes, that is, classes of unimodularly equivalent matrices with rational integer coefficients. If the degree of μ is ?3, we construct explicitly a particularly simple ideal matrix for an ideal which is a product of different prime ideals of degree 1. We obtain the following special n×n matrix (c_ij) in the matrix class corresponding to the ideal class of our ideal: c_i+1,_i=1(i=1,…,n?2); c_ij=0(?i?n, 1?j?n? 2, and i≠j+1); c_nj=0(j)=2,…,n?1). The remaining coefficients are given as explicit polynomials in an integer z which depends on the ideal. It is shown that the matrix class of every regular ideal class of Z[μ] contains a special matrix of this kind.