Three problems on the lengths of increasing runs

Let U₁, U₂,… be a sequence of independent, uniform (0, 1) r.v.'s and let R₁, R₂,… be the lengths of increasing runs of {U_i}, i.e., X₁=R₁=inf{i:U_i+1<U_i},…, X_n=R₁+R₂+?+R_n=inf{i:i>X_n?1,U_i+1<U_i}. The first theorem states that the sequence $\text{(}\text{3}\text{2}\text{n)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{(X}{}_{\mathrm{n}}\text{?2n)}$ can be approximated by a Wiener process in strong sense.Let τ(n) be the largest integer for which R₁+R₂+?+R_τ(n)?n, $\text{R}{}^1{}_{\mathrm{n}}\text{=n?(R}{}_1\text{+R}{}_2\text{+?+R}{}_{\mathrm{\tau (n)}}\text{)}$ and $\text{M}{}_{\mathrm{n}}\text{=}\text{max}\text{{R}{}_1\text{,R}{}_2\text{,…,R}{}_{\mathrm{\tau (n)}}\text{,R}{}^1{}_{\mathrm{n}}\text{}}$. Here M_n is the length of the longest increasing block. A strong theorem is given to characterize the limit behaviour of M_n.The limit distribution of the lengths of increasing runs is our third problem.     

Counting subsets of the random partition and the ‘Brownian Bridge’ process

Let Ω_m be the set of partitions, ω, of a finite m-element set; induce a uniform probability distribution on Ω_m, and define X_ms(ω) as the number of s-element subsets in ω. We alow the existence of an integer-valued function n=n^(m)(t), t?[0, 1], and centering constants b_ms, 0?s? m, such that

$\text{Z}{}^{\mathrm{(m)}}\text{(t)=}\text{∑}\text{s=0}\text{n(m)(t)}\text{(X}{}_{\mathrm{ms}}\text{?b}{}_{\mathrm{ms}}\text{)}\text{√}\text{∑}\text{s=0}\text{m}\text{b}{}_{\mathrm{ms}}$

converges to the ‘Brownian Bridge’ process in terms of its finite-dimensional distributions.     

On long runs of heads and tails II

In a string ofn independent coin tosses we consider the difference between the lengths of the longest blocks of consecutive heads resp. tails. A complete characterization of the a.s. limit properties of this quantity is proved.     

Euclidean semi-matchings of random samples

A linear programming relaxation of the minimal matching problem is studied for graphs with edge weights determined by the distances between points in a Euclidean space. The relaxed problem has a simple geometric interpretation that suggests the name minimal semi-matching. The main result is the determination of the asymptotic behavior of the length of the minimal semi-matching. It is analogous to the theorem of Beardwood, Halton and Hammersley (1959) on the asymptotic behavior of the traveling salesman problem. Associated results on the length of non-random Euclidean semi-matchings and large deviation inequalities for random semi-matchings are also given.Research supported in part by NSF Grant #DMS-8812868, ARO contract DAAL03-89-G-0092.P001, AFOSR-89-08301.A and NSA-MDA-904-89-2034.     

Plane brownian motion in a region with holes

We consider a fixed family of balls with decreasing radii in the plane. We establish a relationship between a Dirichlet problem in a region without the balls and the solution of a Schroedinger equation in the complete region. Then we find upper bounds for the probability that a brownian motion exits the region without touching these balls. This is used to study harmonic measure and entire functions.     

On the asymptotic behaviour of the empirical random field of the brownian motion

Let ξ_t, t ? 0, be a d-dimensional Brownian motion. The asymptotic behaviour of the random field ??∫^t₀?(ξ_s) ds is investigated, where ? belongs to a Sobolev space of periodic functions. Particularly a central limit theorem and a law of iterated logarithm are proved leading to a so-called universal law of iterated logarithm.     

A direct bijection for the Harer-Zagier formula

We give a combinatorial proof of Harer and Zagier's formula for the disjoint cycle distribution of a long cycle multiplied by an involution with no fixed points, in the symmetric group on a set of even cardinality. The main result of this paper is a direct bijection of a set B_p,k, the enumeration of which is equivalent to the Harer-Zagier formula. The elements of B_p,k are of the form (μ,π), where μ is a pairing on {1,…,2p}, π is a partition into k blocks of the same set, and a certain relation holds between μ and π. (The set partitions π that can appear in B_p,k are called “shift-symmetric”, for reasons that are explained in the paper.) The direct bijection for B_p,k identifies it with a set of objects of the form (ρ,t), where ρ is a pairing on a 2(p-k+1)-subset of {1,…,2p} (a “partial pairing”), and t is an ordered tree with k vertices. If we specialize to the extreme case when p=k-1, then ρ is empty, and our bijection reduces to a well-known tree bijection.     

Schilder theorem for the Brownian motion on the diffeomorphism group of the circle

We prove a large deviation principle for flows associated to stochastic differential equations with non-Lipschitz coefficients. As an application we establish a Schilder Theorem for the Brownian motion on the group of diffeomorphisms of the circle.     

Particle picture interpretation of some Gaussian processes related to fractional Brownian motion

We construct fractional Brownian motion, sub-fractional Brownian motion and negative sub-fractional Brownian motion by means of limiting procedures applied to some particle systems. These processes are obtained for full ranges of Hurst parameter.     

On estimation of a density and its derivatives

Summary Letf _n ^(p) be a recursive kernel estimate off ^(p) thepth order derivative of the probability density functionf, based on a random sample of sizen. In this paper, we provide bounds for the moments of and show that the rate of almost sure convergence of to zero isO(n ^−α), α<(r−p)/(2r+1), iff ^(r),r>p≧0, is a continuousL ₂(−∞, ∞) function. Similar rate-factor is also obtained for the almost sure convergence of to zero under different conditions onf. This work was supported in part by the Research Foundation of SUNY.     

On the singular graph and the Weyr characteristic of anM-matrix

LetA be anM-matrix in standard lower block triangular form, with diagonal blocksA _ii irreducible. LetS be the set of indices such that the diagonal blockA is singular. We define the singular graph ofA to be the setS with partial order defined by > if there exists a chain of non-zero blocksA _i, A_ij, , A_l.Let ₁ be the set of maximal elements ofS, and define thep-th level _p ,p = 2, 3, , inductively as the set of maximal elements ofS \( _{1 p-1}). Denote by _p the number of elements in _p . The Weyr characteristic (associated with 0) ofA is defined to be (A) = ( ₁, ₂,, _h ), where ₁ + + _p = dim KerA ^p ,p = 1, 2, , and _h > 0, _h+1 = 0.Using a special type of basis, called anS-basis, for the generalized eigenspaceE(A) of 0 ofA, we associate a matrixD withA. We show that(A) = ( ₁, , _h) if and only if certain submatricesD _p,p+1 ,p = 1, , h – 1, ofD have full column rank. This condition is also necessary and sufficient forE(A) to have a basis consisting of non-negative vectors, which is a Jordan basis for –A. We also consider a given finite partially ordered setS, and we find a necessary and sufficient condition that allM-matricesA with singular graphS have(A) = ( ₁, , _h). This condition is satisfied ifS is a rooted forest.The work of the second-named author was partly supported by the National Science Foundation, under grant MPS-08618 A02.     

Quadrature rule-based bounds for functions of adjacency matrices

Bounds for entries of matrix functions based on Gauss-type quadrature rules are applied to adjacency matrices associated with graphs. This technique allows to develop inexpensive and accurate upper and lower bounds for certain quantities (Estrada index, subgraph centrality, communicability) that describe properties of networks.     

Mixing normal approximations of vectors of sums and maximum sums

Summary The conditioned central limit theorem for the vector of maximum partial sums based on independent identically distributed random vectors is investigated and the rate of convergence is discussed. The conditioning is that of Rényi (1958,Acta Math. Acad. Sci. Hungar.,9, 215–228). Analogous results for the vector of partial sums are obtained. University of Petroleum and Minerals