Hostname: page-component-7b7567c8c-2rsb6 Total loading time: 0 Render date: 2026-11-13T00:38:57.133Z Has data issue: false hasContentIssue false
  • English
  • Français

The Frobenius–Harper technique in a general recurrence model

Part of:Limit theoremsDifference and functional equationsDifference equationsMarkov processesCombinatorial probability

Published online by Cambridge University Press:  14 July 2016

Di Warren
Di Warren*
Affiliation:
University of Sydney
*
∗ Postal address: 9 Trigg Avenue, Carlingford 2118, Australia.
Get accessRights & Permissions [Opens in a new window]

Abstract

We present a general recurrence model which provides a conceptual framework for well-known problems such as ascents, peaks, turning points, Bernstein's urn model, the Eggenberger–Pólya urn model and the hypergeometric distribution. Moreover, we show that the Frobenius-Harper technique, based on real roots of a generating function, can be applied to this general recurrence model (under simple conditions), and so a Berry–Esséen bound and local limit theorems can be found. This provides a simple and unified approach to asymptotic theory for diverse problems hitherto treated separately.

Keywords

Generating functionreal rootsinhomogeneous Markov chainascentspeaksturning pointsurn modelsBernsteinEggenberger–Pólyahypergeometric

MSC classification

Primary:60J10: Markov chains (discrete-time Markov processes on discrete state spaces)60C05: Combinatorial probability60F05: Central limit and other weak theorems39A10: Difference equations, additive

Information

Type
Research Papers
Information
Journal of Applied Probability , Volume 36 , Issue 1 , March 1999, pp. 30 - 47
Copyright
Copyright © Applied Probability Trust 1999 

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.)

Article purchase

Temporarily unavailable

References

Alzaid, A. A., and Rao, C. R. (1986). Characterization of discrete probability distributions by partial independence. Commun. Statist. (A).–Theory Methods 15, 643–656.Google Scholar
Barbour, A. D., Holst, L., and Janson, S. (1992). Poisson Approximation. Clarendon, New York.Google Scholar
Bender, E. A. (1973). Central and local limit theorems applied to asymptotic enumeration. J. Combinatorial Theory Ser. A 15, 91–111.Google Scholar
Bernstein, S. (1940a). Sur un problème du schéma des urnes à composition variable. C.R. (Doklady) Acad. Sci. URSS. 28, 5–7. (Also in Bernstein, 1964.)Google Scholar
Bernstein, S. (1940b). New applications of almost independent quantities. Izvestiia Akademii Nauk SSSR 4, 137–150. (In Russian. Also in Bernstein, 1964.)Google Scholar
Bernstein, S. (1946). Teoriia Veroiatnostei [The Theory of Probability], 4th edn. Nauka, Moscow.Google Scholar
Bernstein, S. (1964). Sobranie Sochinenii [Collected Works]. Tom IV: Teoriia Veroiatnostei. Mathematicheskaia Statistika 1911–1946. Nauka, Moscow.Google Scholar
Bienaymé, I. J. (1874). Sur une question de probabilités. Bull. Math. Soc. France 2, 153–154.Google Scholar
Brenti, F. (1989). Unimodal, log-concave and Pólya frequency sequences in combinatorics. (Mem. Amer. Math. Soc. 81,). AMS, Providence, RI.Google Scholar
Carlitz, L., Kurtz, D. C., Scoville, R., Stackelberg, O. P. (1972). Asymptotic properties of Eulerian numbers. Z. Wahrschleinlichkeitsch. 23, 47–54.Google Scholar
David, F. N., and Barton, D. E. (1962). Combinatorial Chance. Griffin, London.Google Scholar
Eggenberger, F. (1924). Die Wahrschleinlichkeitsansteckung. Mitt. Verein. Schweiz. Versich.–Math 19, 31–143.Google Scholar
Eggenberger, F. and Pólya, G. (1923). Über die Statistik verketteter Vorgänge. Z. Angew. Math. Mech. 3, 279–289.Google Scholar
Esséen, C. G. (1985). On the application of the theory of probability to two combinatorial problems involving permuations. Proc. 7th Conference on Probability Theory, ed. Losifescu, M. VNU Science Press, Utrecht, pp. 137–147.Google Scholar
Feller, W. (1971). An Introduction to Probability Theory and its Applications, Vol. 2, 2nd edn. Wiley, New York, pp. 542–546.Google Scholar
Frobenius, G. (1910). Über die Bernoulli'schen Zahlen und die Eulerschen Polynome. In Sitzungsberichte der Preußischen Akademie der Wissenschaften, pp. 829–830.Google Scholar
Gleissberg, W. (1945). Eine Aufgabe der Kombinatorik und Wahrscheinlichkeitsrechnung. Rev. Fac. Sci. Univ. Istanbul (A) 10, 25–35.Google Scholar
Graham, R. L., Knuth, D. E., and Patashnik, O. (1994). Concrete Mathematics, 2nd edn. Addison-Wesley, Reading, MA.Google Scholar
Hald, A. (1990). A History of Probability and Statistics and Their Applications Before 1750. Wiley, New York.Google Scholar
Harper, L. H. (1967). Stirling behaviour is asymptotically normal. Ann. Math. Statist. 38, 410–414.Google Scholar
Heyde, C. C., and Seneta, E. (1977). I.J. Bienaymé. Statistical Theory Anticipated. Springer, New York.Google Scholar
Jacobsen, M. (1996). Laplace and the origin of the Ornstein–Uhlenbeck process. Bernoulli 2, 271–286.Google Scholar
Johnson, N. L., and Kotz, S. (1977). Urn Models and Their Application, 2nd edn. Wiley, New York.Google Scholar
Johnson, N. L., Kotz, S., and Kemp, A. W. (1992). Univariate Discrete Distributions, 2nd edn. Wiley, New York.Google Scholar
Kendall, M., and Plackett, R. L. (ed.) (1977). Studies in the History of Statistics and Probability, Vol. 2. Griffin, London.Google Scholar
Kotz, S., and Johnson, N. L. (ed.) (1988). Encyclopedia of Statistical Sciences, Vol. 9. Wiley, New York, pp. 429–430.Google Scholar
Kou, S. G., and Ying, Z. (1996). Asymptotics for a 2 × 2 table with fixed margins. Statistica Sinica, 6, 809–829.Google Scholar
Ku, S., and Seneta, E. (1994). The number of peaks in a stationary sample and orthant probabilities. J. Time Series Analysis 15, 385–403.Google Scholar
Kyriakoussis, A. (1984). A central limit theorem for numbers satisfying a class of triangular arrays. Discrete Math. 51, 41–46.Google Scholar
Laplace, P. S. (1812). Théorie Analytique des Probabilitiés, 1st edn. Paris. (1814). 2nd edn. (1820). 3rd edn.Google Scholar
Liagre, M. (1855). Sur la probabilité de l'existence d'une cause d'erreur régulière dans une série d'observations. Bulletins de l'Académie Royale des Sciences, des Lettres et des Beaux Arts de Belgique 22, 7–55.Google Scholar
MacMahon, P. A. (1908). Second memoir of the compositions of numbers. Phil. Trans. Roy. Soc. London (A) 207, 65–134.Google Scholar
De Moivre, A. (1730). Miscellanea Analytica de Seriebus et Quadraturis. Tonson and Watts, London.Google Scholar
Montmort, P. R. (1713). Essay d'Analyse sur les Jeux de Hazard. Revûe et augmentée de plusieurs Lettres, 2nd edn. Paris. Reprinted (1980). Chelsea, New York.Google Scholar
Pitman, J. (1997). Probabilistic bounds on the coefficients of polynomials with only real zeros. J. Combinatorial Theory (A) 77, 279–303.Google Scholar
Quine, M. P. (1994). Probability approximations for divisible discrete distributions. Austral. J. Statist. 36, 339–349.Google Scholar
Rutherford, R. S. G. (1954). On a contagious distribution. Ann. Math. Statist. 25, 703–713.Google Scholar
Savkevitch, V. (1940). Sur le schéma des urnes à composition variable. C.R. (Doklady) Acad. Sci. URSS. 28, 8–12.Google Scholar
Seal, H. L. (1949). The historical development of the use of generating functions in probability theory. Bull. Assoc. Actuaires Suisses 49, 209–228. Reprinted (1977) in Kendall and Plackett.Google Scholar
Shur, W. (1984). The negative contagion reflection of the Pólya–Eggenberger distribution. Commun. Statist. A.–Theory Methods 13, 877–885.Google Scholar
Sirazhdinov, S. H. (1979). Asymptotic expressions for Euler numbers. Izv. Akad. Nauk UzSSR Ser. Fiz.-Mat. Nauk. 6, 39–43. (In Russian.)Google Scholar
Stigler, S. (1986). Estimating serial correlation by visual inspection of diagnostic plots. Amer. Statistician 40, 111–116.Google Scholar
Suzuki, G. (1980). Further modified forms of Binomial and Poisson distributions. Ann. Inst. Statist. Math. 32, 143–159.Google Scholar
Szegö, G. (1975). Orthogonal Polynomials. American Mathematical Society, Rhode Island.Google Scholar
Todhunter, I. (1865). A History of the Mathematical Theory of Probability from the Time of Pascal to that of Laplace. Macmillan, London. Reprinted (1949). Chelsea, New York.Google Scholar
Vatutin, V. A. (1994). Limit theorems for the number of ascending segments in random permutations generated by sorting algorithms. Discrete Math. Appl. 4, 31–44.Google Scholar
Vatutin, V. A., and Mikhailov, V. G. (1982). Limit theorems for the number of empty cells in an equiprobable scheme for group allocation of particles. Theory Prob. Appl. 27, 734–743.Google Scholar
Warren, D. (1997). Polynomial probability generating functions with all roots real. Univ. Sydney (School Math. Statist.) Research Series. 97-32, pp. 1–25. Available at http://www.maths.usyd.edu.au:8000/.Google Scholar
Warren, D., and Seneta, E. (1996). Peaks and Eulerian numbers in a random sequence. J. Appl. Prob. 33, 101–114.Google Scholar
Woodbury, M. A. (1949). On a probability distribution. Ann. Math. Statist. 20, 311–313.Google Scholar