اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدRandom walks on generalized visible lattice points
113
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We consider the proportion of generalized visible lattice points in the plane visited by random walkers. Our work concerns the visible lattice points in random walks in three aspects: (1) generalized visibility along curves; (2) one random walker visible from multiple watchpoints; (3) simultaneous visibility of multiple random walkers. Moreover, we found new phenomenon in the case of multiple random walkers: for visibility along a large class of curves and for any number of random walkers, the proportion of steps at which all random walkers are visible simultaneously is almost surely larger than a positive constant.
قيم البحث
اقرأ أيضاً
This paper concerns the number of lattice points in the plane which are visible along certain curves to all elements in some set S of lattice points simultaneously. By proposing the concept of level of visibility, we are able to analyze more carefull
y about both the visible points and the invisible points in the definition of previous research. We prove asymptotic formulas for the number of lattice points in different levels of visibility.
Let $a,n in mathbb{Z}^+$, with $a<n$ and $gcd(a,n)=1$. Let $P_{a,n}$ denote the lattice parallelogram spanned by $(1,0)$ and $(a,n)$, that is, $$P_{a,n} = left{ t_1(1,0)+ t_2(a,n) , : , 0leq t_1,t_2 leq 1 right}, $$ and let $$V(a,n) = # textrm{ of vi
sible lattice points in the interior of } P_{a,n}.$$ In this paper we prove some elementary (and straightforward) results for $V(a,n)$. The most interesting aspects of the paper are in Section 5 where we discuss some numerics and display some graphs of $V(a,n)/n$. (These graphs resemble an integral sign that has been rotated counter-clockwise by $90^circ$.) The numerics and graphs suggest the conjecture that for $a ot= 1, n-1$, $V(a,n)/n$ satisfies the inequality $$ 0.5 < V(a,n)/n< 0.75.$$
We apply the power-of-two-choices paradigm to a random walk on a graph: rather than moving to a uniform random neighbour at each step, a controller is allowed to choose from two independent uniform random neighbours. We prove that this allows the con
troller to significantly accelerate the hitting and cover times in several natural graph classes. In particular, we show that the cover time becomes linear in the number $n$ of vertices on discrete tori and bounded degree trees, of order $mathcal{O}(n log log n)$ on bounded degree expanders, and of order $mathcal{O}(n (log log n)^2)$ on the ErdH{o}s-R{e}nyi random graph in a certain sparsely connected regime. We also consider the algorithmic question of computing an optimal strategy, and prove a dichotomy in efficiency between computing strategies for hitting and cover times.
We study random walks on the giant component of the ErdH{o}s-Renyi random graph ${cal G}(n,p)$ where $p=lambda/n$ for $lambda>1$ fixed. The mixing time from a worst starting point was shown by Fountoulakis and Reed, and independently by Benjamini, Ko
zma and Wormald, to have order $log^2 n$. We prove that starting from a uniform vertex (equivalently, from a fixed vertex conditioned to belong to the giant) both accelerates mixing to $O(log n)$ and concentrates it (the cutoff phenomenon occurs): the typical mixing is at $( u {bf d})^{-1}log n pm (log n)^{1/2+o(1)}$, where $ u$ and ${bf d}$ are the speed of random walk and dimension of harmonic measure on a ${rm Poisson}(lambda)$-Galton-Watson tree. Analogous results are given for graphs with prescribed degree sequences, where cutoff is shown both for the simple and for the non-backtracking random walk.
We propose a formula for the enumeration of closed lattice random walks of length $n$ enclosing a given algebraic area. The information is contained in the Kreft coefficients which encode, in the commensurate case, the Hofstadter secular equation for
a quantum particle hopping on a lattice coupled to a perpendicular magnetic field. The algebraic area enumeration is possible because it is split in $2^{n/2-1}$ pieces, each tractable in terms of explicit combinatorial expressions.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
