A central limit theorem for the sojourn times of strongly ergodic Markov chains

Let X_n be an irreducible aperiodic recurrent Markov chain with countable state space I and with the mean recurrence times having second moments. There is proved a global central limit theorem for the properly normalized sojourn times. More precisely, if $\text{t}{}^{\mathrm{(n}}\text{)}{}_{\mathrm{i}}\text{=Σ}{}^{\mathrm{n}}{}_{\mathrm{k=1}}\text{i}\text{?}{}_{\mathrm{i}}\text{(X}{}_{\mathrm{k}}\text{)}$, then the probability measures induced by {t⁽ⁿ⁾_i/√n?√nπ_i}_i?I(π_i being the ergotic distribution) on the Hilbert-space of square summable I-sequences converge weakly in this space to a Gaussian measure determined by a certain weak potential operator.     

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.     

Asymptotic expansions in functional limit theorems

Asymptotic expansions for a class of functional limit theorems are investigated. It is shown that the expansions in this class fit into a common scheme, defined by a sequence of functions h_n (ε₁,…, ε_n), n ≥ 1, of “weights” (for n observations), which are smooth, symmetric, compatible and have vanishing first derivatives at zero. Then $\text{h}{}_{\mathrm{n}}\text{(n}{}^{\mathrm{<mtext>?1</mtext><mtext>2</mtext>}}\text{,…, n}{}^{\mathrm{<mtext>?1</mtext><mtext>2</mtext>}}\text{)}$ admits an asymptotic expansion in powers of $\text{n}{}^{\mathrm{<mtext>?1</mtext><mtext>2</mtext>}}$. Applications to quadratic von Mises functionals, the C.L.T. in Banach spaces, and the invariance principle are discussed.     

A remark on the tail probability of a distribution

Let {X_n}_n≥1 be a sequence of independent and identically distributed random variables. For each integer n ≥ 1 and positive constants r, t, and ?, let S_n = Σ_j=1ⁿX_j and $\text{E{N}{}_{\mathrm{\infty }}\text{(r, t, ?)} = Σ}{}_{\mathrm{n=1}}{}^{\mathrm{\infty }}\text{n}{}^{\mathrm{r?2}}\text{P{|S}{}_{\mathrm{n}}\text{| > ?n}{}^{\mathrm{<mtext>r</mtext><mtext>t</mtext>}}\text{}}$. In this paper, we prove that (1) lim_?→0+?^α(r?1)E{N_∞(r, t, ?)} = K(r, t) if E(X₁) = 0, Var(X₁) = 1, and E(| X₁ |^t) < ∞, where 2 ≤ t < 2r ≤ 2t, $\text{K(r, t) =}\text{{2}{}^{\mathrm{<mtext>\alpha (r?1)</mtext><mtext>2</mtext>}}\text{Γ(}\text{(1 + α(r ? 1))}\text{2}\text{)}}\text{{(r ? 1) Γ(}\text{1}\text{2}\text{)}}$, and $\text{α =}\text{2t}\text{(2r ? t)}$; (2) $\text{lim}{}_{\mathrm{?\to 0+}}\text{G(t, ?)}\text{H(t, ?)}\text{= 0}$ if 2 < t < 4, E(X₁) = 0, Var(X₁) > 0, and E(|X₁|^t) < ∞, where G(t, ?) = E{N_∞(t, t, ?)} = Σ_n=1^∞n^t?2P{| S_n | > ?n} → ∞ as ? → 0+ and $\text{H(t, ?) = E{N}{}_{\mathrm{\infty }}\text{(t, t, ?)} = Σ}{}_{\mathrm{n=1}}{}^{\mathrm{\infty }}\text{n}{}^{\mathrm{t?2}}\text{P{| S}{}_{\mathrm{n}}\text{| > ?n}{}^{\mathrm{<mtext>2</mtext><mtext>t</mtext>}}\text{} → ∞}\text{as}\text{? → 0+}$, i.e., H(t, ?) goes to infinity much faster than G(t, ?) as ? → 0+ if 2 < t < 4, E(X₁) = 0, Var(X₁) > 0, and E(| X₁ |^t) < ∞. Our results provide us with a much better and deeper understanding of the tail probability of a distribution.     

Sampling distribution for a class of estimators for nonregular linear processes

Let {X_t; t = 1, 2,…} be a linear process with a location parameter θ defined by X_t ? θ = Σ₀^∞g_rZ_t?r where {Z_t; t = 0, ±1,…} is a sequence of independent and identically distributed random variables, with E∥Z₁∥^δ < ∞ for some δ > 0. If δ ? 1 we assume further than E(Z₁) = 0. Let η = δ if 0 < δ < 2, and η = 2 if δ ? 2. Then assume that Σ₀^∞∥ g_r ∥^η < ∞. Consider the class of estimators $\text{θ}\text{∧}{}_{\mathrm{n}}$ given by $\text{θ}\text{∧}{}_{\mathrm{n}}\text{= Σ}{}_1{}^{\mathrm{n}}\text{c}{}_{\mathrm{nt}}\text{X}{}_{\mathrm{t}}\text{where}\text{c}{}_{\mathrm{nt}}$ is of the form c_nt = Σ_{p = 0}^sβ_npt^p for some s ? 0. An attempt has been made to investigate the distributional properties of $\text{θ}\text{∧}{}_{\mathrm{n}}$ in large samples for various choices of β_np (0 ? p ? s), s, and the distribution of Z₁ under the constraints Σ₀^∞r^kg_r = 0, 0 ? k ? q where q in an arbitrary integer, 0 ? q ? s.     

Strong approximation theorems for density dependent Markov chains

A variety of continuous parameter Markov chains arising in applied probability (e.g. epidemic and chemical reaction models) can be obtained as solutions of equations of the form

$\text{X}{}_{\mathrm{N}}\text{(t)=x}{}_0\text{+∑}\text{1}\text{N}\text{lY}{}_1\text{N ∫}{}^{\mathrm{t}}{}_0\text{f}{}_1\text{(X}{}_{\mathrm{N}}\text{(s))ds}$

where $\text{l∈}\text{Z}{}^{\mathrm{t}}$, the Y₁ are independent Poisson processes, and N is a parameter with a natural interpretation (e.g. total population size or volume of a reacting solution).The corresponding deterministic model, satisfies

$\text{X(t)=x}{}_0\text{+ ∫}{}^{\mathrm{t}}{}_0\text{∑ lf}{}_1\text{(X(s))ds}$

Under very general conditions lim_N→∞X_N(t)=X(t) a.s. The process X_N(t) is compared to the diffusion processes given by

$\text{Z}{}_{\mathrm{N}}\text{(t)=x}{}_0\text{+∑}\text{1}\text{N}\text{lB}{}_1\text{N∫}{}^{\mathrm{t}}{}_0\text{ft(Z}{}_{\mathrm{N}}\text{(s))ds}$

and

$\text{V(t)=∑ l∫}{}^{\mathrm{t}}{}_0\text{f}{}_1\text{(X(s))}\text{d}\text{W}\text{?}{}_1\text{+∫}{}^{\mathrm{t}}{}_0\text{?F(X(s))·V(s)}\text{ds.}$

Under conditions satisfied by most of the applied probability models, it is shown that X_N,Z_N and V can be constructed on the same sample space in such a way that

$\text{X}{}_{\mathrm{N}}\text{(t)=Z}{}_{\mathrm{N}}\text{(t)+O}\text{logN}\text{N}$

and

$\text{N}\text{(X}{}_{\mathrm{N}}\text{(t)?X(t))=V(t)+O}\text{log N}\text{N}$

     

On the sequence of Bayesian estimates of normal random walk process

Let (μ_t)^∞_t=0 be a k-variate (k?1) normal random walk process with successive increments being independently distributed as normal N(δ, R), and μ₀ being distributed as normal N(0, V₀). Let X_t have normal distribution N(μ_t, Σ) when μ_t is given, t = 1, 2,….Then the conditional distribution of μ_t given X₁, X₂,…, X_t is shown to be normal N(U_t, V_t) where U_t's and V_t's satisfy some recursive relations. It is found that there exists a positive definite matrix V and a constant θ, 0 < θ < 1, such that, for all t?1,

$\text{|R}\text{1}\text{2}\text{(V}{}^{\mathrm{?1}}{}_{\mathrm{t}}\text{?V}{}^{\mathrm{?1}}\text{R}\text{1}\text{2}\text{|<θ}{}^{\mathrm{t}}\text{|R}\text{1}\text{2}\text{(V}{}^{\mathrm{?1}}{}_0\text{?V}{}^{\mathrm{?1}}\text{)R}\text{1}\text{2}\text{|}$

where the norm |·| means that |A| is the largest eigenvalue of a positive definite matrix A. Thus, V_t approaches to V as t approaches to infinity. Under the quadratic loss, the Bayesian estimate of μ_t is U_t and the process {U_t}^∞_t=₀, U₀=0, is proved to have independent successive increments with normal N(θ, V_t?V_t+1+R) distribution. In particular, when V₀ =V then V_t = V for all t and {U_t}^∞_t=0 is the same as {μ_t}^∞_t=0 except that U₀ = 0 and μ₀ is random.     

On exponential bases for the Sobolev spaces over an interval

We suppose that K is a countable index set and that $\text{Λ = {λ}{}_{\mathrm{k}}\text{¦ k ? K}}$ is a sequence of distinct complex numbers such that forms a Riesz (strong) basis for L²[a, b], a < b. Let Σ = {σ₁, σ₂,…, σ_m} consist of m complex numbers not in Λ. Then, with p(λ) = Π_{k = 1}^m (λ ? σ_k), forms a Riesz (strong) bas Sobolev space H^m[a, b]. If we take σ₁, σ₂,…, σ_m to be complex numbers already in Λ, then, defining p(λ) as before, forms a Riesz (strong) basis for the space H^?m[a, b]. We also discuss the extension of these results to “generalized exponentials” tⁿe^λ_kt.     

How small are the increments of a Wiener process?

Let $\text{γ}{}_{\mathrm{т}}\text{=(8(}\text{logTa}{}^{-1}{}_{\mathrm{T}}\text{+log log T)}\text{π}{}^2\text{a}{}_{\mathrm{T}}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$, 0<a_T?T<∞, and {W(t);0?t<∞} be a standard Wiener process. This exposition studies the almost sure behaviour of

, under varying conditions on a_T and T/a_T. The following analogue of Lévy's modulus of continuity of a Wiener Process is also given:

$\text{lim}{}_{\mathrm{h\to 0}}\text{inf}{}_{\mathrm{0?t?1}}\text{sup}{}_{\mathrm{0?s?h}}\text{(}\text{8 log h}{}^{-1}\text{π}{}^2\text{h}\text{)}\text{1}\text{2}\text{|W(t+s)?W(t)| =}{}^{\mathrm{a.s.}}\text{1.}$

and this may be viewed as the exact “modulus of non-differentiability” of a Wiener Process.     

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.     

Definition and characterization of multivariate negative binomial distribution

The probability generating function (pgf) of an n-variate negative binomial distribution is defined to be [β(s₁,…,s_n)]^?k where β is a polynomial of degree n being linear in each s_i and k > 0. This definition gives rise to two characterizations of negative binomial distributions. An n-variate linear exponential distribution with the probability function h(x₁,…,x_n)$\text{exp}\text{(}\text{Σ}{}_{\mathrm{i=1}}{}^{\mathrm{n}}\text{θ}{}_{\mathrm{i}}\text{x}{}_{\mathrm{i}}\text{)}\text{f(θ}{}_1\text{,…,θ}{}_{\mathrm{n}}\text{)}$ is negative binomial if and only if its univariate marginals are negative binomial. Let S_t, t = 1,…, m, be subsets of {s₁,…, s_n} with empty ∩_t=1^mS_t. Then an n-variate pgf is of a negative binomial if and only if for all s in S_t being fixed the function is of the form of the pgf of a negative binomial in other s's and this is true for all t.     

On Berry-Esséen rates,a law of the iterated logarithm and an invariance principle for the proportion of the sample below the sample mean

Let F_n(x) be the empirical distribution function based on n independent random variables X₁,…,X_n from a common distribution function F(x), and let $\text{X}\text{= Σ}{}_{\mathrm{i=1}}{}^{\mathrm{n}}\text{X}{}_{\mathrm{i}}\text{n}$ be the sample mean. We derive the rate of convergence of $\text{F}{}_{\mathrm{n}}\text{(}\text{X}\text{)}$ to normality (for the regular as well as nonregular cases), a law of iterated logarithm, and an invariance principle for $\text{F}{}_{\mathrm{n}}\text{(}\text{X}\text{)}$.     

Inverse Hölder inequalities in one and several dimensions

We study certain functionals and obtain an inverse Hölder inequality for n functions f₁^a1,…,f_n^an (f_k concave, 1 dimension).We also prove a multidimensional inverse Hölder inequality for n functions f₁,…,f_n, where $\text{?}{}^2\text{f}{}_{\mathrm{k}}\text{?x}{}_{\mathrm{i}}{}^2\text{? 0, i = 1,…, d, k = 1,…, n}$.Finally we give an inverse Minkowski inequality for concave functions.     

Limit distributions for the maxima of stationary Gaussian processes

Let {X_n} be a stationary Gaussian sequence with E{X₀} = 0, {X²₀} = 1 and E{X₀X_n} = rⁿ_n Let c_n = (2ln n)^{$\text{built1}\text{2}$}, b_n = c_n? $\text{1}\text{2}$c^-1_n ln(4π ln n), and set M_n = max_{0 ?k?n}X_k. A classical result for independent normal random variables is that

$\text{P[c}{}_{\mathrm{n}}\text{(M}{}_{\mathrm{n}}\text{?b}{}_{\mathrm{n}}\text{)?x]→exp[-e}{}^{\mathrm{-x}}\text{] as n → ∞ for all x.}$

Berman has shown that (1) applies as well to dependent sequences provided r_nlnn = o(1). Suppose now that {r_n} is a convex correlation sequence satisfying r_n = o(1), (r_nlnn)^-1 is monotone for large n and o(1). Then

$\text{P[r}{}_{\mathrm{n}}{}^{\mathrm{<mtext>-1</mtext><mtext>2</mtext>}}\text{(M}{}_{\mathrm{n}}\text{? (1?r}{}_{\mathrm{n}}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{b}{}_{\mathrm{n}}\text{)?x] → Ф(x)}$

for all x, where Ф is the normal distribution function. While the normal can thus be viewed as a second natural limit distribution for {M_n}, there are others. In particular, the limit distribution is given below when r_n is (sufficiently close to) γ/ln n. We further exhibit a collection of limit distributions which can arise when r_n decays to zero in a nonsmooth manner. Continuous parameter Gaussian processes are also considered. A modified version of (1) has been given by Pickands for some continuous processes which possess sufficient asymptotic independence properties. Under a weaker form of asymptotic independence, we obtain a version of (2).     

A combinatorial interpretation for two transformations of series that commute with compositional inversion

For a formal power series $\text{g(t) =}\text{1}\text{[1 + ∑}{}_{\mathrm{n=1}}{}^{\mathrm{\infty }}\text{h}{}_{\mathrm{n}}\text{t}{}^{\mathrm{n}}\text{]}$ with nonnegative integer coefficients, the compositional inverse $\text{f}\text{(t) = t · f(t)}$ of $\text{g}\text{(t) = t · g(t)}$ is shown to be the generating function for the colored planted plane trees in which each vertex of degree i + 1 is colored one of h_i colors. Since the compositional inverse of the Euler transformation of f(t) is the star transformation [[g(t)]^?1 ? 1]^?1 of g(t), [2], it follows that the Euler transformation of f(t) is the generating function for the colored planted plane trees in which each internal vertex of degree i + 1 is colored one of h_i colors for i > 1, and h₁ ? 1 colors for i = 1.     

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.     

Deterministic version of Wigner's semicircle law for the distribution of matrix eigenvalues

It is proved that Wigner's semicircle law for the distribution of eigenvalues of random matrices, which is important in the statistical theory of energy levels of heavy nuclei, possesses the following completely deterministic version. Let A_n=(a_ij), 1?i, ?n, be the nth section of an infinite Hermitian matrix, {λ⁽ⁿ⁾}_1?k?n its eigenvalues, and {u_k⁽ⁿ⁾}_1?k?n the corresponding (orthonormalized column) eigenvectors. Let $\text{v}{}^1{}_{\mathrm{n}}\text{=(a}{}_{\mathrm{n1}}\text{,a}{}_{\mathrm{n2}}\text{,?,a}{}_{\mathrm{n,n?1}}\text{)}$, put

$\text{X}{}_{\mathrm{n}}\text{(t)=[n(n-1)]}{}^{\mathrm{<mtext>-1</mtext><mtext>2</mtext>}}\text{∑}\text{k=1}\text{[(n-1)t]}\text{|v}{}_{\mathrm{n}}{}^1\text{u}{}_{\mathrm{f}}{}^{\mathrm{(n-1)}}\text{|}{}^2\text{,}\text{0?t?1}$

(bookeeping function for the length of the projections of the new row v¹_n of A_n onto the eigenvectors of the preceding matrix A_n?1), and let finally

$\text{F}{}_{\mathrm{n}}\text{(x)=n}{}^{-1}\text{(}\text{number of}\text{λ}{}_{\mathrm{k}}{}^{\mathrm{(n)}}\text{?x}\text{n}\text{,1?k?n)}$

(empirical distribution function of the eigenvalues of $\text{A}{}_{\mathrm{n}}\text{n}$. Suppose (i) $\text{lim}{}_{\mathrm{n}}\text{a}{}_{\mathrm{nn}}\text{n}\text{=0}$, (ii) lim_nX_n(t)=Ct(0<C<∞,0?t?1). Then

$\text{F}{}_{\mathrm{n}}\text{?W(·,C)}\text{(n→∞)}$

,where W is absolutely continuous with (semicircle) density

$\text{w(x,C)=}\text{(2Cπ)}{}^{-1}\text{(4C-x}{}^2{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{for}\text{|x|?2}\text{C}\text{0}\text{for}\text{|x|?2}\text{C}$

     

On the probability that given polynomials have a specified highest common factor

The polynomial functions f₁, f₂,…, f_m are found to have highest common factor h for a set of values of the variables x₁, x₂,…,x_m whose asymptotic density is

$\text{1}\text{h}{}^{\mathrm{n}}\text{∑}\text{d∣h}\text{μ(d)Π}{}^{\mathrm{m}}{}_{\mathrm{l\; =\; 1}}\text{?(f}{}_1\text{, dh)}\text{d}{}^{\mathrm{m}}\text{Π}\text{p∣h}\text{1?}\text{Π}{}^{\mathrm{m}}{}_{\mathrm{l\; =\; 1}}\text{?(f}{}_1\text{, p)}\text{p}{}^{\mathrm{m}}$

For the special case f₁(x) = f₂(x) = … = f_m(x) = x and h = 1 the above formula reduces to $\text{Π}{}_{\mathrm{?}}\text{(1 ?}\text{1}\text{p}{}^{\mathrm{m}}\text{) =}\text{1}\text{ζ}\text{(m)}$, the density if m-tuples with highest common factor 1. Necessary and sufficient conditions on the polynomials f₁, f₂,…, f_m for the asymptotic density to be zero are found. In particular it is shown that either the polynomials may never have highest common factor h or else h is the highest common factor infinitely often and in fact with positive density.     

Positive dependence properties of elliptically symmetric distributions

Let X₁, …, X_p have p.d.f. g(x₁² + … + x_p²). It is shown that (a) X₁, …, X_p are positively lower orthant dependent or positively upper orthant dependent if, and only if, X₁,…, X_p are i.i.d. N(0, σ²); and (b) the p.d.f. of |X₁|,…, |X_p| is TP₂ in pairs if, and only if, In g(u) is convex. Let X₁, X₂ have p.d.f. $\text{f(x}{}_1\text{, x}{}_2\text{) =}\text{|Σ|}{}^{\mathrm{<mtext>?</mtext><mtext>1</mtext><mtext>2</mtext>}}\text{g((x}{}_1\text{, x}{}_2\text{)}\text{Σ}{}^{\mathrm{?1}}\text{(x}{}_1\text{, x}{}_2\text{)′)}$. Necessary and sufficient conditions are given for f(x₁, x₂) to be TP₂ for fixed correlation ?. It is shown that if f is TP₂ for all ? >0. then (X₁, X₂)′ ～ N(0, Σ). Related positive dependence results and applications are also considered.     

Families of finite sets in which no set is covered by the union of two others

Let f^k(n) denote the maximum of k-subsets of an n-set satisfying the condition in the title. It is proven that f^{2t ? 1}(n) ? f^2t(n + 1) ? $\text{(}{}_{\mathrm{t}}{}^{\mathrm{n}}\text{)}\text{(}{}_{\mathrm{t}}{}^{\mathrm{2t?1}}\text{)}$ with equalities holding iff there exists a Steiner-system S(t, 2t ? 1, n). The bounds are approximately best possile for k ? 6 and of correct order of magnitude for k >/ 7, as well, even if the corresponding Steiner-systems do not exist.Exponential lower and upper bounds are obtained for the case if we do not put size restrictions on the members of the family (i.e., the nonuniform case).