Score sets ink-partite tournaments

The set S of distinct scores (outdegrees) of the vertices of ak-partite tournamentT(X ₁, X₂, ···, X_k) is called its score set. In this paper, we prove that every set of n non-negative integers, except {0} and {0, 1}, is a score set of some 3-partite tournament. We also prove that every set ofn non-negative integers is a score set of somek-partite tournament for everyn ≥k ≥ 2.     

Sums and differences of four kth powers

We prove an upper bound for the number of representations of a positive integer N as the sum of four kth powers of integers of size at most B, using a new version of the determinant method developed by Heath-Brown, along with recent results by Salberger on the density of integral points on affine surfaces. More generally we consider representations by any integral diagonal form. The upper bound has the form O_N(B^c/?k){O_{N}(B^{c/\sqrt{k}})}, whereas earlier versions of the determinant method would produce an exponent for B of order k ^−1/3 (uniformly in N) in this case. Furthermore, we prove that the number of representations of a positive integer N as a sum of four kth powers of non-negative integers is at most O_e(N^1/k+2/k3/2+e){O_{\varepsilon}(N^{1/k+2/k^{3/2}+\varepsilon})} for k ≥ 3, improving upon bounds by Wisdom.     

On the structure of the sumsets

Let A be a set of nonnegative integers. For h≥2, denote by hA the set of all the integers representable by a sum of h elements from A. In this paper, we prove that, if k≥3, and A={a₀,a₁,…,a_k−1} is a finite set of integers such that 0=a₀<a₁<?<a_k−1 and (a₁,…,a_k−1)=1, then there exist integers c and d and sets C⊆[0,c−2] and D⊆[0,d−2] such that hA=C∪[c,ha_k−1−d]∪(ha_k−1−D) for all . The result is optimal. This improves Nathanson’s result: h≥max{1,(k−2)(a_k−1−1)a_k−1}.     

Another look at independence of hitting place and time for the simple random walk

Results of Samuels and Wendel for the simple random walk with drift on the integers which assert independence of interarrival times at the sets {a?r, a+r}, r=1, 2…, k and the arrival position in the set {a?k,a+k}, where a is the starting point, are reobtained by treating the walk as a Markov chain, and considering related chains conditional on absorption at a specified barrier.     

Moments of Absorption Time for a Conditioned Random Walk

A random walk on the set of integers {0,1,2,...,a} with absorbing barriers at 0 and a is considered. The transition times from the integers z (0<z<a) are random variables with finite moments. The nth moment of the time to absorption at a, D_z,n, conditioned on the walk starting at z and being absorbed at a, is discussed, and a difference equation with boundary values and initial values for D_z,n is given. It is solved in several special cases. The problem is motivated by questions from biology about tumor growth and multigene evolution which are discussed.     

A note on a special case of the Frobenius problem

For a set of positive and relative prime integers A = {a ₁…,a _k }, let Γ(A) denote the set of integers of the form a ₁ x ₁+…+a _k x _k with each x _j ≥ 0. Let g(A) (respectively, n(A) and s(A)) denote the largest integer (respectively, the number of integers and sum of integers) not in Γ(A). Let S*(A) denote the set of all positive integers n not in Γ(A) such that n + Γ(A) \ {0} ? Γ((A)\{0}. We determine g(A), n(A), s(A), and S*(A) when A = {a, b, c} with a | (b + c).     

The Minimum Rank of a 3 × 3 Partial Block Matrix

After recalling the definition and some basic properties of finite hypergroups—a notion introduced in a recent paper by one of the authors—several non-trivial examples of such hypergroups are constructed. The examples typically consist of n n×n matrices, each of which is an appropriate polynomial in a certain tri-diagonal matrix. The crucial result required in the construction is the following: ‘let A be the matrix with ones on the super-and sub-diagonals, and with main diagonal given by a ₁…a _n which are non-negative integers that form either a non-decreasing or a symmetric unimodal sequence; then A_k =P_k (A) is a non-negative matrix, where p_k denotes the characteristic polynomial of the top k× k principal submatrix of A, for k=1,…,n. The matrices A_k as well as the eigenvalues of A, are explicitly described in some special cases, such as (i) a_i =0 for all ior (ii) a_i =0 for i<n and a_n =1. Characters ot finite abelian hypergroups are defined, and that naturally leads to harmonic analysis on such hypergroups.     

Degree sequences of <Emphasis Type="Italic">k</Emphasis>-multi-hypertournaments

Let n and k（n ≥ k 〉 1） be two non-negative integers.A k-multi-hypertournament on n vertices is a pair（V,A）,where V is a set of vertices with ｜V｜=n,and A is a set of k-tuples of vertices,called arcs,such that for any k-subset S of V,A contains at least one（at most k!） of the k! k-tuples whose entries belong to S.The necessary and suffcient conditions for a non-decreasing sequence of non-negative integers to be the out-degree sequence（in-degree sequence） of some k-multi-hypertournament are given.     

The Chromatic Spectrum of Mixed Hypergraphs

 A mixed hypergraph is a triple ℋ=(X, ?, ?), where X is the vertex set, and each of ?, ? is a list of subsets of X. A strict k-coloring of ℋ is a surjection c:X→{1,…,k} such that each member of ? has two vertices assigned a common value and each member of ? has two vertices assigned distinct values. The feasible set of H is {k: H has a strict k-coloring}. Among other results, we prove that a finite set of positive integers is the feasible set of some mixed hypergraph if and only if it omits the number 1 or is an interval starting with 1. For the set {s,t} with 2≤s≤t−2, the smallest realization has 2t−s vertices. When every member of ?∪? is a single interval in an underlying linear order on the vertices, the feasible set is also a single interval of integers. Received: May 24, 1999 Final version received: August 31, 2000     

On a semi-Markov generalization of the random walk

The semi-Markov process studied here is a generalized random walk on the non-negative integers with zero as a reflecting barrier, in which the time interval between two consecutive jumps is given an arbitrary distribution H(t). Our process is identical with the Markov chain studied by Miller [6] in the special case when H(t)=U₁(t), the Heaviside function with unit jump at t=1. By means of a Spitzer-Baxter type identity, we establish criteria for transience, positive and null recurrence, as well as conditions for exponential ergodicity. The results obtained here generalize those of [6] and some classical results in random walk theory [10].     

Sequences of Exponents in Constructing Strongly Annular Products

This paper gives conditions on the behavior of a sequence of holomorphic functions {f _k (z)} and a strictly increasing sequence of positive integers {m _k } that assures the infinite product Pf_k(z^m_k){\Pi f_k(z^{m_k})} is strongly annular. A constructive proof is given that shows if the sequence {f _k (z)} exhibits certain boundary behavior along with a uniform boundedness condition then a number p > 1 exists such that if {m _k } satisfies m _k+1/m _k ≥ p then the above product is strongly annular.     

Random doubly stochastic tridiagonal matrices

Let \begin{align*}{\mathcal T}\end{align*}n be the compact convex set of tridiagonal doubly stochastic matrices. These arise naturally in probability problems as birth and death chains with a uniform stationary distribution. We study ‘typical’ matrices T∈ \begin{align*}{\mathcal T}\end{align*}n chosen uniformly at random in the set \begin{align*}{\mathcal T}\end{align*}n. A simple algorithm is presented to allow direct sampling from the uniform distribution on \begin{align*}{\mathcal T}\end{align*}n. Using this algorithm, the elements above the diagonal in T are shown to form a Markov chain. For large n, the limiting Markov chain is reversible and explicitly diagonalizable with transformed Jacobi polynomials as eigenfunctions. These results are used to study the limiting behavior of such typical birth and death chains, including their eigenvalues and mixing times. The results on a uniform random tridiagonal doubly stochastic matrices are related to the distribution of alternating permutations chosen uniformly at random.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 42, 403–437, 2013     

One-dimensional Tilings Using Tiles with Two Gap Lengths

Let n,p,k,q,l be positive integers with n=k+l+1. Let x₁,x₂, . . . ,x_n be a sequence of positive integers with x₁<x₂<···<x_n. A set {x₁,x₂, . . . ,x_n} is called a set of type (p,k;q,l) if the set of differences {x₂–x₁,x₃–x₂, . . . ,x_n–x_n–1} equals {p, . . . ,p,q, . . . ,q} as a multiset, where p and q appear k and l times, respectively. Among other results, it is shown that for any p,k,q, there exists a finite interval I in the set of integers such that I is partitioned into sets of type (p,k;q,1).     

Distributions of numbers of failures and successes until the first consecutivek successes

Exact distributions of the numbers of failures, successes and successes with indices no less thanl (1lk–1) until the first consecutivek successes are obtained for some {0, 1}-valued random sequences such as a sequence of independent and identically distributed (iid) trials, a homogeneous Markov chain and a binary sequence of orderk. The number of failures until the first consecutivek successes follows the geometric distribution with an appropriate parameter for each of the above three cases. When the {0, 1}-sequence is an iid sequence or a Markov chain, the distribution of the number of successes with indices no less thanl is shown to be a shifted geometric distribution of orderk - l. When the {0, 1}-sequence is a binary sequence of orderk, the corresponding number follows a shifted version of an extended geometric distribution of orderk - l.This research was partially supported by the ISM Cooperative Research Program (92-ISM-CRP-16) of the Institute of Statistical Mathematics.     

Estimating a general function of a quadratic function

Let be an observation from a spherically symmetric distribution with unknown location parameter . For a general non-negative function c, we consider the problem of estimating c(||x − θ||²) under the usual quadratic loss. For p ≥ 5, we give sufficient conditions for improving on the unbiased estimator γ₀ of c(||x − θ||²) by competing estimators γ _s = γ₀ + s correcting γ₀ with a suitable function s. The main condition relies on a partial differential inequality of the form k Δs + s ² ≤ 0 for a certain constant k ≠ 0. Our approach unifies, in particular, the two problems of quadratic loss estimation and confidence statement estimation and allows to derive new results for these two specific cases. Note that we formally establish our domination results (that is, with no recourse to simulation).      

The age of a Markov process

The concept of a limiting conditional age distribution of a continuous time Markov process whose state space is the set of non-negative integers and for which {0} is absorbing is defined as the weak limit as t→∞ of the last time before t an associated “return” Markov process exited from {0} conditional on the state, j, of this process at t. It is shown that this limit exists and is non-defective if the return process is ρ-recurrent and satisfies the strong ratio limit property. As a preliminary to the proof of the main results some general results are established on the representation of the ρ-invariant measure and function of a Markov process. The conditions of the main results are shown to be satisfied by the return process constructed from a Markov branching process and by birth and death processes. Finally, a number of limit theorems for the limiting age as j→∞ are given.     

关于可列非齐次马氏链的若干极限定理

设{Xn,n≥0}是一列非齐次马尔科夫链,{an,n≥0}是一列固定的非负整数序列.首先构造了一个带参数的广义似然比函数,然后利用Borel-Cantelli引理证明随机变量序列几乎处处收敛性,得到了关于可列非齐次马氏链序偶广义平均的若干极限定理,推广了已有的结果.     

On the Waiting Time for the First Success Run

Let k and m are positive integers with k ≥ m. The probability generating function of the waiting time for the first occurrence of consecutive k successes in a sequence of m-th order Markov dependent trials is given as a function of the conditional probability generating functions of the waiting time for the first occurrence of consecutive m successes. This provides an efficient algorithm for obtaining the probability generating function when k is large. In particular, in the case of independent trials a simple relationship between the geometric distribution of order k and the geometric distribution of order k−1 is obtained. This research was partially supported by the ISM Cooperative Research Program(2004-ISM-CRP-2006) and by a Grant-in-Aid for Scientific Research (C) of the JSPI (Grant Number 16500183)