×

On the number of jumps of random walks with a barrier. (English) Zbl 1157.60041

Let \(S_0= 0\) and \(S_k= \xi_1+\cdots +\xi_k\), \(k\in\mathbb{N}\), where \(\{\xi_k: k\in\mathbb{N}\}\) is a sequence of i.i.d. \(\mathbb{N}\)-valued random variables, fix \(n\in\mathbb{N}\), and define a random walk with barrier \(n\), \(\{R^{(n)}_k: k\in\{0\}\cup\mathbb{N}\}\), by \(R^{(n)}_0= 0\) and \(R^{(n)}_k= R^{(n)}_{k-1}+ \xi_k I\{R^{(n)}_{k-1}+_\xi< n\}\), \(k\in\mathbb{N}\). Let \(M_n\) denote the number of jumps in the process \(\{R^{(n)}_k: k\in\{0\}\cup\mathbb{N}\}\). The main aim of the paper is to investigate the asymptotic behaviour of \(M_n\) as \(n\to\infty\). Here is a sample result.
Theorem. If \(P(\xi_1\geq n)\sim L(n)/n^\alpha\) for some function \(L\) slowly varying at \(\infty\) and some \(\alpha\neq ]0,1[\), then \[ M_nL(n)/n^\alpha@>D>>\int^\infty_0 e^{-U_t} dt, \] where \(\{U_t: t\geq 0\}\) is a drift-free subordinator with Lévy measure \(\nu(dt)= e^{-t/\alpha}/(1- e^{-t/\alpha})^{\alpha+1}dt\), \(t> 0\). The authors apply their results to derive limiting theorems for the number of collisions that take place in certain beta-coalescent processes until a single block is formed.

MSC:

60G50 Sums of independent random variables; random walks
60F05 Central limit and other weak theorems
05C05 Trees
60E07 Infinitely divisible distributions; stable distributions
Full Text: DOI

References:

[1] Alsmeyer, G. (1991). Some relations between harmonic renewal measures and certain first passage times. Statist. Prob. Lett. 12 , 19–27. · Zbl 0733.60093 · doi:10.1016/0167-7152(91)90160-S
[2] Alsmeyer, G., Iksanov, A. and Rösler, U. (2007). On distributional properties of perpetuities. Submitted. · Zbl 1173.60309
[3] Bai, Z. D., Hwang, H. K. and Liang, W. Q. (1998). Normal approximations of the number of records in geometrically distributed random variables. Random Structures Algorithms 13 , 319–334. · Zbl 0961.60040 · doi:10.1002/(SICI)1098-2418(199810/12)13:3/4<319::AID-RSA7>3.0.CO;2-Y
[4] Barbour, A. D. and Gnedin, A. V. (2006). Regenerative compositions in the case of slow variation. Stoch. Process. Appl. 116 , 1012–1047. · Zbl 1114.60030 · doi:10.1016/j.spa.2005.12.006
[5] Basdevant, A. L. and Goldschmidt, C. (2007). Asymptotics of the allele frequency spectrum associated with the Bolthausen–Sznitman coalescent. Submitted. · Zbl 1190.60006
[6] Berestycki, J., Berestycki, N. and Schweinsberg, J. (2007). Small time behavior of beta coalescents. To appear in Ann. Inst. H. Poincaré Prob. Statist. · Zbl 1129.60067 · doi:10.1214/009117906000001114
[7] Bertoin, J. and Yor, M. (2001). On subordinators, self-similar Markov processes and some factorization of the exponential variable. Electron. Commun. Prob. 6 , 95–106. · Zbl 1024.60030
[8] Bingham, N. H. (1972). Limit theorems for regenerative phenomena, recurrent events and renewal theory. Z. Wahrscheinlichkeitsth. 21 , 20–44. · Zbl 0212.20001 · doi:10.1007/BF00535105
[9] Bingham N. H., Goldie C. M. and Teugels, J. L. (1989). Regular Variation . Cambridge University Press. · Zbl 0667.26003
[10] Carmona, P., Petit, F. and Yor, M. (1997). On the distribution and asymptotic results for exponential functionals of Lévy processes. In Exponential Functionals and Principal Values Related to Brownian Motion , ed. M. Yor, Rev. Mate. Iberoamericana, Madrid, pp. 73–121. · Zbl 0905.60056
[11] Cramer, M. and Rüschendorf, L. (1995). Analysis of recursive algorithms by the contraction method. In Athens Conference on Applied Probability and Time Series Analysis , Vol. 1, Springer, New York, pp. 18–33. · Zbl 0858.60036
[12] De Haan, L. and Resnick, S. I. (1979). Conjugate \(\Pi\)-variation and process inversion. Ann. Prob. 7 , 1028–1035. · Zbl 0428.60033 · doi:10.1214/aop/1176994895
[13] Delmas, J. F., Dhersin, J. S. and Siri-Jegousse, A. (2007). Asymptotic results on the length of coalescent trees. To appear in Ann Appl. Prob. · Zbl 1141.60007 · doi:10.1214/07-AAP476
[14] Drmota, M., Iksanov, A., Möhle, M. and Rösler, U. (2006). A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree. To appear in Random Structures Algorithms.
[15] Drmota, M., Iksanov, A., Möhle, M. and Rösler, U. (2007). Asymptotic results concerning the total branch length of the Bolthausen–Sznitman coalescent. Stoch. Process. Appl. 117 , 1404–1421. · Zbl 1129.60069 · doi:10.1016/j.spa.2007.01.011
[16] Erickson, K. B. (1970). Strong renewal theorems with infinite mean. Trans. Amer. Math. Soc. 151 , 263–291. JSTOR: · Zbl 0212.51601 · doi:10.2307/1995628
[17] Feller, W. (1949). Fluctuation theory of recurrent events. Trans. Amer. Math. Soc. 67 , 98–119. JSTOR: · Zbl 0039.13301 · doi:10.2307/1990420
[18] Gnedin, A. V. (2004). The Bernoulli sieve. Bernoulli 10 , 79–96. · Zbl 1044.60005 · doi:10.3150/bj/1077544604
[19] Gnedin, A. and Yakubovich, Y. (2007). On the number of collisions in \(\Lambda\)-coalescents. Electron. J. Prob. 12 , 1547–1567. · Zbl 1190.60061
[20] Gnedin, A., Pitman, J. and Yor, M. (2006). Asymptotic laws for compositions derived from transformed subordinators. Ann. Prob. 34 , 468–492. · Zbl 1142.60327 · doi:10.1214/009117905000000639
[21] Gnedin, A., Pitman, J. and Yor, M. (2006). Asymptotic laws for regenerative compositions: gamma subordinators and the like. Prob. Theory Relat. Fields 135 , 576–602. · Zbl 1099.60023 · doi:10.1007/s00440-005-0473-0
[22] Heyde, C. C. (1967). A limit theorem for random walks with drift. J. Appl. Prob. 4 , 144–150. JSTOR: · Zbl 0152.16602 · doi:10.2307/3212307
[23] Hinderer, K. and Walk, H. (1972). Anwendungen von Erneuerungstheoremen und Taubersätzen für eine Verallgemeinerung der Erneuerungsprozesse. Math. Z. 126 , 95–115. · Zbl 0217.50304 · doi:10.1007/BF01122317
[24] Iksanov, A. and Möhle, M. (2007). A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree. Electron. Commun. Prob. 12 , 28–35. · Zbl 1133.60012
[25] Iksanov, A. and Möhle, M. (2007). On a random recursion related to absorption times of death Markov chains. Preprint. Available at www.arxiv.org.
[26] Iksanov, A., Marynych, A. and Möhle, M. (2007). On the number of collisions in beta(\(2,b\))-coalescents. Submitted. · Zbl 1208.60081
[27] Möhle, M. (2006). On the number of segregating sites for populations with large family sizes. Adv. Appl. Prob. 38 , 750–767. · Zbl 1112.92046 · doi:10.1239/aap/1158685000
[28] Neininger, R. and Rüschendorf, L. (2004). On the contraction method with degenerate limit equation. Ann. Prob. 32 , 2838–2856. · Zbl 1060.60005 · doi:10.1214/009117904000000171
[29] Panholzer, A. (2003). Non-crossing trees revisited: cutting down and spanning subtrees. In Discrete Mathematics and Theoretical Computer Science , pp. 265–276. · Zbl 1073.60503
[30] Panholzer, A. (2006). Cutting down very simple trees. Quest. Math. 29 , 211–227. · Zbl 1120.05020 · doi:10.2989/16073600609486160
[31] Petersen, L. C. (1982). On the relation between the multidimensional moment problem and the one-dimensional moment problem. Math. Scand. 51 , 361–366. · Zbl 0514.44007
[32] Pitman, J. (1999). Coalescents with multiple collisions. Ann. Prob. 27 , 1870–1902. · Zbl 0963.60079 · doi:10.1214/aop/1022677552
[33] Port, S. C. (1964). Some theorems on functionals of Markov chains. Ann. Math. Statist. 35 , 1275–1290. · Zbl 0133.10603 · doi:10.1214/aoms/1177703283
[34] Rösler, U. (1991). A limit theorem for “Quicksort”. RAIRO Inform. Théor. Appl. 25 , 85–100. · Zbl 0718.68026
[35] Rösler, U. and Rüschendorf, L. (2001). The contraction method for recursive algorithms. Algorithmica 29 , 3–33. · Zbl 0967.68166 · doi:10.1007/s004530010053
[36] Ross, S. M. (1982). A simple heuristic approach to simplex efficiency. Europ. J. Operat. Res. 9 , 344–346. · Zbl 0477.90037 · doi:10.1016/0377-2217(82)90177-1
[37] Sagitov, S. (1999). The general coalescent with asynchronous mergers of ancestral lines. J. Appl. Prob. 36 , 1116–1125. · Zbl 0962.92026 · doi:10.1239/jap/1032374759
[38] Urbanik, K. (1992). Functionals on transient stochastic processes with independent increments. Studia Math. 103 , 299–315. · Zbl 0809.60068
[39] Van Cutsem, B. and Ycart, B. (1994). Renewal-type behaviour of absorption times in Markov chains. Adv. Appl. Prob. 26 , 988–1005. JSTOR: · Zbl 0816.60065 · doi:10.2307/1427901
[40] Vervaat, W. (1979). On a stochastic difference equation and a representation of nonnegative infinitely divisible random variables. Adv. Appl. Prob. 11 , 750–783. JSTOR: · Zbl 0417.60073 · doi:10.2307/1426858
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.