Absolute regularity and functions of Markov chains

We first give an extension of a theorem of Volkonskii and Rozanov characterizing the strictly stationary random sequences satisfying ‘absolute regularity’. Then a strictly stationary sequence {X_k, k = …, ?1, 0, 1,…} is constructed which is a 0?1 instantaneous function of an aperiodic Markov chain with countable irreducible state space, such that n^?2 var (X₁ + ? + X_n) approaches 0 arbitrarily slowly as n → ∞ and (X₁ + ? + X_n) is partially attracted to every infinitely divisible law.     

On the average number of records for sequences of not identically distributed random variables

The scheme of n series of independent random variables X ₁₁, X ₂₁, …, X _k1, X ₁₂, X ₂₂, …, X _k2, …, X _1n , X _2n , …, X _kn is considered. Each of these successive series X _1m , X _2m , …, X _km , m = 1, 2, …, n consists of k variables with continuous distribution functions F ₁, F ₂, …, F _k , which are the same for all series. Let N(nk) be the number of upper records of the given nk random variables, and EN(nk) be the corresponding expected value. For EN(nk) exact upper and lower estimates are obtained. Examples are given of the sets of distribution functions for which these estimates are attained.     

Matchings in starlike trees

Let m(G,k) be the number of k-matchings in the graph G. We write G₁ ⪯ G₂ if m(G₁, k) ≤ m(G₂, k) for all k = 1, 2,…. A tree is said to be starlike if it possesses exactly one vertex of degree greater than two. The relation T₁ ⪯ T₂ is shown to hold for various pairs of starlike trees T₁, T₂. The starlike trees (with a given number of vertices), extremal with respect to the relation ⪯, are characterized.     

Clones satisfying the term condition

The term condition considered here is the property of an operation ? that holds iff ? and all of its variants obtained by permuting the variables satisfy (for all x,y,u₁,…v₁,…)$\text{?(x,u}{}_1\text{,…) = ?(x,v}{}_1\text{…)??(y,u}{}_1\text{,…) = ?(y,v)}{}_1\text{,…)}$. Clones consisting entirely of operations satisfying this term condition are called TC clones; algebras whose clone of term operations is a TC clone are called TC algebras; varieties such that every algebra in the variety is a TC algebra are called TC varieties. The paper is a systematic study of these notions, giving primary attention to operations and algebras on finite base sets, and to varieties generated by finite algebras. It is proved, among other results, that the number of n-ary TC operations on a k-element set is logarithmically asymptotic to k^(k?1)n when n increases without bound and k is held fixed; that there exist only countably many TC clones on any finite set; that the maximal TC clones on a finite set are finite in number (for each set). Some necessary conditions for an algebra to generate a TC variety are given, also some sufficient conditions.     

Quasi‐randomness of graph balanced cut properties

Quasi‐random graphs can be informally described as graphs whose edge distribution closely resembles that of a truly random graph of the same edge density. Recently, Shapira and Yuster proved the following result on quasi‐randomness of graphs. Let k ≥ 2 be a fixed integer, α₁,…,α_k be positive reals satisfying \begin{align*}\sum_{i} \alpha_i = 1\end{align*} and (α₁,…,α_k)≠(1/k,…,1/k), and G be a graph on n vertices. If for every partition of the vertices of G into sets V ₁,…,V _k of size α₁n,…,α_kn, the number of complete graphs on k vertices which have exactly one vertex in each of these sets is similar to what we would expect in a random graph, then the graph is quasi‐random. However, the method of quasi‐random hypergraphs they used did not provide enough information to resolve the case (1/k,…,1/k) for graphs. In their work, Shapira and Yuster asked whether this case also forces the graph to be quasi‐random. Janson also posed the same question in his study of quasi‐randomness under the framework of graph limits. In this paper, we positively answer their question. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Additive and multiplicative relations connecting conjugate algebraic numbers

We investigate the problem of finding for which sets of integers a₁,…, a_k either of the equations Σ_{i = 1}^k a_iα_i = 0 or Π_{i = 1}^k α_i^a_i = 1 has a non-trivial solution in (not necessarily distinct) conjugate algebraic numbers α₁,…, α_k. The problem turns out to be connected with the existence of certain latin squares having zero determinant.     

A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks

In the complete graph on n vertices, when each edge has a weight which is an exponential random variable, Frieze proved that the minimum spanning tree has weight tending to ζ(3) = 1/1³ + 1/2³ + 1/3³ +… as n → ∞. We consider spanning trees constrained to have depth bounded by k from a specified root. We prove that if k ≥ log₂ logn+ω(1), where ω(1) is any function going to ∞ with n, then the minimum bounded-depth spanning tree still has weight tending to ζ(3) as n → ∞, and that if k < log₂ logn, then the weight is doubly-exponentially large in log₂ logn ? k. It is NP-hard to find the minimum bounded-depth spanning tree, but when k≤log₂ logn?ω(1), a simple greedy algorithm is asymptotically optimal, and when k ≥ log₂ logn+ω(1), an algorithm which makes small changes to the minimum (unbounded depth) spanning tree is asymptotically optimal. We prove similar results for minimum bounded-depth Steiner trees, where the tree must connect a specified set of m vertices, and may or may not include other vertices. In particular, when m=const×n, if k≥log₂ logn+ω(1), the minimum bounded-depth Steiner tree on the complete graph has asymptotically the same weight as the minimum Steiner tree, and if 1 ≤ k ≤ log₂ logn?ω(1), the weight tends to $(1 - 2^{ - k} )\sqrt {8m/n} \left[ {\sqrt {2mn} /2^k } \right]^{1/(2^k - 1)}$ in both expectation and probability. The same results hold for minimum bounded-diameter Steiner trees when the diameter bound is 2k; when the diameter bound is increased from 2k to 2k+1, the minimum Steiner tree weight is reduced by a factor of $2^{1/(2^k - 1)}$ .     

A note on the flow time and the number of tardy jobs in stochastic open shops

In this note open shops with two machines are considered. The processing time of job j, j = 1, …, n, on machine 1 (2) is a random variable X_j (Y_j), which is exponentially distributed with rate γ (μ). If the completion time of job j is C_j, a waiting cost is incurred of g(C_j), where g is a function that is increasing concave. The preemptive policy that minimizes the total expected waiting cost E(Σg(C_j)) is determined. Two machine open shops with jobs that have random due dates are considered as well. For the case where the due dates D₁,…,D_n are exchangeable, the preemptive policy that minimizes the expected number of tardy jobs is determined.     

The general divisor problem

Let Δ_k(x) = Δ(a₁, …, a_k; x) be the error term in the asymptotic formula for the summatory function of the general divisor function d(a₁, …, a_k; n), which is generated by ζ(a₁s) … ζ(a_ks) (1 ≤ a₁ ≤ … ≤ a_k are fixed integers). Precise omega results for the mean square integral ∫₁^x Δ_k²(x) dx are given, with applications to some specific divisor problems.     

Regression estimates of inputs to an M(t)/G/∞ service system

Three problems are solved: proof of convergence in distribution of a sequence {N^k(t)} of nonhomogeneous Poisson random variables to a nonhomogeneous Poisson random variable N(t); construction of a sequence of multiple linear regression models whose conditional expectations equal E(N^k(t)) (k = 1,2, …) aside from an additive constant; exploration of L₁ and L₂ criteria for estimating parameters of the regression models. Presentation of a numerical analysis of a case study involving a M(t)/M/∞ system of reproduction (arrivals) and mortality (services) within a biological population concludes the paper. Potential problems of interpreting parameter estimates obtained from linear programming implementations of the L₁ fitting criterion are analyzed.     

Some results on starlike trees and sunlike graphs

A tree is called starlike if it has exactly one vertex of degree greater than two. In [4] it was proved that two starlike treesG andH are cospectral if and only if they are isomorphic. We prove here that there exist no two non-isomorphic Laplacian cospectral starlike trees. Further, letG be a simple graph of ordern with vertex setV(G)={1,2, …,n} and letH={H ₁,H ₂, ...H _n } be a family of rooted graphs. According to [2], the rooted productG(H) is the graph obtained by identifying the root ofH _i with thei-th vertex ofG. In particular, ifH is the family of the paths $P_{k_1 } , P_{k_2 } , ..., P_{k_n } $ with the rooted vertices of degree one, in this paper the corresponding graphG(H) is called the sunlike graph and is denoted byG(k ₁,k ₂, …,k _n ). For any (x ₁,x ₂, …,x _n ) ∈I _* ⁿ , whereI _*={0,1}, letG(x ₁,x ₂, …,x _n ) be the subgraph ofG which is obtained by deleting the verticesi ₁, i₂, …,i _j ∈ V(G) (0≤j≤n), provided that $x_{i_1 } = x_{i_2 } = ... = x_{i_j } = 0$ . LetG(x ₁,x ₂,…, x _n] be the characteristic polynomial ofG(x ₁,x ₂,…, x _n ), understanding thatG[0, 0, …, 0] ≡ 1. We prove that $$G[k_1 , k_2 ,..., k_n ] = \Sigma _{x \in ^{I_ * ^n } } \left[ {\Pi _{i = 1}^n P_{k_i + x_i - 2} (\lambda )} \right]( - 1)^{n - (\mathop \Sigma \limits_{i = 1}^n x_i )} G[x_1 , x_2 , ..., x_n ]$$ where x=(x ₁,x ₂,…,x _n );G[k ₁,k ₂,…,k _n ] andP _n (γ) denote the characteristic polynomial ofG(k ₁,k ₂,…,k _n ) andP _n , respectively. Besides, ifG is a graph with λ₁(G)≥1 we show that λ₁(G)≤λ₁(G(k ₁,k ₂, ...,k _n )) < for all positive integersk ₁,k ₂,…,k _n , where λ₁ denotes the largest eigenvalue.     

Applications of the Wronskian and Gram matrices of {tieλkt}

A review is made of some of the fundamental properties of the sequence of functions {tⁱe^λ_k^t}, k = 1,…,s, i = 0,…,m_k?1, distinct λ _i. In particular it is shown how the Wronskian and Gram matrices of this sequence of functions appear naturally in such fields as spectral matrix theory, controllability, and Lyapunov stability theory.     

Asymptotics of products of nonnegative random matrices

Asymptotic properties of products of random matrices ξ _k = X _k …X ₁ as k → ∞ are analyzed. All product terms X _i are independent and identically distributed on a finite set of nonnegative matrices A = {A ₁, …, A _m }. We prove that if A is irreducible, then all nonzero entries of the matrix ξ _k almost surely have the same asymptotic growth exponent as k→∞, which is equal to the largest Lyapunov exponent λ(A). This generalizes previously known results on products of nonnegative random matrices. In particular, this removes all additional “nonsparsity” assumptions on matrices imposed in the literature.We also extend this result to reducible families. As a corollary, we prove that Cohen’s conjecture (on the asymptotics of the spectral radius of products of random matrices) is true in case of nonnegative matrices.     

A symmetry relationship for a class of partitions

Let S(n, k, v) denote the number of vectors (a₀,…, a_n?1) with nonnegative integer components that satisfy a₀ + … + a_{n ? 1} = k and Σ_i=0^n?1ia_i ≡ v (mod n). Two proofs are given for the relation S(n, k, v) = S(k, n, v). The first proof is by algebraic enumeration while the second is by combinatorial construction.     

A function with prescribed initial derivatives in different Banach spaces

Let X₀ ? X₁ ? ··· ? X_p be Banach spaces with continuous injection of X_k into X_{k + 1} for 0 ? k ? p ? 1, and with X₀ dense in X_p. We seek a function u: [0, 1] → X₀ such that its kth derivative u^(k), k = 0, 1,…, p, is continuous from [0, 1] into x_k, and satisfies the initial condition u^(k)(0) = a_k?X_k. It is shown that such a function exists if and only if the initial values a₀, a₁, …, a_p satisfy a certain condition reminiscent of interpolation theory. This condition always holds when p = 1; when p ? 2, the spaces X_k (k = 0, 1, …, p) may or may not be such that the desired function exists for any given initial values a_k?X_k.     

Constructing trees with prescribed cardinalities for the components of their vertex deleted subgraphs

Consider a vertex v of a tree T. By deleting v and its incidentadges, a family of subtrees {T_l^v,…,T_k^v} and a sequence of strictly positive integers $\text{v}\text{= (s}{}_{\mathrm{<mtext>l</mtext>}}\text{,…,s}{}_{\mathrm{k}}\text{)}$ are obtained, where every s_i is the number of vertices in the subtree T_i^v. Let V_T denote the family of these sequences corresponding to the vertices of T. Polynomial time algorithms are described to answer the following questions: Given a family W of strictly positive integer sequences, is there a free tree T such that V_T = W? If there is such a tree, are there two nonisomorphic trees T₁, T₂ having V_T1 = V_T2? Based on these algorithms, an algorithm to construct all the nonisomorphic free trees T having V_T = W can be sketched.     

On the value of a random minimum spanning tree problem

Suppose we are given a complete graph on n vertices in which the lenghts of the edges are independent identically distributed non-negative random variables. Suppose that their common distribution function F is differentiable at zero and D = F′ (0) > 0 and each edge length has a finite mean and variance. Let L_n be the random variable whose value is the length of the minimum spanning tree in such a graph. Then we will prove the following: lim_{n → ∞}E(L_n) = ζ(3)/D where ζ(3) = Σ_{k = 1}^∞ 1/k³ = 1.202… and for any ε > 0 lim_{n → ∞} Pr(|L_n^?ζ(3)/D|) > ε) = 0.     

On additive maps of prime rings satisfying the engel condition

Let A be a prime ring with nonzero right ideal R and f : R → A an additive map. Next, let k,n₁, n₂,…,n_k be natural numbers. Suppose that […[[(x), xn¹], xn²],…, xn^k]=0 for all x ∈ R. Then it is proved in Theorem 1.1 that [f(x),x]=0 provided that either char(A)=0 or char (A)> n₁+n₂+ …+n_k Theorem 1.1 is a simultaneous generalization of a number of results proved earlier.     

Permanents of d-dimensional matrices

Let A = (A_i1i2…_id) be an n₁ × n₂ × · × n_d matrix over a commutative ring. The permanent of A is defined by per (A) = ∑πⁿ_1i = ₁A_iσ2(_i)σ₃(_i)…σ_d(_i), where the summation ranges over all one-to-one functions σ_k from {1,2,…, n₁} to {1,2,…, n_k}, k = 2,3,…, d. In this paper it is shown that a number of properties of permanents of 2-dimensional matrices extend to higher-dimensional matrices. In particular, permanents of nonnegative d-dimensional matrices with constant hyperplane sums are investigated. The paper concludes by introducing s-permanents, which generalize the definition above that the permanent becomes the 1-permanent, and showing that an s-permanent can always be converted into a 1-permanent.     

Compound Geometric Distribution of Order <Emphasis Type="Italic">k</Emphasis>

The distribution of the number of trials until the first k consecutive successes in a sequence of Bernoulli trials with success probability p is known as geometric distribution of order k. Let T _k be a random variable that follows a geometric distribution of order k, and Y ₁,Y ₂,… a sequence of independent and identically distributed discrete random variables which are independent of T _k . In the present article we develop some results on the distribution of the compound random variable \(S_{k} =\sum_{t=1}^{T_{k}}Y_{t}\).