Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-23T14:14:20.963Z Has data issue: false hasContentIssue false
  • English
  • Français

Peaks and Eulerian numbers in a random sequence

Part of: Distribution theory Nonparametric inference Stochastic processes

Published online by Cambridge University Press:  14 July 2016

Di Warren  and
E. Seneta
Di Warren*
Affiliation:
University of Sydney
E. Seneta*
Affiliation:
University of Sydney
*
∗Postal address for both authors: School of Mathematics and Statistics, F07, University of Sydney, N.S.W. 2006, Australia.
∗Postal address for both authors: School of Mathematics and Statistics, F07, University of Sydney, N.S.W. 2006, Australia.
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider the exact distribution of the number of peaks in a random permutation of the integers 1, 2, ···, n. This arises from a test of whether n successive observations from a continuous distribution are i.i.d. The Eulerian numbers, which figure in the p.g.f., are then shown to provide a link between the simpler problem of ascents (which has been thoroughly analysed) and both our problem of peaks and similar problems on the circle. This link then permits easy deduction of certain general properties, such as linearity in n of the cumulants, in the more complex settings. Since the focus of the paper is on exact distributional results, a uniform bound on the deviation from the limiting normal is included. A secondary purpose of the paper is synthesis, beginning with the more familiar setting of peaks and troughs.

Keywords

ASCENTSCENTRAL LIMIT PROPERTYCIRCLECONVERGENCE RATECUMULANTSEULERIAN NUMBERSm-DEPENDENCEPEAKS AND TROUGHSPERMUTATIONPHASES

MSC classification

Primary: 60G10: Stationary processes
Secondary: 62E10: Characterization and structure theory 62G10: Hypothesis testing
Type
Research Papers
Information
Journal of Applied Probability , Volume 33 , Issue 1 , March 1996 , pp. 101 - 114
Copyright
Copyright © Applied Probability Trust 1996 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Bertrand, J. (1875) Note relative au théorème de M. Bienaymé. C. R. Acad. Sci. Paris 81, 458; 491–492.Google Scholar
Bienaymé, I. J. (1874) Sur une question de probabilités. Bull. Math. Soc. France 2, 153–154.CrossRefGoogle Scholar
Bienaymé, I. J. (1875) Application d'un théorème nouveau du calcul des probabilités. C. R. Acad. Sci. Paris 81, 417–423.Google Scholar
Carlitz, L., Kurtz, D. C., Scoville, R. and Stackelberg, O. P. (1972) Asymptotic properties of Eulerian numbers. Z. Wahrscheinlichkeitsth. 23, 47–54.CrossRefGoogle Scholar
David, F. N. and Barton, D. E. (1962) Combinatorial Chance. Griffin, London.CrossRefGoogle Scholar
Diananda, P. H. (1953) Some probability limit theorems with statistical applications. Proc. Camb. Phil. Soc. 49, 239–246.CrossRefGoogle Scholar
Draper, R. P. and Tierney, D. E. (1973) Exact formulas for additional terms in some important series expansions. Commun. Statist. 1, 495–524.CrossRefGoogle Scholar
Durbin, J. (1980) Approximations for densities of sufficient estimators. Biometrika 67, 311–333.CrossRefGoogle Scholar
Edgington, E. S. (1961) Probability tables for numbers of runs of signs of first differences in ordered series. J. Amer. Statist. Assoc. 56, 156–159.CrossRefGoogle Scholar
Esseen, C. G. (1985) On the application of the theory of probability to two combinatorial problems involving permutations. Proc. 7th Conf. on Probability Theory, Brasov, Romania. CrossRefGoogle Scholar
Feller, W. (1971) An Introduction to Probability Theory and its Applications. Vol 2. 2nd edn., Wiley, New York.Google Scholar
Fisher, R. A. (1926) On the Random Sequence. Quart. J. R. Meterol. Soc. 52, 250.CrossRefGoogle Scholar
Frobenius, V. G. (1901) Uber die Bernoullischen Zahlen und die Eulerschen Polynome. Sitzungs. K. Preussischen Akad. Wissenschaften, 809–847.Google Scholar
Gleissberg, W. (1945) Eine Aufgabe der Kombinatorik und Wahrscheinlichkeitsrechnung. Univ. Istanbul Rev. Fac. Sci. A 10, 25–35.Google Scholar
Heinrich, L. (1985) Some remarks on asymptotic expansions in the central limit theorem for m-dependent random variables. Math. Nachr. 122, 151–155.CrossRefGoogle Scholar
Hensley, D. (1982) Eulerian numbers and the unit cube. Fibonacci Quart. 20, 344–348.Google Scholar
Heyde, C. C. and Seneta, E. (1977) I. J. Bienaymé: Statistical Theory Anticipated. Springer, New York.CrossRefGoogle Scholar
Kendall, M. G. and Stuart, A. (1958) The Advanced Theory of Statistics. Vol. 1: Distribution Theory. 6th edn. Griffin, London.Google Scholar
Kendall, M. G. and Stuart, A. (1968) The Advanced Theory of Statistics. Vol. 3: Design and Analysis, and Time Series. 4th edn. Griffin, London.Google Scholar
Kermack, W. O. and Mckendrick, A. G. (1936-1937) Some distributions associated with a randomly arranged set of numbers. Proc. R. Soc. Edinburgh 57, 332–376.CrossRefGoogle Scholar
Kimber, A. C. (1987) Eulerian numbers and links with some statistical procedures. Utilitas Math. 31, 57–65.Google Scholar
Kimber, A. C. (1989) Eulerian numbers. Encyclopedia of Statistical Sciences Supplement. ed. Johnson, N. L. and Kotz, S. Wiley, New York.Google Scholar
Ku, S. and Seneta, E. (1994) The number of peaks in a stationary sample and orthant probabilities. J. Time Series Anal. 15, 385–403.CrossRefGoogle Scholar
Levene, H. (1952) On the power function of tests of randomness based on runs up and down. Ann. Math. Statist. 23, 34–56.CrossRefGoogle Scholar
Levene, H. and Wolfowitz, J. (1944) The covariance matrix of runs up and down. Ann. Math. Statist. 15, 58–69.CrossRefGoogle Scholar
Liagre, M. (1855) Sur la probabilité de l'existence d'une cause d'erreur régulière dans une série d'observations. Bull. l'Acad. R. Sci. Lett. Beaux Arts de Belg. 22, 7–55.Google Scholar
Macmahon, P. A. (1908) Second memoir on the compositions of numbers. Phil. Trans. R. Soc. London 207A, 65–134.Google Scholar
Macmahon, P. A. (1915) Combinatory Analysis. Vol. 1. Cambridge University Press, Cambridge.Google Scholar
Mann, H. B. (1945) On a test for randomness based on signs of differences. Ann. Math. Statist. 16, 193–199.CrossRefGoogle Scholar
Moore, G. H. and Wallis, W. A. (1943) Time series significance tests based on signs of differences. J. Amer. Statist. Assoc. 38, 153–164.CrossRefGoogle Scholar
Netto, E. (1901) Lehrbuch der Combinatorik. Teubner, Leipzig.Google Scholar
Riordan, J. (1958) Introduction to Combinatorial Analysis. Wiley, New York.Google Scholar
Selden, D. (1990) Statistical Tests Based on Turning Points. Honours project, Department of Mathematical Statistics, University of Sydney.Google Scholar
Shergin, V. V. (1979) On the convergence rate in the central limit theorem for m-dependent random variables. Theory Prob. Appl. 24, 782–796.CrossRefGoogle Scholar
Stein, C. (1972) A bound for the error in the Normal approximation to the distribution of a sum of dependent random variables. Proc. 6th Berkeley Symp. Math. Statist. 2, 582–602.Google Scholar
Stigler, S. M. (1986) Estimating serial correlation by visual inspection of diagnostic plots. Amer. Statist. 40, 111–116.Google Scholar
Stuart, A. (1954) Asymptotic relative efficiencies of distribution-free tests of randomness against normal alternatives. J. Amer. Statist. Assoc. 49, 147–157.CrossRefGoogle Scholar
Wallace, D. L. (1958) Asymptotic approximations to distributions. Ann. Math. Statist. 29, 635–654.CrossRefGoogle Scholar
Wallis, W. A. and Moore, G. H. (1941a) A significance test for time series analysis. J. Amer. Statist. Assoc. 36, 401–409.CrossRefGoogle Scholar
Wallis, W. A. and Moore, G. H. (1941b) A significance test for time series and other ordered observations. Natl. Bureau Econ. Res. New York. Tech. Paper No. 1.Google Scholar
Wolfowitz, J. (1943) On the theory of runs with some applications to quality control. Ann. Math. Statist. 14, 280–288.CrossRefGoogle Scholar
Wolfowitz, J. (1944) Asymptotic distribution of runs up and down. Ann. Math. Statist. 15, 163–172.CrossRefGoogle Scholar