×

The range of random walk on trees and related trapping problem. (English) Zbl 0889.60078

Let \(T_N\) \((N\geq 2)\) be the infinite tree with \(N+1\) branches emanating from each vertex. Let also \(\{X_n\}_{n\geq 0}\) be the simple random walk on \(T_N\) with the probability law \(\{P_x\}_{x\in T_N}\). The range of \(\{X_n\}_{n\geq 0}\) up to time \(n\) is denoted by \(R_n= \#\{X_0, X_t,\dots, X_n\}\). Let also \(\zeta\) denote a standard normal variable and let \(E_x\) be the expectation with respect to \(P_x\). The main result of the paper is as follows: (i) \(\lim_{n\to\infty} R_n/n= (N- 1)/N\), \(P_0\)-a.s., (ii) \(\lim_{n\to\infty}\text{ var}(R_n)/n= (N^2+ 1)/[N^2(n- 1)]\), (iii) \((R_n- E_0R_n)/n^{1/2} @>d>>\zeta(N^2+ 1)/[N^2(N- 1)]\), \(n\to\infty\). Some results concerning asymptotic behavior for the mean trapping time and survival probability are presented, too.

MSC:

60G50 Sums of independent random variables; random walks
60F05 Central limit and other weak theorems
60K30 Applications of queueing theory (congestion, allocation, storage, traffic, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P.G. Doyle and J.L. Snell. Random Walks and Electric Networks. Washington DC, Math. Assoc. Amer., 1984. · Zbl 0583.60065
[2] P. Gerl and W. Woess. Local Limits and Harmonic Functions for Nonisotropic Random Walks on Free Groups.Prob. Th. Rel. Fields, 1986, 71: 341–355. · Zbl 0562.60011 · doi:10.1007/BF01000210
[3] F. den Hollander and K.E. Shuler. Random Walks in a Random Field of Decaying Traps.J. Statis. Phys., 1992, 67: 13–31. · Zbl 0962.82531 · doi:10.1007/BF01049025
[4] F. den Hollander and G.H. Weiss. Aspects of Trapping in Transport Processes. To appear in ”Some Problems in Statistical Physics”, published by SIAM, 1992.
[5] N.C. Jain and W.E. Pruitt. The Range of Transient Random Walk.J. Analyse Math., 1971, 24: 369–373. · Zbl 0249.60038 · doi:10.1007/BF02790380
[6] J.F. Le Gall and J. Rosen. The Range of Stable Random Walks.Ann. Prob., 1991, 19: 650–705. · Zbl 0729.60066 · doi:10.1214/aop/1176990446
[7] S. Sawyer. Isotropic Random Walks in a Tree.Z. W. Verw Gebiete, 1978, 42: 279–292. · Zbl 0362.60075 · doi:10.1007/BF00533464
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.