An official website of the United States government
Abstract We present analytical results for the distribution of first return (FR) times of non-backtracking random walks (NBWs) on undirected configuration model networks consisting of $$N$$ nodes with degree distribution $P(k)$. We focus on the case in which the network consists of a single connected component. Starting from a random initial node $$i$$ at time $t=0$, an NBW hops into a random neighbor of $$i$$ at time $t=1$ and at each subsequent step it continues to hop into a random neighbor of its current node, excluding the previous node. We calculate the tail distribution $$P ( T_{\rm FR} > t )$$ of first return times from a random initial node to itself. It is found that $$P ( T_{\rm FR} > t )$$ is given by a discrete Laplace transform of the degree distribution $P(k)$. This result exemplifies the relation between structural properties of a network, captured by the degree distribution, and properties of dynamical processes taking place on the network. Using the tail-sum formula, we calculate the mean first return time $${\mathbb E}[ T_{\rm FR} ]$$. Surprisingly, $${\mathbb E}[ T_{\rm FR} ]$$ coincides with the result obtained from Kac's lemma that applies to simple random walks (RWs). We also calculate the variance $${\rm Var}(T_{\rm FR})$$, which accounts for the variability of first return times between different NBW trajectories. We apply this formalism to Erd{\H o}s-R\'enyi networks, random regular graphs and configuration model networks with exponential and power-law degree distributions and obtain closed-form expressions for $$P( T_{\rm FR} > t )$$ as well as its mean and variance. These results provide useful insight on the advantages of NBWs over simple RWs in network exploration, sampling and search processes.
more »
« less
Asymptotics of noncolliding q-exchangeable random walks
Abstract We consider a process of noncolliding $$q$$-exchangeable random walks on $$\mathbb{Z}$$ making steps $$0$$ (straight) and $-1$ (down). A single random walk is called $$q$$-exchangeable if under an elementary transposition of the neighboring steps (down, straight) $$\to$$ (straight, down) the probability of the trajectory is multiplied by a parameter $$q\in(0,1)$$. Our process of $$m$$ noncolliding $$q$$-exchangeable random walks is obtained from the independent $$q$$-exchangeable walks via the Doob's $$h$$-transform for a nonnegative eigenfunction $$h$$ (expressed via the $$q$$-Vandermonde product) with the eigenvalue less than $$1$$. The system of $$m$$ walks evolves in the presence of an absorbing wall at $$0$$. The repulsion mechanism is the $$q$$-analogue of the Coulomb repulsion of random matrix eigenvalues undergoing Dyson Brownian motion. However, in our model, the particles are confined to the positive half-line and do not spread as Brownian motions or simple random walks. We show that the trajectory of the noncolliding $$q$$-exchangeable walks started from an arbitrary initial configuration forms a determinantal point process, and express its kernel in a double contour integral form. This kernel is obtained as a limit from the correlation kernel of $$q$$-distributed random lozenge tilings of sawtooth polygons. In the limit as $$m\to \infty$$, $$q=e^{-\gamma/m}$$ with $$\gamma>0$$ fixed, and under a suitable scaling of the initial data, we obtain a limit shape of our noncolliding walks and also show that their local statistics are governed by the incomplete beta kernel. The latter is a distinguished translation invariant ergodic extension of the two-dimensional discrete sine kernel.
more »
« less
- PAR ID:
- 10440190
- Date Published:
- Journal Name:
- Journal of Physics A: Mathematical and Theoretical
- ISSN:
- 1751-8113
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract For a Brownian directed polymer in a Gaussian random environment, with q ( t , ⋅) denoting the quenched endpoint density and Q n ( t , x 1 , … , x n ) = E [ q ( t , x 1 ) … q ( t , x n ) ] , we derive a hierarchical PDE system satisfied by { Q n } n ⩾ 1 . We present two applications of the system: (i) we compute the generator of { μ t ( d x ) = q ( t , x ) d x } t ⩾ 0 for some special functionals, where { μ t ( d x ) } t ⩾ 0 is viewed as a Markov process taking values in the space of probability measures; (ii) in the high temperature regime with d ⩾ 3, we prove a quantitative central limit theorem for the annealed endpoint distribution of the diffusively rescaled polymer path. We also study a nonlocal diffusion-reaction equation motivated by the generator and establish a super-diffusive O ( t 2/3 ) scaling.more » « less
-
Abstract We study the Kardar–Parisi–Zhang (KPZ) equation on the half-line x ⩾ 0 with Neumann type boundary condition. Stationary measures of the KPZ dynamics were characterized in recent work: they depend on two parameters, the boundary parameter u of the dynamics, and the drift − v of the initial condition at infinity. We consider the fluctuations of the height field when the initial condition is given by one of these stationary processes. At large time t , it is natural to rescale parameters as ( u , v ) = t −1/3 ( a , b ) to study the critical region. In the special case a + b = 0, treated in previous works, the stationary process is simply Brownian. However, these Brownian stationary measures are particularly relevant in the bound phase ( a < 0) but not in the unbound phase. For instance, starting from the flat or droplet initial condition, the height field near the boundary converges to the stationary process with a > 0 and b = 0, which is not Brownian. For a + b ⩾ 0, we determine exactly the large time distribution F a , b stat of the height function h (0, t ). As an application, we obtain the exact covariance of the height field in a half-line at two times 1 ≪ t 1 ≪ t 2 starting from stationary initial condition, as well as estimates, when starting from droplet initial condition, in the limit t 1 / t 2 → 1.more » « less
-
Abstract Let Γ be a Schottky semigroup in {\mathrm{SL}_{2}(\mathbf{Z})} ,and for {q\in\mathbf{N}} , let {\Gamma(q):=\{\gamma\in\Gamma:\gamma=e~{}(\mathrm{mod}~{}q)\}} be its congruence subsemigroupof level q . Let δ denote the Hausdorff dimension of the limit set of Γ.We prove the following uniform congruence counting theoremwith respect to the family of Euclidean norm balls {B_{R}} in {M_{2}(\mathbf{R})} of radius R :for all positive integer q with no small prime factors, \#(\Gamma(q)\cap B_{R})=c_{\Gamma}\frac{R^{2\delta}}{\#(\mathrm{SL}_{2}(%\mathbf{Z}/q\mathbf{Z}))}+O(q^{C}R^{2\delta-\epsilon}) as {R\to\infty} for some {c_{\Gamma}>0,C>0,\epsilon>0} which are independent of q .Our technique also applies to give a similar counting result for the continued fractions semigroup of {\mathrm{SL}_{2}(\mathbf{Z})} ,which arises in the study of Zaremba’s conjecture on continued fractions.more » « less
-
This book develops limit theorems for a natural class of long range random walks on finitely generated torsion free nilpotent groups. The limits in these limit theorems are Lévy processes on some simply connected nilpotent Lie groups. Both the limit Lévy process and the limit Lie group carrying this process are determined by and depend on the law of the original random walk. The book offers the first systematic study of such limit theorems involving stable-like random walks and stable limit Lévy processes in the context of (non-commutative) nilpotent groups.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript
- Journal Article:
- https://doi.org/10.1088/1751-8121/acedda
