Abstract
We consider a random walk in \(\mathbb {Z}^2\) and establish a number of results for the distributions and expectations of the number of usual (undirected) and specifically defined in the paper directed state-crossings and different sets of states crossings. As well, we extend the results to d-dimensional random walks, \(d\ge 2\), in bounded areas.
Similar content being viewed by others
References
Abramov VM (1991) Investigation of the queueing system with service depending on queue-length. Donish, Dushanbe. (In Rissian with Tajik resume.)
Abramov VM (1994) Asymptotic distribution of the maximum number of infectives in epidemic models with immigration. J Appl Probab 31:606–613
Abramov VM (1997) On a property of a refusals stream. J Appl Probab 34:800–805
Abramov VM (2001) Inequalities for the \(GI/M/1/n\) queues. J Appl Probab 38:232–324
Abramov VM (2006) Stochastic inequalities for single-server loss queueing systems. Stoch Anal Appl 24:1205–1221
Abramov VM (2009) Queueing Systems, Networks and Telecommunication Systems. (PhD dissertation.) Lambert Academic Publ., Saarbrücken
Abramov VM (2010) Takács’ asymptotic theorem and its applications a survey. Acta Appl Math 109:609–651
Abramov VM (2013) Characterization theorem on losses in \(GI^X/GI^Y/1/n\) queues. Operat Res Lett 41:150–152
Abramov VM (2018) Conservative and semiconservative random walks: recurrence and transience. J Theoret Probab 31(3):1900–1922. Correction. J. Theoret. Probab., 32 (1) (2019), 541–543
Adler RJ (1976a) Excursion above a fixed level by n-dimensional random fields. J Appl Probab 13:276–289
Adler RJ (1976b) On generalization the notion of uppcrossings to random fields. Adv Appl Probab 8:789–805
Adler RJ, Hasofer AM (1976) Level-crossings for random fields. Ann Probab 4:1–12
Azoury K, Brill PH (1986) An application of the system-point method to inventory models under continuous review. J Appl Probab 23:778–789
Brill PH (1979) An imbedded level-crossing techniques for dams and queues. J Appl Probab 16:405–410
Brill PH (2008) Level-crossing Method in Stochastic Models. Springer, New York
Brill PH, Posner MJM (1977) Level-crossings in point processes applied to queues: Single server case. Operat Res 25:662–673
Burq ZA, Jones OD (2008) Simulation of Brownian motion at first-passage times. Mathem Comput Simulat 77:64–71
Cohen JW (1976) On Regenerative Processes in Queueing Theory. Springer, Berlin
Cohen JW (1977) On up- and down-crossings. J Appl Probab 14:405–410
Doob JL (1953) Stochastic Processes. John Wiley, New York
Doyle PG, Snell JL (1984) Random Walks and Electric Networks. Mathematical Association of America, Washington DC
Durrett R (2013) Probability: Theory and Examples, 4.1 ed. Cambridge Univ. Press, Cambridge
Feller W (1991) An Introduction to Probability Theory and Its Applications. Vol. II, Second ed. John Wiley, New York
Hughes BD (1995) Random Walks and Random Environments. Volume 1: Random Walks. Clarendon Press, Oxford
Jarrow RA, Protter P, Sezer D (2007) Information reduction via level-crossings in a credit risk model. Finance and Stoch 11:195–212
Jones OD, Shen Y (2004) Estimating the Hurst index in self-similar process via crossing tree. IEEE Signal Process Lett 11:416–419
Kratz M (2006) Level crossings and other level functionals of stationary Gaussian processes. Probab Surv 3:230–288
Łochowski RM, Ghomrasni R (2014) Integral and local limit theorems for level-crossings of diffusions and Skorohod problem. Electron J Probab 19(10):1–33
Lyons R, Peres Y (2016) Probability on Trees and Networks. Cambridge University Press
Mijatovíc A, Vysotsky V (2020a) Stability of overshoots of zero-mean random walks. Electron J Probab 25(63):1–22
Mijatovíc A, Vysotsky V (2020b) Stationary entrance Markov chains, inducing, and level-crossings of random walks. Preprint. Accessible at https://arxiv.org/pdf/1808.05010.pdf
Righter R (1999) A note on losses in \(M/G/1/n\) queues. J Appl Probab 36:1240–1243
Rolls DA, Jones OD (2015) An improved test for continuous local martingales. Comm Statist Theor Meth 44:2674–2688
Sezer D (2007) Filtration shrinkage by level-crossings of a diffusion. Ann Probab 35:739–757
Spitzer F (2001) Principles of Random Walk, 2nd edn. Springer, Heidelberg
Szekély GJ (1986) Paradoxes in Probability Theory and Mathematical Statistics. Akademiai Kiado, Budapest
Wolff RW (1982) Poisson arrivals see time average. Operat Res 30:223–231
Wolff RW (1989) Stochastic Modeling and the Theory of Queues. Prentice Hall, Englewood Cliffs
Wolff RW (2002) Losses per cycle in a single-server queue. J Appl Probab 39:905–909
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendix: Derivation of the Formula for the Transition Probability from \(\mathcal {N}(n)\) to \(\mathcal {N}(n+1)\) for the Random Walk in \(\mathbb {Z}^d\)
Appendix: Derivation of the Formula for the Transition Probability from \(\mathcal {N}(n)\) to \(\mathcal {N}(n+1)\) for the Random Walk in \(\mathbb {Z}^d\)
The results of the appendix are taken from Abramov (2018), pp. 1906–1908.
1.1 Description of the Model
The random walk in \(\mathbb {Z}^d\) is modelled by the d independent queueing processes as follows. Assume that arrivals in the ith queueing system are Poisson with rate \(\lambda\), and service times are exponentially distributed with the parameter \(\lambda\). If a system becomes free, it is switched for a special service, which is exponentially distributed with the same parameter \(\lambda\). This service is negative, and it results in a new customer in the queue. If during a negative service a new arrival occurs, the negative service remains unfinished and not resumed. The negative service models the reflection at zero and in fact implies the state-dependent arrival rate, which becomes equal to \(2\lambda\) at the moment when the system is empty. It is associated with the situation, when an original one-dimensional random walk reaches zero at some time moment s, and at the next time moment \(s + 1\) it must take one of the values \(\pm 1\) that corresponds to value \(+1\) for an one-dimensional random walk reflected at zero.
1.2 Queueing Systems with Finite Capacity and Characterization of the Level n Probability
Assume that the number of waiting places in each of the queueing system is N. The assumption on limited number of waiting places means that an arriving customer, who meets N customers in the system, is lost. For a vector \(\mathbf {n}=\big (n^{(1)}, n^{(2)},\ldots , n^{(d)}\big )\) satisfying \(\Vert \mathbf {n}\Vert <N\) let \(P_N(\mathbf {n})\) denote the stationary probability to be in state \(\mathbf {n}\) immediately before arrival of a customer in one of the d queueing systems. Application of the PASTA property Wolff (1982) enables us to first obtain the stationary probability for each single system to obtain then the required stationary probability \(P_N(\mathbf {n})\). Let \(P_N^{(i)}(n)\) denote the stationary probability to be in state \(n<N\) for the ith queueing system. We have
Hence the queueing systems are independent, the product form solution for \(P_N(\mathbf {n})\) is
where \(d_0(\mathbf {n})\) denotes the number of zero components in the presentation of the vector \(\mathbf {n}\).
The total number of vectors having norm n in \(\mathbb {Z}^d_+\) is
(The formula sums over i being the number of nonzero components of the vector.) Hence, denoting the stationary state probability to belong to the set \(\mathcal {N}^+(n)\) by \(P_N[\mathcal {N}^+(n)]\), we have
where the term
on the right-hand side of (71) characterizes the total number of vectors in \(\mathbb {Z}^d\) having norm n.
It follows from (69) that for any two vectors \(\mathbf {n}_1\) and \(\mathbf {n}_2\) satisfying \(\Vert \mathbf {n}_1\Vert <N\) and \(\Vert \mathbf {n}_2\Vert <N\) we have
independently on N. Hence,
For \(N=\infty\), let \(P_\infty (\mathbf {n},\tau )\) be the probability that at time \(\tau\) the system with infinite capacity is in state \(\mathbf {n}\). Then, for the limiting ratio of the final probabilities we also have
The result in (74) is true, since the limit in (73) due to Relation (72) is uniform, and interchanging the order of limits \(\tau\) vs N is correct. (The last can also be established directly Abramov (2018)).
Let \(p_n(d)\) denote the transition probability from the set of states \(\mathcal {N}^+ (n)\) (level n) to the set of states \(\mathcal {N}^+ (n+1)\) (level \(n + 1\)), and let \(q_n(d)\) = \(1-p_n(d)\) denote the transition probability from the level n to the level \(n-1\). Derive the formula for \(p_n(d)\).
The total number of vectors in the set \(\mathcal {N}^+ (n)\) is given by (70). Each vector contains d components. Hence, the total number of components in the set of vectors in \(\mathcal {N}^+ (n)\) is
Among them, the total number of zero components is
and the total number of nonzero components is
To derive the formula for \(p_n(d)\) let us build the sample space. The components of all vectors in \(\mathcal {N}^+ (n)\), the total number of which is given by (75), are not equally likely. According to (69), a nonzero component appears with two times higher probability than a zero component. To make the components equally likely, we are to extend the number of nonzero components by factor 2. Then the total number of equally likely components is to be equal to
Following (78), the sample space for level n contains
that is two times more than that given by (78). This is because it include possible transitions from each state (component) in the two directions. Specifically, let \(C_0(n, d)\) denote the number of possible transitions associated with reflections at zero (the number of zero components given in (76) multiplied by two), and let 2C(n, d) be the rest of transitions, the half of which are associated with the transitions from level n to \(n+1\) and another half with the transitions from level n to \(n-1\). So, C(n, d) is the number of nonzero components given in (77)
That is, the expression in (77) is presented as
Then, the total number of transitions from level n to \(n+1\) is \(C_0(n, d)+C(n, d)\) and the total number of transitions from level n to \(n-1\) is C(n, d). Then, from (76), (77) and (79) we obtain
Rights and permissions
About this article
Cite this article
Abramov, V.M. Crossings States and Sets of States in Random Walks. Methodol Comput Appl Probab 25, 28 (2023). https://doi.org/10.1007/s11009-023-09979-0
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s11009-023-09979-0
Keywords
- Simple random walks
- Level-crossings and state-crossings
- Undirected state-crossings
- Directed state crossings
- Birth-and-death processes
- Markovian single-server queues
- Markov fields
- Branching processes