Two independent random walks of opposite topological charge move on the discrete torus (Z/nZ)2, which contains k well-separated holes. The walks annihilate when they come within a core distance of each other, and each walk is anchored when it first touches a hole. We prove that the probability of annihilation before anchoring converges to w0/(w0+∑jwj), where the weights are explicit and depend only logarithmically on the sizes of the core and of the holes; for point-like core and holes, the limit is 1/(1+k). We then prove a fate theorem: the pair either terminates or ends as two opposite charges anchored on two different holes, with probability (k−1)/(k+1) in the point-like case, and the hosting pair {j,l} is chosen with probability proportional to wjwl. The proof combines an abstract competition lemma for rare sets in reversible Markov chains with sharp two-dimensional Green's function estimates.
Model and results
Model
Let Tn=(Z/nZ)2, N=n2, with ∣⋅∣ the Euclidean norm of the representative in (−n/2,n/2]2, and π the uniform distribution on Tn. A walk is a continuous-time simple random walk on Tn with total jump rate 1; its transition kernel is pu(x,y)=pu(0,y−x).
Fix k≥1 and exponents α0,α1,…,αk∈[0,1); put α∗=maxiαi.
Holes.Aj=B(cj,rj)={x:∣x−cj∣≤rj} with rj=⌊nαj⌋ if αj>0 and rj=0 (a single site) if αj=0, j=1,…,k, and dist(Ai,Aj)≥n/logn for $i\ne j.
Defects.X (charge +1) and Y (charge −1) are independent walks started at x0,y0.
Annihilation. With ρ=⌊nα0⌋ if α0>0 and ρ=0 if α0=0, let T0=inf{u:∣Xu−Yu∣≤ρ}.
Anchoring.TjX=inf{u:Xu∈Aj} and TjY=inf{u:Yu∈Aj}.
The start (x0,y0) is admissible if ∣x0−y0∣≥ρ+n/logn and dist(x0,Aj)∧dist(y0,Aj)≥n/logn for all j. Let T=T0∧minj(TjX∧TjY) be the time of the first event. Almost surely exactly one walk jumps at time T. If the state reached at time T realises several events simultaneously, we give priority to annihilation, then to X, then to the smaller index j. All statements below are unaffected by this convention.
For r≥0 write h(r)=1/EπTB(0,r) for a single walk started from π; by translation invariance EπTB(c,r) does not depend on c. Put hj=h(rj) and H=∑j=1khj.
Results
Theorem 1 (Competition law, rate form). Uniformly over admissible starts and hole positions, asn→∞,
Set wi=1/(1−αi), W=∑j=1kwj, Q=∑j=1kwj2. Theorem 2 gives hj/h(ρ)→wj/w0, hence:
Corollary 1 (Competition law). P(annihilationfirst)→w0/(w0+W). If core and holes are single sites, the limit is1/(1+k); in that caseh(ρ)=hjfor everynby symmetry, so Theorem 2 is not needed.
Fate. After the first event the dynamics continue as follows. If the first event is annihilation, the outcome is termination. If a defect is anchored at Ai, it stops, and the other defect continues as a walk until it first touches ⋃lAl, say at Al. If l=i the charges cancel and the outcome is termination; if l=i the outcome is the sustained pairS{i,l}: charges +1 and −1 anchored on two different holes.
Theorem 3 (Fate of a pair). Uniformly over admissible starts and hole positions,
P(termination)→w0+Ww0+W(w0+W)Q,
P(S{i,l})→W(w0+W)2wiwl(i<l),
P(sustainedpair)→W(w0+W)W2−Q.
In particular, with a single hole the pair terminates with probability→1, and forkpoint-like holes and a point-like coreP(sustainedpair)→(k−1)/(k+1).
Throughout, C,c denote positive constants depending only on k and α∗, whose value may change from line to line, and n is assumed large enough. We fix
g=gn=(logn)1/2,t=gn2,s=g1/2n2.
An abstract competition lemma
Let Z be an irreducible, reversible, continuous-time Markov chain on a finite set S with stationary distribution π, relaxation time trel, and d(u)=maxz∥Pz(Zu∈⋅)−π∥TV, which is non-increasing in u. Let B0,…,Bm⊂S be nonempty (not necessarily disjoint), Ti the hitting time of Bi, T=miniTi, and I=min{i:ZT∈Bi}. Let fi(z)=Pz(I=i) and pˉi=Pπ(I=i). For fixed 0<s<t let
ai=Pπ(Ti≤t),a=i∑ai,δ=i<l∑Pπ(Ti≤t,Tl≤t).
Lemma 2.1. If δ<a, then for every i
pˉi−aai≤d(s)+a−δPπ(T≤s)+δ.
Proof. On {T>t} the Markov property gives Pπ(I=i∣Ft)=fi(Zt), and Eπfi(Zt)=pˉi by stationarity. Hence
On {T≤t−s} the strong Markov property at T gives Eπ[fi(Zt)∣FT]=(Pt−Tfi)(ZT), and since 0≤fi≤1 and t−T≥s, ∣(Pt−Tfi)(ZT)−pˉi∣≤d(s). On the other hand Pπ(t−s<T≤t)≤Pπ(Z visits Bi in [t−s,t])=Pπ(T≤s) by stationarity. Splitting (1) according to {T≤t−s} and {t−s<T≤t},
Proof. The first statement is [1 Theorem 1]; see also [2 Ch. 3, Sec. 5.4]. The rest follows from
x−21x2≤1−e−x≤x.
Heat-kernel facts on the torus
Let pu be the kernel of the rate-1 continuous-time simple random walk W on Z2 started at 0, so that pu(0,z)=∑m∈Z2pu(z+nm). We use two standard inputs.
(L1) Local limit theorem[4 Ch. 2]: for u≥1 and all x∈Z2,
pu(x)−(πu)−1e−∣x∣2/u≤Cu−2.
(The covariance of Wu is (u/2)I.)
(L2) The coordinates of W are independent rate-21 walks on Z with kernel qu(k)=e−u/2I∣k∣(u/2), which is symmetric, non-increasing in ∣k∣, and satisfies qu(0)≤C(1+u)−1/2.
Lemma 3.1. There are absolute constants C,c such that for all large n:
(H0) pu(x,y)≤C/(1+u) for 0≤u≤n2;
(H1) pu(x,y)≤C/n2 for u≥n2, and also for all u≤n2 when ∣x−y∣≥n/8;
(H2) pn2(x,y)≥c/n2 for all x,y;
(H3) G(z):=∫0n2pu(0,z)du satisfies G(z)=π2log∣z∣∨1n+O(1) for ∣z∣≤n/4, and G(z)≤C for ∣z∣>n/4.
Proof. (H0). pu(0,z)=∏i=1,2∑m∈Zqu(zi+nm). Since qu is non-increasing in ∣k∣, for ∣zi∣≤n/2 and m=0 the term qu(zi+nm) is at most (2/n) times the sum of qu over a block of ⌈n/2⌉ consecutive sites, and these blocks are disjoint for distinct m of the same sign. Hence ∑mqu(zi+nm)≤qu(0)+4/n≤C(1+u)−1/2 for u≤n2.
(H1), off-diagonal part. The moment generating function of a coordinate is EeθWv(1)=exp(2v(coshθ−1))≤exp(2vθ2) for ∣θ∣≤1, so Chernoff’s bound with θ=min(1,b/v) gives P(Wv(1)≥b)≤exp(−min(b2/(2v),b/2)). The torus walk is the projection of W, so Px(∣Xv−x∣≥n/16)≤4exp(−min(b2/(2v),b/2)) with b=n/32. Let ∣x−z∣≥n/8 and u≤n2. By Chapman–Kolmogorov at time u/2, and since every y has ∣x−y∣≥n/16 or ∣y−z∣≥n/16, (H0) and symmetry give
(H1), u≥n2, and (H2). Let z be the representative of z with ∣z∣≤n/2. By (L1), pn2(z)≥(πn2)−1e−1/2−Cn−4≥c/n2, which gives (H2) because pn2(0,z)≥pn2(z). By (H0), suppn2≤C/n2, and for u>n2 Chapman–Kolmogorov gives pu(x,y)≤supwpn2(w,y)≤C/n2.
(H3). Let ∣z∣≤n/4 and eu(z)=pu(0,z)−pu(z)≥0. On the event that the torus walk is at z while Wu=z, the time σ=inf{v:∣Wv∣∞≥n/2} is at most u and ∣Xσ−z∣≥n/4−1≥n/8. By the strong Markov property and (H1), eu(z)≤supv≤n2,∣x−z∣≥n/8pv(x,z)≤C/n2 for u≤n2, so 0≤∫0n2eu(z)du≤C. By (L1),
∫0n2pu(z)du=∫1n2πue−∣z∣2/udu+O(1),
the error being at most 1+∫1∞Cu−2du. For z=0 the integral is π2logn. For ∣z∣≥1 substitute v=∣z∣2/u:
because ∫01(1−e−v)v−1dv≤1 and ∫1∞e−vv−1dv≤1. This proves the first part. If ∣z∣>n/4, (H1) gives G(z)≤n2⋅C/n2. ∎
Lemma 3.2 (Mixing). For the single walk, d(mn2)≤(1−c)m and trel≤n2/4. For the pair (X,Y) on Tn×Tn, d(mn2)≤(1−c2)m and trel≤n2/4.
Proof. By (H2), pn2(x,⋅)≥cπ(⋅); Doeblin’s argument gives the bound on d, and the pair satisfies the same minorisation with c2. The generator of the walk has eigenvalues 1−21(cosn2πa+cosn2πb); the smallest non-zero one is 21(1−cosn2π)≥4/n2 because 1−cosx≥2x2/π2 on [−π,π]. The spectral gap of a product of independent chains is the minimum of the gaps. ∎
Hitting estimates for a single walk
Let A=B(a0,r) with 0≤r≤nα∗, and L=logr∨1n≥(1−α∗)logn. For v≥0 and x∈Tn let Γv(x)=Ex∫0v1A(Xu)du=∑y∈A∫0vpu(x,y)du.
Lemma 4.1 (Occupation). For a∈A and n2≤v≤2t, Γv(a)=∣A∣[π2L+O(1+g)], and for all v≤2t, Γv(a)≤∣A∣[π2L+C(1+g)]. If dist(x,A)≥n/logn and v≤4t, then Γv(x)≤∣A∣C(loglogn+g).
Each term of the last sum is at least −log2. Grouping y by ∣a−y∣∈(r2−j−1,r2−j], j≥0, the sum is at most Cr2∑j(j+1)4−j≤C∣A∣ when r≥1 (and it vanishes when r=0). By (H1),
0≤y∈A∑∫n2vpu(a,y)du≤C∣A∣(v−n2)/n2≤C∣A∣g.
This proves the first two claims. If dist(x,A)≥n/logn, then by (H3) G(y−x)≤π2loglogn+C for every y∈A, and the contribution of u∈[n2,v] is at most C∣A∣⋅4g.
Lemma 4.2 (Hitting bounds). (a) For every x and v>0, Px(TA≤v)≤Γ2v(x)/infa∈AΓv(a).
(b) Pπ(TA≤n2)≤C/L and EπTA≥cn2L.
(c) If dist(x,A)≥n/logn and v≤2t, then Px(TA≤v)≤κn:=C(loglogn+g)/logn→0.
Proof. (a) XTA∈A, so by the strong Markov property Γ2v(x)≥Ex[1{TA≤v}Γv(XTA)]. (b) Averaging (a) over x∼π with v=n2 and using EπΓ2n2=2∣A∣ and Lemma 4.1, Pπ(TA≤n2)≤2/(π2L−C)≤C1/L. By stationarity and the union bound, Pπ(TA≤mn2)≤mC1/L; with m=⌊L/(2C1)⌋ this is at most 1/2, so EπTA≥21mn2. (c) Since Px(TA≤v) is non-decreasing in v we may take n2≤v≤2t, and (a) with Lemma 4.1 gives the bound C(loglogn+g)/(π2L−C(1+g)).
Proof of Theorem 2. Write E=EπTA. By stationarity and the strong Markov property,
By Lemma 4.1 the right-hand side is at most Pπ(TA≤t)∣A∣[π2L+C(1+g)] and at least Pπ(TA≤t−n2)∣A∣[π2L−C(1+g)]. Since Pπ(t−n2<TA≤t)≤Pπ(TA≤n2)≤C/L by stationarity and Lemma 4.2(b),
π2L+C(1+g)g≤Pπ(TA≤t)≤π2L−C(1+g)g+LC.
As g→∞ and g/L→0, this gives Pπ(TA≤t)=2Lπg(1+o(1)), uniformly in r. By Lemma 4.2(b), t/E≤g/(cL)→0, and by Lemmas 2.3 and 3.2, ∣Pπ(TA≤t)−t/E∣≤Et(4g1+2Et). Hence
Et=2Lπg(1+o(1)),
i.e. E=π2n2L(1+o(1)).
Proof of Theorem 1
Let Z=(X,Y) on S=Tn×Tn, with stationary law π⊗π (again written π), and
ordered as D0,D1X,…,DkX,D1Y,…,DkY to match the priority convention.
Rates.X−Y is a rate-2 simple random walk on Tn, started uniformly under π, so EπTD0=21EπTB(0,ρ), i.e. the rate of D0 is 2h(ρ). The rates of DjX and DjY are hj. By Lemma 4.2(b) every rate h′ in this list satisfies th′≤Cg/logn→0, and trel/t≤1/(4g). Hence, by Lemma 2.3, each ai=Pπ(Ti≤t) equals t times its rate times 1+ηi, where η:=maxi∣ηi∣≤4g1+Cg/logn→0. In particular a=2t(h(ρ)+H)(1+O(η)).
Pairs. We show δ=o(a). There are finitely many pairs, of three types.
(i) DjX and DlY. X and Y are independent under π, so the probability that both are hit by time t is ajXalY≤Cthj⋅a.
(ii) DjX and DlX, j=l (and likewise for Y). By the strong Markov property at TjX and Lemma 4.2(c), as dist(Aj,Al)≥n/logn,
(iii) D0 and DjX (and likewise for Y). Write Du=Xu−Yu. Realise the stationary pair as follows: X0 and D0 are independent and uniform; jumps occur at the points of a rate-2 Poisson process; at the i-th jump an independent uniform direction ei and an independent fair sign σi are drawn, and X moves by ei if σi=+1 while Y moves by ei if σi=−1. Then D jumps by fi=σiei. The directions (fi) are i.i.d. uniform and independent of (σi), so the path of D is a function of (D0,jump times,(fi)), which is independent of (X0,(σi)). Since Xu=X0+∑i≤Nufi1{σi=+1} and X0 is uniform and independent of everything else, XT0 is uniform and independent of the path of D. By the strong Markov property of the pair at T0,
Pπ(T0≤2t,X visits Aj during [T0,T0+2t])=Pπ(T0≤2t)Pπ(TAj≤2t).(3)
Now let F={∃u≤v≤2t:Xu∈Aj,Dv∈B(0,ρ)} and F={∃v≤u≤2t:Dv∈B(0,ρ),Xu∈Aj}. The stationary pair is reversible, so its time reversal on [0,2t] has the same law and Pπ(F)=Pπ(F). The event F is contained in the event in (3), and {TjX≤t,T0≤t}⊂F∪F. With Lemma 2.3,
Pπ(TjX≤t,T0≤t)≤2(2t+trel)22h(ρ)hj≤Cth(ρ)⋅a.
Altogether δ≤C(κn+g/logn)a=o(a).
Short times. By Lemma 2.3, Pπ(T≤s)≤(s+trel)⋅2(h(ρ)+H)≤C(s/t)a=Cg−1/2a. By Lemma 3.2, d(s)≤(1−c1/2)⌊g1/2⌋→0.
Conclusion from stationarity. Lemma 2.1 now gives pˉi=ai/a+o(1), and ai/a equals the ratio of the corresponding rates up to a factor 1+O(η). Thus pˉ0=h(ρ)/(h(ρ)+H)+o(1) and pˉjX=pˉjY=hj/(2(h(ρ)+H))+o(1).
Admissible starts. Let z0=(x0,y0) be admissible. By Lemma 4.2(c), Px0(TAj≤s)≤κn, and the same holds for y0. The difference X−Y is a rate-2 walk started at distance at least n/logn from B(0,ρ), so Pz0(T0≤s)=Px0−y0(TB(0,ρ)≤2s)≤κn for a rate-1 walk, since 2s≤2t. Hence Pz0(T≤s)≤(2k+1)κn, and Lemma 2.2 gives ∣fi(z0)−pˉi∣≤d(s)+(2k+1)κn→0. All bounds depend on the configuration only through k and α∗.
Remark 5.1. In the point-like case, EπT{a} is the same for every site a, so the three rates are 2h(0),h(0),h(0) exactly and the limit 1/(1+k) uses only Lemma 4.2(b),(c).
Proof of Theorem 3
Single-walk competition. Apply § 2 to one walk with the sets A1,…,Ak. The pair bound (ii), the short-time bound and the mixing bound hold verbatim, so with φl(y)=Py(the first hole touched is Al) and φˉl=Eπφl,
Position of the free defect. Let EiX be the event that the first event is the anchoring of X at Ai. Let τX=minjTjX, which is a function of the path of X only. On EiX we have T=τX, and YT lies in no hole. Let N={y:dist(y,Aj)<n/logn for some j}, so that π(N)≤Ck(n/logn+nα∗)2/n2→0. Since τX is independent of Y,
Second phase. By the strong Markov property at T, on EiX the free defect Y continues as a walk from YT, so P(EiX,Y next touches Al)=E[1EiXφl(YT)]. By (4) and the previous display,
P(EiX,Y next touches Al)=P(EiX)Hhl+o(1)=2H(h(ρ)+H)hihl+o(1),
using Theorem 1. The same holds with the roles of X and Y exchanged.
Summation.S{i,l} occurs in four disjoint ways (X or Y anchored first, at Ai or at Al), so P(S{i,l})=H(h(ρ)+H)2hihl+o(1). Termination occurs by annihilation or by both defects reaching the same hole: P(termination)=h(ρ)+Hh(ρ)+H(h(ρ)+H)∑ihi2+o(1). By Theorem 2, hj/h(ρ)→wj/w0, which gives the stated limits; they sum to 1. For k=1, W2=Q. For point-like core and holes, w0=wj=1, W=Q=k, and (W2−Q)/(W(1+W))=(k−1)/(k+1).
Remarks
Remark 7.1 (Numerical check). Monte Carlo simulation on tori with n=32,64,128 and k=1,2,4 point holes (3,000–6,000 runs each, stationary starts) gives P(annihilation first) and P(sustained pair) within 0.03 of 1/(1+k) and (k−1)/(k+1); for k=1 no sustained pair occurs.
Remark 7.2 (Scope). (i) The error terms are O((logn)−1/4) from the choice of g and are not optimised. (ii) The proof uses the torus only through Lemmas 3.1 and 3.2 and through translation invariance (for the identity of rates and for step (iii), which uses the group structure). (iii) Partial anchoring (a hole anchors with probability q<1 per visit), creation of new pairs, detachment, interaction between defects and anisotropic conduction are not covered by these theorems.
References
[1]D. J. Aldous and M. Brown, Inequalities for rare events in time-reversible Markov chains I, in Stochastic Inequalities, IMS Lecture Notes 22 (1992), 1–16.DOI
[2]D. J. Aldous and J. A. Fill, Reversible Markov Chains and Random Walks on Graphs, monograph, Chapter 3.
[4]G. F. Lawler and V. Limic, Random Walk: A Modern Introduction, Cambridge University Press, 2010.DOI