Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRecords for the number of distinct sites visited by a random walk on the fully-connected lattice
124
0
0.0
(
0
)
Authors
L. Turban
Ask ChatGPT about the research
No Arabic abstract
We consider a random walk on the fully-connected lattice with $N$ sites and study the time evolution of the number of distinct sites $s$ visited by the walker on a subset with $n$ sites. A record value $v$ is obtained for $s$ at a record time $t$ when the walker visits a site of the subset for the first time. The record time $t$ is a partial covering time when $v<n$ and a total covering time when $v=n$. The probability distributions for the number of records $s$, the record value $v$ and the record (covering) time $t$, involving $r$-Stirling numbers, are obtained using generating function techniques. The mean values, variances and skewnesses are deduced from the generating functions. In the scaling limit the probability distributions for $s$ and $v$ lead to the same Gaussian density. The fluctuations of the record time $t$ are also Gaussian at partial covering, when $n-v={mathrm O}(n)$. They are distributed according to the type-I Gumbel extreme-value distribution at total covering, when $v=n$. A discrete sequence of generalized Gumbel distributions, indexed by $n-v$, is obtained at almost total covering, when $n-v={mathrm O}(1)$. These generalized Gumbel distributions are crossing over to the Gaussian distribution when $n-v$ increases.
rate research
Read More
The probability distribution of the number $s$ of distinct sites visited up to time $t$ by a random walk on the fully-connected lattice with $N$ sites is first obtained by solving the eigenvalue problem associated with the discrete master equation. Then, using generating function techniques, we compute the joint probability distribution of $s$ and $r$, where $r$ is the number of sites visited only once up to time $t$. Mean values, variances and covariance are deduced from the generating functions and their finite-size-scaling behaviour is studied. Introducing properly centered and scaled variables $u$ and $v$ for $r$ and $s$ and working in the scaling limit ($ttoinfty$, $Ntoinfty$ with $w=t/N$ fixed) the joint probability density of $u$ and $v$ is shown to be a bivariate Gaussian density. It follows that the fluctuations of $r$ and $s$ around their mean values in a finite-size system are Gaussian in the scaling limit. The same type of finite-size scaling is expected to hold on periodic lattices above the critical dimension $d_{rm c}=2$.
Random walks on discrete lattices are fundamental models that form the basis for our understanding of transport and diffusion processes. For a single random walker on complex networks, many properties such as the mean first passage time and cover time are known. However, many recent applications such as search engines and recommender systems involve multiple random walkers on complex networks. In this work, based on numerical simulations, we show that the fraction of nodes of scale-free network not visited by $W$ random walkers in time $t$ has a stretched exponential form independent of the details of the network and number of walkers. This leads to a power-law relation between nodes not visited by $W$ walkers and by one walker within time $t$. The problem of finding the distinct nodes visited by $W$ walkers, effectively, can be reduced to that of a single walker. The robustness of the results is demonstrated by verifying them on four different real-world networks that approximately display scale-free structure.
We study the random sequential adsorption of $k$-mers on the fully-connected lattice with $N=kn$ sites. The probability distribution $T_n(s,t)$ of the time $t$ needed to cover the lattice with $s$ $k$-mers is obtained using a generating function approach. In the low coverage scaling limit where $s,n,ttoinfty$ with $y=s/n^{1/2}={mathrm O}(1)$ the random variable $t-s$ follows a Poisson distribution with mean $ky^2/2$. In the intermediate coverage scaling limit, when both $s$ and $n-s$ are ${mathrm O}(n)$, the mean value and the variance of the covering time are growing as $n$ and the fluctuations are Gaussian. When full coverage is approached the scaling functions diverge, which is the signal of a new scaling behaviour. Indeed, when $u=n-s={mathrm O}(1)$, the mean value of the covering time grows as $n^k$ and the variance as $n^{2k}$, thus $t$ is strongly fluctuating and no longer self-averaging. In this scaling regime the fluctuations are governed, for each value of $k$, by a different extreme value distribution, indexed by $u$. Explicit results are obtained for monomers (generalized Gumbel distribution) and dimers.
Diffusion-coagulation can be simply described by a dynamic where particles perform a random walk on a lattice and coalesce with probability unity when meeting on the same site. Such processes display non-equilibrium properties with strong fluctuations in low dimensions. In this work we study this problem on the fully-connected lattice, an infinite-dimensional system in the thermodynamic limit, for which mean-field behaviour is expected. Exact expressions for the particle density distribution at a given time and survival time distribution for a given number of particles are obtained. In particular we show that the time needed to reach a finite number of surviving particles (vanishing density in the scaling limit) displays strong fluctuations and extreme value statistics, characterized by a universal class of non-Gaussian distributions with singular behaviour.
The random walk with hyperbolic probabilities that we are introducing is an example of stochastic diffusion in a one-dimensional heterogeneous media. Although driven by site-dependent one-step transition probabilities, the process retains some of the features of a simple random walk, shows other traits that one would associate with a biased random walk and, at the same time, presents new properties not related with either of them. In particular, we show how the system is not fully ergodic, as not every statistic can be estimated from a single realization of the process. We further give a geometric interpretation for the origin of these irregular transition probabilities.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
