Asymptotics of Bernoulli random walks, bridges, excursions and meanders with a given number of peaks

Jean-Maxime Labarbe (LMV, Université de Versailles Saint-Quentin en Yvelines)
Jean-Francois Marckert (LaBRI, Université Bordeaux 1)

Abstract


A Bernoulli random walk is a random trajectory starting from 0 and having i.i.d. increments, each of them being +1 or -1, equally likely. The other families quoted in the title are Bernoulli random walks under various conditions. A peak in a trajectory is a local maximum. In this paper, we condition the families of trajectories to have a given number of peaks. We show that, asymptotically, the main effect of setting the number of peaks is to change the order of magnitude of the trajectories. The counting process of the peaks, that encodes the repartition of the peaks in the trajectories, is also studied. It is shown that suitably normalized, it converges to a Brownian bridge which is independent of the limiting trajectory. Applications in terms of plane trees and parallelogram polyominoes are provided, as well as an application to the ``comparison'' between runs and Kolmogorov-Smirnov statistics.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 229-261

Publication Date: March 11, 2007

DOI: 10.1214/EJP.v12-397

References

  1. Aldous, David. The continuum random tree. II. An overview. Stochastic analysis (Durham, 1990), 23--70, London Math. Soc. Lecture Note Ser., 167, Cambridge Univ. Press, Cambridge, 1991. MR1166406 (93f:60010)
  2. Belkin, Barry. An invariance principle for conditioned recurrent random walk attracted to a stable law. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 21 (1972), 45--64. MR0309200 (46 #8310)
  3. Bertoin, Jean; Chaumont, Loïc; Pitman, Jim. Path transformations of first passage bridges. Electron. Comm. Probab. 8 (2003), 155--166 (electronic). MR2042754 (2005d:60132)
  4. Bertoin, Jean; Pitman, Jim. Path transformations connecting Brownian bridge, excursion and meander. Bull. Sci. Math. 118 (1994), no. 2, 147--166. MR1268525 (95b:60097)
  5. Biane, Ph.; Yor, M. Valeurs principales associées aux temps locaux browniens. (French) [Principal values associated with Brownian local times] Bull. Sci. Math. (2) 111 (1987), no. 1, 23--101. MR0886959 (88g:60188)
  6. Billingsley, Patrick. Convergence of probability measures. John Wiley & Sons, Inc., New York-London-Sydney 1968 xii+253 pp. MR0233396 (38 #1718)
  7. Csáki, Endre; Hu, Yueyun. Invariance principles for ranked excursion lengths and heights. Electron. Comm. Probab. 9 (2004), 14--21 (electronic). MR2041301 (2005f:60076)
  8. Delest, Marie-Pierre; Viennot, Gérard. Algebraic languages and polyominoes enumeration. Theoret. Comput. Sci. 34 (1984), no. 1-2, 169--206. MR0774044 (86e:68062)
  9. de Sainte-Catherine, Myriam; Viennot, Gérard. Combinatorial interpretation of integrals of products of Hermite, Laguerre and Tchebycheff polynomials. Orthogonal polynomials and applications (Bar-le-Duc, 1984), 120--128, Lecture Notes in Math., 1171, Springer, Berlin, 1985. MR0838977 (87g:05007)
  10. Duquesne, Thomas; Le Gall, Jean-François. Random trees, Lévy processes and spatial branching processes. Astérisque No. 281 (2002), vi+147 pp. MR1954248 (2003m:60239)
  11. Iglehart, Donald L. Functional central limit theorems for random walks conditioned to stay positive. Ann. Probability 2 (1974), 608--619. MR0362499 (50 #14939)
  12. Janson, Svante; Marckert, Jean-François. Convergence of discrete snakes. J. Theoret. Probab. 18 (2005), no. 3, 615--647. MR2167644 (2006g:60126)
  13. Kaigh, W. D. An invariance principle for random walk conditioned by a late return to zero. Ann. Probability 4 (1976), no. 1, 115--121. MR0415706 (54 #3786)
  14. Krattenthaler, C. The enumeration of lattice paths with respect to their number of turns. Advances in combinatorial methods and applications to probability and statistics, 29--58, Stat. Ind. Technol., Birkhäuser Boston, Boston, MA, 1997. MR1456725 (98f:05006)
  15. Liggett, Thomas M. An invariance principle for conditioned sums of independent random variables. J. Math. Mech. 18 1968 559--570. MR0238373 (38 #6649)
  16. Marckert, Jean-François; Mokkadem, Abdelkader. The depth first processes of Galton-Watson trees converge to the same Brownian excursion. Ann. Probab. 31 (2003), no. 3, 1655--1678. MR1989446 (2004g:60120)
  17. Marchal, Philippe. Constructing a sequence of random walks strongly converging to Brownian motion. Discrete random walks (Paris, 2003), 181--190 (electronic), Discrete Math. Theor. Comput. Sci. Proc., AC, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2003. MR2042386 (2004m:60099)
  18. Narayana, T. V. A partial order and its applications to probability theory. Sankhy\=a 21 1959 91--98. MR0106498 (21 #5230)
  19. Petrov, Valentin V. Limit theorems of probability theory. Sequences of independent random variables. Oxford Studies in Probability, 4. Oxford Science Publications. The Clarendon Press, Oxford University Press, New York, 1995. xii+292 pp. ISBN: 0-19-853499-X MR1353441 (96h:60048)
  20. Pitman, Jim. Brownian motion, bridge, excursion, and meander characterized by sampling at independent uniform times. Electron. J. Probab. 4 (1999), no. 11, 33 pp. (electronic). MR1690315 (2000e:60137)
  21. Pitman, J. Combinatorial stochastic processes. Lectures from the 32nd Summer School on Probability Theory held in Saint-Flour, July 7--24, 2002. With a foreword by Jean Picard. Lecture Notes in Mathematics, 1875. Springer-Verlag, Berlin, 2006. x+256 pp. ISBN: 978-3-540-30990-1; 3-540-30990-X MR2245368
  22. Ra\v ckauskas, A.; Suquet, Ch. Principe d'invariance hölderien pour des tableaux triangulaires de variables aléatoires. [Holderian invariance principle for triangular arrays of random variables] (French) Liet. Mat. Rink. 43 (2003), no. 4, 513--532; translation in Lithuanian Math. J. 43 (2003), no. 4, 423--438 MR2058924 (2005f:60087)
  23. Stanley, Richard P. Enumerative combinatorics. Vol. 2. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. Cambridge Studies in Advanced Mathematics, 62. Cambridge University Press, Cambridge, 1999. xii+581 pp. ISBN: 0-521-56069-1; 0-521-78987-7 MR1676282 (2000k:05026)
  24. Wald, A.; Wolfowitz, J. On a test whether two samples are from the same population. Ann. Math. Statistics 11, (1940). 147--162. MR0002083 (1,348b)


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.