We prove a limit theorem for paths of random walks with n steps in Rd as n and d both go to infinity. For this, the paths are viewed as finite metric spaces equipped with the ℓp-metric for p∈[1,∞). Under the assumptions that all components of each step are uncorrelated, centered, have finite 2p-th moments, and are identically distributed, we show that such random metric space converges in probability to a deterministic limit space with respect to the Gromov-Hausdorff distance. This result generalises earlier work by Kabluchko and Marynych [Ann. Inst. H. Poincaré Probab. Statist. 60(4): 2945–2974, 2024] for p=2.
Random metric spacerandom walkgrowing dimension60F0560G50Introduction
For each dimension d∈N, consider a random walk (Si(d))i=0,1,… in Rd defined by
S0(d)=0,Sn(d)=X1(d)+X2(d)+⋯+Xn(d),n∈N,
where Xi(d)=(Xi,1(d),…,Xi,d(d)), i≥1, are independent identically distributed random vectors in Rd, and denote Si(d)=(Si,1(d),…,Si,d(d)).
The values of this random walk
Zn(d)={S0(d),…,Sn(d)},n∈N.
are considered as a finite metric space which is embedded in Rd with the induced Euclidean metric.
In the regime where the dimension d and the distribution of X1(d) are fixed, with EX1(d)=0 and an identity covariance matrix Cov(X1(d))=Id. Donsker’s invariance principle implies that, after rescaling by n−1/2, the random set Zn(d) converges in distribution to the path of the d-dimensional standard Brownian motion on [0,1].
Let ℓ2 be the space of square-summable real sequences with norm denoted by ‖·‖2. For every d∈N, we identify Rd with the d-dimensional coordinate subspace of ℓ2, which leads to the embedding of Rd into ℓ2. This identification allows us to view all random walks as subsets of a common ambient space.
When both n and d tend to infinity, under the square integrability and several further assumptions listed in [5], the random metric space (n−1/2Zn(d),‖·‖2) converges in probability to the Wiener spiral with respect to the Gromov–Hausdorff distance. The latter space is defined as the set of indicator functions 1[0,t], t∈[0,1], viewed as a subset of the Hilbert space L2([0,1]) and endowed with the metric induced by the L2-norm. With respect to this metric, the space is isometric to the interval [0,1] equipped with the distance r(t,s)=|t−s|. Later Jin [4] verified that the bridge variant of the random metric space also converges in probability to a deterministic limit in the Gromov–Hausdorff sense, that is [0,1] equipped with the pseudo-metric |t−s|(1−|t−s|). Furthermore, the case of random walk with heavy-tailed increments is considered in [6].
The Gromov–Hausdorff distance between metric spaces X=(X,ρX) and Y=(Y,ρY) is defined as
dGH(X,Y)=infi:X↪Z,j:Y↪ZdH(i(X),j(Y)),
where the infimum is taken over all isometric embeddings i and j into all possible metric spaces (Z,d) which can embed XandY. The Hausdorff distance between sets F and H in (Z,d) is defined as
dH(F,H)=inf{ε>0:F⊂HεandH⊂Fε},
where Fε={x:d(x,F)<ε} is the ε-neighbourhood of F, see [1, Chapter 7].
We replace the ℓ2-metric on the space of sequences with the ℓp-metric for a general p∈[1,∞). The study of random metric spaces relies on identifying the spaces up to isometries. The following remarks explain why the proof for p≠2 is not a routine modification of the ℓ2 case. Contrary to the ℓ2 setting, which admits a large group of rotations as isometries, the isometry group of ℓp for p≠2 is far more constrained, see [7] and [2, Theorem 7.4.1]. Furthermore, while we have the identity ‖x+y‖22=‖x‖22+‖y‖22+2⟨x,y⟩, no analogous simple expression exists for ‖x+y‖pp with p≠2. This complicates the analysis of path of the random walk.
It should be noted that Kabluchko and Marynych [5] established that for subsets of ℓ2, convergence in the Gromov–Hausdorff sense is equivalent to convergence in the Hausdorff distance up to isometries of ℓ2, that is distance for the two subsets defined by taking the infimum over the Hausdorff distance between their images under all possible isometries of ℓ2. However, this equivalence fails for compact subsets of ℓp when p≠2. For instance, consider the two-point metric spaces F={(0,0,…),(1,1,0,…)} and H={(0,0,…),(a1/p,b1/p,(2−a−b)1/p,0,…)} for any a,b>0 such that a+b<2, a+b≠1 and a,b≠1. Equipped with the ℓp-metric, these spaces are isometric for any p∈[1,∞) and thus the Gromov–Hausdorff distance between them vanishes, while it is impossible to map F to H using an isometry of ℓp if p≠2.
Fix a p∈[1,∞). Impose a special structure on the increments of the random walk. Namely, we assume that
X1(d)=d−1/p(ξ1,…,ξd),ξ1,…,ξdshare the same distribution,Eξ1=0,E|ξ1|2p<∞,Cov(ξi,ξj)=0for all1≤i≠j≤d.
Denote Eξ2=σ2. Let Mp be the p-th absolute moment of the standard normal distribution.
Letp∈[1,∞)andd=d(n)be an arbitrary sequence of positive integers such thatd(n)→∞asn→∞. Consider a random walk with increments given by (1). Then, asn→∞, the random metric space(n−1/2Zn(d),‖·‖p), converges in probability to([0,1],|t−s|σMp1/p)under the Gromov-Hausdorff distance.
In the case p=2, we assume Eξ4<∞, while only the finite second moment of ξ is required in [5]. However, we do not see a possibility that the moment assumption can be weaker, since a different tool is applied in our proof.
The paper is organised as follows. In Section 2, we provide the univariate and bivariate moment convergence theorems, which serve as the main tools for proving the limit theorem. Section 3 contains some auxiliary theorems and the proof of the main result.
Moment convergence theorem
We need the following results. (Moment convergence theorem).
Letη,η1,η2,…be independent identically distributed random variables withEη=μandVarη=σ2, andSn=η1+⋯+ηn,n≥1. ThenE|Sn−nμσn|p→Mp=2p/21πΓ(p+12),ifp∈(0,2)and forp≥2ifE|η|p<∞.
(Marcinkiewicz–Zygmund inequality. See Corollary 3.8.2 in [<xref ref-type="bibr" rid="j_vmsta299_ref_003">3</xref>]).
Letp≥1. Suppose thatX,X1,…,Xnare independent, identically distributed random variables with mean 0 andE|X|p<∞. SetSn=∑k=1nXk,n≥1. Then there exists a constantBpdepending only on p such thatE|n−1/2Sn|p≤Bpn1−p/2E|X|p,when1≤p≤2,BpE|X|p,whenp≥2.
(Bivariate moment convergence theorem).
Let(X1,Y1), …,(Xn,Yn)be independent copies of a centered2p-integrable random vector(X,Y)with the covariance matrix Σ. DenoteSn=X1+⋯+XnandZn=Y1+⋯+Yn. ThenE|n−1/2Sn|p|n−1/2Zn|p→E|η1η2|pasn→∞,where(η1,η2)∼N(0,Σ).
By the central limit theorem,
(n−1/2Sn(d),n−1/2Zn)→d(η1,η2)asn→∞.
Now we apply Skorokhod’s representation theorem, which allows us to replace the distributional convergence above with a.s. convergence on a new probability space which accommodates the following objects.
For every d∈N, a distributional copy (X‾k(d),Y‾k(d))k∈N of the sequence (Xk(d),Yk(d));
Distributional copy (η‾1,η‾2) of (η1,η2).
Denote S‾n(d)=X‾1(d)+⋯+X‾n(d) and Z‾n(d)=Y‾1(d)+⋯+Y‾n(d). Then
(n−1/2S‾n(d),n−1/2Z‾n(d))→a.s.(η1,η2)asn→∞.
By Lemma 1, as n→∞,
E(|n−1/2S‾n(d)|2p+|n−1/2Z‾n(d)|2p)=E(n−1/2|Sn(d)|2p+|n−1/2Zn(d)|2p)→E(|η1|2p+|η2|2p)=E(|η‾1|2p+|η‾1|2p).
Furthermore, by Pratt’s extension of the Lebesgue dominated convergence theorem, see [3, Theorem 5.5], and the inequality
|xy|p=|x|p|y|p≤|x|2p+|y|2p2,x,y∈R,
we conclude that, as n→∞,
E|n−1/2Sn(d)||n−1/2Zn(d)|=E|n−1/2S‾n(d)|p|n−1/2Z‾n(d)|p→E|η‾1η‾2|p=E|η1η2|p.
□
Convergence of the <inline-formula id="j_vmsta299_ineq_111"><alternatives><mml:math>
<mml:msub>
<mml:mrow>
<mml:mi>ℓ</mml:mi>
</mml:mrow>
<mml:mrow>
<mml:mi mathvariant="italic">p</mml:mi>
</mml:mrow>
</mml:msub></mml:math><tex-math><![CDATA[${\ell _{p}}$]]></tex-math></alternatives></inline-formula>-metric of random walks
The proof of Theorem 1 relies on the following theorems, while they follow the general scheme of [5], substantial adjustments are necessary to handle the ℓp-case with p≠2.
Letp∈[1,∞). Consider a random walk with increments given by (1). Thenn−p/2‖S⌊nt⌋(d)‖pp→ptp/2σpMpasn→∞for allt∈[0,1].
Without loss of generality, let t=1. By the definition of convergence in probability, we need to verify that
P{|n−p/2∑i=1d|Sn,i(d)|p−σpMp|>ε}→0asn→∞.
Markov’s inequality implies that (3) is bounded above by
ε−2E(n−p/2∑i=1d|Sn,i(d)|p−σpMp)2=ε−2(E(n−p/2∑i=1d|Sn,i(d)|p)2+σ2pMp2−2σpMpE(n−p/2∑i=1d|Sn,i(d)|p))=ε−2(n−pdE|Sn,1(d)|2p+n−p∑1≤i≠j≤dE|Sn,i(d)|p|Sn,j(d)|p+σ2pMp2−2n−p/2σpMpdE|Sn,1(d)|p)=ε−2(A1+A2+A3),
where we have decomposed the terms as follows,
A1=n−pdE|Sn,1(d)|2p,A2=n−p∑1≤i≠j≤dCov(|Sn,i(d)|p,|Sn,j(d)|p),
and
A3=n−pd(d−1)(E|Sn,1(d)|p)2+σ2pMp2−2n−p/2σpMpdE|Sn,1(d)|p.
Let (ξ1(k),…,ξd(k)), 1≤k≤n, be independent copies of (ξ1,…,ξd). Denote
bnij,p=Cov(n−p/2|ξi(1)+ξi(2)+⋯+ξi(n)|p,n−p/2|ξj(1)+ξj(2)+⋯+ξj(n)|p)
for all 1≤i≠j≤d. Thus, by Lemma 2,
A1=d−1En−p|ξ1+ξ1(2)+⋯+ξ1(n)|2p≤d−1B2pE|ξ|2p,
where B2p is a constant depending only on p, and the term A1 converges to 0 as d→∞.
By Theorem 2, the term A2 converges to 0 as n→∞ since limn→∞bndd,p=0.
Furthermore, the term A3 is bounded above by
n−pd2(E|Sn,1(d)|p)2−n−p/2σpMpdE|Sn,1(d)|p+σ2pMp2−n−p/2σpMpdE|Sn,1(d)|p=n−p/2dE|Sn,1(d)|p(n−p/2dE|Sn,1(d)|p−σpMp)+σpMp(σpMp−n−p/2dE|Sn,1(d)|p)=(n−p/2dE|Sn,1(d)|p−σpMp)2,
which converges to 0 as n→∞ by the moment convergence theorem. □
(Uniform convergence of the <inline-formula id="j_vmsta299_ineq_129"><alternatives><mml:math>
<mml:msub>
<mml:mrow>
<mml:mi>ℓ</mml:mi>
</mml:mrow>
<mml:mrow>
<mml:mi mathvariant="italic">p</mml:mi>
</mml:mrow>
</mml:msub></mml:math><tex-math><![CDATA[${\ell _{p}}$]]></tex-math></alternatives></inline-formula>-norm of random walk).
Letp∈[1,∞). Consider a random walk with increments given by (1). Thensupt∈[0,1]|n−p/2‖S⌊nt⌋(d)‖pp−tp/2σpMp|→p0asn→∞.
For all p≥1,
‖Sn(d)‖pp=∑i=1d|Sn,i(d)|p=Tn(d)+Qn(d),
where
Tn(d)=∑i=1d|Sn,i(d)|p−p∑i=1d∑j=1nXj,i(d)Sj−1,i(d)|Sj−1,i(d)|p−2,Qn(d)=p∑i=1d∑j=1nXj,i(d)Sj−1,i(d)|Sj−1,i(d)|p−2.
For all n∈N,
Tn(d)−Tn−1(d)=∑i=1d(|Sn,i(d)|p−p∑j=1nXj,i(d)Sj−1,i(d)|Sj−1,i(d)|p−2−|Sn−1,i(d)|p+p∑j=1n−1Xj,i(d)Sj−1,i(d)|Sj−1,i(d)|p−2)=∑i=1d(|Sn,i(d)|p−|Sn−1,i(d)|p−pXn,i(d)Sn−1,i(d)|Sn−1,i(d)|p−2)=∑i=1d(|Sn,i(d)|p−|Sn−1,i(d)|p−p(Sn,i(d)−Sn−1,i(d))Sn−1,i(d)|Sn−1,i(d)|p−2).
If p>1, then the generic term of this sum is
|Sn,i(d)|p−|Sn−1,i(d)|p−p(Sn,i(d)−Sn−1,i(d))Sn−1,i(d)|Sn−1,i(d)|p−2=|Sn,i(d)|p−|Sn−1,i(d)|p−pSn,i(d)Sn−1,i(d)|Sn−1,i(d)|p−2+p|Sn−1,i(d)|p=|Sn,i(d)|p+(p−1)|Sn−1,i(d)|p−pSn,i(d)Sn−1,i(d)|Sn−1,i(d)|p−2≥|Sn,i(d)|p+(p−1)|Sn−1,i(d)|p−p(|Sn,i(d)|pp+|Sn−1,i(d)|pp/(p−1))=0,
where the last inequality follows from xy≤xpp+yqq with 1p+1q=1, for all p,q>1 and x,y>0.
If p=1, then
Tn(d)−Tn−1(d)=∑i=1d(|Sn,i(d)|−|Sn−1,i(d)|−Xn,i(d)Sn−1,i(d)|Sn−1,i(d)|−1)=∑i=1d|Sn,i(d)|−Sn,i(d),ifSn−1,i(d)>0,|Sn,i(d)|+Sn,i(d),ifSn−1,i(d)<0,≥0.
Thus, the sequence Tn(d) is monotone increasing.
Next, Qn(d) is a martingale, since
E(Qn(d)−Qn−1(d)|Fn−1(d))=E(∑i=1dpXn,i(d)Sn−1,i(d)|Sn−1,i(d)|p−2|Fn−1(d))=pSn−1,i(d)|Sn−1,i(d)|p−2d1−1/pEξ=0,
where Fn−1(d) is the σ-algebra generated by X1(d),…,Xn−1(d). Then, by Doob’s inequality,
P{supt∈[0,1]|Q⌊nt⌋(d)|≥np/2ε}≤n−pε−2E(Qn(d))2.
We shall now estimate the second moment of Qn(d) for p>1. Firstly, by Lemma 1, for all δ>0, there exists an integer N(δ) such that for all j≥N(δ),
M2p−2−δ≤E|∑l=1j−1Xl,1(d)j−1E(X1,1(d))2|2p−2≤M2p−2+δ.
Using this inequality we infer
E(Qn(d))2=p2∑i=1d∑j=1n∑i′=1d∑j′=1nE(Xj,i(d)Xj′,i′(d)Sj−1,i(d)|Sj−1,i(d)|p−2Sj′−1,i′(d)|Sj′−1,i′(d)|p−2)=p2∑i=1d∑j=1nE(Xj,i(d))2E|Sj−1,i(d)|2p−2=p2dE(X1,1(d))2∑j=1n(j−1)2p−2(E(X1,1(d))2)p−1E|∑l=1j−1Xl,1(d)j−1E(X1,1(d))2|2p−2≤p2dE(X1,1(d))2∑j=1N(δ)(j−1)2p−2(E(X1,1(d))2)p−1E|∑l=1j−1Xl,1(d)j−1E(X1,1(d))2|2p−2+p2dE(X1,1(d))2∑j=1n(j−1)2p−2(E(X1,1(d))2)p−1(M2p−2+δ).
Hence,
E(Qn(d))2≤p2dE(X1,1(d))2∑j=1N(δ)E|∑l=1j−1Xl,1(d)|2p−2+p2(M2p−2+δ)npd(E(X1,1(d))2)p≤p2dE(X1,1(d))2N(δ)B2p−2max(N(δ)p−1,N(δ))E|X1,1(d)|2p−2+p2(M2p−2+δ)npd(E(X1,1(d))2)p,
where Lemma 2 is used to bound the first term and B2p−2 is a constant which depends on p. The right-hand side is bounded above by
p2N(δ)B2p−2max(N(δ)p−1,N(δ))d−1Eξ2E|ξ|2p−2+p2cnpd−1(Eξ2)p.
For p≥2, a direct application of Lemma 2 yields the alternative bound
E(Qn(d))2=p2∑i=1d∑j=1nE(Xj,i(d))2E|Sj−1,i(d)|2p−2≤p2dnE(X1,1(d))2B2p−2np−1E|X1,1(d)|2p−2=p2npB2p−2d−1Eξ2E|ξ|2p−2.
Secondly, for p=1,
E(Qn(d))2=E(∑i=1d∑j=1nXj,i(d)Sj−1,i(d)|Sj−1,i(d)|−1)2=∑i=1d∑j=1n∑i′=1d∑j′=1nE(Xj,i(d)Xj′,i′(d)Sj−1,i(d)|Sj−1,i(d)|−1Sj′−1,i′(d)|Sj′−1,i′(d)|−1)=∑i=1d∑j=1nE(Xj,i(d))2=ndE(X1,1(d))2=nd−1Eξ2.
Then we conclude that
n−pε−2E(Qn(d))2→0asn→∞,
and
n−p/2supt∈[0,1]|Q⌊nt⌋(d)|→p0asn→∞.
By Theorem 3,
n−p/2T⌊nt⌋(d)=n−p/2(‖S⌊nt⌋(d)‖pp−Q⌊nt⌋(d))→ptp/2σpMpasn→∞,
for all t∈[0,1]. By monotonicity of the function t↦T⌊nt⌋(d), Dini’s theorem yields that
supt∈[0,1]|n−p/2T⌊nt⌋(d)−tp/2σpMp|→p0asn→∞.
Therefore,
supt∈[0,1]|n−p/2‖S⌊nt⌋(d)‖pp−tp/2σpMp|≤supt∈[0,1]|n−p/2T⌊nt⌋(d)−tp/2σpMp|+n−p/2supt∈[0,1]|Q⌊nt⌋(d)|→p0,
which completes the proof. □
(Uniform convergence of the <inline-formula id="j_vmsta299_ineq_153"><alternatives><mml:math>
<mml:msub>
<mml:mrow>
<mml:mi>ℓ</mml:mi>
</mml:mrow>
<mml:mrow>
<mml:mi mathvariant="italic">p</mml:mi>
</mml:mrow>
</mml:msub></mml:math><tex-math><![CDATA[${\ell _{p}}$]]></tex-math></alternatives></inline-formula>-metric of differences).
Letp∈[1,∞). Consider a random walk with increments given by (1). Thensup0≤s≤t≤1|n−1/2‖S⌊nt⌋(d)−S⌊ns⌋(d)‖p−t−sσMp1/p|→p0asn→∞.
Take some m∈N. By Theorem 3, for every i=0,…,m−1,
n−1/2‖S⌊n(i/m)⌋(d)‖p→pi/mσMp1/p.
Moreover, for every integer 0≤i≤j≤m, by stationarity of the increments of random walks, we obtain that
n−1/2‖S⌊n(j/m)⌋(d)−S⌊n(i/m)⌋(d)‖p→p(j−i)/mσMp1/p.
By the union bound, it follows that, for every fixed m∈N,
max0≤i≤j≤m|n−1/2‖S⌊n(j/m)⌋(d)−S⌊n(i/m)⌋(d)‖p−(j−i)/mσMp1/p|→p0.
If 0≤s≤t≤1 are such that s∈[i/m,(i+1)/m) and t∈[j/m,(j+1)/m), then by the triangle inequality,
|n−1/2‖S⌊nt⌋(d)−S⌊ns⌋(d)‖p−n−1/2‖S⌊n(j/m)⌋(d)−S⌊n(i/m)⌋(d)‖p|≤n−1/2supz∈[im,i+1m]‖S⌊nz⌋(d)−S⌊n(i/m)⌋(d)‖p+n−1/2supz∈[jm,j+1m]‖S⌊nz⌋(d)−S⌊n(j/m)⌋(d)‖p.
Consider the random variable
εm,d=n−1/2maxi∈{0,…,m−1}supz∈[im,i+1m]‖S⌊nz⌋(d)−S⌊n(i/m)⌋(d)‖p.
To complete the proof, it suffices to show that, for every ε>0,
limm→∞lim supn→∞P{εm,d≥ε}=0.
By the union bound, it follows that, for every fixed m∈N,
P{εm,d≥ε}≤mP{supt∈[0,1m]‖S⌊nt⌋(d)‖pp≥np/2εp}.
Since ‖S⌊nt⌋(d)‖pp=T⌊nt⌋(d)+Q⌊nt⌋(d) with T⌊nt⌋(d) and Q⌊nt⌋(d) defined by (4), it suffices to show that
limm→∞lim supn→∞mP{T⌊n/m⌋(d)≥np/2εp/2}=0,
and
limm→∞lim supn→∞mP{supt∈[0,1m]Q⌊nt⌋(d)≥np/2εp/2}=0.
For fixed m∈N,
n−p/2T⌊n/m⌋(d)→pm−p/2σpMpasn→∞.
Hence, (6) holds for every m>22/pσ2(Mp)2/p/ε2. By Doob’s inequality,
mP{supt∈[0,1m]Q⌊nt⌋(d)≥np/2εp/2}≤mn−p(εp/2)−2E(Q⌊n/m⌋(d))2→0,
where the last step is implied by (5), hence (7) holds. □
By Corollary 7.3.28 of [1], the Gromov-Hausdorff distance between (n−1/2Zn,‖·‖p) and ([0,1],|t−s|σMp1/p) is bounded by
2sup0≤s≤t≤1|n−1/2‖S⌊nt⌋(d)−S⌊ns⌋(d)‖p−t−sσMp1/p|.
The proof is completed by referring to Theorem 5. □
Acknowledgments
The author is grateful to Ilya Molchanov for his suggestions and patience in correcting this paper. Special thanks are due to the anonymous referees for their constructive feedback, which helped clarify several ambiguities in the introduction and provided an alternative proof for the bivariate moment convergence theorem.