Evaluation of the discrepancy of the linear congruential pseudo-random number sequencies

The discrepancy of a pseudo-random number (PRN) sequence has been defined as a quantity which measures the deviation of the sequence's distribution from the ideal uniform distribution. In this paper, we give three algorithms for computer evaluation of the discrepancy of PRN sequences. The computational results for the discrepancy of PRN sequences generated by a linear congruential method are included.This research is partially funded by Natural Sciences and Engineering Research Council of Canada, Grant No. 0GP00089. A research grant from IBM Canada through the Supercomputer Center, University of New Brunswick, is gratefully acknowledged.     

Generalized Levinson-Durbin sequences, binomial coefficients and autoregressive estimation

For a discrete time second-order stationary process, the Levinson-Durbin recursion is used to determine the coefficients of the best linear predictor of the observation at time k+1, given k previous observations, best in the sense of minimizing the mean square error. The coefficients determined by the recursion define a Levinson-Durbin sequence. We also define a generalized Levinson-Durbin sequence and note that binomial coefficients form a special case of a generalized Levinson-Durbin sequence. All generalized Levinson-Durbin sequences are shown to obey summation formulas which generalize formulas satisfied by binomial coefficients. Levinson-Durbin sequences arise in the construction of several autoregressive model coefficient estimators. The least squares autoregressive estimator does not give rise to a Levinson-Durbin sequence, but least squares fixed point processes, which yield least squares estimates of the coefficients unbiased to order 1/T, where T is the sample length, can be combined to construct a Levinson-Durbin sequence. By contrast, analogous fixed point processes arising from the Yule-Walker estimator do not combine to construct a Levinson-Durbin sequence, although the Yule-Walker estimator itself does determine a Levinson-Durbin sequence. The least squares and Yule-Walker fixed point processes are further studied when the mean of the process is a polynomial time trend that is estimated by least squares.     

On the chernoff-savage theorem for dependent sequences

Summary Given a sequence of ϕ-mixing random variables not necessarily stationary, a Chernoff-Savage theorem for two-sample linear rank statistics is proved using the Pyke-Shorack [5] approach based on weak convergence properties of empirical processes in an extended metric. This result is a generalization of Fears and Mehra [4] in that the stationarity is not required and that the condition imposed on the mixing numbers is substantially relaxed. A similar result is shown to hold for strong mixing sequences under slightly stronger conditions on the mixing numbers. Research partially supported by the National Research Council of Canada under Grant No. A-3954.     

Almost linear upper bounds on the length of general davenport—schinzel sequences

Davenport—Schinzel sequences are sequences that do not contain forbidden subsequences of alternating symbols. They arise in the computation of the envelope of a set of functions. We obtain almost linear upper bounds on the length λ_s(n) of Davenport—Schinzel sequences composed ofn symbols in which no alternating subsequence is of length greater thans+1. These bounds are of the formO(nα(n)^O(α(n)5-3)), and they generalize and extend the tight bound Θ(nα(n)) obtained by Hart and Sharir for the special cases=3 (α(n) is the functional inverse of Ackermann’s function), and also improve the upper boundO(n log*n) due to Szemerédi. Work on this paper has been supported in part by a grant from the U.S. — Israeli Binational Science Foundation.     

The Gauss code problem off the plane

The classical Gauss code problem asks to characterize which cyclic sequences arise as the vertex sequence of the straight-ahead path of a 4-regular graph embedded in the plane This problem is generalized to certain 4 regular graphs in arbitrary surfacesA characterization is given for the existence of a 4-regular graph in a specified surface yielding the specified sequence This characterization is obtained using a generalization of Shank's left-right paths     

Generalized Fibonacci recurrences and the lex-least de Bruijn sequence

The skew of a binary string is the difference between the number of zeroes and the number of ones, while the length of the string is the sum of these two numbers. We consider certain suffixes of the lexicographically-least de Bruijn sequence at natural breakpoints of the binary string. We show that the skew and length of these suffixes are enumerated by sequences generalizing the Fibonacci and Lucas numbers, respectively.     

Extrapolation methods for some singular fixed point sequences

A fixed point sequence is singular if the Jacobian matrix at the limit has 1 as an eigenvalue. The asymptotic behaviour of some singular fixed point sequences in one dimension are extended toN dimensions. Three algorithms extrapolating singular fixed point sequences inN dimensions are given. Using numerical examples three algorithms are tested and compared.     

Pre-compact families of finite sets of integers and weakly null sequences in Banach spaces

In this paper we use the Nash-Williams theory of fronts and barriers to study weakly null sequences in Banach spaces. Specifically, we show how barriers relate to the classical fact that C(K) with K a countable compactum is c₀-saturated. Another result relates the notion of a barrier to the Maurey-Rosenthal example of a weakly null sequence with no unconditional subsequences. In particular, we construct examples of weakly-null sequences which are α-unconditional but not β-unconditional.     

Central limit theorems under weak dependence

This article is motivated by a central limit theorem of Ibragimov for strictly stationary random sequences satisfying a mixing condition based on maximal correlations. Here we show that the mixing condition can be weakened slightly, and construct a class of stationary random sequences covered by the new version of the theorem but not Ibragimov's original version. Ibragimov's theorem is also extended to triangular arrays of random variables, and this is applied to some kernel-type estimates of probability density.     

Connection between the Hadamard and matrix products with an application to matrix-variate Birnbaum-Saunders distributions

In this paper, we establish a connection between the Hadamard product and the usual matrix multiplication. In addition, we study some new properties of the Hadamard product and explore the inverse problem associated with the established connection, which facilitates diverse applications. Furthermore, we propose a matrix-variate generalized Birnbaum-Saunders (GBS) distribution. Three representations of the matrix-variate GBS density are provided, one of them by using the mentioned connection. The main motivation of this article is based on the fact that the representation of the matrix-variate GBS density based on element-by-element specification does not allow matrix transformations. Consequently, some statistical procedures based on this representation, such as multivariate data analysis and statistical shape theory, cannot be performed. For this reason, the primary goal of this work is to obtain a matrix representation of the matrix-variate GBS density that is useful for some statistical applications. When the GBS density is expressed by means of a matrix representation based on the Hadamard product, such a density is defined in terms of the original matrices, as is common for many matrix-variate distributions, allowing matrix transformations to be handled in a natural way and then suitable statistical procedures to be developed.     

Nonlinearity of davenport—Schinzel sequences and of generalized path compression schemes

Davenport—Schinzel sequences are sequences that do not contain forbidden subsequences of alternating symbols. They arise in the computation of the envelope of a set of functions. We show that the maximal length of a Davenport—Schinzel sequence composed ofn symbols is Θ (nα(n)), where α(n) is the functional inverse of Ackermann’s function, and is thus very slowly increasing to infinity. This is achieved by establishing an equivalence between such sequences and generalized path compression schemes on rooted trees, and then by analyzing these schemes. Work on this paper by the second author has been supported in part by a grant from the U.S.-Israeli Binational Science Foundation.     

On some identities for the Fibonomial coefficients via generating function

Some new identities for the Fibonomial coefficients are derived. These identities are related to the generating function of the kth powers of the Fibonacci numbers. Proofs are based on manipulation with the generating function of the sequence of “signed Fibonomial triangle”.     

Davenport–Schinzel Trees*

In this paper we study labeled–tree analogues of (generalized) Davenport–Schinzel sequences.We say that two sequences a ₁ ... a _k , b ₁ ... b _k of equal length k are isomorphic, if a _i = a _j i b _i = b _j (for all i, j). For example, the sequences 11232, 33141 are isomorphic. We investigate the maximum size of a labeled (rooted) tree with each vertex labeled by one of n labels in such a way that, besides some technical conditions, the sequence of labels along any path (starting from the root) contains no subsequence isomorphic to a fixed forbidden sequence u.We study two models of such labeled trees. Each of the models is known to be essentially equivalent also to other models. The labeled paths in a special case of one of our models correspond to classical Davenport–Schinzel sequences.We investigate, in particular, for which sequences u the labeled tree has at most O(n) vertices. In both models, we answer this question for any forbidden sequence u over a two-element alphabet and also for a large class of other sequences u.* This research was partially supported by Charles University grants No. 99/158 and 99/159 and by Czech Republic Grant GAR 201/99/0242. Supported by project LN00A056 of The Ministry of Education of the Czech Republic.     

Commutative Sequences of Integrable Functions and Best Approximation With Respect to the Weighted Vector Measure Distance

Let λ be a countably additive vector measure with values in a separable real Hilbert space H. We define and study a pseudo metric on a Banach lattice of integrable functions related to λ that we call a λ-weighted distance. We compute the best approximation with respect to this distance to elements of the function space by the use of sequences with special geometric properties. The requirements on the sequence of functions are given in terms of a commutation relation between these functions that involves integration with respect to λ. We also compare the approximation that is obtained in this way with the corresponding projection on a particular Hilbert space.     

A wavelet analysis of the Rosenblatt process: Chaos expansion and estimation of the self-similarity parameter

By using chaos expansion into multiple stochastic integrals, we make a wavelet analysis of two self-similar stochastic processes: the fractional Brownian motion and the Rosenblatt process. We study the asymptotic behavior of the statistic based on the wavelet coefficients of these processes. Basically, when applied to a non-Gaussian process (such as the Rosenblatt process) this statistic satisfies a non-central limit theorem even when we increase the number of vanishing moments of the wavelet function. We apply our limit theorems to construct estimators for the self-similarity index and we illustrate our results by simulations.     

Total positivity properties of Jacobi–Stirling numbers

The Jacobi–Stirling numbers of the first and second kinds were first introduced in Everitt et al. (2007) [8] and they are a generalization of the Legendre–Stirling numbers. Quite remarkably, they share many similar properties with the classical Stirling numbers. In this paper we study total positivity properties of these numbers. In particular, we prove that the matrix whose entries are the Jacobi–Stirling numbers is totally positive and that each row and each column is a Pólya frequency sequence, except for the columns with (unsigned) numbers of the first kind.     

Empirical likelihood analysis of the Buckley-James estimator

The censored linear regression model, also referred to as the accelerated failure time (AFT) model when the logarithm of the survival time is used as the response variable, is widely seen as an alternative to the popular Cox model when the assumption of proportional hazards is questionable. Buckley and James [Linear regression with censored data, Biometrika 66 (1979) 429-436] extended the least squares estimator to the semiparametric censored linear regression model in which the error distribution is completely unspecified. The Buckley-James estimator performs well in many simulation studies and examples. The direct interpretation of the AFT model is also more attractive than the Cox model, as Cox has pointed out, in practical situations. However, the application of the Buckley-James estimation was limited in practice mainly due to its illusive variance. In this paper, we use the empirical likelihood method to derive a new test and confidence interval based on the Buckley-James estimator of the regression coefficient. A standard chi-square distribution is used to calculate the P-value and the confidence interval. The proposed empirical likelihood method does not involve variance estimation. It also shows much better small sample performance than some existing methods in our simulation studies.     

Abelian groups with a vanishing homology group

An abelian group A is called absolutely abelian, if in every central extension N ? G ? A the group G is also abelian. The abelian group A is absolutely abelian precisely when the Schur multiplicator H₂A vanished. These groups, and more generally groups with H_nA = 0 for some n, are characterized by elementary internal properties. (Here H₁A denotes the integral homology of A.) The cases of even n and odd n behave strikingly different. There are 2^?ο different isomorphism types of abelian groups A with reduced torsion subgroup satisfying H_2nA = 0. The major tools are direct limit arguments and the Lyndon-Hochschild-Serre (L-H-S) spectral sequence, but the treatment of absolutely abelian groups does not use spectral sequences. All differentials d^r for r ≥ 2 in the L-H-S spectral sequence of a pure abelian extension vanish. Included is a proof of the folklore theorem, that homology of groups commutes with direct limits also in the group variable, and a discussion of the L-H-S spectral sequence for direct limits.     

Limiting distribution of sums of nonnegative stationary random variables

Summary Let {X _n,j,−∞<j<∞∼,n≧1, be a sequence of stationary sequences on some probability space, with nonnegative random variables. Under appropriate mixing conditions, it is shown thatS _n=X_n,1+…+X _n,n has a limiting distribution of a general infinitely divisible form. The result is applied to sequences of functions {f _n(x)∼ defined on a stationary sequence {X _j∼, whereX _n.f=f_n(X_j). The results are illustrated by applications to Gaussian processes, Markov processes and some autoregressive processes of a general type. This paper represents results obtained at the Courant Institute of Mathematical Sciences, New York University, under the sponsorship of the National Sciences Foundation, Grant MCS 82-01119.     

On the normal approximation for random fields via martingale methods

We prove a central limit theorem for strictly stationary random fields under a sharp projective condition. The assumption was introduced in the setting of random sequences by Maxwell and Woodroofe. Our approach is based on new results for triangular arrays of martingale differences, which have interest in themselves. We provide as applications new results for linear random fields and nonlinear random fields of Volterra-type.