ترغب بنشر مسار تعليمي؟ اضغط هنا

Search via Parallel L{e}vy Walks on ${mathbb Z}^2$

162   0   0.0 ( 0 )
 نشر من قبل Francesco d'Amore
 تاريخ النشر 2020
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English




اسأل ChatGPT حول البحث

Motivated by the emph{L{e}vy foraging hypothesis} -- the premise that various animal species have adapted to follow emph{L{e}vy walks} to optimize their search efficiency -- we study the parallel hitting time of L{e}vy walks on the infinite two-dimensional grid.We consider $k$ independent discrete-time L{e}vy walks, with the same exponent $alpha in(1,infty)$, that start from the same node, and analyze the number of steps until the first walk visits a given target at distance $ell$.We show that for any choice of $k$ and $ell$ from a large range, there is a unique optimal exponent $alpha_{k,ell} in (2,3)$, for which the hitting time is $tilde O(ell^2/k)$ w.h.p., while modifying the exponent by an $epsilon$ term increases the hitting time by a polynomial factor, or the walks fail to hit the target almost surely.Based on that, we propose a surprisingly simple and effective parallel search strategy, for the setting where $k$ and $ell$ are unknown:The exponent of each L{e}vy walk is just chosen independently and uniformly at random from the interval $(2,3)$.This strategy achieves optimal search time (modulo polylogarithmic factors) among all possible algorithms (even centralized ones that know $k$).Our results should be contrasted with a line of previous work showing that the exponent $alpha = 2$ is optimal for various search problems.In our setting of $k$ parallel walks, we show that the optimal exponent depends on $k$ and $ell$, and that randomizing the choice of the exponents works simultaneously for all $k$ and $ell$.



قيم البحث

اقرأ أيضاً

Intermittent stochastic processes appear in a wide field, such as chemistry, biology, ecology, and computer science. This paper builds up the theory of intermittent continuous time random walk (CTRW) and L{e}vy walk, in which the particles are stocha stically reset to a given position with a resetting rate $r$. The mean squared displacements of the CTRW and L{e}vy walks with stochastic resetting are calculated, uncovering that the stochastic resetting always makes the CTRW process localized and L{e}vy walk diffuse slower. The asymptotic behaviors of the probability density function of Levy walk with stochastic resetting are carefully analyzed under different scales of $x$, and a striking influence of stochastic resetting is observed.
Recent experiments (G. Ariel, et al., Nature Comm. 6, 8396 (2015)) revealed an intriguing behavior of swarming bacteria: they fundamentally change their collective motion from simple diffusion into a superdiffusive L{e}vy walk dynamics. We introduce a nonlinear non-Markovian persistent random walk model that explains the emergence of superdiffusive L{e}vy walks. We show that the alignment interaction between individuals can lead to the superdiffusive growth of the mean squared displacement and the power law distribution of run length with infinite variance. The main result is that the superdiffusive behavior emerges as a nonlinear collective phenomenon, rather than due to the standard assumption of the power law distribution of run distances from the inception. At the same time, we find that the repulsion/collision effects lead to the density dependent exponential tempering of power law distributions. This qualitatively explains experimentally observed transition from superdiffusion to the diffusion of mussels as their density increases (M. de Jager et al., Proc. R. Soc. B 281, 20132605 (2014)).
The estimation of functions with varying degrees of smoothness is a challenging problem in the nonparametric function estimation. In this paper, we propose the LABS (L{e}vy Adaptive B-Spline regression) model, an extension of the LARK models, for the estimation of functions with varying degrees of smoothness. LABS model is a LARK with B-spline bases as generating kernels. The B-spline basis consists of piecewise k degree polynomials with k-1 continuous derivatives and can express systematically functions with varying degrees of smoothness. By changing the orders of the B-spline basis, LABS can systematically adapt the smoothness of functions, i.e., jump discontinuities, sharp peaks, etc. Results of simulation studies and real data examples support that this model catches not only smooth areas but also jumps and sharp peaks of functions. The proposed model also has the best performance in almost all examples. Finally, we provide theoretical results that the mean function for the LABS model belongs to the certain Besov spaces based on the orders of the B-spline basis and that the prior of the model has the full support on the Besov spaces.
The Wiener-Hopf factorization is obtained in closed form for a phase type approximation to the CGMY L{e}vy process. This allows, for the approximation, exact computation of first passage times to barrier levels via Laplace transform inversion. Calibr ation of the CGMY model to market option prices defines the risk neutral process for which we infer the first passage times of stock prices to 30% of the price level at contract initiation. These distributions are then used in pricing 50% recovery rate equity default swap (EDS) contracts and the resulting prices are compared with the prices of credit default swaps (CDS). An illustrative analysis is presented for these contracts on Ford and GM.
377 - Jean Bertoin 2018
In a step reinforced random walk, at each integer time and with a fixed probability p $in$ (0, 1), the walker repeats one of his previous steps chosen uniformly at random, and with complementary probability 1 -- p, the walker makes an independent new step with a given distribution. Examples in the literature include the so-called elephant random walk and the shark random swim. We consider here a continuous time analog, when the random walk is replaced by a L{e}vy process. For sub-critical (or admissible) memory parameters p < p c , where p c is related to the Blumenthal-Getoor index of the L{e}vy process, we construct a noise reinforced L{e}vy process. Our main result shows that the step-reinforced random walks corresponding to discrete time skeletons of the L{e}vy process, converge weakly to the noise reinforced L{e}vy process as the time-mesh goes to 0.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا