11institutetext: Department of Biomedical Engineering, McGill University,
Montreal, QC, Canada 11email<EMAIL_ADDRESS>22institutetext: McConnell Brain Imaging Center, Montreal Neurological
Institute and Hospital, Montreal, QC, Canada 33institutetext: Department of
Neurology and Neurosurgery, McGill University, Montreal, QC, Canada

# Hessian-based Similarity Metric for Multimodal Medical Image Registration

Mohammadreza Eskandari 1122 Houssem-Eddine Gueziri 22 D. Louis Collins 112233

###### Abstract

One of the fundamental elements of both traditional and certain deep learning
medical image registration algorithms is measuring the
similarity/dissimilarity between two images. In this work, we propose an
analytical solution for measuring similarity between two different medical
image modalities based on the Hessian of their intensities. First, assuming a
functional dependence between the intensities of two perfectly corresponding
patches, we investigate how their Hessians relate to each other. Secondly, we
suggest a closed-form expression to quantify the deviation from this
relationship, given arbitrary pairs of image patches. We propose a geometrical
interpretation of the new similarity metric and an efficient implementation
for registration. We demonstrate the robustness of the metric to intensity
nonuniformities using synthetic bias fields. By integrating the new metric in
an affine registration framework, we evaluate its performance for MRI and
ultrasound registration in the context of image-guided neurosurgery using
target registration error and computation time.

###### Keywords:

Multimodal registration Similarity metric Image Hessian.

##  1 Introduction

Aligning images of different modalities is the key to combining functional and
anatomical data from multiple sources in image-guided procedures. In this
context, quantifying the similarity of images is an important yet challenging
task due to different intensity distribution arising from distinct protocols
and physical principles governing each modality. This already-complex problem
becomes more complicated in the presence of noise and modality-dependent
artifacts. A huge variety of mathematically proven, hand-crafted, and deep
learning-based solutions have been proposed for many use cases, each having
their own advantages and disadvantages.

One of the earliest successes in multimodal registration was achieved by the
introduction of mutual information [12, 24]. This measure is very general
since it only assumes statistical dependence between the intensities of the
images. To improve its performance for certain tasks, several variants have
been proposed [11, 18, 19]. Soon after mutual information, the correlation
ratio was introduced [21], with the idea of constraining the relationship
between the intensities of the images. The correlation ratio assumes a
functional dependence between image intensities and quantifies the compliance
of this assumption. There exist some variants of the correlation ratio,
however this method did not gain the popularity of mutual information.

Both mutual information and correlation ratio use image intensities directly
as the feature space. Another research avenue in multimodal registration has
been handcrafting features. Image gradients, local statistical information and
local structures such as points, edges, contours, surfaces and volumes, are
some commonly used [16]. Many studies have also tried to convert multimodal
registration to unimodal registration by simulating one image from the other
[1, 26] or mapping both images into a third space [25].

More recently, several deep learning methods have been proposed to overcome
the challenges of measuring similarity between image pairs of distinct
modalities [2, 8, 22]. The main idea behind these metrics is to use supervised
learning to model similarity between registered pairs of patches. As a result,
these methods can only perform well on the modalities they have been trained
on and generalization to other modalities is highly dependent on data
augmentation methods used during training.

One of the well-studied features for image registration and medical image
processing in general is image gradient. The gradient can be a good descriptor
of a neighborhood; its magnitude and direction describe how the intensities
change in a small radius. A popular similarity metric for multimodal
registration is the cosine squared of the angle between gradients of two
images, which we will refer to as gradient orientation alignment [3]. This
method was first intuitively proposed to incorporate local information [7,
17]. Later, it was shown that maximizing mutual information on a small patch
is equivalent to maximizing gradient orientation alignment [10]. The
usefulness of gradient orientation alignment raises the question whether
higher order derivatives can be beneficial in quantifying image similarities.

Despite the long-run progress in research on traditional similarity measures
and transition to deep learning era, we believe there still exists certain
areas to be explored for defining better similarity metrics based on
mathematical properties of the images. Our focus is on the Hessian matrix,
which contains information regarding the geometry of the image in a
neighborhood. One of the most important applications of Hessian matrix in
medical image processing is identifying vessel-like structures [5]. This is
because a Hessian can approximate a neighborhood with an ellipsoid. Our
approach in this paper is similar to that of correlation ratio [21], since we
constrain the relation between the two modalities with a functional
dependence. We develop the mathematical formulation for using Hessians in
measuring image similarity and test the performance of our proposed metric in
synthetic and real use cases.

##  2 Method

###  2.1 Defining the Hessian-based Similarity Metric

We define a metric for quantifying pointwise similarity between two medical
images of distinct modalities. We refer to the images as the fixed image and
the moving image and denote them with
$F(\mathbf{x}),M(\mathbf{x}):\Omega\subset\mathbb{R}^{d}\rightarrow\mathbb{R}$,
respectively, where $d$ is the dimension of the images. We start by deriving
the relationship between the Hessians of two aligned patches centered at
$\mathbf{x_{0}}$, assuming a functional dependence between their intensities,
i.e., there exists a function $g:\mathbb{R}\rightarrow\mathbb{R}$ that maps
the intensities of the fixed patch onto the corresponding intensities of the
moving patch. The gradients and the Hessians of the images are represented by
$\nabla F$, $\nabla M$, $H_{F}$ and $H_{M}$, respectively. For any
$\mathbf{\delta x}$, as long as $\mathbf{x_{0}+\delta x}$ lies inside the
patch of interest, we can formulate the functional dependence assumption as:

$M(\mathbf{x_{0}+\delta x})=g(F(\mathbf{x_{0}+\delta x}))\,.$ (1)

Writing the Taylor expansion of both sides up to the second order and equating
terms of the same order yields:

$\nabla M(\mathbf{x_{0}})=\frac{dg}{dF}\nabla F(\mathbf{x_{0}})\,.$ (2)
$H_{M}(\mathbf{x_{0}})=\frac{dg}{dF}H_{F}(\mathbf{x_{0}})+\frac{d^{2}g}{dF^{2}}\nabla
F(\mathbf{x_{0}})\nabla F^{T}(\mathbf{x_{0}})\,.$ (3)

Since the mapping between the intensities is not given, the derivatives of $g$
are unknown. We rewrite the above equations by replacing the derivatives of
$g$ with scalar variables $\lambda$, $\mu$ and $\nu$. Note that these
equations are valid for any point inside the patch of interest, therefore for
convenience of notation, we drop the dependence of the Hessians and the
gradients on $\mathbf{x}$.

$\nabla M=\lambda\nabla F\,.$ (4) $H_{M}=\mu H_{F}+\nu\nabla F\nabla F^{T}\,.$
(5)

These two equations describe how the gradients and the Hessians of two patches
relate to each other, subject to a functional dependence between their
intensities. The first equation encapsulates $d$ scalar equations and suggests
that the gradients of two patches should be aligned or anti-aligned everywhere
(depending on the sign of $\lambda$). The second equation encapsulates $d^{2}$
equations, only $(d^{2}+d)/2$ of which are unique due to symmetricity of
matrices. It can be inferred from this equation that the Hessian of the moving
patch can be decomposed into a linear combination of the Hessian and the
gradient outer product of the fixed image. In other words, there exist two
scalars, $\mu$ and $\nu$, such that they satisfy all encapsulated scalar
equations at the same time. We use this equation as the starting point for
defining our Hessian-based similarity metric. For arbitrary pairs of patches,
there is no functional dependence between their intensities and hence, Eq. 5
will not hold true. To quantify the violation of this equality, we define a
normalized quadratic error:

$E=\frac{||H_{M}-\mu H_{F}-\nu\nabla F\nabla F^{T}||^{2}}{||H_{M}||^{2}}\,,$
(6)

where $||.||$ denotes the Frobenius norm. To evaluate this error regardless of
the unknown scalars, we find $\mu$ and $\nu$ such that $E$ will be minimized.
We denote the optimal solution with $\mu^{\star}$ and $\nu^{\star}$ and the
optimal value with $E^{\star}$. To minimize $E$, we compute its derivatives
with respect to $\mu$ and $\nu$, equate the derivatives to zero, solve the
resulting system of linear equations, obtain $\mu^{\star}$ and $\nu^{\star}$
and plug them into equation. $E^{\star}$ is a measure of dissimilarity and is
guaranteed to be bounded by zero and one. We define the Hessian-based
similarity metric as $S=1-E^{\star}$. This metric can be represented by a
closed-form expression:

$\scriptsize S=\frac{||\nabla
F||^{4}tr(H_{M}^{T}H_{F})^{2}+||H_{F}||^{2}(\nabla F^{T}H_{M}\nabla
F)^{2}-2tr(H_{M}^{T}H_{F})(\nabla F^{T}H_{M}\nabla F)(\nabla F^{T}H_{F}\nabla
F)}{||H_{M}||^{2}(||\nabla F||^{4}||H_{F}||^{2}-(\nabla F^{T}H_{F}\nabla
F)^{2})}\,,$ (7)

where $S=1$ implies perfect functional dependence between intensities and
$S=0$ implies perfect functional independence. As it was expected from Eq. 5,
the metric is assymetric in terms of fixed and moving image. Another way to
express this metric is by vectorizing Eq. 5. We can formulate the metric in
terms of $\alpha$, $\beta$ and $\gamma$ which denote the angle between
$\operatorname{vec}(H_{M})$ and $\operatorname{vec}(H_{F})$, the angle between
$\operatorname{vec}(H_{M})$ and $\operatorname{vec}(\nabla F\nabla F^{T})$,
and the angle between $\operatorname{vec}(H_{F})$ and
$\operatorname{vec}(\nabla F\nabla F^{T})$, respectively.

$S=\frac{\cos^{2}\alpha+\cos^{2}\beta-2\cos\alpha\cos\beta\cos\gamma}{\sin^{2}\gamma}\,.$
(8)

Additionally, the Hessian-based similarity metric has a clear geometric
interpretation. It can be interpreted as the cosine squared of the angle
between $\operatorname{vec}(H_{M})$ and its projection onto the plane spanned
by $\operatorname{vec}(H_{F})$ and $\operatorname{vec}(\nabla F\nabla F^{T})$.
The angles between the vectorized matrices is depicted in Figure 1. It must be
taken into consideration that vectorized Hessian matrices can not be
visualized in 3 dimensions and this figure is only intended for providing
intuition regarding the defined metric.

Figure 1: Geometric interpretation of the Hessian-based similarity metric

We should mention that by following the above steps for Eq. 4 instead of Eq.
5, the resulting similarity metric will be the cosine squared of the angle
between the gradients of the two images. The derivation of this metric is
included in supplementary material.

In practice, to compute the gradients and the Hessians of the images, we
convolve them with first and second order Gaussian derivative kernels. The
choice of standard deviation for these Gaussian kernels directly affects the
behavior of the similarity metric and enables capturing structures of
different scales. The standard deviation should be the same for both images
and all components of the Gaussian kernels. By setting the standard deviation
to a certain scale, structures of higher scale will not be captured and
structures of lower scale will be smoothed out.

###  2.2 Transforming Hessians

A straightforward strategy for computing the Hessian-based similarity metric
during the registration process involves first applying a deformation onto the
moving image and then computing its Hessian. Since the cost of computing the
Hessian is relatively high, our approach is to compute it only once at the
preprocessing stage and to transform it according to each deformation.

Assuming a diffeomorphism
$\mathbf{P}(\mathbf{x}):\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$ that maps
$\mathbf{x}=(x_{1},...,x_{d})$ from the original image onto
$\mathbf{u}=(u_{1},...,u_{d})$ from the deformed image, each component of the
Hessian in the transformed coordinate can be expressed in terms of the
components of the original Hessian and gradient:

$\frac{\partial^{2}M}{\partial u_{k}\partial
u_{l}}=\sum_{i=1}^{d}\frac{\partial M}{\partial
x_{i}}\frac{\partial^{2}x_{i}}{\partial u_{k}\partial
u_{l}}+\sum_{i=1}^{d}\sum_{j=1}^{d}\frac{\partial^{2}M}{\partial x_{i}\partial
x_{j}}\frac{\partial x_{i}}{\partial u_{k}}\frac{\partial x_{j}}{\partial
u_{l}}\,.$ (9)

Partial derivatives of $\mathbf{x}$ with respect to $\mathbf{u}$ are directly
computable if the inverse transformation, $\mathbf{P}^{-1}(\mathbf{u})$, is
explicitly known. Eq. 9 implies that a nonlinear transformation must be
$C^{2}$ continuous, otherwise the transformed Hessian will be discontinuous.
Note that when the transformation is linear, the first term on the right hand
of Eq. 9 will vanish and the transformed Hessian can be expressed as
$J_{\mathbf{P}}^{-T}H_{M}J_{\mathbf{P}}^{-1}$, where $J_{\mathbf{P}}$ is the
Jacobian matrix of the transformation.

###  2.3 Implementing the Metric in an Affine Registration Scheme

We present a simple affine registration scheme to test the proposed similarity
metric. We start by computing the Hessian of both images and the gradient of
the fixed image. We sample $N$ random voxels from the fixed image. The
Hessian-based similarity metric is computed over the sampled voxels and their
average is used as the similarity score for each deformation. No
regularization term is used in this scheme. We use Differential Evolution [23]
to find the optimal affine deformation. Affine deformations are defined by a
translation vector and three matrices representing rotation, shear, and
scaling. Shear and scaling are defined as an upper triangular matrix and a
diagonal matrix, respectively. For each affine deformation, its inverse is
applied to the location of the sampled voxels to find their corresponding
points on the moving image. Hessian of the moving image is linearly
interpolated over these points and transformed using the Jacobian of the
deformation field. The optimization process terminates as soon as a
termination condition is satisfied.

Figure 2: The effect of intensity nonuniformities on the behavior of the
Hessian-based similarity metric and gradient orientation alignment. (a) and
(b) show T1w and T2w MNI-ICBM152 templates [14]. (c) and (d) are derived by
multiplying (a) and (b) to (e) and (f) as synthetic bias fields, respectively.
(g), (h), (i) and (j) show the computed Hessian-based similarity metric and
gradient orientation alignment on original and corrupted image pairs. The
difference between computed similarity maps are shown in (k) and (l).

##  3 Experiments

###  3.1 Robustness to Intensity Nonuniformities

Intensity nonuniformities can degrade the precision of any analysis in medical
image computing. Therefore, comping up with a similarity metric that is robust
to these low-frequency artefacts is beneficial. To examine qualitatively and
visually how robust our metric is to intensity nonuniformities, we compute the
metric all over a pair of registered images, before and after applying
synthetic bias fields. Figure 2 shows this process for T1w and T2w MNI-ICBM152
templates [14] on the saggital view. As it can be seen, the added artifacts
have a negligible effect on the Hessian-based similarity metric; however,
their effect on gradient orientation alignment is notable.

###  3.2 Quantitative Results

We test the registration performance of our method in the context of image-
guided neurosurgery for aligning preoperative T1w MR volumes to preresection
intraoperative ultrasound volumes of the BITE database [13]. The open-access
BITE database contains scans of 14 patients with brain cancer, along with
homologous manually annotated landmarks. We reconstruct ultrasound volumes
from the ultrasound slices with a voxel size of $0.5\times 0.5\times 0.5$ mm
using IBIS [4]. We resample MR volumes to the same voxel size. We use provided
landmarks to compute mean target registration error (mTRE) as a measure of
accuracy.

To run our registration experiments, We set $N$ to 5000 and the standard
deviation for computing gaussian derivatives to 1.5 mm. Maximum displacement
in each direction and maximum rotation around each axis is set to 10 mm and 5
degrees, respectively. Maximum shear and scaling in each direction are both
set to 5%. For optimization using Differential Evolution we use best/1/bin
strategy [15] and set the population size and maximum number of iterations to
24 and 200, respectively. Crossover probability is set to $0.7$ and
differential weight will be randomly sampled from $(0.5,1)$ interval. Whenever
the standard deviation of population’s cost falls below 0.2% of the mean of
population’s cost, the optimization will terminate.

As a baseline, we implement gradient orientation alignment and run it in the
same framework that we have developed. We are choosing this method for two
main reasons; first, its effectiveness for MR to ultrasound registration task
has been previously demonstrated [3], and second, it follows the same logic as
our proposed metric.

The results of the registration process are shown in Table 1 and Figure 3. CPU
time of each method for each case during preprocessing and optimization is
reported, too. The preprocessing stage includes parsing images, random
sampling, and computing image derivatives. All tests are performed on an
Intel® CoreTM i7-11370H @ 3.30GHz CPU.

Table 1: Mean target registration error (mTRE) and CPU time for registration of preoperative MR to pre-resection ultrasound on BITE database | Hessian-based similarity metric | Gradient orientation alignment
---|---|---
case no. | mTRE (mm) | CPU time (s) | mTRE (mm) | CPU time (s)
preprocess. | optim. | preprocess. | optim.
2 | 1.78 (0.4-4.5) | 30.8 | 4.9 | 2.96 (1.1-5.7) | 13.1 | 3.2
3 | 2.94 (0.7-5.8) | 48.8 | 5.7 | 2.55 (0.6-6.4) | 21.1 | 3.8
4 | 1.63 (0.3-4.2) | 24.9 | 7.0 | 2.29 (0.9-4.5) | 10.7 | 4.3
5 | 2.18 (0.4-6.6) | 33.9 | 3.0 | 2.14 (0.3-6.4) | 14.5 | 5.5
6 | 1.82 (0.4-3.6) | 34.0 | 4.1 | 1.92 (0.8-3.5) | 14.4 | 3.4
7 | 2.44 (0.8-5.0) | 40.2 | 5.0 | 3.17 (1.2-5.9) | 17.2 | 4.0
8 | 2.71 (0.8-5.1) | 37.9 | 5.5 | 3.18 (0.5-6.2) | 16.2 | 3.1
9 | 2.60 (0.5-5.8) | 27.2 | 4.8 | 2.64 (0.5-6.5) | 11.5 | 4.4
10 | 1.84 (0.4-3.9) | 37.3 | 5.9 | 2.28 (0.7-5.7) | 16.6 | 4.0
11 | 1.59 (0.6-3.2) | 32.9 | 5.6 | 2.57 (0.3-5.4) | 14.2 | 3.0
12 | 3.06 (0.7-5.6) | 32.0 | 3.1 | 2.88 (0.7-6.0) | 13.6 | 3.2
13 | 3.56 (0.9-6.3) | 28.3 | 4.6 | 3.99 (1.4-7.6) | 12.2 | 5.7
14 | 2.73 (0.2-4.8) | 35.7 | 3.0 | 3.61 (2.0-6.5) | 15.6 | 3.4
mean | 2.37 | 34.15 | 4.78 | 2.78 | 14.68 | 3.92
Figure 3: Box plot of mTRE for registration of preoperative MR to pre-
resection ultrasound on BITE database. First box on the left shows mTRE before
registering MR to ultrasound. The box on the left shows the minimum mTRE that
is achievable using an affine transformation based solely on the landmarks.
Orange lines and green triangles represent the median and the mean,
respectively.

To further monitor the behavior of each similarity metric, we plot the
similarity score vs. mTRE for each deformation that is evaluated during the
optimization. Figure 4 shows this scatter plot for case 10 of the BITE
database. As it can be seen, both plots have the same general trend; as the
similarity metric increases, mTRE decreases. In addition, the points derived
from the Hessian-based similarity metric are spread out. This can imply a
better capture range for this metric. Scatter plots of all other cases can be
found in supplementary material.

Figure 4: Scatter plots of mTRE vs. similarity for deformations evaluated
during the optimization for one MR-iUS pair. The color of each point shows the
iteration in which the deformation was evaluated. We can see that the Hessian-
based metric has less variability in optimization.

We carry out a statistical test to determine whether the two metrics
demonstrate statistically significant difference in registration accuracy. Our
null hypothesis assumes the two methods result in the same distribution for
mTRE. Our alternative hypothesis states that the Hessian-based similarity
metric results in lower mTRE. Using a paired t-test, we achieve a p-value of
0.0048. Thus, the null hypothesis cannot be accepted, i.e., there is
statistically significant improvement in the accuracy when our proposed
similarity metric is used.

##  4 Discussion and Conclusion

In this paper, we introduce a new similarity metric for multimodal medical
image registration. Our primary contribution has been deriving a closed form
expression for computing the metric. We present geometrical insight into the
mechanics of our proposed similarity metric. We address an efficient way for
transforming the Hessian matrix to prevent recomputing it after applying
deformations. The Hessian-based similarity metric is local, robust to
intensity nonuniformities and computable at arbitrary scales. Moreover, the
similarity metric is very flexible and can be used in a variety of
registration tasks. The metric has shown a significant improvement in
registering MR to ultrasound compared to a previously proposed similarity
metric. However, this improvement comes at the cost of more computation, both
in preprocessing and optimization stages. Since the preprocessing can be
completed offline, its duration should not be a major concern. The increase in
optimization time does not affect the usability of the method for online use
cases.

For comparison, we list the results of some previously proposed methods on the
BITE database. CoCoMI [19] and SeSaMI [20] have reported a mean error of 2.35
mm and 2.29 mm, respectively. Both of these methods use variants of mutual
information as similarity metric along with cubic BSpline as deformation
field. LC2 [6] method which was originally developoed for US-MR registration
based on the physics of ultrasound, has reported a mean error of 2.49 mm using
rigid transformation. In another work, through introducing a modality-
independent binary descriptor called miLBP [9] for deformable registration, an
error of 2.15 mm has been reported. With our Hessian-based similarity metric,
the registration error is 2.37 mm, which is very close to that of other
publications. It must be noted that unlike our method, other methods usually
take advantage of nonlinear transformations, pyramid registration, and
computationally-intensive preprocessing steps for outlier suppression or
selecting regions with structures. We have acheived high accuracies using our
proposed metric only with affine transformations. Therefore, we believe the
Hessian-based similarity metric has great potentials for addressing multimodal
registration tasks.

As future work, we plan to implement our proposed metric in a deformable
registration scheme and test it on a broad range of modality pairs and
registration tasks and compare its performance to that of the state-of-the-art
methods.

## References

  * [1] Arbel, T. et al.: Automatic non-linear MRI-ultrasound registration for the correction of intra-operative brain deformations. Computer Aided Surgery. 9, 4, 123–136 (2004) https://doi.org/10.3109/10929080500079248
  * [2] Daewon Lee et al.: Learning similarity measure for multi-modal 3D image registration. In: 2009 IEEE Conference on Computer Vision and Pattern Recognition. pp. 186–193 IEEE (2009) https://doi.org/10.1109/CVPR.2009.5206840
  * [3] De Nigris, D. et al.: Multi-Modal Image Registration Based on Gradient Orientations of Minimal Uncertainty. IEEE Transactions on Medical Imaging. 31, 12, 2343–2354 (2012) https://doi.org/10.1109/TMI.2012.2218116
  * [4] Drouin, S. et al.: IBIS: an OR ready open-source platform for image-guided neurosurgery. International Journal of Computer Assisted Radiology and Surgery. 12, 3, 363–378 (2017) https://doi.org/10.1007/s11548-016-1478-0
  * [5] Frangi, A.F. et al.: Multiscale vessel enhancement filtering. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). pp. 130–137 (1998) https://doi.org/10.1007/BFb0056195
  * [6] Fuerst, B. et al.: Automatic ultrasound-MRI registration for neurosurgery using the 2D and 3D LC2 Metric. Medical Image Analysis. 18, 8, 1312–1319 (2014) https://doi.org/10.1016/j.media.2014.04.008
  * [7] Haber, E., Modersitzki, J.: Beyond Mutual Information: A Simple and Robust Alternative. In: Bildverarbeitung für die Medizin 2005. pp. 350–354 Springer-Verlag, Berlin/Heidelberg (2005) https://doi.org/10.1007/3-540-26431-0˙72
  * [8] Haskins, G. et al.: Learning deep similarity metric for 3D MR–TRUS image registration. International Journal of Computer Assisted Radiology and Surgery. 14, 3, 417–425 (2019) https://doi.org/10.1007/s11548-018-1875-7
  * [9] Jiang, D. et al.: miLBP: a robust and fast modality-independent 3D LBP for multimodal deformable registration. International Journal of Computer Assisted Radiology and Surgery. 11, 6, 997–1005 (2016) https://doi.org/10.1007/s11548-016-1407-2
  * [10] Karacali, B.: Fully elastic multi-modality image registration using mutual information. In: 2004 2nd IEEE International Symposium on Biomedical Imaging: Macro to Nano (IEEE Cat No. 04EX821). pp. 1455–1458 IEEE (2004) https://doi.org/10.1109/ISBI.2004.1398823
  * [11] Loeckx, D. et al.: Nonrigid Image Registration Using Conditional Mutual Information. IEEE Transactions on Medical Imaging. 29, 1, 19–29 (2010) https://doi.org/10.1109/TMI.2009.2021843
  * [12] Maes, F. et al.: Multimodality image registration by maximization of mutual information. IEEE Transactions on Medical Imaging. 16, 2, 187–198 (1997) https://doi.org/10.1109/42.563664
  * [13] Mercier, L. et al.: Online database of clinical MR and ultrasound images of brain tumors. Medical Physics. 39, 6Part1, 3253–3261 (2012) https://doi.org/10.1118/1.4709600
  * [14] Manera, A.L. et al.: CerebrA, registration and manual label correction of Mindboggle-101 atlas for MNI-ICBM152 template. Scientific Data. 7, 1, 237 (2020) https://doi.org/10.1038/s41597-020-0557-9
  * [15] Mezura-Montes, E. et al.: A comparative study of differential evolution variants for global optimization. In: Proceedings of the 8th annual conference on Genetic and evolutionary computation. pp. 485–492 ACM, New York, NY, USA (2006) https://doi.org/10.1145/1143997.1144086
  * [16] Oliveira, F.P.M., Tavares, J.M.R.S.: Medical image registration: a review. Computer Methods in Biomechanics and Biomedical Engineering. 17, 2, 73–93 (2014) https://doi.org/10.1080/10255842.2012.670855
  * [17] Pluim, J.P.W. et al.: Image Registration by Maximization of Combined Mutual Information and Gradient Information. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) pp. 452–461 (2000) https://doi.org/10.1007/978-3-540-40899-4˙46
  * [18] Pradhan, S., Patra, D.: Enhanced mutual information based medical image registration. IET Image Processing. 10, 5, 418–427 (2016). https://doi.org/10.1049/iet-ipr.2015.0346
  * [19] Rivaz, H. et al.: Nonrigid Registration of Ultrasound and MRI Using Contextual Conditioned Mutual Information. IEEE Transactions on Medical Imaging. 33, 3, 708–725 (2014). https://doi.org/10.1109/TMI.2013.2294630
  * [20] Rivaz, H. et al.: Self-similarity weighted mutual information: A new nonrigid image registration metric. Medical Image Analysis. 18, 2, 343–358 (2014) https://doi.org/10.1016/j.media.2013.12.003
  * [21] Roche, A. et al.: The correlation ratio as a new similarity measure for multimodal image registration. In: Medical Image Computing and Computer-Assisted Intervention—MICCAI’98: First International Conference Cambridge, MA, USA, October.pp.1115–1124 (1998) https://doi.org/10.1007/BFb0056301
  * [22] Simonovsky, M. et al.: A Deep Metric for Multimodal Registration. Presented at the (2016) https://doi.org/10.1007/978-3-319-46726-9˙2
  * [23] Storn, R., Price, K.: Minimizing the real functions of the ICEC’96 contest by differential evolution. In: Proceedings of IEEE International Conference on Evolutionary Computation. pp. 842–844 IEEE (1996) https://doi.org/10.1109/ICEC.1996.542711
  * [24] Viola, P., Wells, W.M.: Alignment by Maximization of Mutual Information. International Journal of Computer Vision. 24, 2, 137–154 (1997) https://doi.org/10.1023/A:1007958904918
  * [25] Wachinger, C., Navab, N.: Entropy and Laplacian images: Structural representations for multi-modal registration. Medical Image Analysis. 16, 1, 1–17 (2012) https://doi.org/10.1016/j.media.2011.03.001
  * [26] Wein, W. et al.: Automatic CT-ultrasound registration for diagnostic imaging and image-guided intervention. Medical Image Analysis. 12, 5, 577–585 (2008) https://doi.org/10.1016/j.media.2008.06.006
  * [27] Xiao, Y. et al.: REtroSpective Evaluation of Cerebral Tumors (RESECT): A clinical database of pre-operative MRI and intra-operative ultrasound in low-grade glioma surgeries. Medical Physics. 44, 7, 3875–3882 (2017) https://doi.org/10.1002/mp.12268


# Capacity of the range of random walks on groups

Rudi Mrazović  Department of Mathematics
University of Zagreb
Zagreb
Croatia<EMAIL_ADDRESS>,  Nikola Sandrić  Department of Mathematics
University of Zagreb
Zagreb
Croatia<EMAIL_ADDRESS>and  Stjepan Šebek  Department of Applied
Mathematics
Faculty of Electrical Engineering and Computing
University of Zagreb
Zagreb
Croatia<EMAIL_ADDRESS>
###### Abstract.

In this paper, we discuss asymptotic behavior of the capacity of the range of
symmetric random walks on finitely generated groups. We show the corresponding
strong law of large numbers and central limit theorem.

###### Key words and phrases:

capacity, central limit theorem, strong law of large numbers, the range of a
random walk

###### 2020 Mathematics Subject Classification:

60G50, 60F05, 05C81

##  1\. Introduction

Let $\mathsf{G}$ be a group with a finite symmetric set of generators $\Gamma$
(i.e. $\Gamma=\Gamma^{-1}$). We define the symmetric random walk
$\\{S_{n}\\}_{n\geq 0}$ on $\mathsf{G}$ with respect to $\Gamma$ by taking a
sequence $\\{X_{n}\\}_{n\in\mathbf{N}}$ of independent random elements,
uniformly distributed on $\Gamma$, and defining $S_{0}=g$ for some fixed
$g\in\mathsf{G}$ and $S_{n+1}=S_{n}X_{n+1}$. We denote the associated
probability by $\mathbf{P}_{g}$. Usually, we will take $g=e$ (identity) and in
this case we will suppress the index and write $\mathbf{P}$. For example,
taking $\mathsf{G}=\mathbf{Z}^{d}$ and its standard set of generators
$\Gamma=\\{e_{1},-e_{1},\dots,e_{d},-e_{d}\\}$ (where
$\\{e_{1},\dots,e_{d}\\}$ is the standard basis of $\mathbf{R}^{d}$) gives the
usual symmetric simple random walk on $\mathbf{Z}^{d}$. We will mention some
other examples later on (we also refer the reader to [29, Section 3.4]).

Although the distribution of the random walk $\\{S_{n}\\}_{n\geq 0}$ depends
on the choice of $\Gamma$, most of its macroscopic properties are independent
of the generating set one decides to work with. For example, in [32] it has
been shown that $\\{S_{n}\\}_{n\geq 0}$ is recurrent if and only if
$\mathsf{G}$ contains a subgroup of finite index isomorphic to trivial group,
$\mathbf{Z}$ or $\mathbf{Z}^{2}$ (as usual, $\\{S_{n}\\}_{n\geq 0}$ is
recurrent if $\sum_{n\geq 0}\mathbf{P}_{e}(S_{n}=e)=\infty$; otherwise it is
transient).

The main aim of this paper is to establish strong law of large numbers (SLLN)
and central limit theorem (CLT) for the capacity of the range process of
$\\{S_{n}\\}_{n\geq 0}$. Recall that the range process
$\\{\mathcal{R}_{n}\\}_{n\geq 0}$ is defined as the sequence of random sets

$\mathcal{R}_{n}=\\{S_{0},\dots,S_{n}\\}.$

For $1\leq m\leq n$ we use the notation
$\mathcal{R}[m,n]=\\{S_{m},\dots,S_{n}\\}$,
$\mathcal{R}[n,\infty)=$$\\{S_{n},S_{n+1},\dots\\}$ and
$\mathcal{R}_{\infty}=\\{S_{0},S_{1},\dots\\}$. The capacity of a set
$A\subseteq\mathsf{G}$ (with respect to the random walk $\\{S_{n}\\}_{n\geq
0}$) is defined as

$\displaystyle{\rm Cap}(A)=\sum_{g\in A}\mathbf{P}_{g}(\tau^{+}_{A}=\infty).$

Here, $\tau^{+}_{A}$ denotes the first return time of $\\{S_{n}\\}_{n\geq 0}$
to the set $A$, i.e.

$\displaystyle\tau^{+}_{A}=\inf\\{n\geq 1:S_{n}\in A\\}.$

We are interested in the asymptotic behavior of the process
$\\{\mathcal{C}_{n}\\}_{n\geq 0}$ defined as

$\mathcal{C}_{n}={\rm Cap}(\mathcal{R}_{n}).$

Before stating our main results, we first remind the reader of the notion of
group growth rate. For $g\in\mathsf{G}$, define its word length $\rho(g)$ as

$\rho(g)=\inf\\{m\geq 0:g=\gamma_{1}\dots\gamma_{m},\text{for
}\gamma_{1},\dots,\gamma_{m}\in\Gamma\\}.$

In other words, $\rho(g)$ is the minimal number of “letters” from “alphabet”
$\Gamma$ needed to express $g$. The growth function $n\mapsto\mathcal{V}(n)$
of $\mathsf{G}$ is defined as (as usual, $|S|$ denotes the size of set $S$)

$\mathcal{V}(n)=|\\{g\in\mathsf{G}:\rho(g)\leq n\\}|.$

Although the growth function depends on the choice of $\Gamma$, its order of
magnitude is independent of that choice. Of special interest are groups of
polynomial growth, i.e. groups for which $\mathcal{V}(n)\asymp n^{d}$ for some
integer growth index $d\geq 0$. Groups for which $\mathcal{V}(n)\gtrsim n^{d}$
for all $d\geq 0$ are said to have superpolynomial growth and they have
infinite growth index ($d=\infty$) by definition.111Here we use the standard
asymptotic notation – see the end of this section. One can show that a
finitely generated group has either polynomial or superpolynomial
growth.222The content of this statement is in discarding the existence of
groups of growth e.g. $n^{5/2}$ or $n^{2}\log n$. Unsurprisingly, the growth
index of $\mathbf{Z}^{d}$ is equal to $d$. The celebrated theorems of Bass and
Gromov show that a finitely generated group is of polynomial growth if and
only if it is virtually nilpotent, see [5, Theorem 2] and [18, Main theorem]
(see also [33, Theorems VI.2.1 and VI.2.2]).

We now state the main results of the paper. Here, and in the rest of the
paper, $d$ will always denote the growth index of the group of polynomial
growth we are working on.

######  Theorem 1.1.

There is $\mu_{d}\geq 0$ such that

(1.1)
$\lim_{n\to\infty}\frac{\mathcal{C}_{n}}{n}=\mu_{d},\qquad\mathbf{P}\text{-a.s.}$

Furthermore, $\mu_{d}=0$ if and only if $d\leq 4$.

######  Theorem 1.2.

Assume that $d\geq 6$. There is $\sigma_{d}>0$ such that

(1.2)
$\frac{\mathcal{C}_{n}-\operatorname*{\mathbf{E}}\left[\mathcal{C}_{n}\right]}{\sigma_{d}\,n^{1/2}}\xrightarrow[n\to\infty]{\rm{(d)}}\mathcal{N}(0,1),$

where $\mathcal{N}(0,1)$ stands for the standard normal random variable and
$\xrightarrow[n\to\infty]{\rm{(d)}}$ denotes the convergence in distribution.

We note that the restriction $d\geq 6$ in Theorem 1.2 is necessary if one is
interested in a general result claiming that in every group with growth index
$d$ there is a nondegenerate Gaussian limit under the scaling $n^{1/2}$.
Indeed, for the symmetric simple random walk on $\mathbf{Z}^{5}$, [30, Theorem
B] shows that one requires $(n\log n)^{1/2}$ scaling in (1.2). Additionally,
for the symmetric simple random walk on $\mathbf{Z}^{3}$ or $\mathbf{Z}^{4}$,
[8, Theorem 1.2] and [3, Theorem 1.1] proved that the limit in (1.2) is non-
Gaussian (case $d=4$ also requires $n/\log^{2}n$ scaling). Finally, from [33,
Theorems VI.2.1, VI.2.2, VI.3.3 and VI.5.1] one easily concludes that $d\leq
2$ if and only if the underlying random walk is recurrent. It is easy to see
that in this case we have $\mathcal{C}_{n}\equiv 0$.

### Literature overview and related results

The study on the range process $\\{\mathcal{R}_{n}\\}_{n\geq 0}$ of
$\mathbf{Z}^{d}$-valued random walks has a long history.

A pioneering work is due to Dvoretzky and Erdős [16] where they obtained a
SLLN for $\\{|\mathcal{R}_{n}|\\}_{n\geq 0}$ in the context of the symmetric
simple random walk in dimension $d\geq 2$. Their result was later extended by
Spitzer [31] for an arbitrary random walk in dimension $d\geq 1$. CLT for
$\\{|\mathcal{R}_{n}|\\}_{n\geq 0}$ was obtained by Jain and Orey [20] for so-
called strongly transient random walks. Jain and Pruit [22] extended this
result to all random walks in dimension $d\geq 3$, while Le Gall [28]
discussed this problem in $\mathbf{Z}^{2}$. Jain and Pruitt [23] also
established a law of the iterated logarithm for
$\\{|\mathcal{R}_{n}|\\}_{n\geq 0}$ in the case when the underlying random
walk is either strongly transient or in dimension $d\geq 4.$ Bass and Kumagai
[6] later extended this result to $\mathbf{Z}^{2}$ and $\mathbf{Z}^{3}$.

The first results on the asymptotic behavior of the capacity process
$\\{\mathcal{C}_{n}\\}_{n\geq 0}$ are due to Jain and Orey [20] who obtained a
version of the SLLN for any transient random walk. Very recently Asselah,
Schapira and Sousi [2] proved a CLT for $\\{\mathcal{C}_{n}\\}_{n\geq 0}$ for
the symmetric simple random walk in dimension $d\geq 6$. Schapira [30]
obtained an analogous result in $\mathbf{Z}^{5}$, while versions of a SLLN and
CLT in $\mathbf{Z}^{4}$ and $\mathbf{Z}^{3}$ were proved by Asselah, Schapira
and Sousi in [3] and Chang in [8], respectively.

On the other hand, to the best of our knowledge, there are only a few works on
asymptotic behavior of the range process of random walks on groups other than
$\mathbf{Z}^{d}$. One of the first results in this direction is due to Chen,
Yan and Zhou [9] who obtained a SLLN and CLT for
$\\{|\mathcal{R}_{n}|\\}_{n\geq 0}$ of the symmetric simple random walk on the
$N$-ary tree with $N\geq 2$ (i.e. the free product $\mathbf{Z}_{2}^{\ast N}$
with the standard $N$ generators). Recently, Benjamini, Izkovsky and Kesten
[7] studied a variant of the SLLN for $\\{|\mathcal{R}_{n}|\\}_{n\geq 0}$
conditioned on the event $\\{S_{n}=S_{0}\\}$ (the so-called random walk
bridge) associated to a symmetric random walk on a finitely generated group.
They showed that the conditional and corresponding unconditional SLLN limits
coincide. Finally, entropy properties of the range process of random walks on
finitely and infinitely generated groups were studied by Chen, Xie and Zhao
[10], Erschler [17] and Windsch [34].

As we have already commented, in this paper we focus on the asymptotic
behavior of the capacity process $\\{\mathcal{C}_{n}\\}_{n\geq 0}$ associated
to a symmetric random walk on a finitely generated group. As the main results
we obtain the SLLN and CLT stated in Theorems 1.1 and 1.2, and show that these
types of behaviours, as in the symmetric simple random walk on
$\mathbf{Z}^{d}$, depend on the growth index $d$ only.

### Notation

Clearly, $\\{S_{n}\\}_{n\geq 0}$ satisfies the (strong) Markov property (with
respect to the corresponding natural filtration) with transition probabilities
given by

$p_{n}(g_{1},g_{2})=\mathbf{P}_{g_{1}}(S_{n}=g_{2}).$

Note that $p_{n}$ is left-translation-invariant (i.e.,
$p_{n}(hg_{1},hg_{2})=p_{n}(g_{1},g_{2})$ for all $h\in\mathsf{G}$) so we may
consider $p_{n}$s as one-variable functions, i.e.
$p_{n}(g_{1}^{-1}g_{2})=p_{n}(e,g_{1}^{-1}g_{2})=p_{n}(g_{1},g_{2})$.

We denote by

$\displaystyle\mathcal{G}(g_{1},g_{2})=\sum_{n\geq 0}p_{n}(g_{1},g_{2})$

the Green function of $\\{S_{n}\\}_{n\geq 0}$. Due to the aforementioned left-
translation-invariance, we sometimes write $\mathcal{G}(g_{1}^{-1}g_{2})$
instead of $\mathcal{G}(g_{1},g_{2})$.

We will use the standard asymptotic notation. For
$f,g:\mathbf{N}\to[0,\infty)$ we write $f(n)\lesssim g(n)$ if and only if
there is a constant $c>0$ such that $f(n)\leq c\,g(n)$ for all
$n\in\mathbf{N}$. We would like to stress that, unless otherwise specified,
implied constant $c$ will depend only on $\mathsf{G}$ (most of the time only
on its growth index $d$ and the set of generators $\Gamma$). In rare
circumstances where it depends on some other parameters, we will indicate them
by adding a subscript after $\lesssim$. We will write $f(n)\asymp g(n)$ if and
only if $f(n)\lesssim g(n)$ and $g(n)\lesssim f(n)$. Finally, we use the
standard $\mathsf{o}$ notation: for $f,g:\mathbf{N}\to[0,\infty)$ we write
$f(n)=\mathsf{o}(g(n))$ if and only if $\lim_{n\to\infty}f(n)/g(n)=0$.

### Organisation of the paper

The rest of the paper is organised as follows. In Section 2, we prove Theorem
1.1. We first show that the limit in (1.1) exists and is finite, and then we
show that it vanishes if and only if $d\leq 4$. In Section 3, we present minor
modifications needed in the proof of [2, Theorem 1.1] to prove Theorem 1.2.
Roughly, we first determine the constant $\sigma_{d}$ in (1.2), and then by
employing the Lindeberg-Feller theorem we prove Theorem 1.2. At the end we
also briefly discuss the functional version of the CLT in (1.2).

##  2\. On the SLLN for $\\{\mathcal{C}_{n}\\}_{n\geq 0}$

In this section, we prove Theorem 1.1. We start with the proof of (1.1).

######  Proposition 2.1.

There is $\mu_{d}\geq 0$ such that

$\lim_{n\to\infty}\frac{\mathcal{C}_{n}}{n}=\mu_{d},\qquad\mathbf{P}\text{-a.s.
and in }\mathrm{L}^{1}.$

###### Proof.

For $0\leq m\leq n$, let

$\mathcal{F}_{m,n}=\operatorname{Cap}(\mathcal{R}[m,n]).$

Clearly, the family $\\{\mathcal{F}_{m,n}:0\leq m\leq n\\}$ forms a
subadditive process in the sense of [25, Chapter 1]. Then, according to
Kingman’s subadditive ergodic theorem (see [25, Chapter 1, Theorem 5.3]) it
holds that $\\{\mathcal{C}_{n}/n\\}_{n\geq 1}$ converges a.s. and in
$\mathrm{L}^{1}$ to a nonnegative integrable random variable. Further, for
$0\leq m\leq n$, using left-translation-invariance and subadditivity of the
capacity (see [31, Proposition 25.11]) we obtain

$\displaystyle\operatorname{Cap}(\\{X_{n}^{-1}\cdots X_{m+1}^{-1},\dots,e\\})$
$\displaystyle=\operatorname{Cap}(X_{n}^{-1}\cdots
X_{1}^{-1}\mathcal{R}[m,n])=\operatorname{Cap}(\mathcal{R}[m,n])$
$\displaystyle\leq\mathcal{C}_{n}\leq\mathcal{C}_{m}+\operatorname{Cap}(\mathcal{R}[m,n])$
$\displaystyle=\mathcal{C}_{m}+\operatorname{Cap}(\\{X_{n}^{-1}\cdots
X_{m+1}^{-1},\dots,e\\}).$

Thus,

$\lim_{n\to\infty}\frac{\mathcal{C}_{n}}{n}=\lim_{n\to\infty}\frac{\operatorname{Cap}(\\{X_{n}^{-1}\cdots
X_{m+1}^{-1},\dots,e\\})}{n},$

which shows that the limit is measurable with respect to the tail
$\sigma$-algebra $\bigcap_{m=1}^{\infty}\sigma(X_{m},X_{m+1},\dots)$.
According to Kolmogorov’s $0$-$1$ law, this $\sigma$-algebra is trivial. The
assertion now follows from [24, Chapter 2, Lemma 2.9]. ∎

As a direct consequence of Proposition 2.1 it follows that

(2.1)
$\lim_{n\to\infty}\frac{\operatorname*{\mathbf{E}}[\mathcal{C}_{n}]}{n}=\mu_{d}.$

We now turn to showing that the limit $\mu_{d}$ in (1.1) vanishes if and only
if $d\leq 4$. As we have already commented, when $d\leq 2$ it necessarily
holds that $\mathcal{C}_{n}\equiv 0$. We first show several auxiliary results.

######  Proposition 2.2.

If $d=\infty$, then

$\sup_{g\in\mathsf{G}}p_{n}(g)\lesssim_{q}n^{-q}$

for all $q\geq 0$. If $d<\infty$, then

$\sup_{g\in\mathsf{G}}p_{n}(g)\lesssim n^{-d/2}\qquad\text{and}\qquad
p_{2n}(e)\gtrsim n^{-d/2}.$

###### Proof.

The assertions are a direct consequence of [33, Theorems VI.2.1, VI.2.2,
VI.3.3 and VI.5.1]. ∎

Further, we conclude the following.

######  Proposition 2.3.

We have

$\operatorname*{\mathbf{E}}\bigg{[}\sum_{k,\ell=0}^{n}\mathcal{G}(S_{k},S_{\ell})\bigg{]}\lesssim\begin{cases}n&d\geq
5,\\\ n\log n&d=4,\\\ n^{3/2}&d=3.\end{cases}$

###### Proof.

We have that

$\displaystyle\operatorname*{\mathbf{E}}\bigg{[}\sum_{k,\ell=0}^{n}\mathcal{G}(S_{k},S_{\ell})\bigg{]}$
$\displaystyle=\operatorname*{\mathbf{E}}\bigg{[}\sum_{k=0}^{n}\mathcal{G}(e)+\sum_{k=0}^{n}\sum_{\begin{subarray}{c}\ell=0\\\
l\neq k\end{subarray}}^{n}\mathcal{G}(S_{|k-\ell|})\bigg{]}$
$\displaystyle=\operatorname*{\mathbf{E}}\bigg{[}(n+1)\mathcal{G}(e)+2\sum_{k=0}^{n}\sum_{\ell=1}^{n-k}\mathcal{G}(S_{\ell})\bigg{]}$
$\displaystyle=(n+1)\mathcal{G}(e)+2\sum_{k=0}^{n}\sum_{\ell=1}^{n-k}\sum_{g\in\mathsf{G}}\mathcal{G}(g)\mathbf{P}(S_{\ell}=g)$
$\displaystyle=(n+1)\mathcal{G}(e)+2\sum_{k=0}^{n}\sum_{\ell=1}^{n-k}\sum_{g\in\mathsf{G}}\sum_{m=0}^{\infty}p_{m}(e,g)p_{\ell}(g,e)$
$\displaystyle=(n+1)\mathcal{G}(e)+2\sum_{k=0}^{n}\sum_{\ell=1}^{n-k}\sum_{m=\ell}^{\infty}p_{m}(e).$

The statement of the proposition now follows using the upper bounds from
Proposition 2.2 and elementary summations. ∎

As a consequence of Proposition 2.3 we conclude the following.

######  Proposition 2.4.

We have

$\operatorname*{\mathbf{E}}\left[\mathcal{C}_{n}\right]\gtrsim\begin{cases}n&d\geq
5,\\\ n/\log n&d=4,\\\ n^{1/2}&d=3.\end{cases}$

###### Proof.

For fixed $n\geq 1$ we consider the following (random) probability measure
defined on $\mathsf{G}$:

(2.2) $\nu_{n}(g)=\frac{1}{n}\sum_{k=1}^{n}\delta_{S_{k}}(g).$

Clearly, $\mathrm{supp}\,\nu_{n}=\mathcal{R}[1,n]$. According to (a
straightforward modification of) [21, Lemma 2.3], the capacity of a set
$A\subseteq\mathsf{G}$ has the following representation

$\mathrm{Cap}(A)=\frac{1}{\inf_{\nu}\sum_{g_{1},g_{2}\in
A}\mathcal{G}(g_{1},g_{2})\nu(g_{1})\nu(g_{2})},$

where the infimum is taken over all probability measures on $\mathsf{G}$ with
$\mathrm{supp}\,\nu\subseteq A.$ Clearly,

$\operatorname*{\mathbf{E}}\left[\sum_{g_{1},g_{2}\in\mathcal{R}_{n}}\mathcal{G}(g_{1},g_{2})\nu_{n}(g_{1})\nu_{n}(g_{2})\right]=\frac{1}{n^{2}}\operatorname*{\mathbf{E}}\bigg{[}\sum_{k,\ell=1}^{n}\mathcal{G}(S_{k},S_{\ell})\bigg{]}.$

Recall that $\mathcal{C}_{n}=\mathrm{Cap}(\mathcal{R}_{n})$. The assertion now
follows from Jensen’s inequality and Proposition 2.3. ∎

Notice that the previous proposition already proves the $d\geq 5$ case of the
second assertion of Theorem 1.1. To cover the cases $d=3$ and $d=4$, we need
to prove that in those settings we have
$\operatorname*{\mathbf{E}}\left[\mathcal{C}_{n}\right]=\mathsf{o}(n)$.

For $r>0$, let
$\mathscr{B}_{\mathsf{G}}(r)=\\{g\in\mathsf{G}\colon\rho(g)<r\\}$ and
$\overline{\mathscr{B}}_{\mathsf{G}}(r)=\\{g\in\mathsf{G}\colon\rho(g)\leq
r\\}$ denote the open and closed ball around $e$ of radius $r$, respectively.
Further, let $\tau_{r}=\inf\\{n\geq
0:S_{n}\in\mathscr{B}^{c}_{\mathsf{G}}(r)\\}$

######  Proposition 2.5.

Suppose $0<d<\infty$. There are $c,C>0$ such that

  1. (i)

$\displaystyle\mathbf{P}\bigl{(}\tau_{r}<n\bigr{)}\lesssim e^{-cr^{2}/n}$ for
all $r\geq 1$;

  2. (ii)

$\displaystyle p_{n}(g)\gtrsim
n^{-d/2}e^{-C\rho(g)^{2}/n}\mathbf{1}_{\mathscr{B}_{\mathsf{G}}(cn)}(g)$ for
all $g\in\mathsf{G}$;

  3. (iii)

$\displaystyle p_{n}(g)\lesssim n^{-d/2}e^{-c\rho(g)^{2}/n}$ for all
$g\in\mathsf{G}$.

###### Proof.

First assertion follows from [33, Theorem VI.5.1], [19, Theorem 2.1] and [4,
Proposition 4.33 and Theorem 5.23], while the second and third follow from
[19, Theorems 2.1 and 5.1]. ∎

We now deal with the case $d=3$.

######  Proposition 2.6.

If $d=3$, then

$\displaystyle\operatorname*{\mathbf{E}}\left[\mathcal{C}_{n}\right]\asymp
n^{1/2}.$

###### Proof.

According to Proposition 2.4 it suffices to show that
$\operatorname*{\mathbf{E}}\left[\mathcal{C}_{n}\right]\lesssim n^{1/2}$. We
follow [2] and [26], where the case of the symmetric simple random walk on
$\mathbf{Z}^{d}$ has been considered. However, we note that in [2] the case
when $d=3$ was covered by invoking the fact that for the symmetric simple
random walk on $\mathbf{Z}^{d}$, the process $\\{\rho(S_{n})\\}_{n\geq 0}$ is
a submartingale. Unfortunately, this is not true in general (see Remark 2.7).
For this reason, our proof is somewhat more complicated and closer to the
approach [2] used for $d=4$ case.

Let $\\{\widetilde{S}_{n}\\}_{n\geq 0}$ be an independent copy of
$\\{S_{n}\\}_{n\geq 0}$, with distribution $\widetilde{\mathbf{P}}$. Due to
[20, Section 2] it holds that (with the convention
$\mathcal{R}_{-1}=\emptyset$)

$\mathcal{C}_{n}=\sum_{k=0}^{n}\widetilde{}\mathbf{P}_{S_{k}}\bigr{(}(S_{k}\,\widetilde{\mathcal{R}}[1,\infty))\cap\mathcal{R}_{n}=\emptyset\bigl{)}\mathbf{1}_{\\{S_{k}\notin\mathcal{R}_{k-1}\\}},$

where $\\{\widetilde{\mathcal{R}}_{n}\\}_{n\geq 0}$ stands for the range
process of $\\{\widetilde{S}_{n}\\}_{n\geq 0}$. Next, for fixed $0\leq k\leq
n$ we consider three independent random walks $\\{S^{1}_{i}\\}_{0\leq i\leq
k}$, $\\{S^{2}_{i}\\}_{0\leq i\leq n-k}$ and $\\{S^{3}_{i}\\}_{i\geq
0}=\\{\widetilde{S}_{i}\\}_{i\geq 0}$, where $S_{i}^{1}=S_{k}^{-1}S_{k-i}$ and
$S_{i}^{2}=S_{k}^{-1}S_{k+i}$. We now have

$\mathcal{C}_{n}=\sum_{k=0}^{n}\widetilde{}\mathbf{P}\bigr{(}\mathcal{R}^{3}[1,\infty)\cap(\mathcal{R}^{1}_{k}\cup\mathcal{R}^{2}_{n-k})=\emptyset\bigl{)}\mathbf{1}_{\\{e\notin\mathcal{R}^{1}[1,k]\\}},$

where $\\{\mathcal{R}^{1}_{i}\\}_{0\leq i\leq k}$,
$\\{\mathcal{R}^{2}_{i}\\}_{0\leq i\leq n-k}$ and
$\\{\mathcal{R}^{3}_{n}\\}_{n\geq 0}$ stand for the range processes of
$\\{S^{1}_{i}\\}_{0\leq i\leq k}$, $\\{S^{2}_{i}\\}_{0\leq i\leq n-k}$ and
$\\{S^{3}_{i}\\}_{i\geq 0}$, respectively. By taking expectations, we conclude

$\displaystyle\operatorname*{\mathbf{E}}\left[\mathcal{C}_{n}\right]$
$\displaystyle=\sum_{k=0}^{n}\mathbf{P}\bigr{(}e\notin\mathcal{R}^{1}[1,k],\,\mathcal{R}^{3}[1,\infty)\cap(\mathcal{R}^{1}_{k}\cup\mathcal{R}^{2}_{n-k})=\emptyset\bigl{)}$
$\displaystyle\leq
2\sum_{k=0}^{n/2}\mathbf{P}\bigr{(}\mathcal{R}^{3}[1,\infty)\cap(\mathcal{R}^{1}_{k}\cup\mathcal{R}^{2}_{n-k})=\emptyset\bigl{)}$
$\displaystyle\leq
2\sum_{k=0}^{n/2}\mathbf{P}\bigr{(}\mathcal{R}^{3}[1,k]\cap(\mathcal{R}^{1}_{k}\cup\mathcal{R}^{2}_{k})=\emptyset\bigl{)}.$

Hence, the desired bound will follow if we show that

(2.3)
$\mathbf{P}\bigr{(}\mathcal{R}^{3}[1,k]\cap(\mathcal{R}^{1}_{k}\cup\mathcal{R}^{2}_{k})=\emptyset\bigl{)}\lesssim
k^{-1/2}.$

To prove this, we follow the proof for the upper bound in [26, Theorem 3.5.1]
(in the case of the symmetric simple random walk on $\mathbf{Z}^{3}$), given
in [26, Section 3.6]. Observe that the probability on the left-hand side in
(2.3) corresponds to the function $F(k)$ in [26, Theorem 3.5.1]. A
straightforward inspection shows that all the arguments in the proofs of [26,
Theorem 6.1 and Proposition 3.6.3] and the first half (up to relation (3.26))
of the proof of [26, Proposition 3.6.2] hold also for finitely generated
groups with symmetric set of generators and $d=3$. Hence, the only part that
has to be clarified is the relation (3.26), i.e. that

(2.4) $\operatorname*{\mathbf{E}}[Z_{n}^{-1}]\lesssim n^{1/2}$

where $Z_{n}$ is defined in the following way. Let $\lambda\in[\frac{1}{2},1)$
and $n=\lfloor(1-\lambda)^{-1}\rfloor$, and let $\Lambda$ be a geometric
random variable with parameter $1-\lambda$, independent of the random walk
$\\{S_{n}\\}_{n\geq 0}$. Set

$\mathcal{G}_{(\lambda)}(g)=\operatorname*{\mathbf{E}}\left[\sum_{k=0}^{\Lambda}\mathbf{1}_{\\{S_{k}=g\\}}\right]\qquad\text{and}\qquad
Z_{n}=\inf_{0\leq i\leq j\leq n}\mathcal{G}_{(\lambda)}(S_{j}^{-1}S_{i}).$

We now prove (2.4). Let $c,C>0$ be as in the second part of Proposition 2.5,
and notice that for $g\in\mathsf{G}$ such that $\rho(g)>32/c^{2}$ we have

$\sum_{k=c\rho(g)^{2}/32}^{c\rho(g)^{2}/16}p_{k}(g)\gtrsim\sum_{k=c\rho(g)^{2}/32}^{c\rho(g)^{2}/16}k^{-3/2}e^{-C\rho(g)^{2}/k}\gtrsim\rho(g)^{-1}.$

This provides us, for such $g$, the following lower bound for
$\mathcal{G}_{(\lambda)}(g)$:

$\mathcal{G}_{(\lambda)}(g)\geq\mathbf{P}(\Lambda\geq
c\rho(g)^{2}/16)\sum_{k=0}^{c\rho(g)^{2}/16}p_{k}(g)\gtrsim
e^{-c\rho(g)^{2}(1-\lambda)/8}\rho(g)^{-1},$

where we used the elementary inequality $\lambda\geq e^{-2(1-\lambda)}$
(recall that $\lambda\in[\frac{1}{2},1]$). Clearly, since the set
$\\{g\in\mathsf{G}:0<\rho(g)\leq 32/c^{2}\\}$ is finite and
$\mathcal{G}_{(\lambda)}(g)\geq\mathcal{G}_{(\frac{1}{2})}(g)>0$, we conclude
that

$\mathcal{G}_{(\lambda)}(g)\gtrsim\rho(g)^{-1}e^{-c\rho(g)^{2}(1-\lambda)/8}$

for all $g\in\mathsf{G}\setminus\\{e\\}$ and $\lambda\in[\frac{1}{2},1]$.

Now, as in [26, Proposition 3.6.2] let

$R_{n}=\sup_{0\leq i\leq j\leq n}\rho(S_{j}^{-1}S_{i})$

and note that

$Z_{n}^{-1}\lesssim R_{n}e^{cR_{n}^{2}/(8n)}=f(R_{n}),$

where $f(u)=ue^{cu^{2}/(8n)}$. Since $\mathbf{P}(R_{n}\geq
r)\leq\mathbf{P}(\sup_{0\leq i\leq n}\rho(S_{i})\geq r/2)$ and $R_{n}\leq n$,
we have that

$\displaystyle\operatorname*{\mathbf{E}}[Z_{n}^{-1}]$
$\displaystyle\lesssim\int_{0}^{n}f^{\prime}(r)\mathbf{P}(R_{n}\geq r)\,dr$
$\displaystyle\lesssim\sum_{k=1}^{n}e^{ck^{2}/(8n)}\left(1+\frac{ck^{2}}{4n}\right)\mathbf{P}\bigl{(}\sup_{0\leq
i\leq n}\rho(S_{i})\geq k/2\bigr{)}.$

Further, observe that

$\mathbf{P}\bigl{(}\sup_{0\leq i\leq n}\rho(S_{i})\geq
k/2\bigr{)}=\mathbf{P}\bigl{(}\tau_{k/2}<n+1\bigr{)}.$

Thus, first part of Proposition 2.5 implies that

$\displaystyle\operatorname*{\mathbf{E}}[Z_{n}^{-1}]$
$\displaystyle\lesssim\sum_{k=1}^{n}e^{ck^{2}/(8n)}\left(1+\frac{ck^{2}}{4n}\right)e^{-ck^{2}/(4n)}$
$\displaystyle=\sum_{k=1}^{n}e^{-ck^{2}/(8n)}\left(1+\frac{ck^{2}}{4n}\right)\lesssim
n^{1/2},$

which concludes the proof. ∎

######  Remark 2.7.

As we mentioned in the previous proof, $\\{\rho(S_{n})\\}_{n\geq 0}$ is a
submartingale in the case of the symmetric simple random walk on
$\mathbf{Z}^{d}$. This is not necessarily the case in general. For example,
one might even have that $\rho(g\gamma)\leq\rho(g)$ for some $g\in\mathsf{G}$
and all $\gamma\in\Gamma$, with strict inequality occurring for at least one
$\gamma$. This rules out the possibility of $\\{\rho(S_{n})\\}_{n\geq 0}$
being a submartingale since the submartingale inequality
$\operatorname*{\mathbf{E}}[\rho(S_{n+1})|X_{1},\dots,X_{n}]\geq\rho(S_{n})$
would obviously not be satisfied on the event $\\{S_{n}=g\\}$. The simplest
example we are aware of that demonstrates this phenomenon is provided by the
group $\mathbf{Z}$ with the set of generators $\\{\pm 2,\pm 3\\}$ and $g=1$.

We now consider the case $d=4$. For $k\in\mathbf{N}$, let

$V_{k}=(\mathscr{B}_{\mathsf{G}}(2^{k})\setminus\mathscr{B}_{\mathsf{G}}(2^{k-1}))\cap\mathcal{R}_{\tau_{2^{k+1}}}.$

######  Proposition 2.8.

Let $\\{\widetilde{S}_{n}\\}_{n\geq 0}$ be an independent copy of
$\\{S_{n}\\}_{n\geq 0}$, and let
$E_{k}=\\{V_{k}\cap\widetilde{V}_{k}\neq\emptyset\\}$, where
$\widetilde{V}_{k}$ is defined as $V_{k}$ but in terms of
$\\{\widetilde{S}_{n}\\}_{n\geq 0}$. There is $c>0$ such that for all
$\ell\in\mathbf{N}$ it holds that

(2.5)
$\sup_{(g_{1},g_{2})\in\overline{\mathscr{B}}_{\mathsf{G}}(2^{4\ell-3})\times\overline{\mathscr{B}}_{\mathsf{G}}(2^{4\ell-3})}\mathbf{P}_{(g_{1},g_{2})}(E_{4\ell})\leq
c\,\inf_{(g_{1},g_{2})\in\overline{\mathscr{B}}_{\mathsf{G}}(2^{4\ell-3})\times\overline{\mathscr{B}}_{\mathsf{G}}(2^{4\ell-3})}\mathbf{P}_{(g_{1},g_{2})}(E_{4\ell}).$

###### Proof.

Notice that we may assume that $\ell$ is large enough when needed. The idea is
to use the elliptic Harnack inequality given in [4, Theorem 7.18], and for
that goal we first need to set the stage by making a couple of group theoretic
arguments.

Let $\mathsf{H}=\langle\Gamma\times\Gamma\rangle$. Note that $\mathsf{H}$ can
be a proper subgroup of $\mathsf{G}\times\mathsf{G}$. For example, if
$\mathsf{G}=\mathbf{Z}$ and $\Gamma=\\{-1,1\\}$, then
$\mathsf{H}=\langle\Gamma\times\Gamma\rangle$ consists of elements of
$\mathbf{Z}^{2}$ with coordinates of the same parity. This is actually typical
– it is easy to prove that either $\mathsf{H}=\mathsf{G}\times\mathsf{G}$ or
$|\mathsf{G}\times\mathsf{G}:\mathsf{H}|=2$, i.e. in any case
$\mathsf{G}\times\mathsf{G}$ can be covered by at most two translates of
$\mathsf{H}$. Indeed, fix $\gamma\in\Gamma$ and take
$(g,h)\in\mathsf{G}\times\mathsf{G}$. Let

$g=g_{1}\dots g_{r},\quad\text{and}\quad\gamma^{-r}h=h_{1}\dots h_{s},\qquad
g_{1},\dots,g_{r},h_{1},\dots,h_{s}\in\Gamma.$

Consider the following product of $r+s$ elements from $\Gamma\times\Gamma$,

$(g_{1},\gamma)\dots(g_{r},\gamma)(\gamma,h_{1})(\gamma^{-1},h_{2})(\gamma,h_{3})\dots(\gamma^{(-1)^{s+1}},h_{s})\in\mathsf{H}.$

This product, depending on the parity of $s$, will be either $(g,h)$ or
$(g\gamma,h)$. Thus,
$\mathsf{G}\times\mathsf{G}=\mathsf{H}\cup(\mathsf{H}\cdot(\gamma^{-1},e))$.

The fact that $|\mathsf{G}\times\mathsf{G}:\mathsf{H}|<\infty$ implies that
$d_{\mathsf{H}}=d_{\mathsf{G}\times\mathsf{G}}$ (see [14, Proposition 8.78]),
where $d_{\mathsf{H}}$ and $d_{\mathsf{G}\times\mathsf{G}}$ denote the growth
indices of $\mathsf{H}$ and $\mathsf{G}\times\mathsf{G}$, respectively. We now
show that $d_{\mathsf{G}\times\mathsf{G}}=2d$, i.e. $d_{\mathsf{H}}=2d.$
Namely, as we have already commented, the growth index does not depend on the
choice of the set of generators. Hence, we can consider the set
$\\{(\gamma,e),(e,\gamma)\colon\gamma\in\Gamma\\}$ of $2|\Gamma|$ generators.
It is straightforward to check that
$\rho_{\mathsf{G}\times\mathsf{G}}(g,h)=\rho_{\mathsf{G}}(g)+\rho_{\mathsf{G}}(h)$.
This in particular implies that for every $r>0$,
$\mathscr{B}_{\mathsf{G}}(r)\times\mathscr{B}_{\mathsf{G}}(r)\subseteq\mathscr{B}_{\mathsf{G}\times\mathsf{G}}(2r)$
and
$\mathscr{B}_{\mathsf{G}\times\mathsf{G}}(r)\subseteq\mathscr{B}_{\mathsf{G}}(r)\times\mathscr{B}_{\mathsf{G}}(r)$,
which proves the assertion.

We next analyse the function $\rho_{\mathsf{H}}$, the word metric in
$\mathsf{H}$. We show that there is $m\in\mathbf{N}$ such that

(2.6)
$\max(\rho(g),\rho(h))+m\geq\rho_{\mathsf{H}}((g,h))\geq\max(\rho(g),\rho(h))$

for all $(g,h)\in\mathsf{H}$. Since the second inequality is trivial, we
concentrate on the first. Without loss of generality assume
$\rho(g)\leq\rho(h)$, and let the corresponding shortest words be

$g=g_{1}\dots g_{s}\quad\text{and}\quad h=h_{1}\dots h_{r},\qquad
g_{1},\dots,g_{s},h_{1},\dots,h_{r}\in\Gamma.$

Let $\gamma\in\Gamma$ be arbitrary, and consider the product

$(g_{1},h_{1})(g_{2},h_{2})\dots(g_{s},h_{s})(\gamma,h_{s+1})(\gamma^{-1},h_{s+2})(\gamma,h_{s+3})\dots(\gamma^{(-1)^{r-s+1}},h_{r})\in\mathsf{H}.$

This product is either $(g,h)$ or $(g\gamma,h)$. In the latter case, write
$(\gamma^{-1},e)$ as a product of some elements (say, $m$ of them) from
$\Gamma\times\Gamma$ (this is possible since
$(\gamma^{-1},e)=(g\gamma,h)^{-1}(g,h)\in\mathsf{H}$) and concatenate it with
the above product. This gives a representation of $(g,h)$ as a product of at
most $r+m$ elements from $\Gamma\times\Gamma$, hence (2.6).

Fix some $\ell\in\mathbf{N}$, and define
$f_{\ell}:\mathscr{B}_{\mathsf{G}}(2^{4\ell-1})\times\mathscr{B}_{\mathsf{G}}(2^{4\ell-1})\to[0,1]$
by

$f_{\ell}(g_{1},g_{2})=\mathbf{P}_{(g_{1},g_{2})}(E_{4\ell}).$

From (2.6) we have that
$\overline{\mathscr{B}}_{\mathsf{G}}(2^{4\ell-3})\times\overline{\mathscr{B}}_{\mathsf{G}}(2^{4\ell-3})\subseteq\mathscr{B}_{\mathsf{H}}(2^{4\ell-3}+m+1)$.
We aim to apply the elliptic Harnack inequality for elements from this ball,
and for this we need $f_{\ell}$ to be harmonic on
$\mathscr{B}_{\mathsf{H}}(2^{4\ell-2}+2m+2)$. However, (2.6) implies also that
$\mathscr{B}_{\mathsf{H}}(2^{4\ell-2}+2m+2)\subseteq\mathscr{B}_{\mathsf{G}}(2^{4\ell-2}+2m+2)\times\mathscr{B}_{\mathsf{G}}(2^{4\ell-2}+2m+2)$.
For $\ell$ large enough the latter set is contained in
$\mathscr{B}_{\mathsf{G}}(2^{4\ell-1})\times\mathscr{B}_{\mathsf{G}}(2^{4\ell-1})$,
and the Markov property easily shows that $f_{\ell}$ is harmonic on this set.

Finally, it is clear that $\\{(S_{n},\widetilde{S}_{n})\\}_{n\geq 0}$ is a
random walk on $\mathsf{H}$ with transition probabilities

$p^{\mathsf{H}}_{n}((g_{1},g_{2}),(h_{1},h_{2}))=p_{n}(g_{1},h_{1})p_{n}(g_{2},h_{2}).$

Using the fact that $d_{\mathsf{H}}=2d=8$, and employing [4, Corollary 7.17
and Theorem 7.18] together with Proposition 2.5 for function $f_{\ell}$ gives
the inequality (2.5). ∎

We now conclude the following.

######  Proposition 2.9.

If $d=4$, then

$\displaystyle\operatorname*{\mathbf{E}}\left[\mathcal{C}_{n}\right]=\mathsf{o}(n).$

###### Proof.

As in Proposition 2.6, we have that

$\displaystyle\operatorname*{\mathbf{E}}\left[\mathcal{C}_{n}\right]$
$\displaystyle=\sum_{k=0}^{n}\mathbf{P}\bigr{(}e\notin\mathcal{R}^{1}[1,k],\,\mathcal{R}^{3}[1,\infty)\cap(\mathcal{R}^{1}_{k}\cup\mathcal{R}^{2}_{n-k})=\emptyset\bigl{)}$
$\displaystyle\leq\sum_{k=0}^{n}\mathbf{P}\bigr{(}\mathcal{R}^{3}[1,\infty)\cap\mathcal{R}^{1}_{k}=\emptyset\bigl{)}.$

Since

$\lim_{n\to\infty}\mathbf{P}\bigr{(}\mathcal{R}^{3}[1,\infty)\cap\mathcal{R}^{1}_{n}=\emptyset\bigl{)}=\mathbf{P}\bigr{(}\mathcal{R}^{3}[1,\infty)\cap\mathcal{R}^{1}_{\infty}=\emptyset\bigl{)},$

the claim would easily follow if we prove that the probability on the right
hand side is equal to $0$. We will show a somewhat stronger claim – that
$\mathcal{R}^{1}_{\infty}$ is almost surely a recurrent set for
$\\{S_{n}^{3}\\}_{n\geq 0}$, i.e. that

(2.7) $\mathbf{P}(S^{3}_{n}\in\mathcal{R}^{1}_{\infty}\ \text{for infinitely
many }n)=1.$

For $k\in\mathbf{N}$, let

$\displaystyle\tau_{2^{k}}^{1}$ $\displaystyle=\inf\\{n\geq
0:S^{1}_{n}\in\mathscr{B}^{c}_{\mathsf{G}}(2^{k})\\},$
$\displaystyle\tau_{2^{k}}^{2}$ $\displaystyle=\inf\\{n\geq
0:S^{2}_{n}\in\mathscr{B}^{c}_{\mathsf{G}}(2^{k})\\},$ $\displaystyle
V_{k}^{1}$
$\displaystyle=(\mathscr{B}_{\mathsf{G}}(2^{k})\setminus\mathscr{B}_{\mathsf{G}}(2^{k-1}))\cap\mathcal{R}^{1}_{\tau^{1}_{2^{k+1}}},$
$\displaystyle V_{k}^{2}$
$\displaystyle=(\mathscr{B}_{\mathsf{G}}(2^{k})\setminus\mathscr{B}_{\mathsf{G}}(2^{k-1}))\cap\mathcal{R}^{2}_{\tau^{2}_{2^{k+1}}},$
$\displaystyle E_{k}$
$\displaystyle=\\{V_{k}\cap\widetilde{V}_{k}\neq\emptyset\\},$

where $\widetilde{V}_{k}$ is defined as $V_{k}$ (see Proposition 2.8) but in
terms of an independent copy $\\{\widetilde{S}_{n}\\}_{n\geq 0}$ of
$\\{S_{n}\\}_{n\geq 0}$. By completely the same reasoning as in [27, Theorem
6.5.10], (2.7) will follow if we show that $\mathbf{P}(E_{k}\ \text{i.o.})>0$.
According to [27, Corollary A.6.2], it suffices to show that

  * (i)

$\displaystyle\sum_{k=1}^{\infty}\mathbf{P}(E_{4k})=\infty;$

  * (ii)

there is $c>0$ such that $\mathbf{P}(E_{4k}\cap E_{4\ell})\leq
c\,\mathbf{P}(E_{4k})\mathbf{P}(E_{4\ell})$ for all $k,\ell\in\mathbf{N}$.

The relation in (i) will follow easily once we prove
$\mathbf{P}(E_{4k})\gtrsim 1/k$ using the second moment method. For
$k\in\mathbf{N}$ set
$\mathscr{A}_{\mathsf{G}}(k)=\mathscr{B}_{\mathsf{G}}(2^{k})\setminus\mathscr{B}_{\mathsf{G}}(2^{k-1}).$
Expressing $|V_{k}^{1}\cap V_{k}^{3}|$ as a sum of indicator functions and
taking expectation gives

(2.8) $\displaystyle\operatorname*{\mathbf{E}}\left[|V_{k}^{1}\cap
V_{k}^{3}|\right]=\sum_{g\in\mathscr{A}_{\mathsf{G}}(k)}\mathbf{P}(S^{1}_{n}=g$
$\displaystyle\text{for some }n<\tau^{1}_{2^{k+1}})$
$\displaystyle\mathbf{P}(S^{3}_{n}=g\ \text{for some }n<\tau^{3}_{2^{k+1}}).$

According to [4, Theorem 1.31], for all $k\in\mathbf{N}$ and $g\neq e$, we
have

$\mathbf{P}\bigl{(}S^{1}_{n}=g\ \text{for some
}n<\tau^{1}_{2^{k+1}}\bigr{)}=c(k)\sum_{n=0}^{\infty}\mathbf{P}\bigl{(}S_{n}^{1}=g,\
n<\tau_{2^{k+1}}^{1}\bigr{)},$

where

$c(k)^{-1}=\sum_{n=0}^{\infty}\mathbf{P}_{g}(S_{n}^{1}=g,\
n<\tau_{2^{k+1}}^{1})\leq\sum_{n=0}^{\infty}\mathbf{P}_{g}(S_{n}^{1}=g)=\mathcal{G}(e).$

On the other hand, due to Proposition 2.5 and [4, Theorems 4.25 and 4.26], we
obtain

$\mathbf{P}\bigl{(}S^{1}_{n}=g\ \text{for some
}n<\tau^{1}_{2^{k+1}}\bigr{)}\geq\mathcal{G}(e)^{-1}\sum_{n=0}^{\infty}\mathbf{P}\bigl{(}S_{n}^{1}=g,\
n<\tau_{2^{k+1}}^{1}\bigr{)}\gtrsim\rho(g)^{-2}.$

Plugging this into (2.8), and using that $\rho(g)\leq 2^{k}$ on
$\mathscr{A}_{\mathsf{G}}(k)$ and $|\mathscr{A}_{\mathsf{G}}(k)|\asymp 2^{4k}$
(recall that $d=4$), we now have

$\operatorname*{\mathbf{E}}\left[|V_{k}^{1}\cap
V_{k}^{3}|\right]\gtrsim\sum_{g\in\mathscr{A}_{\mathsf{G}}(k)}2^{-4k}\asymp
1,$

and this completes the first part of the second moment method, i.e. proving
that the appropriate first moment is large. It remains to prove that the
second moment is small. We have that

(2.9) $\displaystyle\operatorname*{\mathbf{E}}\left[|V_{k}^{1}\cap
V_{k}^{3}|^{2}\right]=\sum_{g_{1},g_{2}\in\mathscr{A}_{\mathsf{G}}(k)}$
$\displaystyle\mathbf{P}(S^{1}_{n}=g_{1}\ \text{and}\ S^{1}_{m}=g_{2}\
\text{for some }n,m<\tau^{1}_{2^{k+1}})$
$\displaystyle\mathbf{P}(S^{3}_{n}=g_{1}\ \text{and}\ S^{3}_{m}=g_{2}\
\text{for some }n,m<\tau^{3}_{2^{k+1}}).$

Notice that

(2.10) $\displaystyle\mathbf{P}(S^{1}_{n}=g_{1}\ \text{and}\ S^{1}_{m}=g_{2}\
\text{for some }n,m<\tau^{1}_{2^{k+1}})$ $\displaystyle\quad\leq
2\,\mathbf{P}(S^{1}_{n}=g_{1}\ \text{and}\ S^{1}_{m}=g_{2}\ \text{for some
}n\leq m<\tau^{1}_{2^{k+1}})$ $\displaystyle\quad\leq
2\,\mathbf{P}(S^{1}_{n}=g_{1}\ \text{and}\ S^{1}_{m}=g_{2}\ \text{for some
}n\leq m)$ $\displaystyle\quad\leq 2\,\sum_{m\geq n\geq
0}\mathbf{P}\bigl{(}S^{1}_{n}=g_{1}\bigr{)}\mathbf{P}_{g_{1}}\bigl{(}S^{1}_{m-n}=g_{2}\bigr{)}$
$\displaystyle\quad=2\,\mathcal{G}(g_{1})\mathcal{G}(g_{1}^{-1}g_{2})$

We can easily bound the Green function by using the bound $p_{n}(g)\lesssim
n^{-2}e^{-c\rho(g)^{2}/n}$ provided by Proposition 2.5. For $g\neq e$ this
gives

$\mathcal{G}(g)\lesssim\sum_{n=1}^{\infty}n^{-2}e^{-c\rho(g)^{2}/n}\lesssim\int_{1}^{\infty}u^{-2}e^{-c\rho(g)^{2}/u}\,du\lesssim\rho(g)^{-2}\lesssim(1+\rho(g))^{-2},$

where the last step was done so that we can also include $g=e$. Using this
bound, from (2.9) and (LABEL:eq:niz) we obtain

$\displaystyle\operatorname*{\mathbf{E}}\left[|V_{k}^{1}\cap
V_{k}^{3}|^{2}\right]$
$\displaystyle\lesssim\sum_{g_{1},g_{2}\in\mathscr{A}_{\mathsf{G}}(k)}2^{-4k}\bigl{(}1+\rho(g_{1}^{-1}g_{2})\bigr{)}^{-4}$
$\displaystyle=\sum_{g_{1}\in\mathscr{A}_{\mathsf{G}}(k)}2^{-4k}\sum_{g_{2}\in\mathscr{A}_{\mathsf{G}}(k)}\bigl{(}1+\rho(g_{1}^{-1}g_{2})\bigr{)}^{-4}.$

Since $|\mathscr{A}_{\mathsf{G}}(k)|\asymp 2^{4k}$ and
$\rho(g_{1}^{-1}g_{2})<2^{k+1}$ whenever
$g_{1},g_{2}\in\mathscr{A}_{\mathsf{G}}(k)$, this boils down to a sum we can
easily deal with via dyadic decomposition:

$\displaystyle\operatorname*{\mathbf{E}}\left[|V_{k}^{1}\cap
V_{k}^{3}|^{2}\right]$
$\displaystyle\lesssim\sum_{g\in\mathscr{B}_{\mathsf{G}}(2^{k+1})}\bigl{(}1+\rho(g)\bigr{)}^{-4}\lesssim\sum_{\ell=0}^{k}\sum_{g\in\mathscr{A}_{\mathsf{G}}(\ell+1)}\bigl{(}1+\rho(g)\bigr{)}^{-4}$
$\displaystyle\lesssim\sum_{\ell=0}^{k}(2^{\ell+1})^{4}\bigl{(}1+2^{\ell}\bigr{)}^{-4}\lesssim
k.$

We are finally in a position to use a variant of the second moment method (see
e.g. [27, Lemma A.6.1])

$\displaystyle\mathbf{P}\bigl{(}E_{k}\bigr{)}$
$\displaystyle=\mathbf{P}\bigl{(}|V_{k}^{1}\cap
V_{k}^{3}|>0\bigr{)}=\lim_{u\to 0}\mathbf{P}\bigl{(}|V_{k}^{1}\cap
V_{k}^{3}|\geq u\,\operatorname*{\mathbf{E}}\left[|V_{k}^{1}\cap
V_{k}^{3}|\right]\bigr{)}$ $\displaystyle\geq\lim_{u\to
0}\frac{(1-u)^{2}\bigl{(}\operatorname*{\mathbf{E}}\left[|V_{k}^{1}\cap
V_{k}^{3}|\right]\bigr{)}^{2}}{\operatorname*{\mathbf{E}}\left[|V_{k}^{1}\cap
V_{k}^{3}|^{2}\right]}\gtrsim\frac{1}{k},$

which proves (i).

It remains to prove (ii). Assume $k<l$ and note that

(2.11)
$\mathbf{P}\bigl{(}E_{4\ell}|E_{4k}\bigr{)}=\sum_{F}\mathbf{P}\bigl{(}E_{4\ell}|E_{4k}\cap
F\bigr{)}\,\mathbf{P}\bigl{(}F|E_{4k}\bigr{)},$

where sum goes over all possible trajectories of $\\{S_{n}^{3}\\}_{0\leq
n\leq\tau^{3}_{2^{4k+1}}}$. Additionally, let $\mathcal{R}_{F}$ be the set of
all elements in $\mathsf{G}$ visited by $\\{S_{n}^{3}\\}_{0\leq
n\leq\tau^{3}_{2^{4k+1}}}$ that followed a fixed trajectory $F$,
$h=S^{3}_{\tau^{3}_{2^{4k+1}}}$, and $H_{g}$ be the event in which $g$ is the
first element of $\mathcal{R}_{F}\cap V_{4k}^{3}$ visited by
$\\{S_{n}^{1}\\}_{n\geq 0}$. Then using Markov property we obtain

$\displaystyle\mathbf{P}\bigl{(}E_{4\ell}|E_{4k}\cap F\bigr{)}$
$\displaystyle=\sum_{g\in\mathcal{R}_{F}\cap
V_{4k}^{3}}\mathbf{P}\bigl{(}E_{4\ell}|H_{g}\cap E_{4k}\cap
F\bigr{)}\,\mathbf{P}\bigl{(}H_{g}|E_{4k}\cap F\bigr{)}$
$\displaystyle=\sum_{g\in\mathcal{R}_{F}\cap
V_{4k}^{3}}\mathbf{P}_{(g,h)}\bigl{(}E_{4\ell})\,\mathbf{P}\bigl{(}H_{g}|E_{4k}\cap
F\bigr{)}.$

From Proposition 2.8 it follows that there is $c>0$ such that for all
$\ell\in\mathbf{N}$ we have $\mathbf{P}_{(g_{1},g_{2})}(E_{4\ell})\leq
c\,\mathbf{P}_{(e,e)}(E_{4\ell})$ for all
$(g_{1},g_{2})\in\overline{\mathscr{B}}_{\mathsf{G}}(2^{4\ell-3})\times\overline{\mathscr{B}}_{\mathsf{G}}(2^{4\ell-3})$.
Thus, from Markov property we can conclude that

$\mathbf{P}\bigl{(}E_{4\ell}|E_{4k}\cap F\bigr{)}\leq
c\,\mathbf{P}_{(e,e)}(E_{4\ell}),$

and plugging this back into (2.11) we obtain

$\mathbf{P}\bigl{(}E_{4\ell}|E_{4k}\bigr{)}\leq c\,\mathbf{P}(E_{4\ell}),$

which proves (ii). ∎

######  Remark 2.10.

  * (i)

We remark that in [2, Corollary 1.4] a much more quantitative version of
Proposition 2.9 has been proven – namely that for the symmetric simple random
walk on $\mathbf{Z}^{4}$ one has
$\operatorname*{\mathbf{E}}\left[\mathcal{C}_{n}\right]\asymp n/\log n$. We
conjecture, and leave as an open problem, that the same holds in the setting
of finitely generated groups with symmetric set of generators and $d=4$.

We believe there are couple of special cases of this conjecture that are
interesting on its own. Most obviously, is
$\operatorname*{\mathbf{E}}\left[\mathcal{C}_{n}\right]\asymp n/\log n$
whichever symmetric set of generators of $\mathbf{Z}^{4}$ one considers?

One could also consider the same question on a specific group with the growth
index $4$ which does not contain $\mathbf{Z}^{4}$ as a finite index subgroup.
An important example of such a group is the discrete Heisenberg group
$H_{3}(\mathbf{Z})$, i.e. the group of matrices of the form

$\begin{pmatrix}1&a&c\\\ 0&1&b\\\ 0&0&1\\\ \end{pmatrix},\qquad
a,b,c\in\mathbf{Z}.$

Is it true that $\operatorname*{\mathbf{E}}\left[\mathcal{C}_{n}\right]\asymp
n/\log n$ for the symmetric simple random walk on $H_{3}(\mathbf{Z})$ with
respect to the standard generators $\\{x,y,x^{-1},y^{-1}\\}$ where

$x=\begin{pmatrix}1&1&0\\\ 0&1&0\\\ 0&0&1\\\ \end{pmatrix},\qquad
y=\begin{pmatrix}1&0&0\\\ 0&1&1\\\ 0&0&1\\\ \end{pmatrix}?$

  * (ii)

By completely the same reasoning as in Proposition 2.9 one can show that
$\operatorname*{\mathbf{E}}\left[\mathcal{C}_{n}\right]=\mathsf{o}(n)$ in the
case when $d=3$. However, Proposition 2.6 gives much sharper result.

We finally have:

###### Proof of Theorem 1.1.

The assertions follow from Propositions 2.1, 2.4, 2.6 and 2.9 and relation
(2.1). ∎

##  3\. CLT for $\\{\mathcal{C}_{n}\\}_{n\geq 0}$

In this section, we show how the proof of [2, Theorem 1.1] can be adapted to
prove Theorem 1.2. We first determine the constant $\sigma_{d}$ in (1.2). If
$d\geq 6$, we show that the sequence
$\\{\operatorname{Var}(\mathcal{C}_{n})/n\\}_{n\geq 1}$ is convergent and its
limit is exactly $\sigma_{d}^{2}$.

We start with the following auxiliary result. For $n\geq 0$, we write
$\mathcal{G}_{n}(g_{1},g_{2})$ for the Green function up to time $n$, i.e.

$\mathcal{G}_{n}(g_{1},g_{2})=\sum_{k=0}^{n}p_{k}(g_{1},g_{2}).$

######  Proposition 3.1.

Assume $d\geq 5$. Then, for all $g\in\mathsf{G}$,

(3.1)
$\sum_{g_{1},g_{2}\in\mathsf{G}}\mathcal{G}_{n}(g_{1})\mathcal{G}_{n}(g_{2})\mathcal{G}(g_{1}^{-1}gg_{2})\lesssim\mathcal{E}(n),$

where

$\mathcal{E}(n)=\begin{cases}1,&\quad d\geq 7,\\\ \log n,&\quad d=6,\\\
\sqrt{n},&\quad d=5.\\\ \end{cases}$

###### Proof.

For all $k,j\geq 0$ we have that

$\displaystyle\sum_{g_{1},g_{2}\in\mathsf{G}}p_{k}(e,g_{1})p_{j}(e,g_{2})\mathcal{G}(g_{1},gg_{2})$
$\displaystyle=\sum_{i=0}^{\infty}\sum_{g_{1},g_{2}\in\mathsf{G}}p_{k}(e,g_{1})p_{j}(g,gg_{2})p_{i}(g_{1},gg_{2})$
$\displaystyle=\sum_{i=0}^{\infty}\sum_{g_{1},g_{2}\in\mathsf{G}}p_{k}(e,g_{1})p_{i}(g_{1},gg_{2})p_{j}(gg_{2},g)$
$\displaystyle=\sum_{i=0}^{\infty}p_{k+i+j}(g).$

Using Proposition 2.2, we thus get

$\sum_{g_{1},g_{2}\in\mathsf{G}}p_{k}(e,g_{1})p_{j}(e,g_{2})\mathcal{G}(g_{1},gg_{2})\lesssim(j+k)^{-d/2+1}.$

Summing over $j,k=0,\dots,n$ gives the stated bounds. ∎

We now conclude the announced first step of the proof of the CLT.

######  Proposition 3.2.

Assume $d\geq 6$. Then, $\\{\operatorname{Var}(\mathcal{C}_{n})/n\\}_{n\geq
1}$ converges to a finite limit.

###### Proof.

The proof proceeds analogously as for the symmetric simple random walk on
$\mathbf{Z}^{d}$, $d\geq 6$, given in [2]. For the reader’s convenience we
give a complete proof. For $n,m\in\mathbf{N}$, let
$\mathcal{R}_{n}^{(1)}=\\{S_{n}^{-1}S_{0},\dots,S_{n}^{-1}S_{n}\\}$,
$\mathcal{R}_{n,m}^{(2)}=\\{S_{n}^{-1}S_{n},\dots,S_{n}^{-1}S_{n+m}\\}$,
$\mathcal{C}_{n}^{(1)}=\mathrm{Cap}(\mathcal{R}_{n}^{(1)})$ and
$\mathcal{C}_{n,m}^{(2)}=\mathrm{Cap}(\mathcal{R}_{n,m}^{(2)})$. Clearly,
$\mathcal{R}_{n}^{(1)}$ and $\mathcal{R}_{n,m}^{(2)}$ ($\mathcal{C}_{n}^{(1)}$
and $\mathcal{C}_{n,m}^{(2)}$) are independent and have the same law as
$\mathcal{R}_{n}$ and $\mathcal{R}_{m}$ ($\mathcal{C}_{n}$ and
$\mathcal{C}_{m}$), respectively. According to

  * (i)

capacity decomposition shown in [31, Proposition 25.11] and [2, Proposition
1.2]: for any finite sets $A,B\subset\mathsf{G}$,

$\mathrm{Cap}(A)+\mathrm{Cap}(B)-2\mathcal{G}(A,B)\leq\mathrm{Cap}(A\cup
B)\leq\mathrm{Cap}(A)+\mathrm{Cap}(B)-\mathrm{Cap}(A\cap B);$

  * (ii)

left-translation-invariance of the capacity: for any $n,m\in\mathbf{N}$,

$\mathcal{C}_{n+m}=\mathrm{Cap}\bigl{(}S_{n}^{-1}\mathcal{R}_{n+m}\bigr{)}=\mathrm{Cap}\bigl{(}\mathcal{R}_{n}^{(1)}\cup\mathcal{R}_{n,m}^{(2)}\bigr{)},$

we conclude

(3.2)
$\mathcal{C}_{n}^{(1)}+\mathcal{C}_{n,m}^{(2)}-2\mathcal{G}(\mathcal{R}_{n}^{(1)},\mathcal{R}_{n,m}^{(2)})\leq\mathcal{C}_{n+m}\leq\mathcal{C}_{n}^{(1)}+\mathcal{C}_{n,m}^{(2)}.$

We remark that both [31, Proposition 25.11] and [2, Proposition 1.2] are
stated only for the symmetric simple random walk on $\mathbf{Z}^{d}$, but the
proofs are valid for any finitely generated group with symmetric set of
generators.

Further, for $n,m\in\mathbf{N}$ define
$\overline{\mathcal{C}}_{n}=\mathcal{C}_{n}-\operatorname*{\mathbf{E}}[\mathcal{C}_{n}]$,
and similarly $\overline{\mathcal{C}}_{n}^{(1)}$ and
$\overline{\mathcal{C}}_{n,m}^{(2)}$. Taking expectation in (3.2) and then
subtracting those two relations yields

$\big{|}\overline{\mathcal{C}}_{n+m}-(\overline{\mathcal{C}}_{n}^{(1)}+\overline{\mathcal{C}}_{n,m}^{(2)})\big{|}\leq
2\max\\{\mathcal{G}(\mathcal{R}_{n}^{(1)},\mathcal{R}_{n,m}^{(2)}),\operatorname*{\mathbf{E}}[\mathcal{G}(\mathcal{R}_{n}^{(1)},\mathcal{R}_{n,m}^{(2)})]\\}.$

Proceeding in a completely analogous way as in [12, Lemma 3.2] (and using
(3.1)) we obtain

(3.3)
$\operatorname*{\mathbf{E}}\left[\big{(}\mathcal{G}(\mathcal{R}^{(1)}_{n},\mathcal{R}^{(2)}_{n,n})\big{)}^{q}\right]\lesssim_{q}\mathcal{E}(n)^{q}$

for every $q\in\mathbb{N}$. Recall the definition of the function
$\mathcal{E}(n)$ from Proposition 3.1. Denote
$\lVert\cdot\rVert_{2}=\operatorname*{\mathbf{E}}[(\cdot)^{2}]^{1/2}$.
Clearly,
$\operatorname{Var}(\mathcal{C}_{n})=\lVert\overline{\mathcal{C}}_{n}\rVert_{2}^{2}$
for $n\in\mathbf{N}$. The triangle inequality and independence of
$\overline{\mathcal{C}}_{n}^{(1)}$ and $\overline{\mathcal{C}}_{n,m}^{(2)}$
together with the estimate
$\operatorname*{\mathbf{E}}[\mathcal{G}(\mathcal{R}_{n}^{(1)},\mathcal{R}_{n,m}^{(2)})]\leq\|\mathcal{G}(\mathcal{R}_{n}^{(1)},\mathcal{R}_{n,m}^{(2)})\|_{2}$
and (3.3) imply

$\displaystyle\|\overline{\mathcal{C}}_{n+m}\|_{2}$
$\displaystyle\leq\big{(}\|\overline{\mathcal{C}}_{n}^{(1)}\|_{2}^{2}+\|\overline{\mathcal{C}}_{n,m}^{(2)}\|_{2}^{2}\big{)}^{1/2}+4\|\mathcal{G}(\mathcal{R}_{n}^{(1)},\mathcal{R}_{n,m}^{(2)})\|_{2}$
$\displaystyle\leq\big{(}\|\overline{\mathcal{C}}_{n}^{(1)}\|_{2}^{2}+\|\overline{\mathcal{C}}_{n,m}^{(2)}\|_{2}^{2}\big{)}^{1/2}+c\mathcal{E}(n+m)$

for some $c>0$, where in the last inequality we used

$\mathcal{G}(\mathcal{R}_{n}^{(1)},\mathcal{R}_{n,m}^{(2)})\leq\mathcal{G}(\mathcal{R}_{n+m}^{(1)},\mathcal{R}_{n+m,n+m}^{(2)}).$

Consequently,

$\displaystyle\|\overline{\mathcal{C}}_{n+m}\|_{2}^{2}\leq\|\overline{\mathcal{C}}_{n}\|_{2}^{2}+\|\overline{\mathcal{C}}_{m}\|_{2}^{2}+2c\big{(}\|\overline{\mathcal{C}}_{n}\|_{2}^{2}+\|\overline{\mathcal{C}}_{m}\|_{2}^{2}\big{)}^{1/2}\mathcal{E}(n+m)+c^{2}\mathcal{E}(n+m)^{2}.$

By setting $g(n)=\|\overline{\mathcal{C}}_{n}\|_{2}^{2}$ for $n\in\mathbf{N}$,
the above relation reads

(3.4) $g(n+m)\leq
g(n)+g(m)+2c\big{(}\|\overline{\mathcal{C}}_{n}\|_{2}^{2}+\|\overline{\mathcal{C}}_{m}\|_{2}^{2}\big{)}^{1/2}\mathcal{E}(n+m)+c^{2}\mathcal{E}(n+m)^{2}.$

In the sequel we find an upper bound for the third term of the right hand side
of inequality (3.4). If we prove that

(3.5) $\|\overline{\mathcal{C}}_{n}\|_{2}\lesssim\sqrt{n}\,\mathcal{E}(n),$

then by defining $\varphi(n)\asymp\sqrt{n}\mathcal{E}(n)^{2}$ the assertion of
the lemma will follow directly from (3.4), the fact that $d\geq 6$ and de
Brujin-Erdős extension of Fekete’s lemma (see [13, Theorem 23]).

Let us prove (3.5). For $k\in\mathbf{N}$ we set

(3.6) $\gamma(k)=\sup\left\\{\|\overline{\mathcal{C}}_{i}\|_{2}:\,2^{k}\leq
i\leq 2^{k+1}\right\\}.$

Further, for $k\geq 2$ we take $n\in\mathbf{N}$ such that $2^{k}\leq
n<2^{k+1}$, and we set $l=\lfloor n/2\rfloor$ and $m=n-l$. Analogously as
above we have

$\mathcal{C}_{l}^{(1)}+\mathcal{C}_{l,m}^{(2)}-2G(\mathcal{R}_{l}^{(1)},\mathcal{R}_{l,m}^{(2)})\leq\mathcal{C}_{n}\leq\mathcal{C}_{l}^{(1)}+\mathcal{C}_{l,m}^{(2)},$

and we arrive at

(3.7) $\displaystyle\|\overline{\mathcal{C}}_{n}\|_{2}$
$\displaystyle\leq\big{(}\|\overline{\mathcal{C}}_{l}^{(1)}\|_{2}^{2}+\|\overline{\mathcal{C}}_{l,m}^{(2)}\|_{2}^{2}\big{)}^{1/2}+c\mathcal{E}(n)$

for some $c>0$. Recall that $\mathcal{R}_{l}^{(1)}$ and
$\mathcal{R}_{l,m}^{(2)}$ ($\mathcal{C}_{l}^{(1)}$ and
$\mathcal{C}_{l,m}^{(2)}$) are independent and have the same law as
$\mathcal{R}_{l}$ and $\mathcal{R}_{m}$ ($\mathcal{C}_{l}$ and
$\mathcal{C}_{m}$), respectively. Hence, equation (3.7) implies

$\|\overline{\mathcal{C}}_{n}\|_{2}\leq\sqrt{2}\gamma(k-1)+c\mathcal{E}(n).$

Taking supremum over $2^{k}\leq n\leq 2^{k+1}$ yields

$\gamma(k)\leq\sqrt{2}\gamma(k-1)+c\mathcal{E}(2^{k+1}).$

We next set $\delta(k)=\gamma(k)/\mathcal{E}(2^{k})$. Due to monotonicity of
$\mathcal{E}(n)$ and the fact that $\mathcal{E}(2^{k+1})\leq
2\mathcal{E}(2^{k})$ for all $n\in\mathbf{N}$ (recall the definition of
$\mathcal{E}(n)$) it holds that

$\delta(k)\leq\sqrt{2}\delta(k-1)+2c.$

By iteration of this inequality we have $\delta(k)\lesssim 2^{k/2}$ which
implies $\gamma(k)\lesssim 2^{k/2}\mathcal{E}(2^{k})$. Finally, using
definition of $\gamma(k)$ we obtain

$\lVert\overline{\mathcal{C}}_{n}\rVert_{2}^{2}\leq\gamma(k)^{2}\lesssim
2^{k}\mathcal{E}(2^{k})^{2}\lesssim n\,\mathcal{E}(n)^{2},$

which is (3.5). ∎

Denote the limit of $\\{\operatorname{Var}(\mathcal{C}_{n})/n\\}_{n\geq 1}$ by
$\sigma_{d}^{2}$. Strict positivity of $\sigma_{d}^{2}$ now follows from (a
straightforward adaptation of) [2, Section 3.3] where $\\{S_{n}\\}_{n\geq 0}$
is decomposed into two independent processes. The first process is the process
counting double-backtracks at even times and it is given as a sequence of
i.i.d. geometric random variables $\\{\xi_{i}\\}_{i\in 2\mathbf{N}}$ with
parameter $p=1-1/|\Gamma|^{2}$ (we say that a random walk
$\\{\widetilde{S}_{n}\\}_{n\geq 0}$ on $\mathsf{G}$ makes a double backtrack
at even time $n\in 2\mathbf{N}$ if $\widetilde{S}_{n-1}=\widetilde{S}_{n-3}$
and $\widetilde{S}_{n}=\widetilde{S}_{n-2}$). The second process is a random
walk $\\{\hat{S}_{n}\\}_{n\geq 0}$ on $\mathsf{G}$ with no double-backtracks
at even times constructed as follows: set $\hat{S}_{0}=0$ and then choose
$\hat{S}_{1}$ and $\hat{S}_{2}$ in the same fashion as one would choose them
in a symmetric random walk on $\mathsf{G}$. Suppose that we have constructed
$\\{\hat{S}_{n}\\}_{n\geq 0}$ for all times $k\leq 2n$. We now let
$(\hat{S}_{2n+1},\hat{S}_{2n+2})$ be uniform in the set

$\\{(g_{1},g_{2})\in\mathsf{G}\times\mathsf{G}:\rho(g_{1},g_{2})=1,\,\rho(\hat{S}_{2n},g_{1})=1\,\textnormal{
and }\,(g_{1},g_{2})\neq(\hat{S}_{2n-1},\hat{S}_{2n})\\}.$

Further, setting $N_{0}=N_{1}=0$ and

$N_{k}=\sum_{\begin{subarray}{c}i=2\\\ i\in
2\mathbf{N}\end{subarray}}^{k}\xi_{i}$

for $k\geq 2$, we construct $\\{\tilde{S}_{n}\\}_{n\geq 0}$ from
$\\{\hat{S}_{n}\\}_{n\geq 0}$ as follows. First we set
$\tilde{S}_{i}=\hat{S}_{i}$ for $i=0,1,2$, and for all $k\in\mathbf{N}$ we set
$I_{k}=[2k+2N_{2(k-1)}+1,2k+2N_{2k}]$. If $I_{k}\neq\emptyset$, then if $i\in
I_{k}$ is odd, we set $\tilde{S}_{i}=\hat{S}_{2k-1}$, while if $i$ is even, we
set $\tilde{S}_{i}=\hat{S}_{2k}$. Afterwards, for the next two steps, we
follow the path of $\\{\hat{S}_{n}\\}_{n\geq 0}$, i.e.

$\tilde{S}_{2k+2N_{2k}+1}=\hat{S}_{2k+1}\qquad\textnormal{and}\qquad\tilde{S}_{2k+2N_{2k}+2}=\hat{S}_{2k+2}.$

It is now immediate that $\\{\tilde{S}_{n}\\}_{n\geq 0}$ is a symmetric random
walk on $\mathsf{G}$, i.e. identical in law to $\\{S_{n}\\}_{n\geq 0}$. Strict
positivity of $\sigma_{d}^{2}$ now follows by performing an analogous analysis
as in [2, Lemma 3.3].

We finally have:

###### Proof of Theorem 1.2.

The proof proceeds analogously as for [2, Theorem 1.1]. We explain the main
steps of the proof only. The proof is based on the following three results:

  * (a)

dyadic capacity decomposition formula (generalisation of formula (3.2))
derived in [2, Corollary 2.1]: Let $L,n\geq 1$ be such that $2^{L}\leq n$.
Then,

(3.8)
$\sum_{i=1}^{2^{L}}\mathrm{Cap}\,(\mathcal{R}^{(i)}_{n/2^{L}})-2\sum_{l=1}^{L}\sum_{i=1}^{2^{l-1}}\mathrm{Er}_{l}^{(i)}\leq\mathcal{C}_{n}\leq\sum_{i=1}^{2^{L}}\mathrm{Cap}\,(\mathcal{R}^{(i)}_{n/2^{L}}),$

where $\\{\mathcal{R}^{(i)}_{n/2^{L}}\\}_{i=1,\dots,2^{L}}$ are independent
and $\mathcal{R}^{(i)}_{n/2^{L}}$ has the same law as $\mathcal{R}_{\lfloor
n/2^{L}\rfloor}$ or $\mathcal{R}_{\lfloor n/2^{L}+1\rfloor}$, and for each
$l=1,\dots,2^{L}$ the random variables
$\\{\mathrm{Er}_{l}^{(i)}\\}_{i=1,\dots,2^{l-1}}$ are independent and
$\mathrm{Er}_{l}^{(i)}$ has the same law as
$\mathcal{G}(\mathcal{R}^{(i)}_{n/2^{l}},\bar{\mathcal{R}}^{(i)}_{n/2^{l}})$
with $\\{\bar{\mathcal{R}}_{n}\\}_{n\geq 0}$ being an independent copy of
$\\{\mathcal{R}_{n}\\}_{n\geq 0}$.

  * (b)

fourth moment estimate of the capacity derived in [2, Lemma 4.2]: If $d\geq
6$, then

(3.9)
$\operatorname*{\mathbf{E}}\big{[}\overline{\mathcal{C}}_{n}^{4}\big{]}\lesssim
n^{2},$

where again
$\overline{\mathcal{C}}_{n}=\mathcal{C}_{n}-\operatorname*{\mathbf{E}}[\mathcal{C}_{n}].$

  * (c)

Lindeberg-Feller central limit theorem (see [15, Theorem 4.5]): For
$n\in\mathbf{N}$ let $\\{X_{n,i}\\}_{1\leq i\leq n}$ be a sequence of
independent random variables. If

    * (i)

$\displaystyle\lim_{n\to\infty}\sum_{i=1}^{n}\operatorname{Var}(X_{n,i})=\sigma^{2}>0;$

    * (ii)

for every $\varepsilon>0$,
$\displaystyle\lim_{n\to\infty}\sum_{i=1}^{n}\operatorname*{\mathbf{E}}\left[(X_{n,i}-\operatorname*{\mathbf{E}}[X_{n,i}])^{2}\mathbbm{1}_{\\{|X_{n,i}-\operatorname*{\mathbf{E}}[X_{n,i}|>\varepsilon\\}}\right]=0,$

then
$X_{n,1}+\cdots+X_{n,n}\xrightarrow[n\to\infty]{\rm{(d)}}\mathcal{N}(0,\sigma^{2}).$

We remark that both [2, Corollary 2.1 and Lemma 4.2] are stated only for the
symmetric simple random walk on $\mathbf{Z}^{d}$, but the proofs are valid for
any finitely generated group with symmetric set of generators.

Denote
$\mathcal{C}^{(i)}_{n/2^{L}}=\mathrm{Cap}\,(\mathcal{R}^{(i)}_{n/2^{L}})$ for
$i=1,\dots,2^{L}$. By taking expectation in (3.8) and then subtracting those
two relations we obtain

(3.10)
$\sum_{i=1}^{2^{L}}\overline{\mathcal{C}}^{(i)}_{n/2^{L}}-2\sum_{l=1}^{L}\sum_{i=1}^{2^{l-1}}\mathrm{Er}_{l}^{(i)}\leq\overline{\mathcal{C}}_{n}\leq\sum_{i=1}^{2^{L}}\overline{\mathcal{C}}^{(i)}_{n/2^{L}}+2\sum_{l=1}^{L}\sum_{i=1}^{2^{l-1}}\operatorname*{\mathbf{E}}[\mathrm{Er}_{l}^{(i)}],$

where
$\overline{\mathcal{C}}^{(i)}_{n/2^{L}}=\mathcal{C}^{(i)}_{n/2^{L}}-\operatorname*{\mathbf{E}}[\overline{\mathcal{C}}^{(i)}_{n/2^{L}}]$
for $i=1,\dots,2^{L}$. For $n\in\mathbf{N}$, define

$\mathrm{Er}(n)=\sum_{i=1}^{2^{L}}\overline{\mathcal{C}}^{(i)}_{n/2^{L}}-\overline{\mathcal{C}}_{n}.$

Using (3.10) and (3.3), we get that

$\operatorname*{\mathbf{E}}\big{[}|\mathrm{Er}(n)|\big{]}\leq
4\operatorname*{\mathbf{E}}\bigg{[}\sum_{l=1}^{L}\sum_{i=1}^{2^{l-1}}\mathrm{Er}_{l}^{(i)}\bigg{]}\lesssim\sum_{l=1}^{L}\sum_{i=1}^{2^{l-1}}\mathcal{E}\bigg{(}\frac{n}{2^{l}}\bigg{)}\leq\mathcal{E}(n)\sum_{l=1}^{L}2^{l-1}\leq
2^{L}\log(n)$

(recall the definition of the function $\mathcal{E}(n)$ from Proposition 3.1).
Set now $L=L(n)=\lfloor\log_{2}\big{(}n^{1/4}\big{)}\rfloor$. Then,

$\lim_{n\to\infty}\frac{\operatorname*{\mathbf{E}}\big{[}|\mathrm{Er}(n)|\big{]}}{\sqrt{n}}=0.$

We are thus left to prove that

$\sum_{i=1}^{2^{L}}\frac{\overline{\mathcal{C}}^{(i)}_{n/2^{L}}}{\sqrt{n}}\xrightarrow[n\to\infty]{\text{(d)}}\mathcal{N}(0,\sigma_{d}^{2}).$

To establish this result we apply the Lindeberg-Feller central limit theorem.
For $n\in\mathbf{N}$ and $1\leq i\leq 2^{L}$ put
$X_{2^{L},i}=\overline{\mathcal{C}}^{(i)}_{n/2^{L}}/\sqrt{n}.$ By Proposition
3.2 we have

$\lim_{n\to\infty}\sum_{i=1}^{2^{L}}\operatorname{Var}(X_{2^{L},i})=\lim_{n\to\infty}\sum_{i=1}^{2^{L}}\frac{1}{n}\operatorname{Var}(\overline{\mathcal{C}}^{(i)}_{n/2^{L}})=\sigma_{d}^{2},$

which means that the first Lindeberg-Feller condition is satisfied. It remains
to check that for any $\varepsilon>0$ it holds that

$\lim_{n\to\infty}\sum_{i=1}^{2^{L}}\operatorname*{\mathbf{E}}\left[X_{2^{L},i}^{2}\mathbbm{1}_{\\{|X_{2^{L},i}|>\varepsilon\\}}\right]=\lim_{n\to\infty}\sum_{i=1}^{2^{L}}\frac{1}{n}\operatorname*{\mathbf{E}}\left[\left(\overline{\mathcal{C}}^{(i)}_{n/2^{L}}\right)^{2}\mathbbm{1}_{\\{|\overline{\mathcal{C}}^{(i)}_{n/2^{L}}|>\varepsilon\sqrt{n}\\}}\right]=0.$

Observe that by the Cauchy-Schwartz inequality we have

$\displaystyle\operatorname*{\mathbf{E}}\left[\left(\overline{\mathcal{C}}^{(i)}_{n/2^{L}}\right)^{2}\mathbbm{1}_{\\{|\overline{\mathcal{C}}^{(i)}_{n/2^{L}}|>\varepsilon\sqrt{n}\\}}\right]$
$\displaystyle\leq\left(\operatorname*{\mathbf{E}}\left[\left(\overline{\mathcal{C}}^{(i)}_{n/2^{L}}\right)^{4}\right]\mathbf{P}(|\overline{\mathcal{C}}^{(i)}_{n/2^{L}}|>\varepsilon\sqrt{n})\right)^{1/2}.$

Further, the Chebyshev inequality combined with (3.9), strict positivity of
$\sigma_{d}$ and Proposition 3.2, imply

$\displaystyle\operatorname*{\mathbf{E}}\left[\left(\overline{\mathcal{C}}^{(i)}_{n/2^{L}}\right)^{4}\right]\mathbf{P}(|\overline{\mathcal{C}}^{(i)}_{n/2^{L}}|>\varepsilon\sqrt{n})\lesssim\bigg{(}\frac{n}{2^{L}}\bigg{)}^{2}\,\frac{\operatorname{Var}\left(\overline{\mathcal{C}}^{(i)}_{n/2^{L}}\right)}{\varepsilon^{2}n}\lesssim
2\sigma_{d}^{2}\frac{n^{2}}{\varepsilon^{2}2^{3L}}.$

Based on the choice $L=\lfloor\log_{2}\big{(}n^{1/4}\big{)}\rfloor$, we
conclude

$\sum_{i=1}^{2^{L}}\frac{1}{n}\operatorname*{\mathbf{E}}\left[\left(\overline{\mathcal{C}}^{(i)}_{n/2^{L}}\right)^{2}\mathbbm{1}_{\\{|\overline{\mathcal{C}}^{(i)}_{n/2^{L}}|>\varepsilon\sqrt{n}\\}}\right]\lesssim
n^{-1/8},$

and this finishes the proof.

∎

######  Remark 3.3.

Having the CLT at our disposal, under the same assumptions we can also obtain
a functional version of this result. It is straightforward to reproduce the
arguments from [11, Theorem 1.1] (by checking the Aldous’ tightness condition
and showing convergence of finite dimensional distributions in (3.11)) and
conclude the following

(3.11) $\left\\{\frac{\mathcal{C}_{\lfloor
nt\rfloor}-\operatorname*{\mathbf{E}}[\mathcal{C}_{\lfloor
nt\rfloor}]}{\sigma_{d}\sqrt{n}}\right\\}_{t\geq
0}\xrightarrow[n\to\infty]{(\textnormal{J}_{1})}\,\\{B_{t}\\}_{t\geq 0}\,,$

where $\sigma_{d}$ is the constant from Theorem 1.2,
$\xrightarrow[n\to\infty]{(\textnormal{J}_{1})}$ stands for the weak
convergence in the Skorohod space $\mathcal{D}([0,\infty),\mathbb{R})$ endowed
with the $\textnormal{J}_{1}$ topology, and $\\{B_{t}\\}_{t\geq 0}$ denotes a
standard one-dimensional Brownian motion.

## Acknowledgement

We would like to thank an anonymous referee for numerous valuable comments.
This work has been supported by Deutscher Akademischer Austauschdienst (DAAD)
and Ministry of Science and Education of the Republic of Croatia (MSE) via
project Random Time-Change and Jump Processes. Financial support through the
Croatian Science Foundation under project 4129 (for R. Mrazović), Alexander-
von-Humboldt Foundation under project No. HRV 1151902 HFST-E and Croatian
Science Foundation under project 8958 (for N. Sandrić), and Croatian Science
Foundation under project 4197 (for S. Šebek) is gratefully acknowledged.

## References

  * namelastnametitle __jtitleetaljournalvolumeISBNISSNurl}numeral
  * [1]
  * [2] A. Asselah, B. Schapira P. Sousi, Capacity of the range of random walk on $\mathbb{Z}^{d}$Capacity of the range of random walk on $\mathbb{Z}^{d}$, Trans. Amer. Math. Soc. 370 (2018), . 11, 7627–7645.
  * [3] by same author, Capacity of the range of random walk on $\mathbb{Z}^{4}$Capacity of the range of random walk on $\mathbb{Z}^{4}$, Ann. Probab. 47 (2019), . 3, 1447–1497.
  * [4] M.T. Barlow, Random walks and heat kernels on graphsRandom walks and heat kernels on graphs, Cambridge University Press, Cambridge, 2017.
  * [5] H. Bass, The degree of polynomial growth of finitely generated nilpotent groupsThe degree of polynomial growth of finitely generated nilpotent groups, Proc. London Math. Soc. (3) 25 (1972), 603–614.
  * [6] R.F. Bass T. Kumagai, Laws of the iterated logarithm for the range of random walks in two and three dimensionsLaws of the iterated logarithm for the range of random walks in two and three dimensions, Ann. Probab. 30 (2002), . 3, 1369–1396.
  * [7] I. Benjamini, R. Izkovsky H. Kesten, On the range of the simple random walk bridge on groupsOn the range of the simple random walk bridge on groups, Electron. J. Probab. 12 (2007), no. 20, 591–612.
  * [8] Y. Chang, Two observations on the capacity of the range of simple random walks on $\mathbb{Z}^{3}$ and $\mathbb{Z}^{4}$Two observations on the capacity of the range of simple random walks on $\mathbb{Z}^{3}$ and $\mathbb{Z}^{4}$, Electron. Commun. Probab. 22 (2017), . 25, 9 pp.
  * [9] M. Chen, S. Yan X. Zhou, The range of random walk on trees and related trapping problemThe range of random walk on trees and related trapping problem, Acta Math. Appl. Sinica (English Ser.) 13 (1997), . 1, 1–16.
  * [10] X. Chen, J. Xie M. Zhao, Asymptotic entropy of the ranges of random walks on discrete groupsAsymptotic entropy of the ranges of random walks on discrete groups, Sci. China Math. 63 (2020), . 6, 1153–1168.
  * [11] W. Cygan, N. Sandrić S. Šebek, Functional CLT for the range of stable random walksFunctional CLT for the range of stable random walks, Bull. Malays. Math. Sci. Soc. 44 (2021), . 3, 1371–1386.
  * [12] by same author, CLT for the capacity of the range of stable random walksCLT for the capacity of the range of stable random walks, https://www.tandfonline.com/doi/full/10.1080/17442508.2021.1920941, to appear in Stochastics: An International Journal of Probability and Stochastic Processes.
  * [13] N.G. de Bruijn P. Erdös, Some linear and some quadratic recursion formulas. IISome linear and some quadratic recursion formulas. II, Nederl. Akad. Wetensch. Proc. Ser. A. 55 = Indagationes Math. 14 (1952), 152–163.
  * [14] C. Druţu M. Kapovich, Geometric group theoryGeometric group theory, American Mathematical Society, Providence, RI, 2018.
  * [15] R. Durrett, Probability: theory and examplesProbability: theory and examples, second., Duxbury Press, Belmont, CA, 1996.
  * [16] A. Dvoretzky P. Erdös, Some problems on random walk in spaceSome problems on random walk in space, Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, 1950, University of California Press, Berkeley and Los Angeles, 1951, . 353–367.
  * [17] A. Erschler, On continuity of range, entropy and drift for random walks on groupsOn continuity of range, entropy and drift for random walks on groups, Random walks, boundaries and spectra, Progr. Probab., . 64, Birkhäuser/Springer Basel AG, Basel, 2011, . 55–64.
  * [18] M. Gromov, Groups of polynomial growth and expanding mapsGroups of polynomial growth and expanding maps, Inst. Hautes Études Sci. Publ. Math. (1981), . 53, 53–73.
  * [19] W. Hebisch L. Saloff-Coste, Gaussian estimates for Markov chains and random walks on groupsGaussian estimates for Markov chains and random walks on groups, Ann. Probab. 21 (1993), . 2, 673–709.
  * [20] N.C. Jain S. Orey, On the range of random walkOn the range of random walk, Israel J. Math. 6 (1968), 373–380 (1969).
  * [21] by same author, Some properties of random walk pathsSome properties of random walk paths, J. Math. Anal. Appl. 43 (1973), 795–815.
  * [22] N.C. Jain W.E. Pruitt, The range of transient random walkThe range of transient random walk, J. Analyse Math. 24 (1971), 369–393.
  * [23] by same author, The law of the iterated logarithm for the range of random walkThe law of the iterated logarithm for the range of random walk, Ann. Math. Statist. 43 (1972), 1692–1697.
  * [24] O. Kallenberg, Foundations of modern probabilityFoundations of modern probability, Springer-Verlag, New York, 1997.
  * [25] U. Krengel, Ergodic theoremsErgodic theorems, Walter de Gruyter & Co., Berlin, 1985.
  * [26] G.F. Lawler, Intersections of random walksIntersections of random walks, Birkhäuser/Springer, New York, 2013.
  * [27] G.F. Lawler V. Limic, Random walk: a modern introductionRandom walk: a modern introduction, Cambridge University Press, Cambridge, 2010.
  * [28] J.F. Le Gall, Propriétés d’intersection des marches aléatoires. I. Convergence vers le temps local d’intersectionPropriétés d’intersection des marches aléatoires. I. Convergence vers le temps local d’intersection, Comm. Math. Phys. 104 (1986), . 3, 471–507.
  * [29] R. Lyons Y. Peres, Probability on trees and networksProbability on trees and networks, Cambridge University Press, New York, 2016.
  * [30] B. Schapira, Capacity of the range in dimension 5Capacity of the range in dimension 5, Ann. Probab. 48 (2020), . 6, 2988–3040.
  * [31] F. Spitzer, Principles of random walkPrinciples of random walk, second., Springer-Verlag, New York-Heidelberg, 1976.
  * [32] N.Th. Varopoulos, Isoperimetric inequalities and Markov chainsIsoperimetric inequalities and Markov chains, J. Funct. Anal. 63 (1985), . 2, 215–239.
  * [33] N.Th. Varopoulos, L. Saloff-Coste T. Coulhon, Analysis and geometry on groupsAnalysis and geometry on groups, Cambridge University Press, Cambridge, 1992.
  * [34] D. Windisch, Entropy of random walk range on uniformly transient and on uniformly recurrent graphsEntropy of random walk range on uniformly transient and on uniformly recurrent graphs, Electron. J. Probab. 15 (2010), no. 36, 1143–1160.