Search

This paper considers non-backtracking random walks on random graphs generated according to the configuration model. The quantity of interest is the scaling of the mixing time of the random walk as the number of vertices of the random graph tends to infinity. Subject to mild general conditions, we link two mixing times: one for a static version of the random graph, the other for a class of dynamic versions of the random graph in which the edges are randomly rewired but the degrees are preserved. The link is provided by the probability that the random walk has not yet stepped along a previously rewired edge. We use this link to compute the scaling of the mixing time for three specific classes of random rewirings. Depending on the speed and the range of the rewiring relative to the current location of the random walk, the mixing time may exhibit no cut-off, one-sided cut-off or two-sided cut-off, a trichotomy that was also found in earlier work. Interestingly, for a class of dynamics that are `mesoscopic', i.e., non-local and non-global, we find new behaviour with six subregimes. Proofs are built on a new and flexible coupling scheme, in combination with sharp estimates on the degrees encountered by the random walk in the static and the dynamic version of the random graph. Some of these estimates require sharp control on possible short-cuts in the graph between the edges that are traversed by the random walk., Comment: 38 pages, 9 figures

We consider the near-critical Erdős–Rényi random graph G(n, p) and provide a new probabilistic proof of the fact that, when p is of the form $p=p(n)=1/n+\lambda/n^{4/3}$ and A is large, \begin{equation*}\mathbb{P}(|\mathcal{C}_{\max}|>An^{2/3})\asymp A^{-3/2}e^{-\frac{A^3}{8}+\frac{\lambda A^2}{2}-\frac{\lambda^2A}{2}},\end{equation*} where $\mathcal{C}_{\max}$ is the largest connected component of the graph. Our result allows A and $\lambda$ to depend on n. While this result is already known, our proof relies only on conceptual and adaptable tools such as ballot theorems, whereas the existing proof relies on a combinatorial formula specific to Erdős–Rényi graphs, together with analytic estimates.

Let ( g n ) n ⩾ 1 be a sequence of independent and identically distributed random elements of the general linear group G L d ( R ) , with law μ . Consider the random walk G n : = g n … g 1 . Denote respectively by ‖ G n ‖ and ρ ( G n ) the operator norm and the spectral radius of G n . For log ‖ G n ‖ and log ρ ( G n ) , we prove moderate deviation principles under exponential moment and strong irreducibility conditions on μ ; we also establish moderate deviation expansions in the normal range [ 0 , o ( n 1 / 6 ) ] and Berry–Esseen bounds under the additional proximality condition on μ . Similar results are found for the couples ( X n x , log ‖ G n ‖ ) and ( X n x , log ρ ( G n ) ) with target functions, where X n x : = G n ⋅ x is a Markov chain and x is a starting point on the projective space P ( R d ) .

In certain non-stationary processes, the non-stationary dynamics is caused by degradation or wearing of certain process components. Such dynamics can be characterized by a latent monotonic signal. Meanwhile, there also exist stationary dynamics characterizing the regular process variables. It hence becomes pertinent to distinguish these two sets of latent variables for the monitoring of the process from both the stationary and non-stationary aspects. In this regard, we propose a methodology to achieve such a goal by modeling the latent monotonic trend as a closed skew-normal random walk model. The other stationary relations are characterized by a state-space model with Gaussian noises. The problem is solved as a simultaneous state and parameter estimation problem using the expectation–maximization algorithm. As a result of the closed skew-normal random walk model for the monotonic trend, the state estimation problem becomes a skew-normal filtering and smoothing problem. The effectiveness of the proposed method is verified through a numerical simulation, and the algorithm is applied to solve a Hot Lime Softener fouling predictive monitoring problem.

Spatial memory has been considered significant in animal movement modeling. In this paper, we formulate a two-species interaction model by incorporating both random walk and spatial memory-based walk in their movement. The spatial memory-based walk, described by a chemotactic-like term, is derived by a modified Fick's law involving a directed movement toward the gradient of the density distribution function at a past time. For the proposed model, local stability and bifurcations are studied at constant steady states. Unlike a classical reaction-diffusion equation, we show that the accumulation points of eigenvalues for the model will locate at a vertical line in the complex plane, which will make the model generate spatially inhomogeneous time-periodic patterns through Hopf bifurcation. As illustrations, we apply these results to competition and cooperative models with memory-based diffusion. For the competition model, it turns out that the outcomes are far more complicated than those of classic Lotka-Volterra reaction-diffusion models, due to the consideration of memory-based diffusion. In particular, the existence of periodic oscillations is proved under weak competition. Similar conclusions hold for the cooperative model.

Graph-limit theory focuses on the convergence of sequences of graphs when the number of nodes becomes arbitrarily large. This framework defines a continuous version of graphs allowing for the study of dynamical systems on very large graphs, where classical methods would become computationally intractable. Through an approximation procedure, the standard system of coupled ordinary differential equations is replaced by a nonlocal evolution equation on the unit interval. In this work, we adopt this methodology to explore the continuum limit of random walks, a popular model for diffusion on graphs. We focus on two classes of processes on dense weighted graph, in discrete and in continuous time, whose dynamics are encoded in the transition matrix and the random-walk Laplacian. We also show that previous works on the discrete heat equation, associated to the combinatorial Laplacian, fall within the scope of our approach. Finally, we apply the spectral theory of operators to characterize the relaxation time of the process in the continuum limit., Comment: 22 pages, 1 figure

We further develop in this study the Random Walk on Spheres (RWS) stochastic algorithm for solving systems of coupled diffusion-recombination equations first suggested in our recent article [K. Sabelfeld, First passage Monte Carlo algorithms for solving coupled systems of diffusion–reaction equations, Appl. Math. Lett. 88 2019, 141–148]. The random walk on spheres process mimics the isotropic diffusion of two types of particles which may recombine to each other. Our motivation comes from the transport problems of free and bound exciton recombination. The algorithm is based on tracking the trajectories of the diffusing particles exactly in accordance with the probabilistic distributions derived from the explicit representation of the relevant Green functions for balls and spheres. Therefore, the method is mesh free both in space and time. In this paper we implement the RWS algorithm for solving the diffusion-recombination problems both in a steady-state and transient settings. Simulations are compared against the exact solutions. We show also how the RWS algorithm can be applied to calculate exciton flux to the boundary which provides the electron beam-induced current, the concentration of the survived excitons, and the cathodoluminescence intensity which are all integral characteristics of the solution to diffusion-recombination problem.

Recently, motivated by problems in image processing, by the analysis of the peridynamic formulation of the continuous mechanic and by the study of Markov jump processes, there has been an increasing interest in the research of nonlocal partial differential equations. In the last years and with these problems in mind, we have studied some gradient flows in the general framework of a metric random walk space, that is, a Polish metric space (X, d) together with a probability measure assigned to each $$x\in X$$ x ∈ X , which encode the jumps of a Markov process. In this way, we have unified into a broad framework the study of partial differential equations in weighted discrete graphs and in other nonlocal models of interest. Our aim here is to provide a summary of the results that we have obtained for the heat flow and the total variational flow in metric random walk spaces. Moreover, some of our results on other problems related to the diffusion operators involved in such processes are also included, like the ones for evolution problems of p-Laplacian type with nonhomogeneous Neumann boundary conditions.

We prove that a "random" free group outer automorphism is an ageometric fully irreducible outer automorphism whose ideal Whitehead graph is a union of triangles. In particular, we show that its attracting (and repelling) tree is a nongeometric $\mathbb R$-tree all of whose branch points are trivalent, Comment: 27 pages comments are welcome!

Kemeny’s constant of a simple connected graph G is the expected length of a random walk from i to any given vertex $$j \ne i$$ . We provide a simple method for computing Kemeny’s constant for 1-separable graphs via effective resistance methods from electrical network theory. Using this formula, we furnish a simple proof that the path graph on n vertices maximizes Kemeny’s constant for the class of undirected trees on n vertices. Applying this method again, we simplify existing expressions for the Kemeny’s constant of barbell graphs and demonstrate which barbell maximizes Kemeny’s constant. This 1-separation identity further allows us to create sufficient conditions for the existence of Braess edges in 1-separable graphs. We generalize the notion of the Braess edge to Braess sets, collections of non-edges in a graph such that their addition to the base graph increases the Kemeny constant. We characterize Braess sets in graphs with any number of twin pendant vertices, generalizing work of Kirkland and Zeng (Electron J Linear Algebra 31(1):444–464, 2016) and Ciardo (Linear Algebra Appl, 2020).

The diffusion least mean square (DLMS) and the diffusion normalized least mean square (DNLMS) algorithms are analyzed for a network having a fusion center. This structure reduces the dimensionality of the resulting stochastic models while preserving important diffusion properties. The analysis is done in a system identification framework for cyclostationary white nodal inputs. The system parameters vary according to a random walk model. The cyclostationarity is modeled by periodic time variations of the nodal input powers. The analysis holds for all types of nodal input distributions and nodal input power variations. The derived models consist of simple scalar recursions. These recursions facilitate the understanding of the network mean and mean-square dependence upon the 1) nodal weighting coefficients, 2) nodal input kurtosis and cyclostationarities, 3) nodal noise powers and 4) the unknown system mean-square parameter increments. Optimization of the node weighting coefficients is studied. Also investigated is the stability dependence of the two algorithms upon the nodal input kurtosis and weighting coefficients. Significant differences are found between the behaviors of the DLMS and DNLMS algorithms for non-Gaussian nodal inputs. Simulations provide strong support for the theory.

A Galton–Watson branching process with immigration evolving in a random environment is considered. Its associated random walk is assumed to be oscillating. We prove a functional limit theorem in which the process under consideration is normalized by a random coefficient depending on the random environment only. The distribution of the limiting process is described in terms of a strictly stable Levy process and a sequence of independent and identically distributed random variables which is independent of this process.

We suggest in this paper a global random walk on grid (GRWG) method for solving second order elliptic equations. The equation may have constant or variable coefficients. The GRWS method calculates the solution in any desired family of m prescribed points of the gird in contrast to the classical stochastic differential equation based Feynman–Kac formula, and the conventional random walk on spheres (RWS) algorithm as well. The method uses only N trajectories instead of mN trajectories in the RWS algorithm and the Feynman–Kac formula. The idea is based on the symmetry property of the Green function and a double randomization approach.

In this paper we consider the expansion properties and the spectrum of the combinatorial Laplace operator of a $d$-dimensional Linial-Meshulam random simplicial complex, above the cohomological connectivity threshold. We consider the spectral gap of the Laplace operator and the Cheeger constant as this was introduced by Parzanchevski, Rosenthal and Tessler ($Combinatorica$ 36, 2016). We show that with high probability the spectral gap of the random simplicial complex as well as the Cheeger constant are both concentrated around the minimum co-degree of among all $d-1$-faces. Furthermore, we consider a generalisation of a random walk on such a complex and show that the associated conductance is with high probability bounded away from 0., 28 pages

A recommendation system has been built for a web resource’s users that applies statistics about user activities to provide recommendations. The purpose of the system operation is to provide recommendations in the form of an orderly sequence of HTML pages of the resource suggested for the user. The ranking procedure uses statistical information about user transitions between web resource pages. The web resource model is represented in the form of a web graph; the user behavior model is shown as a graph of transitions between resource pages. The web graph is represented by an adjacency matrix; for the transition graph, a weighted matrix of probabilities of transitions between the vertices of the graph has been constructed. It was taken into consideration that user transitions between pages of a web resource may involve entering a URL in the address bar of a browser or by clicking on a link in the current page. The user’s transition between vertices in a finite graph according to probabilities determined by the weight of the graph’s edges is represented by a homogeneous Markov chain and is considered a process of random walk on the graph with the possibility of moving to a random vertex. Random Walk with Restarts was used to rank web resource pages for a particular user. Numerical analysis has been performed for an actual online store website. The initial data on user sessions are divided into training and test samples. According to the training sample, a weighted matrix of the probability of user transitions between web resource pages was constructed. To assess the quality of the built recommendation system, the accuracy, completeness, and Half-life Utility metrics were used. On the elements of the test sample, the accuracy value of 65‒68% was obtained, the optimal number of elements in the recommendation list was determined. The influence of model parameters on the quality of recommendation systems was investigated.

We present new criteria for geometric and algebraic transience for discrete-time transient Markov chains on general state spaces, based on the moment of the last exit time, the modified moment of the first return time and the drift condition for the transition kernel. These criteria turn out to be more convenient to use, supplementing and extending conditions introduced by Mao and Song [Stochastic Process. Appl. 124 (2014) 1648-1678]. Several applications are presented including discrete queueing Markov chains, Galton–Watson branching processes, downwardly skip-free chains, unrestricted random walks and autoregressive models of order one.

A network is defined as an abstract structure that consists of nodes that are connected by links. In this paper, we study two types of rounded networks Nn (resp., Nn′). By using the recursive relat...

With the ease of deployment, capabilities of evading the jammers and obscuring their existence, unmanned aerial vehicles (UAVs) are one of the most suitable candidates to perform surveillance. There exists a body of literature in which the inspectors follow a deterministic trajectory to conduct surveillance, which results in a predictable environment for malicious entities. Thus, introducing randomness to the surveillance is of particular interest. In this work, we propose a novel framework for stochastic UAV-assisted surveillance that i) inherently considers the battery constraints of the UAVs, ii) proposes random moving patterns modeled via random walks, and iii) adds another degree of randomness to the system via considering probabilistic inspections. We formulate the problem of interest, i.e., obtaining the energy-efficient random walk and inspection policies of the UAVs subject to probabilistic constraints on inspection criteria of the sites and battery consumption of the UAVs, which turns out to be signomial programming that is highly non-convex. To solve it, we propose a centralized and a distributed algorithm along with their performance guarantee. This work contributes to both UAV-assisted surveillance and classic random walk literature by designing random walks with random inspection policies on weighted graphs with energy limited random walkers., This paper is accepted for publication in IEEE Transactions on Wireless Communications

Considering mobile terminals with time-varying velocities and randomly moving clusters, a novel multi-mobility non-stationary wideband multiple-input multiple-output (MIMO) channel model for future intelligent vehicle-to-everything (V2X) communications is proposed. To describe the non-stationarity of multi-mobility V2X channels, the proposed model employs a time-varying acceleration model and a random walk process to describe the motion of the communication terminals and that of the scattering clusters, respectively. The evolution of the model parameters over time and the stochastic characteristics of the phase shift caused by the time-varying Doppler frequency are derived. The proposed model is sufficiently general and suitable for characterizing various V2X communication scenarios. Under two-dimensional (2D) non-isotropic scattering scenarios, the important channel statistical properties of the proposed model are derived and thoroughly investigated. The impact of the random walk process of the clusters and the velocity variations of the communication terminals on these statistical properties is studied. The simulation results verify that the proposed model is useful for characterizing V2X channels.

In recent years, lncRNAs (long non-coding RNAs) have been proved to be closely related to many diseases that are seriously harmful to human health. Although researches on clarifying the relationships between lncRNAs and diseases are developing rapidly, associations between the lncRNAs and diseases are still remaining largely unknown. In this manuscript, a novel Local Random Walk based prediction model called LRWHLDA is proposed for inferring potential associations between human lncRNAs and diseases. In LRWHLDA, a new heterogeneous network is established first, which allows that LRWHLDA can be implemented in the case of lacking known lncRNA-disease associations. And then, an improved local random walk method is designed for prediction of novel lncRNA-disease associations, which can help LRWHLDA achieve high prediction accuracy but with low time complexity. Finally, in order to evaluate the prediction performance of LRWHLDA, different frameworks such as LOOCV, 2-folds CV, and 5-folds CV have been implemented, simulation results indicate that LRWHLDA can achieve reliable AUCs of 0.8037, 0.8354, and 0.8556 under the frameworks of 2-fold CV, 5-fold CV, and LOOCV, respectively. Hence, it is easy to know that LRWHLDA contains the potential to be a representative of emerging methods in the field of research on potential lncRNA-disease associations prediction.

We consider random walks on the group of orientation-preserving homeomorphisms of the real line ${\mathbb R}$ . In particular, the fundamental question of uniqueness of an invariant measure of the generated process is raised. This problem was studied by Choquet and Deny [Sur l’équation de convolution $\mu = \mu * \sigma $ . C. R. Acad. Sci. Paris250 (1960), 799–801] in the context of random walks generated by translations of the line. Nowadays the answer is quite well understood in general settings of strongly contractive systems. Here we focus on a broader class of systems satisfying the conditions of recurrence, contraction and unbounded action. We prove that under these conditions the random process possesses a unique invariant Radon measure on ${\mathbb R}$ . Our work can be viewed as following on from Babillot et al [The random difference equation $X_n=A_n X_{n-1}+B_n$ in the critical case. Ann. Probab.25(1) (1997), 478–493] and Deroin et al [Symmetric random walk on $\mathrm {HOMEO}^{+}(\mathbb {R})$ . Ann. Probab.41(3B) (2013), 2066–2089].

Community detection is a complex and meaningful process, which plays an important role in studying the characteristics of complex networks. In recent years, the discovery and analysis of community structures in complex networks has attracted the attention of many scholars, and many community discovery algorithms have been proposed. Many existing algorithms are only suitable for small-scale data, not for large-scale data, so it is necessary to establish a stable and efficient label propagation algorithm to deal with massive data and complex social networks. In this paper, we propose a novel label propagation algorithm, called WRWPLPA (Parallel Label Propagation Algorithm based on Weight and Random Walk). WRWPLPA proposes a new similarity calculation method combining weights and random walks. It uses weights and similarities to update labels in the process of label propagation, improving the accuracy and stability of community detection. First, weight is calculated by combining the neighborhood index and the position index, and the weight is used to distinguish the importance of the nodes in the network. Then, use random walk strategy to describe the similarity between nodes, and the label of nodes are updated by combining the weight and similarity. Finally, parallel propagation is comprehensively proposed to utilize label probability efficiently. Experiment results on artificial network datasets and real network datasets show that our algorithm has improved accuracy and stability compared with other label propagation algorithms.

This is the first of a series of two papers dealing with local limit theorems in relatively hyperbolic groups. In this first paper, we prove rough estimates for the Green function. Along the way, we introduce the notion of relative automaticity which will be useful in both papers and we show that relatively hyperbolic groups are relatively automatic. We also define the notion of spectral positive recurrence for random walks on relatively hyperbolic groups. We then use our estimates for the Green function to prove that $p_n\asymp R^{-n}n^{-3/2}$ for spectrally positive-recurrent random walks, where $p_n$ is the probability of going back to the origin at time n and where R is the inverse of the spectral radius of the random walk.

We consider continuous-time branching random walks on multidimensional lattices with birth and death of particles at a finite number of lattice points. Such processes are used in numerous applications, in particular, in statistical physics, population dynamics, and chemical kinetics. In the last decade, for various models of branching random walks, a series of limit theorems about the behavior of the process for large times has been obtained. However, it is almost impossible to analyze analytically branching random walks on finite time intervals; so in this paper we present an algorithm for simulating branching random walks and examples of its numerical realization.

We study Markovian continuous-time random walk models for Lévy flights and we show an example in which the convergence to stable densities is not guaranteed when jumps follow a bi-modal power-law distribution that is equal to zero in zero. The significance of this result is two-fold: i) with regard to the probabilistic derivation of the fractional diffusion equation and also ii) with regard to the concept of site fidelity in the framework of Lévy-like motion for wild animals., Severo Ochoa SEV-2017-0718

In this paper, we study the initial-boundary value problem of a repulsion Keller–Segel system with a logarithmic sensitivity modelling the reinforced random walk. By establishing an energy–dissipation identity, we prove the existence of classical solutions in two dimensions as well as existence of weak solutions in the three-dimensional setting. Moreover, it is shown that the weak solutions enjoy an eventual regularity property, i.e., it becomes regular after certain time T > 0. An exponential convergence rate towards the spatially homogeneous steady states is obtained as well. We adopt a new approach developed recently by the author to study the eventual regularity. The argument is based on observation of the exponential stability of constant solutions in scaling-invariant spaces together with certain dissipative property of the global solutions in the same spaces.

This paper investigates change point detection in state space models, in which the pre-change distribution $f^{\theta_0}$ is given, while the poster distribution $f^{\theta}$ after change is unknown. The problem is to raise an alarm as soon as possible after the distribution changes from $f^{\theta_0}$ to $f^{\theta}$, under a restriction on the false alarms. We investigate theoretical properties of a weighted Shiryayev-Roberts-Pollak (SRP) change point detection rule in state space models. By making use of a Markov chain representation for the likelihood function, exponential embedding of the induced Markovian transition operator, nonlinear Markov renewal theory, and sequential hypothesis testing theory for Markov random walks, we show that the weighted SRP procedure is second-order asymptotically optimal. To this end, we derive an asymptotic approximation for the expected stopping time of such a stopping scheme when the change time $\omega = 1$. To illustrate our method we apply the results to two types of state space models: general state Markov chains and linear state space models., Comment: 17 pages. arXiv admin note: text overlap with arXiv:1801.04756 by other authors

A random walk of a particle in ${R}^d$ is considered. The weak convergence of various transformations of trajectories of random flights with Poisson switching times was studied by Davydov and Konak...

When Iterated Prisoner's Dilemma takes place on a two-dimensional plane among mobile agents, the course of the game slightly differs from that one in a well-mixed population. In this paper we present a detailed derivation of the expected number of encounters required for Tit-for-tat strategy to get even with Always-Defect strategy in a Brownian-like population. It will be shown that in such an environment Tit-for-Tat can perform better than in a well-mixed population.

In this paper, we derive and analyse mean-field models for the dynamics of groups of individuals undergoing a random walk. The random motion of individuals is only influenced by the perceived densities of the different groups present as well as the available space. All individuals have the tendency to stay within their own group and avoid the others. These interactions lead to the formation of aggregates in case of a single species and to segregation in the case of multiple species. We derive two different mean-field models, which are based on these interactions and weigh local and non-local effects differently. We discuss existence and stability properties of solutions for both models and illustrate the rich dynamics with numerical simulations.

We answer positively a question of Kaimanovich and Vershik from 1979, showing that the final configuration of lamps for simple random walk on the lamplighter group over ${\Bbb Z}^d$ ($d \ge 3$) is the Poisson boundary. For $d \ge 5$, this had been shown earlier by Erschler (2011). We extend this to walks of more general types on more general groups.