Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFrom coalescing random walks on a torus to Kingmans coalescent
122
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $mathbb{T}^d_N$, $dge 2$, be the discrete $d$-dimensional torus with $N^d$ points. Place a particle at each site of $mathbb{T}^d_N$ and let them evolve as independent, nearest-neighbor, symmetric, continuous-time random walks. Each time two particles meet, they coalesce into one. Denote by $C_N$ the first time the set of particles is reduced to a singleton. Cox [6] proved the existence of a time-scale $theta_N$ for which $C_N/theta_N$ converges to the sum of independent exponential random variables. Denote by $Z^N_t$ the total number of particles at time $t$. We prove that the sequence of Markov chains $(Z^N_{ttheta_N})_{tge 0}$ converges to the total number of partitions in Kingmans coalescent.
rate research
Read More
Full likelihood inference under Kingmans coalescent is a computationally challenging problem to which importance sampling (IS) and the product of approximate conditionals (PAC) method have been applied successfully. Both methods can be expressed in terms of families of intractable conditional sampling distributions (CSDs), and rely on principled approximations for accurate inference. Recently, more general $Lambda$- and $Xi$-coalescents have been observed to provide better modelling fits to some genetic data sets. We derive families of approximate CSDs for finite sites $Lambda$- and $Xi$-coalescents, and use them to obtain approximately optimal IS and PAC algorithms for $Lambda$-coalescents, yielding substantial gains in efficiency over existing methods.
The main results in this paper are about the full coalescence time $mathsf{C}$ of a system of coalescing random walks over a finite graph $G$. Letting $mathsf{m}(G)$ denote the mean meeting time of two such walkers, we give sufficient conditions under which $mathbf{E}[mathsf{C}]approx 2mathsf{m}(G)$ and $mathsf{C}/mathsf{m}(G)$ has approximately the same law as in the mean field setting of a large complete graph. One of our theorems is that mean field behavior occurs over all vertex-transitive graphs whose mixing times are much smaller than $mathsf{m}(G)$; this nearly solves an open problem of Aldous and Fill and also generalizes results of Cox for discrete tori in $dgeq2$ dimensions. Other results apply to nonreversible walks and also generalize previous theorems of Durrett and Cooper et al. Slight extensions of these results apply to voter model consensus times, which are related to coalescing random walks via duality. Our main proof ideas are a strengthening of the usual approximation of hitting times by exponential random variables, which give results for nonstationary initial states; and a new general set of conditions under which we can prove that the hitting time of a union of sets behaves like a minimum of independent exponentials. In particular, this will show that the first meeting time among $k$ random walkers has mean $approxmathsf{m}(G)/bigl({matrix{k 2}}bigr)$.
We prove new results on lazy random walks on finite graphs. To start, we obtain new estimates on return probabilities $P^t(x,x)$ and the maximum expected hitting time $t_{rm hit}$, both in terms of the relaxation time. We also prove a discrete-time version of the first-named authors ``Meeting time lemma~ that bounds the probability of random walk hitting a deterministic trajectory in terms of hitting times of static vertices. The meeting time result is then used to bound the expected full coalescence time of multiple random walks over a graph. This last theorem is a discrete-time version of a result by the first-named author, which had been previously conjectured by Aldous and Fill. Our bounds improve on recent results by Lyons and Oveis-Gharan; Kanade et al; and (in certain regimes) Cooper et al.
For $dge 3$ we construct a new coupling of the trace left by a random walk on a large $d$-dimensional discrete torus with the random interlacements on $mathbb Z^d$. This coupling has the advantage of working up to macroscopic subsets of the torus. As an application, we show a sharp phase transition for the diameter of the component of the vacant set on the torus containing a given point. The threshold where this phase transition takes place coincides with the critical value $u_*(d)$ of random interlacements on $mathbb Z^d$. Our main tool is a variant of the soft-local time coupling technique of [PT12].
We construct admissible circulant Laplacian matrix functions as generators for strictly increasing random walks on the integer line. These Laplacian matrix functions refer to a certain class of Bernstein functions. The approach has connections with biased walks on digraphs. Within this framework, we introduce a space-time generalization of the Poisson process as a strictly increasing walk with discrete Mittag-Leffler jumps subordinated to a (continuous-time) fractional Poisson process. We call this process `{it space-time Mittag-Leffler process}. We derive explicit formulae for the state probabilities which solve a Cauchy problem with a Kolmogorov-Feller (forward) difference-differential equation of general fractional type. We analyze a `well-scaled diffusion limit and obtain a Cauchy problem with a space-time convolution equation involving Mittag-Leffler densities. We deduce in this limit the `state density kernel solving this Cauchy problem. It turns out that the diffusion limit exhibits connections to Prabhakar general fractional calculus. We also analyze in this way a generalization of the space-time fractional Mittag-Leffler process. The approach of construction of good Laplacian generator functions has a large potential in applications of space-time generalizations of the Poisson process and in the field of continuous-time random walks on digraphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
