# Repeated measurements and random scattering in quantum walks

K. Ziegler
Institut für Physik, Universität Augsburg
D-86135 Augsburg, Germany

Abstract:

We study the effect of random scattering in quantum walks on a finite graph
and compare it with the effect of repeated measurements. To this end, a
constructive approach is employed by introducing a localized and a delocalized
basis for the underlying Hilbert space. This enables us to design Hamiltonians
whose eigenvectors are either localized or delocalized. By presenting some
specific examples we demonstrate that the localization of eigenvectors
restricts the transition probabilities on the graph and leads to dark states
in the monitored evolution. We conclude that repeated measurements as well as
random scattering provide efficient tools for controlling quantum walks.

##  1 Introduction

Classical random walks play an important role in the description of the
dynamics in statistical physics [1, 2] with applications in many research
areas, ranging from biological [3], chemical [4] and physical systems [5, 6,
7] to the dynamics of financial markets [8]. The basic idea of a classical
random walk [5, 6] is to consider the transition probability $0\leq P_{{\bf
r}{\bf r}^{\prime}}\leq 1$ of a random walker to move from the site ${\bf
r}^{\prime}$ to the site ${\bf r}$ in a fixed time interval. The available
sites form a lattice or a graph with the constraint $\sum_{{\bf r}}P_{{\bf
r}{\bf r}^{\prime}}=1$ for the transition probabilities, which is called
detailed balance [9]. It reflects that the random walker does not get lost or
absorbed during the random walk. In order to include quantum effects, we
replace the transition probabilities by a unitary evolution from the local
state $|{\bf r}^{\prime}\rangle$ to the local state $|{\bf r}\rangle$ during
the time $\tau$. This can be expressed by the unitary operator
$U(\tau)=\exp(-iH\tau)$ with the Hermitian Hamiltonian $H$. For the elements
of a unitary matrix $U_{{\bf r}{\bf r}^{\prime}}=\langle{\bf
r}|\exp(-iH\tau)|{\bf r}^{\prime}\rangle$ we apply the same constraint
$\sum_{{\bf r}^{\prime}}U_{{\bf r}{\bf r}^{\prime}}=1$ as for the classical
transition probability. Thus, the substitution $P_{{\bf r}{\bf r}^{\prime}}\to
U_{{\bf r}{\bf r}^{\prime}}$ constitutes a “quantization” of the classical
random walk. Most interesting is the asymptotic behavior of
$U(\tau)^{n}=U(n\tau)$ for large $n$, where the time reads $t=n\tau$. In the
following we will consider a continuous time $t$ for simplicity. This is a
special model from the more general field of quantum walks, which has become
the subject of intensive research recently [10, 11, 12, 13, 14, 15, 16, 17].

Properties of the quantum walk depend on the eigenstates and eigenvalues of
the Hamiltonian $H$, which are also the eigenstates of the evolution operator.
An important characterization is how far an initial state $|{\bf
r}_{0}\rangle$ can be transferred to other local states $|{\bf r}\rangle$ by
the unitary evolution over a large time. In other words, is the quantum walk
restricted inside the Hilbert space or not? This depends on whether the
eigenbasis of $U(t)$ is localized or delocalized. In the former case the
initial state will only evolve to states $\\{|{\bf r}\rangle\\}$ in a
restricted vicinity of $|{\bf r}_{0}\rangle$, while for a delocalized basis it
can reach any of the existing states. For a given graph, comprising of points
$\\{{\bf r}_{1},\ldots,{\bf r}_{N}\\}$ embedded in a $d$–dimensional space,
there are equivalent basis sets for the corresponding Hilbert space, spanned
by $\\{|{\bf r}_{1}\rangle,\ldots,|{\bf r}_{N}\rangle\\}$, which are either
localized or delocalized or a mixture of both. Here is an example of two
equivalent basis sets, one is localized, the other delocalized: The states
$\\{|{\bf r}_{1}\rangle,\ldots,|{\bf r}_{N}\rangle\\}$ can be represented by a
Cartesian basis $\\{{\bf e}_{k}\\}$, which are localized vectors.
Alternatively, the plane-wave basis $\\{{\bf w}_{k}\\}_{k=1,\ldots,N}$,
consisting of extended vectors with

${\bf w}_{k}:=(1,e^{2\pi i(k-1)/N},e^{2\pi i(k-1)2/N},\ldots,e^{2\pi
i(k-1)(N-1)/N})^{T}/\sqrt{N},$ (1)

also spans this Hilbert space. A Hermitian operator $H$ or a unitary operator
$U$ can be expanded in any of these basis sets. Then the question is, in which
basis the operator is diagonal? Or more specific, is the diagonal basis
localized or not? In this paper we will reverse the mapping $U(\tau)\to\\{{\bf
x}_{k},E_{k}\\}$ by constructing an operator $U(\tau)$ for a given set of
eigenvalues $\\{E_{k}\\}$ in a specific basis $\\{{\bf x}_{k}\\}$: $\\{{\bf
x}_{k},E_{k}\\}\to U(\tau)$. For a given spectrum this enables us to choose a
localized, a delocalized or a mixed basis to construct the operator $U(\tau)$.
In this context we will demonstrate that for degenerate eigenvalues both types
of basis sets give the same operator. This means that the distinction between
a localized vs. a delocalized diagonal basis is not applicable in this case
and the mapping $\\{{\bf x}_{k},E_{k}\\}\to U(\tau)$ is not invertible. This
reflects the more general problem that the mapping $U(\tau)\to\\{{\bf
x}_{k},E_{k}\\}$ does not have a unique solution in the case of degenerate
eigenvalues. After setting up the unitary operator for a localized and for a
plane-wave basis, we will study the effect of (i) repeated projective
measurements and (ii) random scattering on the quantum walk.

Before we proceed with a detailed discussion of the quantum walk model we give
a short summary of the present work. After defining a quantum walk model on a
finite graph with $N$ sites, we introduce a symmetric Hamiltonian that
connects all sites of the graph with equal transition amplitudes. This
Hamiltonian has one zero eigenvalue and an $N-1$–fold degenerate eigenvalue 1.
Within the Gram-Schmidt approach we construct a localized orthonormal basis
for this Hamiltonian. Since the plane-wave basis is also a diagonal basis due
to the degeneracy of the eigenvalue 1, we create new Hamiltonians in Sect. 2.1
by lifting the degeneracy. These Hamiltonians and their corresponding unitary
evolution operators either have a plane-wave diagonal basis or a localized
diagonal basis. The effect of repeated projective measurements on the quantum
walk is studied in Sect. 2.2. We find that the localized basis implies a
strong localization effect for the monitored evolution, while the plane-wave
basis provides a uniform spreading of the quantum walk. In contrast, the
unitary evolution with random scattering, based on a random distribution of
eigenvalues, creates two different contributions to the average quantum walk.
As shown in Sect. 2.3, there is a quantum contribution and a classical
contribution, where the latter dominates at large times. Both contributions
are either localized or delocalized, depending on the localization properties
of their diagonal basis.

##  2 Quantum walks on a graph

The general concept of a quantum walk is quite broad and has many models and
realizations [10, 18, 15, 16, 17]. We will focus here on the tight-binding
model, including random scattering [19, 20] and repeated projective
measurements [21, 22, 23, 24, 25]. To this end, we define a graph ${\cal G}$
as a set of spatial sites, embedded in a $d$–dimensional space, as

${\cal G}:=\\{{\bf r}_{1},{\bf r}_{2},\ldots,{\bf r}_{N}\\}\ \ \ (N<\infty),$
(2)

where ${\bf r}_{j}$ is a $d$–dimensional vector. Then the quantum walk on
${\cal G}$ is defined by a unitary evolution operator $\exp(-iHt)$ with the
Hamiltonian $H$, which is acting on the $N-1$–dimensional Hilbert space
$\mathcal{H}$ that is spanned by the basis of the position states $\\{|{\bf
r}_{n}\rangle\\}_{n=1,2,\ldots,N}$. It describes quantum tunneling between the
sites of the graph. ${\cal H}$ is also spanned by the eigenstates
$\\{|E_{k}\rangle\\}$ of $H$, whose corresponding eigenvalues are
$\\{E_{k}\\}$. Then we write for the unitary evolution matrix

$U_{MM^{\prime}}(t)=\langle{\bf r}_{M}|e^{-iHt}|{\bf
r}_{M^{\prime}}\rangle=\sum_{k=1}^{N}q_{M,k}e^{-iE_{k}t}q^{*}_{M^{\prime},k},$
(3)

where $q_{M,k}=\langle{\bf r}_{M}|E_{k}\rangle=\langle E_{k}|{\bf
r}_{M}\rangle^{*}$ is the overlap or scalar product of the particle position
state and the energy eigenstate.

Complementary to the unitary evolution we consider a monitored evolution with
repeated projective measurements. For the projection $\Pi_{M}$ onto the state
$|{\bf r}_{M}\rangle$, we define the non-unitary evolution operator
$T_{M}=U(\tau/2)({\bf 1}-\Pi_{M})U(\tau/2)$ with matrix elements in the energy
basis as [25]

$T_{M;kl}(\tau):=\langle E_{k}|e^{-iH\tau}|E_{l}\rangle-\langle
E_{k}|e^{-iH\tau/2}|{\bf r}_{M}\rangle\langle{\bf
r}_{M}|e^{-iH\tau/2}|E_{l}\rangle=e^{-iE_{M}\tau/2}(\delta_{kl}-q^{*}_{M,k}q_{M,l})e^{-iE_{l}\tau/2}.$
(4)

This provides the $N\times N$ matrix $T_{M}(\tau)=U(\tau/2)({\bf
1}-Q_{M}^{*}EQ_{M})U(\tau/2)$, where ${\bf 1}$ is the $N\times N$ unit matrix
and $E$ is the $N\times N$ matrix whose matrix elements are 1, and with the
diagonal matrices

$U={\rm diag}(e^{-iE_{1}\tau},\ldots,e^{-iE_{N}\tau})\ ,\ \ Q_{M}={\rm
diag}(q_{M,1},\ldots,q_{M,N}).$

It describes a unitary evolution for the time $\tau/2$, followed by a
projection onto the space orthogonal to $|{\bf r}_{M}\rangle$ by ${\bf
1}-Q_{M}^{*}EQ_{M}$, and finally a unitary evolution for the time $\tau/2$
again.

Both evolution matrices $U$ and $T$ are defined via the eigenvalues
$\\{E_{k}\\}$ of the Hamiltonian $H$ and the overlap functions $\\{q_{n,k}\\}$
between the position states and the eigenstates of the Hamiltonian. The
eigenvalues of $U(t)$ are on the unit circle and the eigenvalues of
$T(M,\tau)$ are on the unit disk with one eigenvalue at the center, since
${\bf 1}-Q_{M}^{*}EQ_{M}$ has an eigenvalue 0 with the eigenvector ${{\bf
q}}^{*}_{M}=(q^{*}_{M,1},\ldots,q^{*}_{M,N})^{T}$ and the $N-1$–fold
degenerate eigenvalue 1 with eigenvectors $\\{{\bf q}^{*}_{k}\\}_{k\neq M}$.

To define a quantum walk on ${\cal G}$ we begin with the idealistic case, in
which the diagonal elements are $1-1/N$ and the off-diagonal elements connect
all sites equally:

$H_{{\bf r}_{j}{\bf r}_{j^{\prime}}}\equiv
H_{jj^{\prime}}=\delta_{jj^{\prime}}-\frac{1}{N}.$ (5)

This can also be written as the symmetric $N\times N$ matrix $H={\bf 1}-E/N$.
The vector ${\bf u}_{1}:=(1,\ldots,1)^{T}$ is eigenvector with eigenvalue 0:
$H{\bf u}_{1}=0$. This reflects the detailed balance property
$\sum_{j^{\prime}}U_{jj^{\prime}}=1$ of the quantum walk at each site of the
graph. Besides the zero eigenvalue of $H$ with eigenvector ${\bf u}_{1}$,
there is the $N-1$–fold degenerate eigenvalue 1. Thus, we must construct a
basis of linear independent vectors, which are orthogonal to ${\bf u}_{1}$. An
example is $\\{{\bf u}_{l}\\}_{l=2,\ldots,N}$ with ${\bf
u}_{l}:=(1,0,\ldots,0,-1,0\ldots 0)^{T}$, where the $l^{\rm th}$ component is
$-1$. This means that the Hilbert space ${\cal H}$ separates into
$\mathcal{H}_{1}$, spanned by ${\bf u}_{1}$ and $\mathcal{H}^{\prime}$,
spanned by $\\{{\bf u}_{l}\\}_{l=2,\ldots,N}$, as
$\mathcal{H}=\mathcal{H}_{1}\oplus\mathcal{H}^{\prime}$. The basis $\\{{\bf
u}_{l}\\}_{l=2,\ldots,N}$ is not orthogonal, though, but can be
orthonormalized by the Gram-Schmidt approach. This recursive procedure creates
$N$-component vectors that are systematically filled with non-zero components,
beginning, for instance, with ${\bf
v}_{2}=\frac{1}{\sqrt{2}}(1,-1,0,\ldots,0)^{T}$ and proceeding with

${\bf v}_{k}=\frac{1}{\sqrt{k(k-1)}}(1,\ldots,1,-k+1,0,\ldots,0)^{T}\ \ \
(3\leq k\leq N),$ (6)

where the first $k-1$ components are $1$. This enables us to expand the matrix
$(H_{jj^{\prime}})$ in terms of its eigenvalues and eigenvectors as

$H_{jj^{\prime}}=\sum_{k=2}^{N}v^{*}_{kj}E_{k}v_{kj^{\prime}},\ \ E_{1}=0\ ,\
\ E_{k}=1\ \ \ (2\leq k\leq N),$ (7)

where the first index $k$ of $v_{kl}$ refers to the vector ${\bf v}_{k}$ and
the second index $l$ refers to its components. It should be noted that
$v_{kl}=q^{*}_{l,k}=\langle{\bf r}_{l}|E_{k}\rangle^{*}=\langle E_{k}|{\bf
r}_{l}\rangle$. Moreover, the matrix elements $v_{1l}=1/\sqrt{N}$ do not
appear in the expansion of $H$ due to $E_{1}=0$, which is required by detailed
balance. For $2\leq k\leq N$, $1\leq l\leq N$ we get from Eq. (6)

$v_{kl}=\frac{1}{\sqrt{k(k-1)}}\cases{1&$1\leq l\leq k-1$\cr-k+1&$l=k$\cr
0&$k<l\leq N$\cr}.$ (8)

This can also be written as

$v_{kl}=\frac{1}{\sqrt{k(k-1)}}\left[(-k+1)\delta_{kl}+\Theta_{kl}\right]\ \
{\rm with}\ \ \Theta_{kl}=\cases{0&$l\geq k$\cr 1&$l<k$\cr}.$ (9)

Although we don’t need ${\bf v}_{1}=(1,\ldots,1)^{T}/\sqrt{N}$ for the
expansion of $H$, it contributes to the expansion of the unitary evolution
matrix $U(t)=\exp(-iHt)$. After including $k=1$ in the matrix $v$ we obtain
from Eq. (9) for its elements

$v_{kl}=\frac{1}{\sqrt{N}}\delta_{k1}+(1-\delta_{k1})\frac{1}{\sqrt{k(k-1)}}\left[(-k+1)\delta_{kl}+\Theta_{kl}\right].$
(10)

While the Gram-Schmidt procedure gives a unique basis (which depends on the
choice of ${\bf u}_{2}$ though), another basis can be created by a unitary
transformation. An important question is related to the localization of
eigenvectors. $\\{{\bf u}_{l}\\}_{l=2,\ldots,N}$ are localized eigenvectors
but summing them creates also extended eigenvectors, as already demonstrated
for the orthonormal basis $\\{{\bf v}_{l}\\}_{l=2,\ldots,N}$. This ambiguity
exists only for degenerate eigenvalues, where any linear combination of
eigenvectors gives another eigenvector.

For specific values of $k$ and $l$ the spectral weights
$(v_{kl})^{2}=\langle{\bf r}_{k}|E_{l}\rangle\langle E_{k}|{\bf r}_{l}\rangle$
characterizes the decay of the eigenvector ${\bf v}_{k}$. For instance, ${\bf
r}_{1}$ is equally connected through $U(t)$ to any site ${\bf r}_{l}$ on the
graph, while ${\bf r}_{2}$ is only connected to ${\bf r}_{1}$, ${\bf r}_{3}$
to ${\bf r}_{1}$ and ${\bf r}_{2}$ etc. up to ${\bf r}_{N}$ which is connected
to all sites but also has a dominant spectral weight $(v_{NN})^{2}=1-1/N$.
This, as well as $(v_{kk})^{2}=1-1/k$ ($2\leq k\leq N$), reflects localization
with increasing spectral weight due to increasing $k$. More general, the
quantity

$c_{k}:=\sum_{l=1}^{N}(v_{kl})^{4}$ (11)

provides a criterion for the localization of ${\bf v}_{k}$: It defines
localization for $c_{k}\sim 1/N^{0}$ and delocalization for $c_{k}\sim 1/N$.
For the basis $\\{{\bf v}_{k}\\}$ we get $c_{1}=1/N$ and for $2\leq k\leq N$

$c_{k}=\frac{1}{k^{2}(k-1)^{2}}\sum_{l=1}^{N}[(k-1)^{4}\delta_{kl}+\Theta_{kl}]=(1-1/k)^{2}+\frac{1}{k^{2}(k-1)},$
(12)

which is independent of $N$ and bounded as $1/2\leq c_{k}\leq 1$. Thus, all
eigenvectors are localized except for ${\bf v}_{1}$. The localization
originates in the component $v_{kk}$ of the degenerate spectrum, which is
larger than the other components of ${\bf v}_{k}$. In contrast to the
localized $\\{{\bf v}_{k}\\}_{l=2,\ldots,N}$, the basis $\\{{\bf w}_{l}\\}$ is
a set of delocalized eigenvectors with $c_{k}=\sum_{l}|w_{kl}|^{4}=1/N$.

${\cal H}$ can also be spanned by plane waves $\\{{\bf w}_{k}\\}$ in Eq. (1),
which form an orthonormal basis. This provides the elements $w_{jk}:=\exp[2\pi
i(j-1)(k-1)/N]/\sqrt{N}$ ($1\leq j,k\leq N$) of the $N\times N$ unitary matrix

$w=\frac{1}{\sqrt{N}}\pmatrix{1&1&1&\cdots&1\cr 1&e^{2\pi i/N}&e^{2\pi
i2/N}&\ldots&e^{2\pi i(N-1)/N}\cr\vdots&\vdots&\vdots&\ddots&\vdots\cr
1&e^{2\pi i(N-1)/N}&e^{2\pi i2(N-1)/N}&\ldots&e^{2\pi i(N-1)^{2}/N}\cr}$

with

$\sum_{k=1}^{N}w_{jk}w_{j^{\prime}k}^{*}=\sum_{k=1}^{N}\frac{e^{2\pi
i(j-j^{\prime})(k-1)/N}}{N}=\delta_{jj^{\prime}}.$

This enables us to expand the unitary evolution matrix as

$U_{jj^{\prime}}=\sum_{k=1}^{N}w_{kj}^{*}e^{-iE_{k}\tau}w_{kj^{\prime}},$ (13)

which gives the same Hamiltonian as the expansion in Eq. (7) due to the
spectral degeneracy in ${\cal H}^{\prime}$.

###  2.1 Non-degenerate energy eigenvalues

Based on the expansions (7) and (13) with a non-degenerate set of eigenvalues
$\\{E_{j}\\}$ we create new Hamiltonians, only keeping $E_{1}=0$ to preserve
the detailed balance, either with the localized eigenvector basis $\\{{\bf
v}_{k}\\}$ or with the delocalized eigenvector basis $\\{{\bf w}_{k}\\}$:

$U^{\prime}_{jj^{\prime}}=\sum_{k=1}^{N}v_{kj}e^{-iE_{k}\tau}v_{kj^{\prime}}\
,\ \ \
U^{\prime\prime}_{jj^{\prime}}=\sum_{k=1}^{N}w_{kj}^{*}e^{-iE_{k}\tau}w_{kj^{\prime}},$
(14)

where $U^{\prime\prime}$ is translational invariant on the graph in the sense
of $U^{\prime\prime}_{jj^{\prime}}\equiv H^{\prime\prime}_{j-j^{\prime}}$. (It
should be noted that this does not mean translational invariance with respect
the embedding space.) Formally, we can also consider $E_{1}\neq 0$. In that
case the Hamiltonian also depends on the delocalized eigenvector ${\bf
v}_{1}$.

The expansions in Eq. (14) mean that we can create two different Hamiltonians
with the same spectrum but different properties of the eigenvectors; in one
case with a delocalized basis $\\{{\bf w}_{l}\\}$, in the other case with a
localized basis $\\{{\bf v}_{l}\\}$. This concept can be generalized by mixing
the two type of basis states in different subspaces of ${\cal H}^{\prime}$ to
create a random ensemble, where the average can either be dominated by the
localized or by the delocalized eigenvectors. Formally, we write
$\mathcal{H}^{\prime}=\mathcal{H}_{2}\oplus\cdots\oplus\mathcal{H}_{n}$ and
choose randomly either a localized or delocalized basis to span
$\mathcal{H}_{j}$. Finally, we employ the Gram-Schmidt procedure to
orthormalize the basis in $\mathcal{H}^{\prime}$.

###  2.2 Transition probabilities for the monitored evolution

From the unitary evolution matrix of Eq. (3) and the monitored evolution
matrix in Eq. (4) we obtain the corresponding transition probabilities as

$P_{MM^{\prime}}(t)=|U_{MM^{\prime}}(t)|^{2}=\left|\sum_{k=1}^{N}q_{M,k}e^{-iE_{k}t}q^{*}_{M^{\prime},k}\right|^{2}$
(15)

and, according to Ref. [25],

$\Pi_{MM^{\prime}}(m,\tau)=\left|{\rm
Tr}(U(\tau/2)T_{M}^{m-1}U(\tau/2)Q^{*}_{M^{\prime}}EQ_{M})\right|^{2}=\left|\sum_{k,l=1}^{N}e^{-i(E_{k}+E_{l})\tau/2}[T_{M}^{m-1}]_{kl}q^{*}_{M^{\prime},l}q_{M,k}\right|^{2}.$
(16)

The conservation of the quantum walker requires
$\sum_{M}P_{MM^{\prime}}(t)=1$, which is automatically implied by the unitary
evolution. This condition reflects that the quantum walker is not absorbed at
any time and that it can be found somewhere on the graph with total
probability 1. This corresponds with the detailed balance of a classical
random walk, while the detailed balance of the quantum walk
$\sum_{j^{\prime}}U_{jj^{\prime}}(t)=1$ is an additional condition.

The time of the monitored evolution is $t=m\tau$, which is interrupted by
$m-1$ measurements. The two transition probabilities are related as
$\Pi_{MM^{\prime}}(1,\tau)=P_{MM^{\prime}}(\tau)$, which reflects that $m=1$
means no measurement. For the monitored transition $|{\bf
r}_{M^{\prime}}\rangle\to|{\bf r}_{M}\rangle$ the matrix $T_{M}^{m-1}$ is
crucial. Its matrix elements $q^{*}_{M^{\prime},k}q_{M,l}$ read in the plane-
wave basis $\\{{\bf w}_{l}\\}$

$q^{*}_{M^{\prime},k}q_{M,l}=w_{kM^{\prime}}w^{*}_{lM}=\frac{e^{2\pi
i[(M^{\prime}-1)(k-1)-(M-1)(l-1)]/N}}{N},$ (17)

which implies that the transition probability reads

$\Pi_{MM^{\prime}}(m,\tau)=\frac{1}{N^{2}}\left|\sum_{k,l=1}^{N}e^{-i(E_{k}+E_{l})\tau/2+2\pi
i[(M^{\prime}-1)(k-1)-(M-1)(l-1)]/N}[T_{M}^{m-1}]_{kl}\right|^{2}.$ (18)

For the corresponding expression in the localized basis $\\{{\bf v}_{l}\\}$ we
use Eq. (10). The decay of the monitored transfer probability with respect to
$|M-M^{\prime}|$ is determined by the matrix $T_{M}^{m-1}$ in Eq. (16). When
$m\ll N$ we can neglect terms of $O(1/\sqrt{N})$. Then the transfer matrix
$T_{M}$ is reduced to the matrix $(v_{kl})$ for ($2\leq k,l\leq N$) as

$A_{kl}:=\delta_{kl}-q^{*}_{M,k}q_{M,l}=\delta_{kl}-v_{kM}v_{lM}$
$=\delta_{kl}[1-(1-1/M)\delta_{kM}]+\frac{\sqrt{1-1/M}}{\sqrt{k(k-1)}}\Theta_{kM}\delta_{lM}+\frac{\sqrt{1-1/M}}{\sqrt{l(l-1)}}\Theta_{lM}\delta_{kM}-\frac{1}{\sqrt{k(k-1)l(l-1)}}\Theta_{kM}\Theta_{lM}.$

Thus, the $(N-1)\times(N-1)$ matrix $A$ can be written as a matrix with a
block structure as

$A=\pmatrix{{\bf 1}&0\cr 0&B\cr}\ \ {\rm and}\ \
T_{M}=U(\tau/2)AU(\tau/2)=\pmatrix{u_{1}&0\cr 0&u_{2}Bu_{2}\cr}$ (19)

with an $M\times M$ block matrix $B$ and diagonal matrices $u_{1,2}$ with
$u_{1}={\rm diag}(e^{-iE_{1}\tau},\ldots,e^{-iE_{M-1}\tau},0,\ldots)$ and
$u_{2}={\rm diag}(0,\ldots,0,e^{-iE_{M}\tau/2},\ldots,e^{-iE_{N}\tau/2})$.
This means that a vector ${\bf x}=\sum_{k=2}^{M-1}x_{k}{\bf v}_{k}$ is
completely localized on the graph under a monitored evolution: $T_{M}{\bf
x}=u_{1}{\bf x}$. On the other hand, the complementary vector ${\bf
y}=\sum_{k=M}^{N}y_{k}{\bf v}_{k}$ can not leave the subspace spanned by
$\\{{\bf v}_{k}\\}_{k=M,\ldots,N}$ under the monitored evolution: ${\bf
v}_{k}\cdot T_{M}^{m-1}{\bf y}=0$ for $k=2,\ldots,M-1$ and any $m>1$. For the
plane-wave basis $\\{{\bf w}_{l}\\}$ the corresponding matrix reads

$A_{kl}=\delta_{kl}-q^{*}_{M,k}q_{M,l}=\delta_{kl}-w^{*}_{kM}w_{lM}=\delta_{kl}-\frac{1}{N}e^{-2\pi
i(k-l)(M-1)/N},$

such that

$T_{M;kl}=e^{-i{\bar{E}}_{k}\tau}\delta_{kl}-\frac{1}{N}e^{-2\pi
i(k-l)(M-1)/N-i({\bar{E}}_{k}-{\bar{E}}_{l})\tau/2}.$ (20)

In this case we get ${\bf v}_{k}\cdot T_{M}^{m-1}{\bf y}\neq 0$, which
indicates that there is no restriction of the monitored evolution.

###  2.3 Random scattering in the unitary evolution

In this section we consider random scattering in the unitary evolution by
random eigenvalues $\\{E_{k}\\}$. In general, both matrices $E$ and $u$ in
$H=u^{\dagger}Eu$ can be random, where only $E$ appears in the time dependence
of the unitary evolution matrix of Eq. (3), though. Thus, we get from Eq. (15)
the average with respect to the eigenvalue distribution for a general unitary
matrix $u$

$\langle
P_{MM^{\prime}}(t)\rangle=\langle[e^{-iHt}]_{MM^{\prime}}[e^{iHt}]_{M^{\prime}M}\rangle=\sum_{k,l}p_{kl}(t)u^{\dagger}_{Mk}u_{kM^{\prime}}u^{\dagger}_{M^{\prime}l}u_{lM}$
(21)

with $p_{kl}(t)=\langle e^{-i(E_{k}-E_{l})t}\rangle=\langle
e^{-i(x_{k}-x_{l})t}\rangle e^{-i({\bar{E}}_{k}-{\bar{E}}_{l})t}$ and with
random fluctuations $x_{k}=E_{k}-{\bar{E}}_{k}$ around the mean eigenvalue
${\bar{E}}_{k}$. Moreover, we split the double summation as

$\langle
P_{MM^{\prime}}(t)\rangle=\sum_{k}u^{\dagger}_{Mk}u_{kM^{\prime}}u^{\dagger}_{M^{\prime}k}u_{kM}+\sum_{k,l}(1-\delta_{kl})p_{kl}(t)u^{\dagger}_{Mk}u_{kM^{\prime}}u^{\dagger}_{M^{\prime}l}u_{lM},$
(22)

where we have used $p_{kk}(t)=1$. Thus, only the remaining double sum depends
on time through $p_{kl}(t)$. These results can be summarized by the expression

$\langle
P_{MM^{\prime}}(t)\rangle=[1-w(t)]\sum_{k=1}^{N}|u_{kM^{\prime}}|^{2}|u_{kM}|^{2}+w(t){\bar{P}}_{MM^{\prime}}(t),$
(23)

where ${\bar{P}}_{MM^{\prime}}(t)$ is the transition probability of Eq. (15),
in which the Hamiltonian $H$ is replaced by its average ${\bar{H}}=\langle
H\rangle$. The weight function $w(t)=\langle e^{-i(x_{k}-x_{l})t}\rangle$ is
determined by the distribution of the eigenvalues. We can assume that
$\lim_{t\to\infty}w(t)=0$, as will be demonstrated in several examples in
Sect. 3.1. The splitting of the average transition probability into a static
part $\sum_{k=1}^{N}|u_{kM^{\prime}}|^{2}|u_{kM}|^{2}$ and the evolution part
${\bar{P}}_{MM^{\prime}}(t)$ with time dependent weights $1-w(t)$ and $w(t)$,
respectively, indicates a separation of the unitary evolution into a classical
and a quantum part.

For the sum in Eq. (23) we get from Eq. (10) with $M\geq M^{\prime}$ in the
localized basis $\\{{\bf v}_{k}\\}$

$\lim_{t\to\infty}{\bar{P}}_{MM^{\prime}}(t)=\sum_{k=1}^{N}v_{kM}^{2}v_{kM^{\prime}}^{2}=\delta_{MM^{\prime}}\frac{(M-1)^{2}-1}{M^{2}}+\frac{1}{N^{2}}+\frac{1}{M^{2}}+\sum_{k=M+1}^{N}\frac{1}{k^{2}(k-1)^{2}}.$
(24)

The sum on the right-hand side gives a closed expression in terms of the
digamma function [26]. This result is not translational invariant because it
favors transitions to small values of $M,M^{\prime}$. Of course, this is a
consequence of the chosen basis of localized eigenvectors, which itself is not
translational invariant. But it can be made translational invariant by summing
up a permuted basis on the graph, rather than fixing a specific one. This
would remove the $M$–dependent terms and replace it by an average over all
positions on the graph.

In contrast to the localized basis, for the plane-wave basis we get in the
infinite-time limit a uniform transition probability:

$\lim_{t\to\infty}{\bar{P}}_{MM^{\prime}}(t)=\sum_{k=1}^{N}|w_{kM}|^{2}|w_{kM^{\prime}}|^{2}=\frac{1}{N},$
(25)

indicating a uniform distribution for the quantum walk at large times. This
reflects the result for $T_{M}$ in Eq. (20).

##  3 Discussion

According to Eq. (14), the unitary evolution matrix $U(t)$ can be expanded in
terms of its eigenbasis. The properties of this basis determine the range of
the evolution, i.e., which sites of the graph are connected by $U(t)$ during
the evolution. This can be realized by designing an appropriate quantum
circuit, enabling us to study the localized as well as delocalized regimes on
a quantum computer.

Averaging of the transition probability over a random distribution of
eigenvalues of $U(t)$, as described in Sect. 2.3, reveals two separate regimes
in the evolution. One is static and classical, while the other represents a
quantum walk with the average Hamiltonian (cf. Eq. (23)). They appear with
time-dependent weights, in which the contribution of the classic static part
becomes more important with increasing time. It means that the quantum effect
is suppressed in the long-time asymptotic under the average. This classical
limit reflects the distribution of the transition probabilities according to
their eigenbasis, as given in Eq. (24) for a localized basis and in Eq. (25)
for the plane-wave basis.

Instead of random scattering in the unitary evolution of a quantum walk, we
also considered the effect of repeated projective measurements on the quantum
walk in Sect. 2.2. The result of such a monitored evolution also depends
strongly on the properties of the underlying eigenbasis. The corresponding
evolution operator $T_{M}$, where $|{\bf r}_{M}\rangle$ is the projected state
in the measurement, is even more sensitive to the localization properties, as
reflected by the results in Eqs. (19), (20). In particular, the relation
$T_{M}^{m-1}{\bf x}=u_{1}^{m-1}{\bf x}$ for ${\bf x}=\sum_{k=2}^{M-1}x_{k}{\bf
v}_{k}$ implies a projection onto a subspace that is defined by the measured
state. This could be used to control and guide quantum walks inside a larger
Hilbert space by constructing proper Hamiltonians $H$ with the mapping
$\\{E_{k},{\bf v}_{k}\\}\to H$ in a localized basis.

###  3.1 Examples for the distribution of random eigenvalues

We consider the Gaussian distribution of the eigenvalues $\\{E_{k}\\}$

$\frac{1}{\cal
N}\prod_{k,k^{\prime}}e^{-\gamma_{kk^{\prime}}(E_{k}-{\bar{E}}_{k})(E_{k^{\prime}}-{\bar{E}}_{k^{\prime}})}\prod_{\bar{k}}dE_{\bar{k}}\
\ \ \ \ (-\infty<E_{k}<\infty)$ (26)

with the positive symmetric correlation matrix $\gamma$ and the normalization
${\cal N}\propto\det\gamma^{-1/2}$. This gives us

$p_{kk^{\prime}}(t)=\langle
e^{-i(E_{k}-E_{k^{\prime}})t}\rangle=e^{-(\gamma^{-1}_{kk}-\gamma^{-1}_{k^{\prime}k})t^{2}/2}e^{-i({\bar{E}}_{k}-{\bar{E}}_{k^{\prime}})t}.$
(27)

A constant part of the $k$ dependent average eigenvalues cancels in
${\bar{E}}_{k}-{\bar{E}}_{k^{\prime}}$ and only the dispersive part
contributes.

The uncorrelated limit is obtained from Eq. (27) when we assume a diagonal
matrix $\gamma$. Assuming that $\gamma^{-1}_{kk}$ is constant in $k$ with
$\gamma^{-1}_{kk}=\kappa$, this provides

$p_{kk^{\prime}}(t)=\cases{1&for $k^{\prime}=k$\cr e^{-\kappa
t^{2}/2-i({\bar{E}}_{k}-{\bar{E}}_{k^{\prime}})t}&for $k^{\prime}\neq k$\cr}.$
(28)

This means that the function $w(t)$ in the average return probability in Eq.
(23) reads in this case $w(t)=e^{-\kappa t^{2}/2}$.

A special example for a correlated distribution of the fluctuations
$x_{k}=E_{k}-{\bar{E}}_{k}$ is an attraction of eigenvalues with

$\sum_{k,k^{\prime}}x_{k}\gamma_{kk^{\prime}}x_{k^{\prime}}=\frac{1}{\kappa}\left[a\sum_{k}x_{k}^{2}+\frac{1}{2N}\sum_{k,k^{\prime}}(x_{k}-x_{k^{\prime}})^{2}\right]\
\ \ (a>0),$ (29)

which implies

$\gamma_{kk^{\prime}}=\frac{1}{\kappa}[(1+a)\delta_{kk^{\prime}}-1/N].$

Then the elements of the inverse correlation matrix read

$\gamma^{-1}_{kk^{\prime}}=\frac{\kappa}{1+a}\left(\delta_{kk^{\prime}}+\frac{1}{aN}\right)\
\ {\rm and}\ \gamma^{-1}_{kk}-\gamma^{-1}_{kk^{\prime}}=\frac{\kappa}{1+a}\ \
(k^{\prime}\neq k).$

Another example is a repulsion of eigenvalues with

$\sum_{k,k^{\prime}}x_{k}\gamma_{kk^{\prime}}x_{k^{\prime}}=\frac{1}{\kappa}\left[b\sum_{k}x_{k}^{2}-\frac{1}{2N}\sum_{k,k^{\prime}}(x_{k}-x_{k^{\prime}})^{2}\right]\
\ (b>1),$ (30)

which yields

$\gamma_{kk^{\prime}}=\frac{1}{\kappa}[(b-1)\delta_{kk^{\prime}}+1/N]$

and the elements of the inverse correlation matrix

$\gamma^{-1}_{kk^{\prime}}=\frac{\kappa}{(b-1)}\left(\delta_{kk^{\prime}}-\frac{1}{Nb}\right)\
\ {\rm and}\ \gamma^{-1}_{kk}-\gamma^{-1}_{kk^{\prime}}=\frac{\kappa}{b-1}\ \
(k^{\prime}\neq k).$

Then we get from Eq. (27) for attractive eigenvalues

$p_{kk^{\prime}}(t)=\cases{1&for $k^{\prime}=k$\cr e^{-\kappa
t^{2}/2(1+a)-i({\bar{E}}_{k}-{\bar{E}}_{k^{\prime}})t}&for $k^{\prime}\neq
k$\cr}$ (31)

and for repulsive eigenvalues

$p_{kk^{\prime}}(t)=\cases{1&for $k^{\prime}=k$\cr e^{-\kappa
t^{2}/2(b-1)-i({\bar{E}}_{k}-{\bar{E}}_{k^{\prime}})t}&for $k^{\prime}\neq
k$\cr},$ (32)

which is similar to the uncorrelated result in Eq. (28). In particular, for
all examples the off-diagonal part of $p_{kk^{\prime}}(t)$ decays with time,
such that in the end the walker is distributed over the graph ${\cal G}$
according to Eq. (24) for a localized eigenbasis or according to Eq. (25) for
a plane-wave eigenbasis. For finite values of $t$ there is scaling with the
variable $\kappa t^{2}$, where a smaller $\kappa$ means smaller fluctuations
of the eigenvalues. With these results for $p_{kk^{\prime}}(t)$ we return to
the average transition probability of Eq. (23) and insert the new weight
functions $w(\kappa t^{2})$. Thus, Gaussian random scattering results in a
fast decay of the weight of the quantum term in $\langle
P_{MM^{\prime}}(t)\rangle$ that is supported by increasing fluctuations.
Therefore, in order to describe a realistic situation, either a finite $t$ or
a time average by integrating over all times should be considered. Finally, in
the degenerate case ${\bar{E}}_{k}={\bar{E}}=const.$ we get strict
localization of the quantum term in
${\bar{P}}_{MM^{\prime}}(t)=\delta_{MM^{\prime}}$. This indicates that a
degenerate average Hamiltonian reproduces an unphysical result similar to that
observed for the Hamiltonian in Eq. (5).

##  4 Conclusions

We suggest an approach, based on the mapping from a given set of eigenvalues
and eigenvectors to the evolution operator $\\{{\bf x}_{k},E_{k}\\}\to
U(\tau)$, to construct a quantum walk model. This is an alternative to the
usual mapping from a given Hamiltonian to the eigenvalues and eigenvectors
$H\to\\{{\bf x}_{k},E_{k}\\}$. It provides a more direct insight into the
properties of the quantum walk and avoids the costly calculation of the
eigenvectors and eigenvalues of $H$. As demonstrated in Sects. 2.2 and 2.3,
this approach reveals how the localization properties of the unitary and the
monitored evolution can be controlled by designing the Hamiltonian. In
particular, it is found that the localization effects due to repeated
measurements are stronger than those under random scattering in the unitary
evolution. This approach offers a concept for the design, for instance, of
quantum circuits. It can be extended by introducing a random basis, consisting
of a mixture of localized and delocalized eigenvectors or random-time
measurements [27, 28].

## References

  * [1] Karl Pearson.  The problem of the random walk.  Nature, 72(1865):294–294, Jul 1905.
  * [2] J. Klafter and I. M. Sokolov.  First Steps in Random Walks: From Tools to Applications.  Oxford University Press, 08 2011.
  * [3] Edward A. Codling, Michael J. Plank, and Simon Benhamou.  Random walk models in biology.  Journal of the Royal Society interface, 5(25):813–834, AUG 6 2008\.
  * [4] GH Weiss and RJ Rubin.  Random-walks - theory and selected applications.  Advances in Chemical Physics, 52:363–505, 1983.
  * [5] J. Glimm and A. Jaffe.  Quantum Physics: A Functional Integral Point of View.  Springer New York, 2012.
  * [6] Claude Itzykson and Jean-Michel Drouffe.  From Brownian motion to Euclidean fields, volume 1 of Cambridge Monographs on Mathematical Physics, page 1–47.  Cambridge University Press, 1989.
  * [7] Frank Spitzer.  Principles of Random Walk, volume 34 of Graduate Texts in Mathematics.  Springer, 1964.
  * [8] Manfred Gilli, Dietmar Maringer, and Enrico Schumann.  Numerical Methods and Optimization in Finance (Second Edition).  Academic Press, second edition edition, 2019.
  * [9] Z. Burda, J. Duda, J. M. Luck, and B. Waclaw.  Localization of the maximal entropy random walk.  Phys. Rev. Lett., 102:160602, Apr 2009.
  * [10] Y. Aharonov, L. Davidovich, and N. Zagury.  Quantum random walks.  Phys. Rev. A, 48:1687–1690, Aug 1993.
  * [11] Vivien M. Kendon and Christina Tamon.  Perfect state transfer in quantum walks on graphs.  JOURNAL OF COMPUTATIONAL AND THEORETICAL NANOSCIENCE, 8(3):422–433, MAR 2011.
  * [12] Salvador Elias Venegas-Andraca.  Quantum walks: a comprehensive review.  QUANTUM INFORMATION PROCESSING, 11(5, SI):1015–1106, OCT 2012.
  * [13] Yutaka Shikano.  From discrete time quantum walk to continuous time quantum walk in limit distribution.  JOURNAL OF COMPUTATIONAL AND THEORETICAL NANOSCIENCE, 10(7, SI):1558–1570, JUL 2013.
  * [14] Karuna Kadian, Sunita Garhwal, and Ajay Kumar.  Quantum walk and its application domains: A systematic review.  COMPUTER SCIENCE REVIEW, 41, AUG 2021.
  * [15] J Kempe.  Quantum random walks: an introductory overview.  CONTEMPORARY PHYSICS, 44(4):307–327, JUL-AUG 2003.
  * [16] Oliver Mülken and Alexander Blumen.  Continuous-time quantum walks: Models for coherent transport on complex networks.  Physics Reports, 502(2):37–87, 2011.
  * [17] Debraj Das and Shamik Gupta.  Quantum random walk and tight-binding model subject to projective measurements at random times.  Journal of Statistical Mechanics: Theory and Experiment, 2022(3):033212, mar 2022.
  * [18] Andrew M. Childs.  Universal computation by quantum walk.  Phys. Rev. Lett., 102:180501, May 2009.
  * [19] M. J. Cantero, F. A. Gruenbaum, L. Moral, and L. Velazquez.  One-dimensional quantum walks with one defect.  REVIEWS IN MATHEMATICAL PHYSICS, 24(2), MAR 2012.
  * [20] Rostislav Duda, Moein N. Ivaki, Isac Sahlberg, Kim Pöyhönen, and Teemu Ojanen.  Quantum walks on random lattices: Diffusion, localization, and the absence of parametric quantum speedup.  Phys. Rev. Res., 5:023150, Jun 2023.
  * [21] F. A. Grünbaum, L. Velázquez, A. H. Werner, and R. F. Werner.  Recurrence for discrete time unitary evolutions.  Communications in Mathematical Physics, 320(2):543–569, Jun 2013\.
  * [22] Shrabanti Dhar, Subinay Dasgupta, and Abhishek Dhar.  Quantum time of arrival distribution in a simple lattice model.  Journal of Physics A: Mathematical and Theoretical, 48(11):115304, feb 2015.
  * [23] H Friedman, D A Kessler, and E Barkai.  Quantum renewal equation for the first detection time of a quantum walk.  Journal of Physics A: Mathematical and Theoretical, 50(4):04LT01, dec 2016.
  * [24] Quancheng Liu, Klaus Ziegler, David A. Kessler, and Eli Barkai.  Driving quantum systems with periodic conditional measurements.  Phys. Rev. Research, 4:023129, May 2022.
  * [25] Quancheng Liu and Klaus Ziegler.  Entanglement of bosonic systems under monitored evolution; arxiv:2403.06297, 2024.
  * [26] Milton Abramowitz and Irene A. Stegun.  Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables.  Dover Publications, Inc., New York, ninth dover printing, tenth gpo printing edition, 1964.
  * [27] K Ziegler, E Barkai, and D Kessler.  Randomly repeated measurements on quantum systems: correlations and topological invariants of the quantum evolution.  Journal of Physics A: Mathematical and Theoretical, 54(39):395302, sep 2021.
  * [28] David A. Kessler, Eli Barkai, and Klaus Ziegler.  First-detection time of a quantum state under random probing.  Phys. Rev. A, 103:022222, Feb 2021.


EXTREMA OF LUROTH DIGITS AND A ZETA FUNCTION LIMIT RELATIONS
Jayadev S. Athreya111Supported by National Science Foundation Grant DMS
2003528
Department of Mathematics and Department of Comparative History of Ideas,
University of Washington, Seattle, WA, USA.
<EMAIL_ADDRESS>
Krishna B. Athreya
Department of Mathematics and Department of Statistics, Iowa State University,
Ames, IA, USA.
<EMAIL_ADDRESS>

Received: , Revised: , Accepted: , Published:

Abstract

We describe how certain properties of the extrema of the digits of Luroth
expansions lead to a probabilistic proof of a limiting relation involving the
Riemann zeta function and the Bernoulli triangles. We also discuss trimmed
sums of Luroth digits. Our goal is to show how direct computations in this
case lead to formulas and some interesting discussions of special functions.

##  1 Introduction

Let $X_{1},X_{2},\ldots X_{k},\ldots$ be a sequence of independent,
identically distributed (IID) random variables taking values in the positive
integers $\mathbb{N}=\\{1,2,3,\ldots\\}$ with

$P(X_{1}=n)=\frac{1}{n(n+1)},n\geq 1.$

We call this distribution the _Luroth_ distribution. The _Luroth map_
$L:(0,1]\rightarrow(0,1]$ is the piecewise-linear map given by

$L(x)=N(x)((N(x)+1)x-1),$

where

$N(x)=\left\lfloor\frac{1}{x}\right\rfloor.$

It is a nice exercise to check that $L$ preserves Lebesgue measure $m$, and
that if $U$ is a uniform $(0,1]$ random variable, the sequence
$X_{k}=N(L^{k-1}(U))$ is a sequence of IID random variables with the above
distribution, since

$P(X_{1}=n)=m\left(N^{-1}(n)\right)=m\left(\frac{1}{n+1},\frac{1}{n}\right]=\frac{1}{n(n+1)}.$

This map and its associated digit expansion was introduced by Luroth in [9].
Subsequently, Luroth random variables have been extensively studied, since
they provide an attractive motivating example at the intersection of many
questions on number theory, probability theory, and dynamical systems and
ergodic theory. The Luroth map is in some sense a kind of linearized version
of the Gauss map (see Section 4), where, as we remark above, the resulting
digit expansion of numbers have the appealing property that the digits are
_independent_ random variables.

This makes it often possible to do very explicit computations with Luroth
random variables. See [8] for an introduction to the ergodic properties of the
map $L$, [6] for a discussion of different types of digit expansions, and, for
example [7] and [12] and the references within for more recent work on Luroth
and related expansions from the probabilistic and dynamical perspectives
respectively.

Our results center on understanding the limiting behavior of _maxima_ of
sequences of IID Luroth random variables, and the convergence behavior of
appropriately centered and scaled sums. These are classical topics in the
theory of sequences of random variables, and focusing on this setting leads to
some interesting computations.

Using the fact that the Luroth random variables are _heavy-tailed_ , we will
show that the probability $\rho_{k}$ that the maximum $M_{k}$ of the first $k$
elements $\\{X_{1},\ldots,X_{k}\\}$ of a a sequence of Luroth variables is
_unique_ tends to $1$ as $k\rightarrow\infty.$ Our main new result, Theorem 1,
shows how to _explicitly_ compute this probability $\rho_{k}$, giving an
interesting relationship between this probability, the Riemann zeta function,
and partial sums of binomial coefficients which are entries in what is known
as Bernoulli’s triangle. Using the fact that $\rho_{k}\rightarrow 1$, we
obtain a new limiting relation, Corollary 1, between these coefficients and
the Riemann zeta function.

Our other main result considers the behavior of the sample sums

$S_{k}=\sum_{i=1}^{k}X_{i}.$

Since $E(X_{1})=\infty$, the law of large numbers shows that $S_{k}/k$ tends
to infinity with probability one. Inspired by work of Diamond-Vaaler, who
studied the corresponding _trimmed sum_ for continued fraction expansions, and
using a result of Mori [10] we show in Theorem 2 that by removing the maximum,
and normalizing by $k\log k$, we have, with probability $1$, as
$k\rightarrow\infty$,

$\frac{S_{k}-M_{k}}{k\log k}\rightarrow 1.$

Note that the asymptotic uniqueness result says that asymptotically, we are
removing the _unique_ largest summand in $S_{k}$ by subtracting $M_{k}$. Let

$M_{k}=\max(X_{1},\ldots,X_{k})$

be the sample maximum, and let

$\rho_{k}=P(\mbox{ there exists }!1\leq i\leq k\mbox{ such that }X_{i}=M_{k})$

be the probability that this maximum is achieved exactly once. Our first main
observation is the following explicit formula for $\rho_{k}$.

######  Theorem 1.

For $k\geq 1$,

$\rho_{k}=k\left(2^{k-1}+\sum_{j=2}^{k}T(k-1,k-j)\zeta(j)(-1)^{j+1}\right),$
(1)

where $\zeta(j)=\sum_{n=1}^{\infty}n^{-j},j>1$ is the Riemann zeta function
and for $l\geq j$ positive integers,

$T(l,j)=\sum_{i=0}^{j}\binom{l}{i}.$

By [1, 5], we have

$\lim_{k\rightarrow\infty}\rho_{k}=1.$

Thus, as a corollary, we obtain the following limiting relation involving the
coefficients $T(l,j)$ and values of the Riemann zeta function.

######  Corollary 1.

We have

$\lim_{k\rightarrow\infty}k\left(2^{k-1}+\sum_{j=2}^{k}T(k-1,k-j)\zeta(j)(-1)^{j+1}\right)=1.$
(2)

The coefficients $T(l,j)$, partial sums of binomial coefficients, are entries
in what is known as _Bernoulli’s triangle_ ; see [11]. Note that $T(l,0)=1$,
$T(l,l)=2^{l}$, and $T(l,l-1)=2^{l}-1$. Let

$S_{k}=\sum_{i=1}^{k}X_{i}$

be the sample sum. Since $E(X_{1})=\infty$, we have, by the strong law of
large numbers,

$\lim_{k\rightarrow\infty}\frac{S_{k}}{k}=+\infty.$

However, if we subtract the sample maximum, we have the following almost sure
result.

######  Theorem 2.

With probability $1$,

$\lim_{k\rightarrow\infty}\frac{S_{k}-M_{k}}{k\log k}=1.$

This is a consequence of a result of Mori [10]. The proof features a nice
appearance of the Lambert $W$-function. There is a (more difficult) analogous
result [4] for continued fraction digits, where the limiting value is $\log
2$. There are substantial additional difficulties in that setting since
continued fraction digits of a randomly chosen $x\in(0,1)$ do not form an IID
sequence.

##  2 Uniqueness of Maxima

Suppose $Y_{1},\ldots,Y_{k},\ldots$ is a sequence of IID $\mathbb{N}$-valued
random variables with

$P(Y_{1}=n)=p_{n}.$

Let

$\tau_{n}=\sum_{m\geq n}p_{m}=P(Y_{1}\geq n).$

Let $\rho_{k,m}$ denote the probability that the sample maximum
$M_{k}=\max(Y_{1},\ldots,Y_{k})=m$ and is achieved exactly once. Then

$\rho_{k,m}=kp_{m}(1-\tau_{m})^{k-1}.$

Note that $\rho_{k}$, the probability that the sample maximum $M_{k}$ is
achieved exactly once by $Y_{1},\ldots,Y_{k}$, is then given by

$\rho_{k}=\sum_{m=1}^{\infty}\rho_{k,m}.$

Also note that (although it is not a probability) we have

$\sum_{k=1}^{\infty}\rho_{k,m}=p_{m}\sum_{k=1}^{\infty}k(1-\tau_{m})^{k-1}=\frac{p_{m}}{\tau_{m}^{2}}.$

Specializing to Luroth sequences, we have $p_{m}=\frac{1}{m(m+1)}$ and
$\tau_{m}=\frac{1}{m}$. Thus

$\rho_{k,m}=\frac{k}{m(m+1)}\left(1-\frac{1}{m}\right)^{k-1}=k\frac{(m-1)^{k-1}}{m^{k}(m+1)}.$

Let

$Q_{k}(m)=\frac{1}{k}\rho_{k,m}=\frac{(m-1)^{k-1}}{m^{k}(m+1)}.$

Th next lemma shows how to expand $Q_{k}$ as a partial fraction.

######  Lemma 1.

We have

$Q_{k}(m)=2^{k-1}\left(\frac{1}{m}-\frac{1}{m+1}\right)+\sum_{j=2}^{k}T(k-1,k-j)(-1)^{j+1}\frac{1}{m^{j}}.$
(3)

###### Proof.

Note that

$T(k-1,0)=1,T(k-1,k-1)=2^{k-1},T(k-1,k-2)=2^{k-1}-1$

and

$Q_{k+1}(m)=\left(1-\frac{1}{m}\right)Q_{k}(m).$

Our proof proceeds by induction. For $k=1$, we have

$Q_{1}(m)=\rho_{1,m}=\frac{1}{m(m+1)}.$

The right hand side of Equation (3) for $k=1$ is

$2^{1-1}\left(\frac{1}{m}-\frac{1}{m+1}\right)=\frac{1}{m(m+1)},$

since the index of the sum starts at $j=2$, making the sum empty. Thus the
base case ($k=1$) is verified. We now assume that Equation (3) is true for
$k$, and we need to prove it for $k+1$. Let

$c(j,k)=(-1)^{j+1}T(k-1,k-j).$

Note that

$\displaystyle Q_{k+1}(m)$
$\displaystyle=\left(1-\frac{1}{m}\right)Q_{k}(m)=\left(1-\frac{1}{m}\right)\left(2^{k-1}\left(\frac{1}{m}-\frac{1}{m+1}\right)+\sum_{j=2}^{k}c(j,k)\frac{1}{m^{j}}\right)$
$\displaystyle=2^{k-1}\frac{1}{m(m+1)}-\frac{2^{k-1}}{m}\left(\frac{1}{m}-\frac{1}{m+1}\right)+\sum_{j=2}^{k}\left(\frac{c(j,k)}{m^{j}}-\frac{c(j-1,k)}{m^{j+1}}\right)$
$\displaystyle=2^{k}\frac{1}{m(m+1)}-\frac{(2^{k-1}-c(2,k))}{m^{2}}+\sum_{j=3}^{k+1}\frac{\left(c(j,k)-c(j-1,k)\right)}{m^{j}}.$

Now note that for $j\geq 2$,

$c(j,k)=c(j,k-1)-c(j-1,k-1)$

and

$c(k+1,k)=0,c(2,k)=1-2^{k-1},c(k,k)=(-1)^{k+1},c(1,k)=2^{k-1}.$

Plugging these into Equation (2), we have our result. ∎

###  2.1 Proof of Theorem 1

To prove Theorem 1, we note that

$\sum_{m=1}^{\infty}\frac{1}{m(m+1)}=1;\sum_{m=1}^{\infty}\frac{1}{m^{j}}=\zeta(j),j\geq
2.$

Using Lemma 1, and summing over $m$, we obtain Equation (1). To obtain
Corollary 1, it was shown in [1, 5] that

$\rho_{k}\rightarrow 1\mbox{ if and only if }p_{m}/\tau_{m}\rightarrow 0.$

In our setting, $\rho_{m}/\tau_{m}=\frac{1}{m+1}$, so the condition is
satisfied, and we obtain Corollary 1. In Figure 1, we show numerical values of
$\rho_{k}$ for $2\leq k\leq 40$ (note that $\rho_{1}=1$).

Figure 1: $\rho_{k}$ for $k=2$ to $k=40$.

##  3 Trimmed sums

In this section, we prove Theorem 2. We first note that using standard limit
theorems in probability theory, we can show that

$\frac{S_{k}-M_{k}}{k\log k}\xrightarrow{d}1.$

The random variables $X_{n}$ are in the domain of attraction of a _stable law_
of order $1$. Using [2, Theorem 11.2.3], we have

$\frac{S_{k}-k\log k}{k}\xrightarrow{d}C,$

where $C$ is a Cauchy random variable. Thus,

$\frac{S_{k}}{k\log k}=\left(\frac{1}{\log k}\frac{(S_{k}-k\log
k)}{k}+1\right)\xrightarrow{d}1.$

Next, note that for $c>0$,

$\lim_{k\rightarrow\infty}P\left(\frac{M_{k}}{k}<c\right)=\lim_{k\rightarrow\infty}\left(1-\frac{1}{ck}\right)^{k}=e^{-1/c}.$

Therefore

$\frac{M_{k}}{k\log k}\xrightarrow{d}0.$

Putting these together, we obtain

$\frac{S_{k}-M_{k}}{k\log k}\xrightarrow{d}1,$

and therefore we also have this convergence in probability.

To replace convergence in probability with almost sure convergence, we use a
result of Mori [10, Theorem 1], with, in his notation,

$r=1,A(x)=x\log x.$

Mori studies the behavior of the sample sums with the first $r$ largest terms
removed, normalized by $A(n)$, where $A$ is an absolutely continuous
increasing function such that there is an $0<\alpha<2$, with

$A(x)x^{-\frac{1}{\alpha}}\mbox{ increasing and
}\sup\frac{A(2x)}{A(x)}<\infty.$

Keeping our notation consistent with [10, Section 1], we write $A(x)=x\log x$,
and note that this is a non-decreasing absolutely continuous function, with
inverse function $B(x)=\frac{x}{W(x)}$, where $W(x)$ is the Lambert $W$
function, that is, the inverse of the function $we^{w}$. Putting

$\mathcal{F}(x)=P(X_{1}>x)=\frac{1}{\lfloor x\rfloor+1}$

and

$J_{2}=\int_{0}^{\infty}\mathcal{F}^{2}(x)dB^{2}(x)=\sum_{n=2}^{N}\frac{1}{n^{2}}\left(\frac{n^{2}}{W(n)^{2}}-\frac{(n-1)^{2}}{W(n-1)^{2}}\right),$

Mori’s result shows that if $J_{2}<\infty$, that almost surely

$\frac{S_{k}-M_{k}}{A(k)}-c_{k}\rightarrow 0,$

where

$c_{k}=\frac{k}{A(k)}E(X_{1}|X_{1}<A(k)).$

In our setting,

$c_{k}\sim\frac{k}{k\log k}\log(k\log k)\rightarrow 1\mbox{ as
}k\rightarrow\infty.$

So if we can show $J_{2}<\infty$, we have completed our proof of Theorem 2.
From [13], we see that for $x>>1$,

$W(x)=\log x-\log\log x+o(1).$

Note that

$dB^{2}(x)=2B(x)B^{\prime}(x)dx=\frac{x}{W(x)(W(x)+1)}dx.$

Thus we have

$J_{2}\leq\int_{1}^{\infty}\frac{2}{x^{2}}B(x)B^{\prime}(x)dx\sim
2\int_{1}^{\infty}\frac{1}{xW(x)(W(x)+1)}=2\left(\frac{1}{W(1)}\right).$

In particular, $J_{2}<\infty$. In Figure 2, we show the partial sums for
$J_{2}$.

Figure 2: Partial sums of
$\sum_{n=2}^{N}\frac{1}{n^{2}}\left(\frac{n^{2}}{W(n)^{2}}-\frac{(n-1)^{2}}{W(n-1)^{2}}\right)$,
$N=3,\ldots,1000$.

##  4 Continued Fractions

Similar questions can be asked for the _Gauss map_ $G:(0,1)\rightarrow(0,1)$,

$G(x)=\left\\{\frac{1}{x}\right\\},$

and the associated continued fraction expansion of a number $x\in[0,1)$.
Recall that for $x\in(0,1)$, we can set, for $n\geq 1$,

$a_{n}=a_{n}(x)=\left\lfloor\frac{1}{G^{n-1}(x)}\right\rfloor,$

and we can write

$x=\frac{1}{a_{1}+\frac{1}{a_{2}+\frac{1}{a_{3}+\ldots}}}.$

The probability measure $\mu_{G}$ given by

$d\mu_{G}(x)=\frac{1}{\log 2}\frac{dx}{1+x}$

is an absolutely continuous ergodic invariant measure for $G$, and as noted
after Theorem 2, Diamond and Vaaler [4] proved a similar result for the digits
$a_{n}$ for an $x$ chosen at random according to $\mu_{G}$. This is more
difficult than our setting since although the digits form a stationary
sequence, they are no longer IID. Regarding the uniqueness of sample maxima,
if we define

$\rho_{k}=\mu_{G}\left(x\in(0,1):\mbox{ there exists }!1\leq i\leq k\mbox{
such that }a_{i}(x)=\max_{1\leq j\leq k}a_{j}(x)\right),$

we conjecture that

$\lim_{k\rightarrow\infty}\rho_{k}=1.$

We believe this conjecture since although the sequence $\\{a_{i}\\}$ is not
IID, it is rapidly mixing, and the distribution of $a_{i}$ is heavy-tailed.
The Gauss map is associated in a natural way to geodesic flow on the modular
surface, and we believe similar results should also hold for other continued
fraction type expansions associated to geodesic flow on other hyperbolic
surfaces, for example, the Rosen continued fractions.

Acknowledgements. We thank Bruce Berndt, Alex Kontorovich, and Jeffrey
Lagarias for useful discussions. Lagarias pointed out to us some interesting
asymptotics involving binomial coefficients and zeta functions in [3, Theorem
2]. We thank Avanti Athreya, the anonyomous referee, and the Integers
Editorial Office for suggestions that greatly improved the exposition of the
paper. The first author thanks the National Science Foundation for its support
via grant NSF DMS 2003528. The first author is a faculty member at the
University of Washington, which is on the lands of the Coast Salish people,
and touches the shared waters of all tribes and bands within the Suquamish,
Tulalip and Muckleshoot nations.

## References

  * [1] J.S. Athreya and L. Fidkowski, Number theory, balls in boxes, and the asymptotic uniqueness of maximal discrete order statistics, Integers 0 (2000), #A3.
  * [2] K.B. Athreya and S.N.Lahiri, Measure Theory and Probability Theory, Springer-Verlag, New York, 2006.
  * [3] E. Bombieri and J. Lagarias, Complements to Li’s criterion for the Riemann hypothesis, J. Number Theory 77 (1999), 274-287.
  * [4] H. Diamond and J. Vaaler, Estimates for partial sums of continued fraction partial quotients, Pacific J. Math. 122 (1986), #1, 73-82.
  * [5] B. Eisenberg, G. Stengle, and G. Strang, The asymptotic probability of a tie for first place. Ann. Appl. Probab. 3 (1993), #3, 731-745.
  * [6] J. Galambos, Representations of real numbers by infinite series, Lecture Notes in Mathematics, 502, Springer-Verlag, Berlin-New York, 1976.
  * [7] R. Giuliano and M. Hadjikyriakou, Convergence for weighted sums of Lüroth type random variables, J. Math. Anal. Appl. 502 (2021), # 2.
  * [8] H. Jager, C. De Vroedt, Lüroth series and their ergodic properties, Indag. Math. (N.S.) 72 (1969), #1, 31-42.
  * [9] J. Lüroth, Ueber eine eindeutige Entwickelung von Zahlen in eine unendliche Reihe. Math. Ann. 21 (1883), #3, 411-423.
  * [10] T. Mori, Stability for sums of i.i.d. random variables when extreme terms are excluded. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 40 (1977), # 2, 159-167.
  * [11] Online Encyclopedia of Integer Sequences, A008949, `http://oeis.org/A008949`
  * [12] X. Tan and Z. Zhang, The relative growth rate for the digits in Lüroth expansions, C. R. Math. Acad. Sci. Paris 358 (2020), # 5, 557–562.
  * [13] `https://en.wikipedia.org/wiki/Lambert_W_function`