Random rotor walks and i.i.d. sandpiles on Sierpin ski graphs Robin Kaiser and Ecaterina Sava-Huss February 27 2024

2025-04-29 0 0 411.16KB 13 页 10玖币

侵权投诉

Random rotor walks and i.i.d. sandpiles on Sierpin´ski graphs

Robin Kaiser and Ecaterina Sava-Huss

February 27, 2024

Abstract

We prove that, on the inﬁnite Sierpin´ski gasket graph 𝖲𝖦, rotor walk with random initial

conﬁguration of rotors is recurrent. We also give a necessary condition for an i.i.d. sandpile to

stabilize. In particular, we prove that an i.i.d. sandpile with expected number of chips per site

greater or equal to three does not stabilize almost surely. Furthermore, the proof also applies

to divisible sandpiles and shows that divisible sandpile at critical density one does not stabilize

almost surely on 𝖲𝖦.

2020 Mathematics Subject Classiﬁcation. 60J10, 60J45, 05C81.

Keywords: rotor walk, rotor conﬁguration, simple random walk, recurrence, transience, Abelian

sandpile, divisible sandpile, stabilization, toppling procedure, inﬁnite volume, Sierpin´ski gasket,

critical density.

1 Introduction

Rotor-router walk (or shortly rotor walk) is a deterministic counterpart of a random walk on a graph

𝐺, deﬁned as follows. For each vertex 𝑥∈𝐺, we ﬁx a cyclic ordering of its neighbors and we refer

to it as the rotor mechanism at 𝑥. In addition, each vertex 𝑥is equipped with an arrow (or rotor),

which points initially to one of the neighbours of 𝑥. A particle (a walker) is located at the beginning

at some vertex in 𝐺and its location evolves in time as following. At each time step, the rotor at the

particle’s location 𝑥is incremented to point to the next neighbour in the cyclic ordering of 𝑥, and

then the particle follows this new direction and moves to the vertex the rotor points to. The rotor

walk (𝑅𝑡)𝑡∈ℕis obtained by repeated applications of this rule. If the initial direction of the arrows is

random, then we call this process random rotor walk or rotor walk with random initial conﬁguration.

Such processes are interesting because there is remarkable agreement between their behaviour and

the expected behaviour of random walks. On the other hand, between these two processes there

are also striking diﬀerences, for instance in what concerns the recurrence and transience. A rotor

walk is called recurrent if it visits each vertex inﬁnitely many times, almost surely. Otherwise is

called transient. The role of the underlying graph 𝐺and its properties inﬂuences the behaviour of

the rotor walks on them, and this aspect is observed in the current work where the underlying state

space is a non-transitive self-similar graph, the inﬁnite Sierpin´ski gasket graph. In particular, we

prove that a random rotor walk on the inﬁnite gasket is recurrent, a property shared by the simple

random walk as well. Recurrence and transience of rotor walks with random initial conﬁguration

has been investigated on regular trees in [AH11], on Galton-Watson trees and periodic trees in

arXiv:2210.00810v3 [math.PR] 26 Feb 2024

[HMSH15,HS12]. For the recurrence of 𝑝-walks, a process that interpolates between random and

rotor walks, see also [HLSH18]; a generalization of 𝑝-walks on higher dimensional lattices has been

considered in [Cha23], where the author investigates the recurrence and transience behaviour of the

process. On state spaces other than ℤ, where the simple random walk is recurrent, the behaviour

of random rotor walks is not completely understood.

Stabilization of i.i.d. sandpiles. A sandpile on a graph 𝐺is a function 𝜎:𝐺→ℕ0, where for 𝑥∈𝐺,

𝜎(𝑥) represents the number of grains of sand present at site 𝑥. The sandpile 𝜎is stable if for each

𝑥,𝜎(𝑥) is strictly less than the number of neighbours of 𝑥in 𝐺. If at some vertex 𝑥the sandpile

𝜎(𝑥) has some number of grains greater or equal to the number of neighbours of 𝑥, then 𝜎(𝑥) is

unstable and topples by sending one grain of sand to each of the neighbours. The toppling at 𝑥

can create other unstable vertices, and we say that 𝜎stabilizes if we can reach a stable sandpile

conﬁguration containing only stable vertices by toppling each vertex ﬁnitely many times, and 𝜎is

then called stabilizable. If the heights (𝜎(𝑥))𝑥∈𝐺are independent and identically distributed (i.i.d.)

random variables, we refer to 𝜎as an i.i.d. sandpile. Conditions for sandpiles at critical density1on

ℤ2were investigated in [HJL19, Theorem 1], where it is shown that an i.i.d. sandpile with E[𝜎(0)]

slightly less than 3 cannot stabilize almost surely unless 𝜎(𝑥)≤3 with high probability. We are not

aware of state spaces other than ℤ𝑑where necessary and suﬃcient conditions for i.i.d. sandpiles to

stabilize are given.

Rotor walks and sandpiles. While both processes may be seen as approaches to distribute chips

and move particles on a graph, another relation between them may not be obvious at ﬁrst sight.

Indeed, there is another natural relation between these two processes, in terms of group actions.

In particular, for any ﬁnite graph one can deﬁne a rotor-router group with elements being the set

of acyclic rotor conﬁgurations, where a conﬁguration is called acyclic if the rotors do not form a

directed cycle. On the same graph, over the set of stable sandpile conﬁgurations, one can deﬁne

in a natural way a Markov chain, by adding one chip uniformly at random and stabilizing. The

set of recurrent states for this Markov chain is a group, with group operation given by pointwise

addition followed by stabilization. This group is called the sandpile group or the critical group and

it acts transitively on the rotor-router group. These two groups are also isomorphic; we refer to

[HLM+08] and the references there for a beautiful exposition and more details in this direction.

Our contribution. We consider rotor walks and i.i.d. sandpiles 𝜎on the doubly inﬁnite Sierpin´ski

gasket graph 𝖲𝖦 with ﬁxed vertex 𝑜= (0,0) as in Figure 1. Our motivation for looking at such

state spaces comes from physics, because Abelian sandpiles on Sierpin´ski gasket graphs have been

considered by physicists for more than 20 years ago in [DPV01,DV98,KUZMS96], where several

predictions and conjectures have been made. While the conjectures are still lacking mathematical

proofs, there has been some recent progress on the limit shape for the Abelian sandpile on 𝖲𝖦 in

[CKF20]. For recent results on the identity element of the sandpile group and bounds on the speed

of convergence to stationarity of the Abelian sandpile Markov chain on 𝖲𝖦 see [KSHW24]; for the

scaling limit of the identity element, see also [KSH24].

We denote by (𝑅𝑡)𝑡∈ℕthe rotor walk with random initial conﬁguration of rotors on the doubly-

inﬁnite Sierpin´ski gasket graph 𝖲𝖦. If at the beginning of the process, for each 𝑥∈𝖲𝖦, the rotor

at 𝑥is uniformly distributed on the neighbours of 𝑥, that is, it points to each of the neighbours

with the same probability, then we call (𝑅𝑡)𝑡∈ℕuniform rotor walk, shortly 𝖴𝖱𝖶. It is not known

1On ℤ𝑑, the authors of [FdBR05] consider the case of 2𝑑particles at a site as stable, hence a shift in their results,

and they prove that a necessary condition for an i.i.d. sandpile to stabilize is E[𝜎(0)] ≤2𝑑−1, but this condition is

not suﬃcient for stabilization.

if the uniform rotor walk on ℤ2is recurrent. We prove the following.

Theorem 1.1. The uniform rotor walk (𝑅𝑡)𝑡∈ℕon the doubly-inﬁnite Sierpin´ski gasket graph 𝖲𝖦,

with anticlockwise ordering of the neighbours of each vertex, is recurrent.

Concerning Theorem 1.1, almost sure convergence of the uniform rotor walk is the best possible

result one could hope for, since transient rotor conﬁgurations always exist. On the Sierpin´ski

gasket one can consider a rotor conﬁguration which sends the particle always to the right. This

conﬁguration is a null set if rotors are chosen uniformly at random.

Theorem 1.2. Let 𝜎= (𝜎(𝑥))𝑥∈𝖲𝖦 be an i.i.d. sandpile on 𝖲𝖦 with 𝔼[𝜎(𝑜)] ≥3. If 0<Var[𝜎(𝑜)] <

∞, then 𝜎does not stabilize almost surely.

Above, if 𝖵𝖺𝗋[𝜎(𝑜)] = 0, then 𝜎is the constant conﬁguration which is already stable in the case

𝔼[𝜎(𝑜)] = 3 and does not stabilize if 𝔼[𝜎(𝑜)] >3. The proof of Theorem 1.2 carries over to divisible

sandpiles and as a consequence we obtain in Proposition 4.5 that an i.i.d. divisible sandpile 𝜎on

𝖲𝖦 with 𝔼[𝜎(𝑜)] ≥1 and 0 <𝖵𝖺𝗋[𝜎(𝑜)] <∞does not stabilize alsmot surely. We would like to

emphasize here that on ℤ𝑑, for an i.i.d. sandpile with 𝔼[𝜎(0)] = 2𝑑both cases - stabilization and

non-stabilization - can occur [FdBR05].

2 Preliminaries and notation

Graphs. Let 𝐺= (𝑉, 𝐸) be a locally ﬁnite, undirected, inﬁnite graph with vertex set 𝑉and edge

set 𝐸⊂𝑉×𝑉, and we ﬁx a vertex 𝑜∈𝑉where particles start their walk (random or deterministic).

For an edge 𝑒= (𝑥, 𝑦) we write sometimes 𝑥∼𝑦to denote that vertices 𝑥, 𝑦 are neigbours. For a

subset 𝑆⊂𝑉, we denote by 𝜕𝑜𝑆the outer boundary of 𝑆, that is,

𝜕𝑜𝑆={𝑥 /∈𝑆:𝑥has a neighbour in 𝑆}.

We denote by 𝖽𝖾𝗀(𝑥) the degree of 𝑥, i.e. the number of vertices in 𝐺that are neighbours of 𝑥, and

by abuse of notation we use 𝑥∈𝐺to denote vertices. The graph 𝐺comes with a natural metric

𝑑(𝑥, 𝑦), the graph distance, i.e. the minimal length of a path between two vertices 𝑥and 𝑦.

Rotor walks. For any 𝑥∈𝐺, we ﬁx an ordered family of its neighbours 𝖼𝗒𝖼(𝑥) = {𝑥1, . . . , 𝑥𝖽𝖾𝗀(𝑥)},

which may be thought of as the order in which, a particle exiting 𝑥, visits its neighbours. For

simplicity of notation, we ﬁx during this work the anticlockwise ordering of the neighbours for each

vertex. In addition, at the beginning of the process, each vertex 𝑥is equipped with an arrow (or

rotor) pointing to one of the neighbours, that indicates where should a particle leaving 𝑥for the

ﬁrst time move to. Subsequent exits from 𝑥are then determined by 𝖼𝗒𝖼(𝑥). The set 𝜌of all rotors

on 𝐺is called rotor conﬁguration. We represent the rotor conﬁguration 𝜌by a function 𝜌:𝐺→ℕ0,

with 𝜌(𝑥) = 𝑖∈ {1,...,𝖽𝖾𝗀(𝑥)}meaning that the rotor at 𝑥points to the 𝑖-th neighbour 𝑥𝑖in

the cyclic ordering 𝖼𝗒𝖼(𝑥) of 𝑥. With the rotor conﬁguration 𝜌and the anticlockwise ordering of

the neighbours for all vertices in 𝐺, we deﬁne recursively a rotor walk (𝑅𝑡)𝑡∈ℕas the sequence of

consecutive locations in 𝐺of a particle initially located at some ﬁxed vertex 𝑜∈𝐺so 𝑅0=𝑜, while

the subsequent locations are determined by the following rule. For any 𝑡≥1, if the location at

time 𝑡is 𝑥∈𝐺, so 𝑅𝑡=𝑥then in order to determine the next move, the particle (the walker) ﬁrst

increments the rotor at 𝑥, i.e. it changes its direction to the next neighbor in the counterclockwise

order 𝖼𝗒𝖼(𝑥), and then it follows this new direction. Thus at each time step 𝑡, we change not only

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Randomrotorwalksandi.i.d.sandpilesonSierpin´skigraphsRobinKaiserandEcaterinaSava-HussFebruary27,2024AbstractWeprovethat,ontheinfiniteSierpin´skigasketgraph��,rotorwalkwithrandominitialconfigurationofrotorsisrecurrent.Wealsogiveanecessaryconditionforani.i.d.sandpiletostabilize...

展开>> 收起<<

Random rotor walks and i.i.d. sandpiles on Sierpin ski graphs Robin Kaiser and Ecaterina Sava-Huss February 27 2024.pdf

共13页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Random rotor walks and i.i.d. sandpiles on Sierpin ski graphs Robin Kaiser and Ecaterina Sava-Huss February 27 2024

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: