Log in

Relevant bibliographies by topics / Hitting time of random walk / Journal articles

To see the other types of publications on this topic, follow the link: Hitting time of random walk.

Journal articles on the topic 'Hitting time of random walk'

Author: Grafiati

Published: 9 March 2023

Last updated: 10 March 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Hitting time of random walk.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Emms, D., R. Wilson, and E. Hancock. "Graph embedding using quantum hitting time." Quantum Information and Computation 9, no. 3&4 (March 2009): 231–54. http://dx.doi.org/10.26421/qic9.3-4-4.

Full text

Abstract:

In this paper, we explore analytically and experimentally a quasi-quantum analogue of the hitting time of the continuous-time quantum walk on a graph. For the classical random walk, the hitting time has been shown to be robust to errors in edge weight structure and to lead to spectral clustering algorithms with improved performance. Our analysis shows that the quasi-quantum analogue of the hitting time of the continuous-time quantum walk can be determined via integrals of the Laplacian spectrum, calculated using Gauss-Laguerre quadrature. We analyse the quantum hitting times with reference to their classical counterpart. Specifically, we explore the graph embeddings that preserve hitting time. Experimentally, we show that the quantum hitting times can be used to emphasise cluster-structure.

APA, Harvard, Vancouver, ISO, and other styles

2

Lardizabal, Carlos F. "Open quantum random walks and the mean hitting time formula." Quantum Information and Computation 17, no. 1&2 (January 2017): 79–105. http://dx.doi.org/10.26421/qic17.1-2-5.

Full text

Abstract:

We make use of the Open Quantum Random Walk setting due to S. Attal, F. Petruccione, C. Sabot and I. Sinayskiy in order to discuss hitting times and a quantum version of the Mean Hitting Time Formula from classical probability theory. We study an open quantum notion of hitting probability on a finite collection of sites and with this we are able to describe the problem in terms of linear maps and its matrix representations. After setting an open quantum version of the fundamental matrix for ergodic Markov chains we are able to prove our main result and as consequence a version of the Random Target Lemma. We also study a mean hitting time formula in terms of the minimal polynomial associated to the matrix representation of the quantum walk. We discuss applications of the results to open quantum dynamics on graphs together with open questions.

APA, Harvard, Vancouver, ISO, and other styles

3

Aldous, David. "Hitting times for random walks on vertex-transitive graphs." Mathematical Proceedings of the Cambridge Philosophical Society 106, no. 1 (July 1989): 179–91. http://dx.doi.org/10.1017/s0305004100068079.

Full text

Abstract:

AbstractFor random walks on finite graphs, we record some equalities, inequalities and limit theorems (as the size of graph tends to infinity) which hold for vertex-transitive graphs but not for general regular graphs. The main result is a sharp condition for asymptotic exponentiality of the hitting time to a single vertex. Another result is a lower bound for the coefficient of variation of hitting times. Proofs exploit the complete monotonicity properties of the associated continuous-time walk.

APA, Harvard, Vancouver, ISO, and other styles

4

Meerschaert, Mark M., and Hans-Peter Scheffler. "Limit theorems for continuous-time random walks with infinite mean waiting times." Journal of Applied Probability 41, no. 3 (September 2004): 623–38. http://dx.doi.org/10.1239/jap/1091543414.

Full text

Abstract:

A continuous-time random walk is a simple random walk subordinated to a renewal process used in physics to model anomalous diffusion. In this paper we show that, when the time between renewals has infinite mean, the scaling limit is an operator Lévy motion subordinated to the hitting time process of a classical stable subordinator. Density functions for the limit process solve a fractional Cauchy problem, the generalization of a fractional partial differential equation for Hamiltonian chaos. We also establish a functional limit theorem for random walks with jumps in the strict generalized domain of attraction of a full operator stable law, which is of some independent interest.

APA, Harvard, Vancouver, ISO, and other styles

5

Meerschaert, Mark M., and Hans-Peter Scheffler. "Limit theorems for continuous-time random walks with infinite mean waiting times." Journal of Applied Probability 41, no. 03 (September 2004): 623–38. http://dx.doi.org/10.1017/s002190020002043x.

Full text

Abstract:

A continuous-time random walk is a simple random walk subordinated to a renewal process used in physics to model anomalous diffusion. In this paper we show that, when the time between renewals has infinite mean, the scaling limit is an operator Lévy motion subordinated to the hitting time process of a classical stable subordinator. Density functions for the limit process solve a fractional Cauchy problem, the generalization of a fractional partial differential equation for Hamiltonian chaos. We also establish a functional limit theorem for random walks with jumps in the strict generalized domain of attraction of a full operator stable law, which is of some independent interest.

APA, Harvard, Vancouver, ISO, and other styles

6

Afanasyev, Valeriy I. "On the non-recurrent random walk in a random environment." Discrete Mathematics and Applications 28, no. 3 (June 26, 2018): 139–56. http://dx.doi.org/10.1515/dma-2018-0014.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Bertoin, Jean. "On overshoots and hitting times for random walks." Journal of Applied Probability 36, no. 2 (June 1999): 593–600. http://dx.doi.org/10.1239/jap/1032374474.

Full text

Abstract:

Consider an oscillating integer valued random walk up to the first hitting time of some fixed integer x > 0. Suppose there is a fee to be paid each time the random walk crosses the level x, and that the amount corresponds to the overshoot. We determine the distribution of the sum of these fees in terms of the renewal functions of the ascending and descending ladder heights. The proof is based on the observation that some path transformation of the random walk enables us to translate the problem in terms of the intersection of certain regenerative sets.

APA, Harvard, Vancouver, ISO, and other styles

8

Bertoin, Jean. "On overshoots and hitting times for random walks." Journal of Applied Probability 36, no. 02 (June 1999): 593–600. http://dx.doi.org/10.1017/s0021900200017344.

Full text

Abstract:

Consider an oscillating integer valued random walk up to the first hitting time of some fixed integer x > 0. Suppose there is a fee to be paid each time the random walk crosses the level x, and that the amount corresponds to the overshoot. We determine the distribution of the sum of these fees in terms of the renewal functions of the ascending and descending ladder heights. The proof is based on the observation that some path transformation of the random walk enables us to translate the problem in terms of the intersection of certain regenerative sets.

APA, Harvard, Vancouver, ISO, and other styles

9

Haslegrave, John, Thomas Sauerwald, and John Sylvester. "Time Dependent Biased Random Walks." ACM Transactions on Algorithms 18, no. 2 (April 30, 2022): 1–30. http://dx.doi.org/10.1145/3498848.

Full text

Abstract:

We study the biased random walk where at each step of a random walk a “controller” can, with a certain small probability, move the walk to an arbitrary neighbour. This model was introduced by Azar et al. [STOC’1992]; we extend their work to the time dependent setting and consider cover times of this walk. We obtain new bounds on the cover and hitting times. Azar et al. conjectured that the controller can increase the stationary probability of a vertex from p to p 1-ε ; while this conjecture is not true in full generality, we propose a best-possible amended version of this conjecture and confirm it for a broad class of graphs. We also consider the problem of computing an optimal strategy for the controller to minimise the cover time and show that for directed graphs determining the cover time is PSPACE -complete.

APA, Harvard, Vancouver, ISO, and other styles

10

Kalikova, A. "Statistical analysis of random walks on network." Scientific Journal of Astana IT University, no. 5 (July 27, 2021): 77–83. http://dx.doi.org/10.37943/aitu.2021.99.34.007.

Full text

Abstract:

This paper describes an investigation of analytical formulas for parameters in random walks. Random walks are used to model situations in which an object moves in a sequence of steps in randomly chosen directions. Given a graph and a starting point, we select a neighbor of it at random, and move to this neighbor; then we select a neighbor of this point at random, and move to it etc. It is a fundamental dynamic process that arise in many models in mathematics, physics, informatics and can be used to model random processes inherent to many important applications. Different aspects of the theory of random walks on graphs are surveyed. In particular, estimates on the important parameters of hitting time, commute time, cover time are discussed in various works. In some papers, authors have derived an analytical expression for the distribution of the cover time for a random walk over an arbitrary graph that was tested for small values of n. However, this work will show the simplified analytical expressions for distribution of hitting time, commute time, cover time for bigger values of n. Moreover, this work will present the probability mass function and the cumulative distribution function for hitting time, commute time.

APA, Harvard, Vancouver, ISO, and other styles

11

Bulinskaya, E. Vl. "Hitting times with taboo for a random walk." Siberian Advances in Mathematics 22, no. 4 (October 2012): 227–42. http://dx.doi.org/10.3103/s1055134412040013.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

Serlet, Laurent. "Hitting times for the perturbed reflecting random walk." Stochastic Processes and their Applications 123, no. 1 (January 2013): 110–30. http://dx.doi.org/10.1016/j.spa.2012.09.003.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

BEVERIDGE, ANDREW. "A Hitting Time Formula for the Discrete Green's Function." Combinatorics, Probability and Computing 25, no. 3 (June 29, 2015): 362–79. http://dx.doi.org/10.1017/s0963548315000152.

Full text

Abstract:

The discrete Green's function (without boundary)$\mathbb{G}$is a pseudo-inverse of the combinatorial Laplace operator of a graphG= (V, E). We reveal the intimate connection between Green's function and the theory of exact stopping rules for random walks on graphs. We give an elementary formula for Green's function in terms of state-to-state hitting times of the underlying graph. Namely,$\mathbb{G}(i,j) = \pi_j \bigl( H(\pi,j) - H(i,j) \bigr),$where πiis the stationary distribution at vertexi,H(i, j) is the expected hitting time for a random walk starting from vertexito first reach vertexj, andH(π,j) = ∑k∈VπkH(k, j). This formula also holds for the digraph Laplace operator.The most important characteristics of a stopping rule are its exit frequencies, which are the expected number of exits of a given vertex before the rule halts the walk. We show that Green's function is, in fact, a matrix of exit frequencies plus a rank one matrix. In the undirected case, we derive spectral formulas for Green's function and for some mixing measures arising from stopping rules. Finally, we further explore the exit frequency matrix point of view, and discuss a natural generalization of Green's function for any distribution τ defined on the vertex set of the graph.

APA, Harvard, Vancouver, ISO, and other styles

14

Nakajima, Tadashi. "Joint distribution of the first hitting time and first hitting place for a random walk." Kodai Mathematical Journal 21, no. 2 (1998): 192–200. http://dx.doi.org/10.2996/kmj/1138043873.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Fukai, Yasunari. "Hitting time of a half-line by two-dimensional random walk." Probability Theory and Related Fields 128, no. 3 (March 1, 2004): 323–46. http://dx.doi.org/10.1007/s00440-003-0306-y.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Pozzoli, Gaia, Mattia Radice, Manuele Onofri, and Roberto Artuso. "A Continuous-Time Random Walk Extension of the Gillis Model." Entropy 22, no. 12 (December 18, 2020): 1431. http://dx.doi.org/10.3390/e22121431.

Full text

Abstract:

We consider a continuous-time random walk which is the generalization, by means of the introduction of waiting periods on sites, of the one-dimensional non-homogeneous random walk with a position-dependent drift known in the mathematical literature as Gillis random walk. This modified stochastic process allows to significantly change local, non-local and transport properties in the presence of heavy-tailed waiting-time distributions lacking the first moment: we provide here exact results concerning hitting times, first-time events, survival probabilities, occupation times, the moments spectrum and the statistics of records. Specifically, normal diffusion gives way to subdiffusion and we are witnessing the breaking of ergodicity. Furthermore we also test our theoretical predictions with numerical simulations.

APA, Harvard, Vancouver, ISO, and other styles

17

HONG, WENMING, and HUAMING WANG. "INTRINSIC BRANCHING STRUCTURE WITHIN (L-1) RANDOM WALK IN RANDOM ENVIRONMENT AND ITS APPLICATIONS." Infinite Dimensional Analysis, Quantum Probability and Related Topics 16, no. 01 (March 2013): 1350006. http://dx.doi.org/10.1142/s0219025713500069.

Full text

Abstract:

We figure out the intrinsic branching structure within (L-1) random walk in random environment. As applications, the branching structure enable us to calculate the expectation of the first hitting time directly, and specify the density of the invariant measure for the Markov chain of "the environment viewed from particles" explicitly.

APA, Harvard, Vancouver, ISO, and other styles

18

Dorogovtsev, A. A., and I. I. Nishchenko. "Loop-erased random walks associated with Markov processes." Theory of Stochastic Processes 25(41), no. 2 (December 11, 2021): 15–24. http://dx.doi.org/10.37863/tsp-1348277559-92.

Full text

Abstract:

A new class of loop-erased random walks (LERW) on a finite set, defined as functionals from a Markov chain is presented. We propose a scheme in which, in contrast to the general settings of LERW, the loop-erasure is performed on a non-markovian sequence and moreover, not all loops are erased with necessity. We start with a special example of a random walk with loops, the number of which at every moment of time does not exceed a given fixed number. Further we consider loop-erased random walks, for which loops are erased at random moments of time that are hitting times for a Markov chain. The asymptotics of the normalized length of such loop-erased walks is established. We estimate also the speed of convergence of the normalized length of the loop-erased random walk on a finite group to the Rayleigh distribution.

APA, Harvard, Vancouver, ISO, and other styles

19

Radice, Mattia. "Non-homogeneous random walks with stochastic resetting: an application to the Gillis model." Journal of Statistical Mechanics: Theory and Experiment 2022, no. 12 (December 1, 2022): 123206. http://dx.doi.org/10.1088/1742-5468/aca587.

Full text

Abstract:

Abstract We consider the problem of the first passage time to the origin of a spatially non-homogeneous random walk (RW) with a position-dependent drift, known as the Gillis random walk, in the presence of resetting. The walk starts from an initial site x 0 and, with fixed probability r, at each step may be relocated to a given site x r . From a general perspective, we first derive a series of results regarding the first and the second moment of the first hitting time distribution, valid for a wide class of processes, including RWs lacking the property of translational invariance; we then apply these results to the specific model. When resetting is not applied, by tuning the value of a parameter which defines the transition probability of the process, denoted by ε, the recurrence properties of the walk are changed, and we can observe: a transient walk, a null-recurrent walk, or a positive-recurrent walk. When the resetting mechanism is switched on, we study quantitatively in all regimes the improvement of the search efficiency. In particular, in every case resetting allows the system to reach the target with probability one and, on average, in a finite time. If the reset-free system is in the transient or null-recurrent regime, this makes resetting always advantageous and moreover, it assures the existence of an optimal resetting probability r ∗ which minimizes the mean first hitting time. Instead, when the system is positive-recurrent, the introduction of resetting is not necessarily beneficial. We explain that in this case there exists a threshold r t h for the resetting probability r, above which the resetting mechanism yields a larger mean first hitting time with respect to the reset-free system. We provide a study of r t h , which can be zero for some values of the system parameters, meaning that resetting cannot be beneficial in those situations. All the theoretical findings are corroborated with numerical simulations.

APA, Harvard, Vancouver, ISO, and other styles

20

Patel, Rushabh, Andrea Carron, and Francesco Bullo. "The Hitting Time of Multiple Random Walks." SIAM Journal on Matrix Analysis and Applications 37, no. 3 (January 2016): 933–54. http://dx.doi.org/10.1137/15m1010737.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Hoyer, Peter, and Zhan Yu. "Analysis of lackadaisical quantum walks." Quantum Information and Computation 20, no. 13&14 (November 2020): 1138–53. http://dx.doi.org/10.26421/qic20.13-14-4.

Full text

Abstract:

The lackadaisical quantum walk is a quantum analogue of the lazy random walk obtained by adding a self-loop to each vertex in the graph. We analytically prove that lackadaisical quantum walks can find a unique marked vertex on any regular locally arc-transitive graph with constant success probability quadratically faster than the hitting time. This result proves several speculations and numerical findings in previous work, including the conjectures that the lackadaisical quantum walk finds a unique marked vertex with constant success probability on the torus, cycle, Johnson graphs, and other classes of vertex-transitive graphs. Our proof establishes and uses a relationship between lackadaisical quantum walks and quantum interpolated walks for any regular locally arc-transitive graph.

APA, Harvard, Vancouver, ISO, and other styles

22

Klein Haneveld, Leendert A. "ON IDENTITIES FOR A RANDOM WALK IN AN ORTHANT WITH ABSORBING BOUNDARY." Probability in the Engineering and Informational Sciences 17, no. 3 (June 6, 2003): 411–15. http://dx.doi.org/10.1017/s026996480317307x.

Full text

Abstract:

For a left-continuous random walk in an orthant with absorbing boundary, the generating function of the transition probabilities is determined by a well-known functional equation. We give a simple probabilistic derivation of this functional equation, which simultaneously proves the hitting point identity and Wald's exponential identity for the absorption time.

APA, Harvard, Vancouver, ISO, and other styles

23

Yamamoto, Ken. "Solution and Analysis of a One-Dimensional First-Passage Problem with a Nonzero Halting Probability." International Journal of Statistical Mechanics 2013 (October 27, 2013): 1–9. http://dx.doi.org/10.1155/2013/831390.

Full text

Abstract:

This paper treats a kind of a one-dimensional first-passage problem, which seeks the probability that a random walker first hits the origin at a specified time. In addition to a usual random walk which hops either rightwards or leftwards, the present paper introduces the “halt” that the walker does not hop with a nonzero probability. The solution to the problem is expressed using a Gauss hypergeometric function. The moment generating function of the hitting time is also calculated, and a calculation technique of the moments is developed. The author derives the long-time behavior of the hitting-time distribution, which exhibits power-law behavior if the walker hops to the right and left with equal probability.

APA, Harvard, Vancouver, ISO, and other styles

24

Roberto, Beraldi, Querzoni Leonardo, and Baldoni Roberto. "Low hitting time random walks in wireless networks." Wireless Communications and Mobile Computing 9, no. 5 (May 2009): 719–32. http://dx.doi.org/10.1002/wcm.625.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Brightwell, Graham, and Peter Winkler. "Maximum hitting time for random walks on graphs." Random Structures & Algorithms 1, no. 3 (September 1990): 263–76. http://dx.doi.org/10.1002/rsa.3240010303.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Meise, Christian. "On spectral gap estimates of a Markov chain via hitting times and coupling." Journal of Applied Probability 36, no. 2 (June 1999): 310–19. http://dx.doi.org/10.1239/jap/1032374455.

Full text

Abstract:

Well-known inequalities for the spectral gap of a discrete-time Markov chain, such as Poincaré's and Cheeger's inequalities, do not perform well if the transition graph of the Markov chain is strongly connected. For example in the case of nearest-neighbour random walk on the n-dimensional cube Poincaré's and Cheeger's inequalities are off by a factor n. Using a coupling technique and a contraction principle lower bounds on the spectral gap can be derived. Finally, we show that using the contraction principle yields a sharp estimate for nearest-neighbour random walk on the n-dimensional cube.

APA, Harvard, Vancouver, ISO, and other styles

27

Meise, Christian. "On spectral gap estimates of a Markov chain via hitting times and coupling." Journal of Applied Probability 36, no. 02 (June 1999): 310–19. http://dx.doi.org/10.1017/s0021900200017150.

Full text

Abstract:

Well-known inequalities for the spectral gap of a discrete-time Markov chain, such as Poincaré's and Cheeger's inequalities, do not perform well if the transition graph of the Markov chain is strongly connected. For example in the case of nearest-neighbour random walk on the n-dimensional cube Poincaré's and Cheeger's inequalities are off by a factor n. Using a coupling technique and a contraction principle lower bounds on the spectral gap can be derived. Finally, we show that using the contraction principle yields a sharp estimate for nearest-neighbour random walk on the n-dimensional cube.

APA, Harvard, Vancouver, ISO, and other styles

28

Palacios, José Luis. "On the Moments of Hitting Times for Random Walks on Trees." Journal of Probability and Statistics 2009 (2009): 1–4. http://dx.doi.org/10.1155/2009/241539.

Full text

Abstract:

Using classical arguments we derive a formula for the moments of hitting times for an ergodic Markov chain. We apply this formula to the case of simple random walk on trees and show, with an elementary electric argument, that all the moments are natural numbers.

APA, Harvard, Vancouver, ISO, and other styles

29

Dshalalow, Jewgeni H., and Ryan T. White. "Random Walk Analysis in a Reliability System under Constant Degradation and Random Shocks." Axioms 10, no. 3 (August 23, 2021): 199. http://dx.doi.org/10.3390/axioms10030199.

Full text

Abstract:

In this paper, we study a reliability system subject to occasional random shocks hitting an underlying device in accordance with a general marked point process with position dependent marking. In addition, the system ages according to a linear path that eventually fails even without any external shocks that accelerate the total failure. The approach for obtaining the distribution of the failure time falls into the area of random walk analysis. The results obtained are in closed form. A special case of a marked Poisson process with exponentially distributed marks is discussed that supports our claim of analytical tractability. The example is further confirmed by simulation. We also provide a classification of the literature pertaining to various reliability systems with degradation and shocks.

APA, Harvard, Vancouver, ISO, and other styles

30

Lehec, Joseph. "Cover Times and Generic Chaining." Journal of Applied Probability 51, no. 1 (March 2014): 247–61. http://dx.doi.org/10.1239/jap/1395771427.

Full text

Abstract:

A recent result of Ding, Lee and Peres (2012) expressed the cover time of the random walk on a graph in terms of generic chaining for the commute distance. Their argument is based on Dynkin's isomorphism theorem. The purpose of this article is to present an alternative approach to this problem, based only on elementary hitting time estimates and chaining arguments.

APA, Harvard, Vancouver, ISO, and other styles

31

Lehec, Joseph. "Cover Times and Generic Chaining." Journal of Applied Probability 51, no. 01 (March 2014): 247–61. http://dx.doi.org/10.1017/s0021900200010214.

Full text

Abstract:

A recent result of Ding, Lee and Peres (2012) expressed the cover time of the random walk on a graph in terms of generic chaining for the commute distance. Their argument is based on Dynkin's isomorphism theorem. The purpose of this article is to present an alternative approach to this problem, based only on elementary hitting time estimates and chaining arguments.

APA, Harvard, Vancouver, ISO, and other styles

32

Chen, Haiyan. "The generating functions of hitting times for random walk on trees." Statistics & Probability Letters 77, no. 15 (September 2007): 1574–79. http://dx.doi.org/10.1016/j.spl.2007.03.044.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Lawler, Gregory F. "Expected hitting times for a random walk on a connected graph." Discrete Mathematics 61, no. 1 (August 1986): 85–92. http://dx.doi.org/10.1016/0012-365x(86)90030-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Gerbaud, Antoine, Karine Altisen, Stéphane Devismes, and Pascal Lafourcade. "Comparison of mean hitting times for a degree-biased random walk." Discrete Applied Mathematics 170 (June 2014): 104–9. http://dx.doi.org/10.1016/j.dam.2014.01.021.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Golomoziy, V. "On estimating exponential moment for the simultaneous renewal time for two random walks on a half line." Bulletin of Taras Shevchenko National University of Kyiv. Series: Physics and Mathematics, no. 2 (2021): 26–31. http://dx.doi.org/10.17721/1812-5409.2021/2.4.

Full text

Abstract:

In this paper, we consider conditions for existence and finitness for an exponential moment for the time of the simultaneous hitting of a given set by two random walks on a half-line. It is addmitted that random walks may be time-inhomogeneous. Obtained conditions that guarantee existence of the hitting time for individual chains and simultaneous hitting time for both chains. It is shown, how the estimates could be calculated in practical applications.

APA, Harvard, Vancouver, ISO, and other styles

36

FUKAI, Yasunari. "HITTING TIME OF A HALF-LINE BY A TWO-DIMENSIONAL NON-SYMMETRIC RANDOM WALK." Kyushu Journal of Mathematics 69, no. 1 (2015): 145–71. http://dx.doi.org/10.2206/kyushujm.69.145.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Löwe, Matthias, and Felipe Torres. "On hitting times for a simple random walk on dense Erdös–Rényi random graphs." Statistics & Probability Letters 89 (June 2014): 81–88. http://dx.doi.org/10.1016/j.spl.2014.02.017.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Sylvester, John. "Random walk hitting times and effective resistance in sparsely connected Erdős‐Rényi random graphs." Journal of Graph Theory 96, no. 1 (February 17, 2020): 44–84. http://dx.doi.org/10.1002/jgt.22551.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

J., Abhijith, and Apoorva Patel. "Spatial search using flip-flop quantum walk." Quantum Information and Computation 18, no. 15&16 (December 2018): 1295–331. http://dx.doi.org/10.26421/qic18.15-16-3.

Full text

Abstract:

We analyse the eigenvalue and eigenvector structure of the flip-flop quantum walk on regular graphs, explicitly demonstrating how it is quadratically faster than the classical random walk. Then we use it in a controlled spatial search algorithm with multiple target states, and determine the oracle complexity as a function of the spectral gap and the number of target states. The oracle complexity is optimal as a function of the graph size and the number of target states, when the spectral gap of the adjacency matrix is $\Theta(1)$. It is also optimal for spatial search on D>4 dimensional hypercubic lattices. Otherwise it matches the best result available in the literature, with a much simpler algorithm. Our results also yield bounds on the classical hitting time of random walks on regular graphs, which may be of independent interest.

APA, Harvard, Vancouver, ISO, and other styles

40

Zhang, Mei Juan. "Large deviations for hitting times of a random walk in random environment on a strip." Acta Mathematica Sinica, English Series 30, no. 3 (February 15, 2014): 395–410. http://dx.doi.org/10.1007/s10114-014-2683-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

HARTMAN, YAIR, YURI LIMA, and OMER TAMUZ. "An Abramov formula for stationary spaces of discrete groups." Ergodic Theory and Dynamical Systems 34, no. 3 (January 15, 2013): 837–53. http://dx.doi.org/10.1017/etds.2012.167.

Full text

Abstract:

AbstractLet $(G, \mu )$ be a discrete group equipped with a generating probability measure, and let $\Gamma $ be a finite index subgroup of $G$. A $\mu $-random walk on $G$, starting from the identity, returns to $\Gamma $ with probability one. Let $\theta $ be the hitting measure, or the distribution of the position in which the random walk first hits $\Gamma $. We prove that the Furstenberg entropy of a $(G, \mu )$-stationary space, with respect to the action of $(\Gamma , \theta )$, is equal to the Furstenberg entropy with respect to the action of $(G, \mu )$, times the index of $\Gamma $ in $G$. The index is shown to be equal to the expected return time to $\Gamma $. As a corollary, when applied to the Furstenberg–Poisson boundary of $(G, \mu )$, we prove that the random walk entropy of $(\Gamma , \theta )$ is equal to the random walk entropy of $(G, \mu )$, times the index of $\Gamma $ in $G$.

APA, Harvard, Vancouver, ISO, and other styles

42

Jarai, Antal, and Harry Kesten. "A Bound for the Distribution of the Hitting Time of Arbitrary Sets by Random Walk." Electronic Communications in Probability 9 (2004): 152–61. http://dx.doi.org/10.1214/ecp.v9-1119.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Kolokoltsov, V. N. "Generalized Continuous-Time Random Walks, Subordination by Hitting Times, and Fractional Dynamics." Theory of Probability & Its Applications 53, no. 4 (January 2009): 594–609. http://dx.doi.org/10.1137/s0040585x97983857.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Sheng, Yibin, and Zhongzhi Zhang. "Low-Mean Hitting Time for Random Walks on Heterogeneous Networks." IEEE Transactions on Information Theory 65, no. 11 (November 2019): 6898–910. http://dx.doi.org/10.1109/tit.2019.2925610.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

Palacios, JoséLuis. "Bounds on expected hitting times for a random walk on a connected graph." Linear Algebra and its Applications 141 (November 1990): 241–52. http://dx.doi.org/10.1016/0024-3795(90)90321-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

Uchiyama, Kohei. "The First Hitting Time of a Single Point for Random Walks." Electronic Journal of Probability 16 (2011): 1960–2000. http://dx.doi.org/10.1214/ejp.v16-931.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Su, Jing, Xiaomin Wang, and Bing Yao. "Mean Hitting Time for Random Walks on a Class of Sparse Networks." Entropy 24, no. 1 (December 24, 2021): 34. http://dx.doi.org/10.3390/e24010034.

Full text

Abstract:

For random walks on a complex network, the configuration of a network that provides optimal or suboptimal navigation efficiency is meaningful research. It has been proven that a complete graph has the exact minimal mean hitting time, which grows linearly with the network order. In this paper, we present a class of sparse networks G(t) in view of a graphic operation, which have a similar dynamic process with the complete graph; however, their topological properties are different. We capture that G(t) has a remarkable scale-free nature that exists in most real networks and give the recursive relations of several related matrices for the studied network. According to the connections between random walks and electrical networks, three types of graph invariants are calculated, including regular Kirchhoff index, M-Kirchhoff index and A-Kirchhoff index. We derive the closed-form solutions for the mean hitting time of G(t), and our results show that the dominant scaling of which exhibits the same behavior as that of a complete graph. The result could be considered when designing networks with high navigation efficiency.

APA, Harvard, Vancouver, ISO, and other styles

48

Pène, Françoise, Benoît Saussol, and Roland Zweimüller. "Recurrence rates and hitting-time distributions for random walks on the line." Annals of Probability 41, no. 2 (March 2013): 619–35. http://dx.doi.org/10.1214/11-aop698.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Das, Debraj, and Luca Giuggioli. "Dynamics of lattice random walk within regions composed of different media and interfaces." Journal of Statistical Mechanics: Theory and Experiment 2023, no. 1 (January 1, 2023): 013201. http://dx.doi.org/10.1088/1742-5468/aca8f9.

Full text

Abstract:

Abstract We study the lattice random walk dynamics in a heterogeneous space of two media separated by an interface and having different diffusivity and bias. Depending on the position of the interface, there exist two exclusive ways to model the dynamics: (a) Type A dynamics whereby the interface is placed between two lattice points, and (b) Type B dynamics whereby the interface is placed on a lattice point. For both types, we obtain exact results for the one-dimensional generating function of the Green’s function or propagator for the composite system in unbounded domain as well as domains confined with reflecting, absorbing, and mixed boundaries. For the case with reflecting confinement in the absence of bias, the steady-state probability shows a step-like behavior for the Type A dynamics, while it is uniform for the Type B dynamics. We also derive explicit expressions for the first-passage probability and the mean first-passage time, and compare the hitting time dependence to a single target. Finally, considering the continuous-space continuous-time limit of the propagator, we obtain the boundary conditions at the interface. At the interface, while the flux is the same, the probability density is discontinuous for Type A and is continuous for Type B. For the latter we derive a generalized version of the so-called leather boundary condition in the appropriate limit.

APA, Harvard, Vancouver, ISO, and other styles

50

Baeumer, Boris, Mark M. Meerschaert, and Erkan Nane. "Space–Time Duality for Fractional Diffusion." Journal of Applied Probability 46, no. 4 (December 2009): 1100–1115. http://dx.doi.org/10.1239/jap/1261670691.

Full text

Abstract:

Zolotarev (1961) proved a duality result that relates stable densities with different indices. In this paper we show how Zolotarev's duality leads to some interesting results on fractional diffusion. Fractional diffusion equations employ fractional derivatives in place of the usual integer-order derivatives. They govern scaling limits of random walk models, with power-law jumps leading to fractional derivatives in space, and power-law waiting times between the jumps leading to fractional derivatives in time. The limit process is a stable Lévy motion that models the jumps, subordinated to an inverse stable process that models the waiting times. Using duality, we relate the density of a spectrally negative stable process with index 1<α<2 to the density of the hitting time of a stable subordinator with index 1/α, and thereby unify some recent results in the literature. These results provide a concrete interpretation of Zolotarev's duality in terms of the fractional diffusion model. They also illuminate a current controversy in hydrology, regarding the appropriate use of space- and time-fractional derivatives to model contaminant transport in river flows.

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!