Home | Current | Past volumes | About | Login | Notify | Contact | Search
 Probability Surveys > Vol. 4 (2007) open journal systems 


Brownian excursion area, Wright's constants in graph enumeration, and other Brownian areas

Svante Janson, Uppsala University


Abstract
This survey is a collection of various results and formulas by different authors on the areas (integrals) of five related processes, viz. Brownian motion, bridge, excursion, meander and double meander; for the Brownian motion and bridge, which take both positive and negative values, we consider both the integral of the absolute value and the integral of the positive (or negative) part. This gives us seven related positive random variables, for which we study, in particular, formulas for moments and Laplace transforms; we also give (in many cases) series representations and asymptotics for density functions and distribution functions. We further study Wright's constants arising in the asymptotic enumeration of connected graphs; these are known to be closely connected to the moments of the Brownian excursion area. The main purpose is to compare the results for these seven Brownian areas by stating the results in parallel forms; thus emphasizing both the similarities and the differences. A recurring theme is the Airy function which appears in slightly different ways in formulas for all seven random variables. We further want to give explicit relations between the many different similar notations and definitions that have been used by various authors. There are also some new results, mainly to fill in gaps left in the literature. Some short proofs are given, but most proofs are omitted and the reader is instead referred to the original sources.

AMS 2000 subject classifications: Primary 60J65; secondary 05C30, 60G15.

Creative Common LOGO

Full Text: PDF


Janson, Svante, Brownian excursion area, Wright's constants in graph enumeration, and other Brownian areas, Probability Surveys, 4, (2007), 80-145 (electronic). DOI: 10.1214/07-PS104.

References

[1]    M. Abramowitz & I. A. Stegun, eds., Handbook of Mathematical Functions. Dover, New York, 1972.

[2]     D. Aldous, Brownian excursions, critical random graphs and the multiplicative coalescent. Ann. Probab. 25 (1997), 812–854. MR1434128

[3]    B. L. Altshuler, A. G. Aronov & D. E. Khmelnitsky, Effects of electron-electron collisions with small energy transfers on quantum localisation. J. Phys. C: Solid State. Phys. 15 (1982) 7367–7386.

[4]     G. N. Bagaev & E. F. Dmitriev, Enumeration of connected labeled bipartite graphs. (Russian.) Doklady Akad. Nauk BSSR 28 (1984), 1061–1063. MR0775755

[5]     E. A. Bender, E. R. Canfield & B. D. McKay, Asymptotic properties of labeled connected graphs. 32 (1992), 183–202. MR1151361

[6]    J. Bertoin, J. Pitman & J. Ruiz de Chavez, Constructions of a Brownian path with a given minimum. Electron. Comm. Probab. 4 (1999), 31–37. MR1703609

[7]    A. N. Borodin & P. Salminen, Handbook of Brownian motion—facts and formulae. 2nd edition. Birkhäuser, Basel, 2002. MR1912205

[8]     P. Chassaing & G. Louchard, Reflected Brownian bridge area conditioned on its local time at the origin. J. Algorithms 44 1 (2002), 29–51. MR1932676

[9]     D. M. Cifarelli, Contributi intorno ad un test per l’omogeneità tra due campioni. Giorn. Econom. Ann. Econom. (N.S.) 343–4 (1975), 233–249. MR0433704

[10]    A. Comtet, J. Desbois & C. Texier, Functionals of Brownian motion, localization and metric graphs. J. Phys. A 38 (2005), no. 37, R341–R383. MR2169321

[11]     M. Csörgʺo  , Z. Shi & M. Yor, Some asymptotic properties of the local time of the uniform empirical process. Bernoulli 5 (1999), no. 6, 1035–1058. MR1735784

[12]     D. A. Darling, On the supremum of a certain Gaussian process. Ann. Probab. 113 (1983), 803–806. MR0704564

[13]    I. V. Denisov, Random walk and the Wiener process considered from a maximum point. (Russian.) Teor. Veroyatnost. i Primenen. 28 (1983), no. 4, 785–788. English translation: Theory Probab. Appl. 28 (1983), no. 4, 821–824. MR0726906

[14]    R. T. Durrett, D. L. Iglehart & D. R. Miller, Weak convergence to Brownian meander and Brownian excursion. Ann. Probab. 5 (1977), no. 1, 117–129. MR0436353

[15]     W. Feller, An Introduction to Probability Theory and its Applications, Vol. II. 2nd ed., Wiley, New York, 1971. MR0270403

[16]     J. A. Fill & S. Janson, Precise logarithmic asymptotics for the right tails of some limit random variables for random trees. Preprint, 2007. http://www.arXiv.org/math.PR/0701259

[17]     P. Flajolet & G. Louchard, Analytic variations on the Airy distribution. Algorithmica 31 (2001), 361–377. MR1855255

[18]     P. Flajolet, P. Poblete & A. Viola, On the analysis of linear probing hashing. Algorithmica 224 (1998), 490–515. MR1701625

[19]     P. Groeneboom, Brownian motion with a parabolic drift and Airy functions. Probab. Theory Related Fields 81 (1989), no. 1, 79–109. MR0981568

[20]     S. Janson, Gaussian Hilbert Spaces. Cambridge Univ. Press, Cambridge, 1997. MR1474726

[21]    S. Janson, The Wiener index of simply generated random trees. 224 (2003), 337–358. MR1980963

[22]     S. Janson, Left and right pathlenghts in random binary trees. Algorithmica, 463/4 (2006), 419–429.

[23]     S. Janson & P. Chassaing, The center of mass of the ISE and the Wiener index of trees. Electronic Comm. Probab. 9 (2004), paper 20, 178–187. MR2108865

[24]     S. Janson, D. E. Knuth, T. Łuczak & B. Pittel, The birth of the giant component. 3 (1993), 233–358.

[25]    S. Janson & G. Louchard, Tail estimates for the Brownian excursion area and other Brownian areas. In preparation.

[26]     S. Janson & N. Petersson. In preparation.

[27]    M. Jeanblanc, J. Pitman & M. Yor, The Feynman–Kac formula and decomposition of Brownian paths. Mat. Apl. Comput. 16 (1997), no. 1, 27–52. MR1458521

[28]     B. McK. Johnson & T. Killeen, An explicit formula for the C.D.F. of the L1 norm of the Brownian bridge. Ann. Probab. 11 (1983), no. 3, 807–808. MR0704570

[29]     M. Kac, On the average of a certain Wiener functional and a related limit theorem in calculus of probability. Trans. Amer. Math. Soc. 59 (1946), 401–414. MR0016570

[30]     M. Kac, On distributions of certain Wiener functionals. Trans. Amer. Math. Soc. 65 (1949), 1–13. MR0027960

[31]     M. Kac, On some connections between probability theory and differential and integral equations. Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, 1950, University of California Press, Berkeley and Los Angeles, 1951, pp. 189–215. MR0045333

[32]    N. N. Lebedev, Special Functions and their Applications. Dover, New York, 1972. (Translated from Russian.) MR0350075

[33]     G. Louchard, Kac’s formula, Lévy’s local time and Brownian excursion. J. Appl. Probab. 213 (1984), 479–499. MR0752014

[34]     G. Louchard, The Brownian excursion area: a numerical analysis. Comput. Math. Appl. 106 (1984), 413–417. Erratum: Comput. Math. Appl. Part A 123 (1986), 375. MR0783514

[35]    S. N. Majumdar & A. Comtet, Airy distribution function: from the area under a Brownian excursion to the maximal height of fluctuating interfaces. J. Stat. Phys. 119 (2005), no. 3-4, 777–826. MR2151223

[36]     M. Nguyên Thê, Area of Brownian motion with generatingfunctionology. Discrete random walks (Paris, 2003), Discrete Math. Theor. Comput. Sci. Proc., AC, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2003, pp. 229–242, MR2042390

[37]     M. Nguyen The, Area and inertial moment of Dyck paths. Combin. Probab. Comput. 134–5 (2004), 697–716. MR2095979

[38]    M. Perman & J. A. Wellner, On the distribution of Brownian areas. Ann. Appl. Probab. 6 (1996), no. 4, 1091–1111. MR1422979

[39]    D. Revuz & M. Yor, Continuous martingales and Brownian motion. 3rd edition. , Berlin, 1999. MR1725357

[40]     S. O. Rice, The integral of the absolute value of the pinned Wiener process—calculation of its probability density by numerical integration. Ann. Probab. 10 (1982), no. 1, 240–243. MR0637390

[41]     C. Richard, On q-functional equations and excursion moments. Preprint, 2005. http://www.arXiv.org/math.CO/0503198

[42]     L. A. Shepp, On the integral of the absolute value of the pinned Wiener process. Ann. Probab. 10 1 (1982), 234–239. Acknowledgment of priority: Ann. Probab. 19 (1991), no. 3, 1397. MR0637389

[43]     J. Spencer, Enumerating graphs and Brownian motion. Comm. Pure Appl. Math. 503 (1997), 291–294. MR1431811

[44]     L. Takács, A Bernoulli excursion and its various applications. Adv. in Appl. Probab. 233 (1991), 557–585. MR1122875

[45]     L. Takács, On a probability problem connected with railway traffic. J. Appl. Math. Stochastic Anal. 4 1 (1991), 1–27. MR1095187

[46]     L. Takács, Conditional limit theorems for branching processes. J. Appl. Math. Stochastic Anal. 4 4 (1991), 263–292. MR1136428

[47]     L. Takács, Random walk processes and their applications to order statistics. Ann. Appl. Probab. 2 2 (1992), 435–459. MR1161061

[48]     L. Takács, On the total heights of random rooted binary trees. J. Combin. Theory Ser. B 612 (1994), 155–166. MR1280604

[49]     L. Takács, On the distribution of the integral of the absolute value of the Brownian motion. Ann. Appl. Probab. 31 (1993), 186–197. MR1202522

[50]    L. Takács, Limit distributions for the Bernoulli meander. J. Appl. Probab. 32 (1995), no. 2, 375–395. MR1334893

[51]    L. Tolmatz, Asymptotics of the distribution of the integral of the absolute value of the Brownian bridge for large arguments. Ann. Probab. 28 (2000), no. 1, 132–139. MR1756000

[52]    L. Tolmatz, The saddle point method for the integral of the absolute value of the Brownian motion. Discrete random walks (Paris, 2003), Discrete Math. Theor. Comput. Sci. Proc., AC, Nancy, 2003, pp. 309–324. MR2042397

[53]    L. Tolmatz, Asymptotics of the distribution of the integral of the positive part of the Brownian bridge for large arguments. J. Math. Anal. Appl. 304 (2005), no. 2, 668–682. MR2126559

[54]     W. Vervaat, A relation between Brownian bridge and Brownian excursion. Ann. Probab. 71 (1979), 143–149. MR0515820

[55]     V. A. Voblyĭ, O koeffitsientakh Raĭta i Stepanova-Raĭta. Matematicheskie Zametki 42 (1987), 854–862. English translation: Wright and Stepanov-Wright coefficients. Mathematical Notes 42 (1987), 969–974. MR0934817

[56]     G. S. Watson, Goodness-of-fit tests on a circle. Biometrika 48 (1961), 109–114. MR0131930

[57]    D. Williams, Path decomposition and continuity of local time for one-dimensional diffusions. I. Proc. London Math. Soc. (3) 28 (1974), 738–768. MR0350881

[58]     E. M. Wright, The number of connected sparsely edged graphs. J. Graph Th. 1 (1977), 317–330. MR0463026

[59]     E. M. Wright, The number of connected sparsely edged graphs. III. Asymptotic results. J. Graph Th. 4 (1980), 393–407. MR0595607




Home | Current | Past volumes | About | Login | Notify | Contact | Search

Probability Surveys. ISSN: 1549-5787