# Lifetime of Infrared Quantum Information in Qubits

Elyana Crowder  Jiahao Chen  Georgia Institute of Technology, Atlanta,
Georgia, United States  Dragomir Davidović  Georgia Institute of Technology,
Atlanta, Georgia, United States<EMAIL_ADDRESS>
(August 28, 2024)

###### Abstract

Clarifying the principles leading to complete decoherence is essential for
understanding information loss in black hole formation. We employ strictly
perturbative quantum master equations to compute the long-term decoherence
rate in infrared-divergent qubit dynamics. In moderately sub-Ohmic
dissipation, we find that this rate exceeds the Hubble’s constant, meaning
that infrared particles do not completely destroy quantum information at the
universe’s current age. Deep sub-Ohmic dissipation leads to infrared-divergent
recovery of quantum coherence.

Over the past decade, the notion of infrared quantum information (IQI) has
gained relevance in gauge theories and black hole formation fields [1, 2, 3,
4]. Including IQI in the theory, a single scattering event between point
charges can cause the complete decoherence of outgoing states, if the charges
start off in a quantum superposition of momentum states and interact over long
distances through Maxwellian electrodynamics [1]. Complete decoherence in
gravitational scattering can restore unitarity in Hawking radiation [5, 6],
resolving the long-standing paradox of black hole information loss [7]. IQI is
the entanglement between particles and photons or gravitons near zero
frequency (infrared) that are produced in the scattering.

It is well known in electrodynamics and gravity that the scattering cross-
sections found in the second or higher order Born approximations have
logarithmic infrared divergences. The leading divergences of different orders
in the coupling constant sum up to zero. This is known as the infrared
catastrophe. Only after accounting for radiation fields can these divergences
properly cancel out, resulting in nonzero cross-sections [8, 9]. On the other
hand, as the leading divergences are re-summed, the entanglement entropy of
the infrared bosons becomes infrared-finite, leading to total decoherence of
the asymptotic states. In Ref. [1], the timescale of the decoherence is not
given by the infinite-time approximation of the $S$-matrix. This letter aims
to lay the groundwork for this timescale within qubit dynamics.

The system under consideration is a two-level system that is connected to a
bath of linear harmonic oscillators. This is a type of the Pauli-Fierz model
[10] also known as the spin-boson model (SBM) [11]. It is the simplest matter-
field interaction model and has frequently been used to test field theoretical
concepts, see for instance Refs. [12, 13, 14]. Pure and relaxation-induced
dephasing are the primary forms of decoherence observed in the SBM [15] and
are of critical importance in quantum computing. However, the asymptotic
states of infrared-regular dynamics exhibit non-zero coherences (in the energy
eigenbasis of the isolated qubit) [16, 17, 18]. They are small, namely of the
order $O(\lambda^{2})$, where $\lambda$ represents the dimensionless coupling
constant that is proportional to the qubit-bath interaction Hamiltonian.
Complete decoherence of the qubit requires a perturbative breakdown in the
asymptotic states. This is clear by assuming the contradiction, that the
perturbative expansion of the asymptotic state in $\lambda^{2}$ is valid.
Then, in the fourth-order, the asymptotic coherences will receive a
contribution $O(\lambda^{4})$. Since this is significantly smaller than
$O(\lambda^{2})$, the coherence cannot reach zero.

There are two essential timescales in qubit dynamics, determined solely in
terms of the properties of the bath: the minimum relaxation time and the bath
correlation time ($\tau_{B}$) [19, 20]. In the case of Ohmic dissipation at
zero temperature, the latter displays a logarithmic infrared divergence; the
ground states also have this divergence [21]. In our recent paper we showed
that these divergences cancel out in the generator of the dynamics when
computed at the fourth power of $\lambda$ [22]. This resulted in nonzero
asymptotic coherences of order $O(\lambda^{2})$.

However, in the sub-Ohmic regime, both $\tau_{B}$ and the dynamics generator
diverge as power laws versus time [22]. While the qubit can sustain coherence
at limited time in this case [23], the presence of the divergence in the
dynamics suggests an unlimited number of infrared bosons are produced, and we
anticipate zero asymptotic coherence, the same as in Ref. [1]. For Ohmic
dissipation, Legget et al. showed that bath coupling completely eliminates
coherence at all times if $\lambda^{2}\geq 1/2$, while $\lambda^{2}<1/2$ was
at least a necessary condition for coherence [11]. The value $\lambda^{2}=1/2$
is called the Toulouse limit [24].

Phase transitions at finite coupling were the primary emphasis of previous
research in the SBM; for instance, refer to Refs. [23, 25, 26, 27]. Our focus
is on the transition into complete decoherence at arbitrarily weak coupling.
Additionally, this letter is unique since it uses a strictly perturbative
approach, (no resummation, dressing, or open-system methods such as
hierarchical equations or matrix-product operators), which enables the
examination of the qubit’s decoherence as it moves away from the Fock space
because of the production of infrared bosons. For general information on exit
from the Fock space, see the review article [28]. We shall demonstrate that as
the bath dispersion approaches Ohmic dissipation, an essential singularity in
the decoherence time emerges, dramatically slowing down the process of
reaching complete decoherence. The relation with the Toulouse limit and black
hole information loss will be discussed after Fig. 3 and at the end,
respectively.

The SBM Hamiltonian can be expressed as $H=H_{S}+H_{B}+H_{I}$. The isolated
qubit is represented by $H_{S}=-\Delta\sigma_{z}/2$, where $\Delta=1$, while
the bath is described by $H_{B}=\sum_{k}\omega_{k}b_{k}^{\dagger}b_{k}$. The
qubit-bath coupling is given by
$H_{I}=AB=A\sum_{k}g_{k}(b_{k}+b_{k}^{\dagger})$. The qubit coupling operator
$A$ will be expressed as $[\sigma_{x}\cos(\theta)+\sigma_{z}\sin(\theta)]/2$,
where $\sigma_{x,z}$ are the Pauli sigmas. In the paper, $\theta=\pi/16$ is
consistently used as an example of a generic qubit. We exclude specific
instances, such as unbiased ($\theta=0$) and pure dephasing ($\theta=\pi/2$)
limit, from our consideration. While these lack any asymptotic coherences,
they exhibit distinct symmetries and do not embody typical qubits. The $b_{k}$
operators represent the annihilation of bosons, while the $\omega_{k}$ values
correspond to their frequencies. The $g_{k}$ factors, which are real, serve as
form factors that couple to the continuous spectral density in the
thermodynamic limit. This can be seen in the formula as follows:

$J(\omega)=\pi\sum_{k}g_{k}^{2}\delta(\omega-\omega_{k})\mapsto
2\pi\lambda^{2}\omega_{c}^{1-s}\omega^{s}e^{-\frac{\omega}{\omega_{c}}}\Theta(\omega).$
(1)

Throughout the paper, we assume a temperature of 0 K. The Heaviside step
function is $\Theta(\omega)$ and the bath cut-off frequency is $\omega_{c}$.
The bath dispersion parameter is denoted by $s$. For values of $s$ between 0
and 1, the bath is sub-Ohmic. When $s$ equals 1, the bath is Ohmic. And for
values of $s$ greater than 1, the bath is super-Ohmic.

The system is initialized with the qubit in the excited state and the bath in
the vacuum state. In our most recent study, we established a method to
calculate the strict fourth-order generator of the time convolutionless master
equation for reduced dynamics (TCL4) [22]. This allows us to investigate the
reduced dynamics at previously impossible timescales. We established the
generator’s infrared divergence in the sub-Ohmic regime only. See Supplemental
Material [29] for relevant computational details, including references [14]
and [30].

Figure 1: (a) Excited state population ($\rho_{22}$) and coherence
[$\text{Re}(\rho_{12})$ and $\text{Im}(\rho_{12})$] versus time. Inset:
Coherence revival amplitude versus time. (b) The same as (a) on a much larger
timescale. The drop in coherence over time while the population is constant is
the key result. Inset: crossing of the time-averaged coherences at zero
(dashed light green and blue lines). $s=0.72$, $\Delta=1$, $\omega_{c}=10$,
$\theta=\pi/16$, $\lambda^{2}=0.05875$. All energies (times) are in units of
$\Delta$ ($1/\Delta$).

Figure 1 (a) shows the initial loss of the excited state population and the
coherence. The best fit to an exponential has a relaxation time of
$T_{1}=3.43$, which is consistent with $T_{1}=3.27$ calculated using the
Fermi-golden-rule rate

$\nu_{1}=\frac{1}{T_{1}}=2|A_{12}|^{2}J(\Delta).$ (2)

At this time, both the population and coherence approach a steady-like state,
with values of around 0.047 and 0.048. The ground state populations and
coherences in the second order Rayleigh-Schrödinger perturbation theory are
[22]

$\displaystyle\rho_{22}^{\prime}=-|A_{12}|^{2}S^{\prime}(-\Delta),$ (3)
$\displaystyle\rho_{12}^{\prime}=2A_{11}A_{12}\frac{S(-\Delta)-S(0)}{\Delta},$
(4)

where
$S(\omega)=(1/\pi)\mathcal{P}\int_{-\infty}^{\infty}d\omega^{\prime}\frac{J(\omega^{\prime})}{\omega-\omega^{\prime}}$
and $S^{\prime}(\omega)=dS/d\omega$. We have shown that these formulas also
apply to the asymptotic states in the second order in $\lambda$ [22]. The
respective values 0.0497 and 0.0415 align well with Fig. 1 (a).

The coherence does not come to a complete rest and continues to oscillate for
a significantly extended time. This recurrence is created by the master
equation’s dependence on the initial time, which is a non-Markovian effect
[31, 32]. The fourth order in $\lambda$ significantly enhances the oscillatory
time dependence of the master equation’s coefficients when compared to the
second-order master equation. See Eq. 22 and further details in Supplemental
Material [29]. The inset in Fig. 1 (a) shows a power law drop in the amplitude
of the recurrence over time.

Fig. 1 (b) shows the population and coherence over a very long timescale. The
main result is that the coherence strongly decreases while the population
remains remarkably stable. Thus, there is a negligibly weak energy exchange
between the qubit and the bath, while the decrease of the coherence implies
entanglement with the infrared bosons. The inset focuses on the point where
coherence becomes zero. Given the significant difference in coherence
recurrence between the inset in Fig. 1 (b) and the asymptotic coherence
provided by Eq. 4, we will consider the coarse-grained density matrix, e.g.,
we make the approximation

$\rho(t)\mapsto\rho_{cg}(t)=\frac{1}{T_{cg}}\int_{t-T_{cg}/2}^{t+T_{cg}/2}\rho(\tau)d\tau.$
(5)

where $T_{cg}=2\pi/\Delta$. The dashed lines in Fig. 1 (b) display the coarse-
grained coherence. We define the IQI dephasing rate as the reciprocal of
$T_{IQ}$, indicating the point where the time-averaged coherence reaches zero.

$\sigma(t)=-\text{Tr}[\rho_{cg}(t)\ln\rho_{cg}(t)]$, or the von-Neumann
entropy, peaks at $T_{IQ}$ and decreases beyond this point. This happens
because the population remains relatively constant while the magnitude of the
coherence increases versus time at $t>T_{IQ}$. Over a significantly extended
period of time, the coherence exceeds a value of one and the norm of the
density matrix diverges as time progresses. This holds true for any positive
value of $\lambda^{2}$ and implies that there exists a time constraint on the
accuracy of these findings. We cannot compute the dynamics perturbatively
beyond this time frame, hence we will cut-off the dynamics beyond $T_{IQ}$.
That is, $\rho_{cg}(t)$ is constant and diagonal beyond $T_{IQ}$. This cut-off
makes the dynamics consistent with Carney et al. [1]’s approach in their
infinite time $S$-matrix approximation, where they observe the absence of
coherence and the presence of finite entanglement entropy by summing up the
dominant divergences across all coupling constant orders. We shall return to
this point once we attain Eq. 8.

Figure 2:  (a) Excited state population ($\rho_{22}$) and coherence
[$\text{Re}(\rho_{12})$ and $\text{Im}(\rho_{12})$] versus time. (b) The same
as (a) on a much larger timescale. The oscillation period is less than the
image resolution. Dashed yellow line is the best fit of the envelope of
$\text{Im}(\rho_{12})$ to power law. $s=0.1$, $\Delta=1$, $\omega_{c}=10$,
$\theta=\pi/16$, and $\lambda^{2}=4.25\times 10^{-4}$.

Next, we investigate the dynamics in deeply sub-Ohmic regime with a value of
$s=0.1$. The usual relaxation and dephasing are depicted in Fig. 2 (a). The
best fit of $\rho_{22}(t)$ with an exponential function yields a value of
$\nu_{1}$ that is consistent with Eq. 2 in three significant digits, while the
quasi-asymptotic population and coherence are consistent with Eqs. 3 and 4 in
2 significant digits. The amplitude of the oscillations in the real part of
the coherence grows at above approximately $t=600$. Fig. 2 (b) illustrates the
behavior over a significantly longer timeframe. The coarse-grained coherence
crosses zero at $T_{IQ}=1.09\times 10^{6}$.

The main distinction between Figs. 1 and 2 lies in the fact that the coherence
revivals exhibit growth in the latter. The best fit of
$\max[\text{Im}\rho_{12}]$ with the function $ct^{k}$ results in $k=0.558$. A
closer look reveals that the population has minimal oscillations at time
$T_{IQ}$ compared to the coherence oscillations, suppressed by a factor of
$2.6\times 10^{3}$. This indicates that there is minimal energy transfer
between the qubit and the bath in the recurrence as well. As time approaches
infinity, the amplitude of the recurrences obtained by solving the TCL4 master
equation will diverge. We propose that the emission and subsequent absorption
of the infrared bosons stimulate the recurrence.

Next, we analyze the relationship between the decoherence rate,
$\omega_{IQ}=1/T_{IQ}$, and the variables $s$ and $\lambda^{2}$. Fig. 3 (a)
displays $\omega_{IQ}$ as a function of $\lambda^{2}$ while keeping $s$
constant. As the value of $s$ approaches one, the curve becomes almost
perpendicular to the x-axis. It demonstrates that $\omega_{IQ}$ decreases
drastically with decreasing coupling when the variable $s$ approaches a
critical threshold. By employing linear interpolation, we may derive the
relationship between $\lambda^{2}$ and $s$ while keeping $\omega_{IQ}$
constant. The results are represented in Fig. 3 (b). When shown on a
logarithmic scale, all data at a fixed $\omega_{IQ}$ extend on a straight line
to a single point at $s=1$.

The data in Fig. 3 can be reduced into a function with three independent
parameters, as follows:

$\omega_{IQ}=\omega_{0}\left(\lambda^{2}/\lambda_{c}^{2}\right)^{\frac{z}{1-s}}.$
(6)

The lines connecting the markers in Fig. 3 (b) represent the optimum fit, with
the parameters $\omega_{0}=6.29$, $\lambda_{c}^{2}=0.546$, and $z=1.95$. The
equation 6 shows an essential singularity versus $s$ at $s=1$. If $s=1$ and
$\lambda^{2}<\lambda_{c}^{2}$, $\omega_{IQ}=0$, indicating the qubit has
asymptotic coherence. However, if $s=1$ and $\lambda^{2}>\lambda_{c}^{2}$,
$\omega_{IQ}=\infty$. Then the qubit dynamics will be completely incoherent.
This is the scenario that Leggett et al. argued in Ref. [11]. Thus, we
attribute $s=1$ and $\lambda^{2}=\lambda_{c}^{2}$ to the Toulouse limit. For
the unbiased SBM with Ohmic dissipation, the limit is located at
$\lambda^{2}=1/(2\cos^{2}\frac{\pi}{16})=0.520$, which is very near
$\lambda_{c}^{2}$. In Fig. 3 (b), the Toulouse limit reassembles a quantum
critical point, because it generates a critical fan that spreads the values of
$s$ at any $\lambda^{2}$ over the full range of complete decoherence
timescales.

Figure 3: (a) IQI decoherence rate as a function of the coupling strength. The
legend shows the bath dispersion parameters $s$. The orange, black and yellow
lines represent Eq. 7 at $s=0.15,0.5,$ and $0.8$, respectively. (b)
Relationship between coupling strength and bath dispersion parameter for a
constant value of $\omega_{IQ}$. The symbols are derived from the solutions of
the TCL4-master equation. The lines connecting the points provide the best fit
to Eq. 6. $\Delta=1$, $\omega_{c}=10$, $\theta=\pi/16$.

To acquire a better understanding of $T_{IQ}$, we first average out the
oscillations of the TCL4 master equation in the Schrödinger picture, since
$T_{IQ}\gg 1/\Delta$. Then we apply the adiabatic approximation, since
$T_{IQ}\gg T_{1}$. The approximate solution for coherence is obtained as
described in the Supplementary Material [29],

$\displaystyle\frac{\rho_{12}(t)}{\rho_{12}^{\prime}}$
$\displaystyle=1-\frac{c_{s}\lambda^{2}|A_{12}|^{2}S^{\prime}(-\Delta)}{T_{1}[S(0)-S(-\Delta)]}(\omega_{c}t)^{1-s}+O(\lambda^{8}t^{2-2s})$
(7) $\displaystyle\underset{\frac{\omega_{c}}{\Delta}\to\infty}{\to}1-4\pi
c_{s}\lambda^{4}|A_{12}|^{4}\left(\frac{\omega_{c}^{2}t}{\Delta}\right)^{1-s}+O(\lambda^{8}t^{2-2s}),$
(8)

where $c_{s}=\frac{4\Gamma(s+1)}{1-s}\cos\frac{\pi s}{2}$. The orange, black,
and yellow lines in Fig. 3 (a) derived from Eq. 7 show considerable agreement
at small $\lambda^{2}$. In the scaling limit, Eq. 8 produces the scaling of
Eq. 6, but with the parameters $\omega_{0}=\omega_{c}^{2}/\Delta$,
$\lambda_{c}^{2}=\lim_{s\to 1^{-}}[1/(|A_{12}|^{2}\sqrt{4\pi c_{s}})]=0.450$,
and $z=2$. Although these numbers qualitatively coincide with the values
obtained from the numerical solution of the master equation, the adiabatic
approximation gets increasingly inaccurate as $s$ approaches zero or one.

The right-hand sides of Eqs. 7 and 8 do not depend on the diagonal elements of
$A$. This is because infrared bosons are emitted concurrently with the qubit
relaxation process. In contrast, the rate for a pure dephasing process is
entirely diagonal in $A$, e.g., $\propto\lambda^{2}(A_{11}-A_{22})^{2}$ [15].

The remainder in Eqs. 7 and 8 is speculative and based on our discovery that
the TCL2 equation lacks infrared divergence, but the TCL4 equation has one
diverging term [22]. Namely, we expect that the TCL6 master equation
contributes a subleading correction of order $O(\lambda^{6}t^{1-s})$. We also
propose that Eqs. 7 and 8 may indicate the start of a series whose sum is an
exponential, leading to complete decoherence and finite entropy at
$t\to\infty$, agreeing with the results of Carney at al.[1].

Figure 4:  The exponent in the recurrent coherences power law versus time. The
legend shows the bath dispersion parameters $s$. Inset: zoom into the regime
of small $s$ and $\lambda^{2}$. $\Delta=1$, $\omega_{c}=10$, $\theta=\pi/16$.

Now we explore the relationships between the coherence revivals and the
variables $s$ and $\lambda^{2}$. For every value of $\lambda^{2}$ and $s$ in
Fig. 3, we analyze the imaginary part of $\rho_{12}$ over time and fit the
envelopes of the oscillations using the function $ct^{k}$. (See the dashed
yellow line in Fig. 2 as an example.) Fig. 4 shows the exponent $k$ versus
$\lambda^{2}$ for fixed values of $s$. It can be observed that the value of
$k$ generally decreases as the coupling increases. At the lowest couplings for
each $s$, the exponent reaches zero somewhere in the range $0.4<s<0.45$. As
$s$ gets closer to $1$, $k$ goes to $-1$. Because $\omega_{IQ}$ has an
essential singularity versus $s$, (Eq. 6), the coherence recurrences are also
essentially suppressed at the IQI timescale. Thus, the coherence revivals
appear not to impede the process of complete decoherence.

The inset in Fig. 4 gives a more detailed look at the area up to $s=0$. As $s$
approaches 0, the curves become more perpendicular to the x-axis, similar to
the behavior in Fig. 4 (a) as $s$ approaches one. It demonstrates that the
coherence revivals diminish rapidly as the coupling increases near $s=0$. But,
overall, given suitably small coupling and $s$, coherence revivals grow with
time. This contradicts the notion that the SBM in a sub-Ohmic bath is fully
incoherent in the asymptotic limit.

For instance, we may compute $\omega_{IQ}$ in solid state qubits. When
$\lambda^{2}=10^{-3}$, it overestimates the current state of the art while
underestimating the fine structure constant. Given $\Delta\sim 1$ GHz and a
dispersion parameter of $s=0.5$, (determined for example by measuring the
exponent in the noise-spectrum), and a cutoff frequency of $\sim 10\Delta$, we
estimate $\omega_{IQ}\sim 10^{7}$ Hz. This is particularly interesting since
it may be experimentally accessible in today’s noisy quantum computers,
opening up new avenues for studying the phenomenon of IQI. However,
$\omega_{IQ}$ is highly sensitive to parameters, particularly when it comes to
the value of $s$. Assuming $s=0.82$, we find $\omega_{IQ}\sim 10^{-18}$ Hz,
which is on the order of the Hubble’s constant ($H_{0}$). With a value of
$s=0.95$, the calculation yields $\omega_{IQ}\sim 10^{-77}H_{0}$. This implies
that any qubit has not lost all quantum information yet. Although the
information loss in a black hole formation is incredibly large, ($10^{66}$
bits per square meter on the event horizon), it is difficult to explain on the
microscopic level using single qubits without considering the possibility of
moderate sub-Ohmic dissipation. However, this would be incompatible with the
Ohmic impedance of electromagnetic radiation. It is also possible that the
lifetime of IQI in electrodynamics is significantly shortened due to the
continuous spectrum of hard matter in contrast to qubit’s discrete spectrum.

In conclusion, we have determined the time scale of long-term decoherence in
the sub-Ohmic SBM. The decoherence rate shows an essential singularity when
the bath dispersion changes, leading to astronomically large decoherence time
in moderately sub-Ohmic dissipation. Further research will explore the effects
of finite temperatures. Our preliminary findings suggest complex behavior,
particularly the reemergence of coherence, which may be relevant in quantum
biology.

We acknowledge support from the School of Physics at the Georgia Institute of
Technology.

## References

  * Carney  _et al._ [2017] D. Carney, L. Chaurette, D. Neuenfeld, and G. W. Semenoff, Infrared quantum information, Physical Review Letters 119, 180502 (2017).
  * Strominger [2018] A. Strominger, Lectures on the infrared structure of gravity and gauge theory (2018), arXiv:1703.05448 [hep-th] .
  * Neill and Waalewijn [2019] D. Neill and W. J. Waalewijn, Entropy of a jet, Phys. Rev. Lett. 123, 142001 (2019).
  * Danielson  _et al._ [2023] D. L. Danielson, G. Satishchandran, and R. M. Wald, Killing horizons decohere quantum superpositions, Phys. Rev. D 108, 025007 (2023).
  * Hawking  _et al._ [2016] S. W. Hawking, M. J. Perry, and A. Strominger, Soft hair on black holes, Phys. Rev. Lett. 116, 231301 (2016).
  * Mirbabayi and Porrati [2016] M. Mirbabayi and M. Porrati, Dressed hard states and black hole soft hair, Phys. Rev. Lett. 117, 211301 (2016).
  * Hawking [1976] S. W. Hawking, Breakdown of predictability in gravitational collapse, Phys. Rev. D 14, 2460 (1976).
  * Bloch and Nordsieck [1937] F. Bloch and A. Nordsieck, Note on the radiation field of the electron, Phys. Rev. 52, 54 (1937).
  * Weinberg [1965] S. Weinberg, Infrared photons and gravitons, Phys. Rev. 140, B516 (1965).
  * Pauli and Fierz [1938] W. Pauli and M. Fierz, Zur theorie der emission langwelliger lichtquanten, Il Nuovo Cimento (1924-1942) 15, 167 (1938).
  * Leggett  _et al._ [1987] A. J. Leggett, S. Chakravarty, A. T. Dorsey, M. P. A. Fisher, A. Garg, and W. Zwerger, Dynamics of the dissipative two-state system, Rev. Mod. Phys. 59, 1 (1987).
  * Dereziński and Gérard [1999] J. Dereziński and C. Gérard, Asymptotic completeness in quantum in field theory: massive pauli–fierz hamiltonians, Reviews in Mathematical Physics 11, 383 (1999).
  * Bach  _et al._ [2000] V. Bach, J. Fröhlich, and I. M. Sigal, Return to equilibrium, Journal of Mathematical Physics 41, 3985 (2000).
  * De Roeck and Kupiainen [2013] W. De Roeck and A. Kupiainen, Approach to ground state and time-independent photon bound for massless spin-boson models, in  _Annales Henri Poincaré_ , Vol. 14 (Springer, 2013) pp. 253–311.
  * Weiss [2012] U. Weiss,  _Quantum Dissipative Systems_, 4th ed. (WORLD SCIENTIFIC, 2012) https://www.worldscientific.com/doi/pdf/10.1142/8334 .
  * Fleming and Cummings [2011] C. H. Fleming and N. I. Cummings, Accuracy of perturbative master equations, Phys. Rev. E 83, 031117 (2011).
  * Thingna  _et al._ [2012] J. Thingna, J.-S. Wang, and P. Hänggi, Generalized gibbs state with modified redfield solution: Exact agreement up to second order, The Journal of Chemical Physics 136, 194110 (2012), https://doi.org/10.1063/1.4718706 .
  * Trushechkin  _et al._ [2022] A. Trushechkin, M. Merkli, J. Cresser, and J. Anders, Open quantum system dynamics and the mean force gibbs state, AVS Quantum Science 4 (2022).
  * Mozgunov and Lidar [2020] E. Mozgunov and D. Lidar, Completely positive master equation for arbitrary driving and small level spacing, Quantum 4, 227 (2020), 1908.01095 .
  * Nathan and Rudner [2020] F. Nathan and M. S. Rudner, Universal lindblad equation for open quantum systems, Phys. Rev. B 102, 115109 (2020).
  * Spohn [1980] H. Spohn, Kinetic equations from hamiltonian dynamics: Markovian limits, Rev. Mod. Phys. 52, 569 (1980).
  * Crowder  _et al._ [2024] E. Crowder, L. Lampert, G. Manchanda, B. Shoffeitt, S. Gadamsetty, Y. Pei, S. Chaudhary, and D. Davidović, Invalidation of the bloch-redfield equation in the sub-ohmic regime via a practical time-convolutionless fourth-order master equation, Phys. Rev. A 109, 052205 (2024).
  * Bulla  _et al._ [2003] R. Bulla, N.-H. Tong, and M. Vojta, Numerical renormalization group for bosonic systems and application to the sub-ohmic spin-boson model, Physical review letters 91, 170601 (2003).
  * Toulouse [1970] G. Toulouse, Infinite-$u$ anderson hamiltonian for dilute alloys, Phys. Rev. B 2, 270 (1970).
  * Chin  _et al._ [2011] A. W. Chin, J. Prior, S. F. Huelga, and M. B. Plenio, Generalized polaron ansatz for the ground state of the sub-ohmic spin-boson model: An analytic theory of the localization transition, Physical review letters 107, 160601 (2011).
  * Otterpohl  _et al._ [2022] F. Otterpohl, P. Nalbach, and M. Thorwart, Hidden phase of the spin-boson model, Phys. Rev. Lett. 129, 120406 (2022).
  * Link  _et al._ [2024] V. Link, H.-H. Tu, and W. T. Strunz, Open quantum system dynamics from infinite tensor network contraction, Physical Review Letters 132, 200403 (2024).
  * Merkli [2006] M. Merkli, The ideal quantum gas, in  _Open Quantum Systems I: The Hamiltonian Approach_ (Springer, 2006) pp. 183–233.
  * Supplemental Material: Fourth-order time-convolutionless master equation [TCL4] Supplemental Material: Fourth-order time-convolutionless master equation (TCL4), .
  * Davies [1974] E. B. Davies, Markovian master equations, Comm. Math. Phys. 39, 91 (1974).
  * Breuer  _et al._ [2016] H.-P. Breuer, E.-M. Laine, J. Piilo, and B. Vacchini, Colloquium: Non-markovian dynamics in open quantum systems, Rev. Mod. Phys. 88, 021002 (2016).
  * de Vega and Alonso [2017] I. de Vega and D. Alonso, Dynamics of non-markovian open quantum systems, Rev. Mod. Phys. 89, 015001 (2017).


which means that $f_{0}=\psi_{d+1}$. Thus, only $f_{1}=f_{0}=\psi_{d+1}$ is
orthogonal to $\hat{\Psi}$, so $\hat{\Psi}$ must span the top-$d$ eigenspace.

Sufficiency: Suppose $\hat{\Psi}$ spans the top-$d$ eigenspace. For any
$f\in{\mathcal{F}}_{B}(\Gamma;\epsilon)$ such that $f=\sum_{i}u_{i}\psi_{i}$,
we have $\sum_{i}u_{i}^{2}\leq B^{2}$, and
$\sum_{i}\frac{1-\epsilon-\lambda_{i}}{\lambda_{i}}u_{i}^{2}\leq 0$. Let
$a=\sum_{i\geq d+1}u_{i}^{2}$ and $b=\sum_{i=1}^{d}u_{i}^{2}$. Then,
$a=\min_{w}\textnormal{err}(w^{\top}\hat{\Psi},f)$, and $a+b\leq B^{2}$. So we
have

$\displaystyle 0$
$\displaystyle\geq\sum_{i}\frac{1-\epsilon-\lambda_{i}}{\lambda_{i}}u_{i}^{2}\geq-\epsilon
b+\frac{1-\epsilon-\lambda_{d+1}}{\lambda_{d+1}}a\quad\left(\text{since
}\frac{1-\epsilon-\lambda}{\lambda}\text{ decreases with }\lambda\right)$
$\displaystyle\geq-\epsilon(B^{2}-a)+\frac{1-\epsilon-\lambda_{d+1}}{\lambda_{d+1}}a$
$\displaystyle=-\epsilon
B^{2}+(1-\epsilon)\frac{1-\lambda_{d+1}}{\lambda_{d+1}}a,$

which combined with the necessity part implies that
$\textnormal{err}({\hat{\Psi}};{\mathcal{F}}_{B}(\Gamma;\epsilon))=\frac{\epsilon}{1-\epsilon}\frac{\lambda_{d+1}}{1-\lambda_{d+1}}B^{2}$.
∎

##### Lemma 5.

Suppose there exists a constant $C>0$ such that
$\mathbb{E}_{P_{\mathcal{A}}}[g^{4}]\leq C^{2}\|g\|_{P_{\mathcal{A}}}^{2}$,
for all $g=w^{\top}\hat{\Phi}$ where $\|g\|_{P_{\mathcal{A}}}\leq 1$. Then,
for any $\delta>0$, it holds with probability at least $1-\delta$ that

$|\operatorname{Tr}({\hat{{\bm{G}}}}^{-1}{\hat{{\bm{F}}}})-\operatorname{Tr}({\bm{G}}^{-1}{\bm{F}})|\leq\left(2+\sqrt{2\log\frac{2}{\delta}}\right)\frac{C\kappa+\kappa^{2}}{\sqrt{N}}d.$

###### Proof.

Since multiplying an invertible $d\times d$ matrix to $\hat{\Phi}$ does not
change either $\operatorname{Tr}({\hat{{\bm{G}}}}^{-1}{\hat{{\bm{F}}}})$ or
$\operatorname{Tr}({\bm{G}}^{-1}{\bm{F}})$, for simplicity let us multiply
${\bm{G}}^{-1/2}$ to $\hat{\Phi}$, so that
$\langle\hat{\phi}_{i},\hat{\phi}_{j}\rangle_{P_{\mathcal{A}}}=\delta_{i,j}$
for all $i,j\in[d]$ (i.e. ${\bm{G}}={\bm{I}}$). Define
${\mathcal{F}}_{1}={\left\\{f\in{{\mathcal{H}}_{\Gamma}}\;\middle|\;\|f\|_{{{\mathcal{H}}_{\Gamma}}}\leq
1\right\\}}$. Its Rademacher complexity is given by

$\mathfrak{R}_{N}({\mathcal{F}}_{1})=\underset{x_{1},\cdots,x_{N}}{\mathbb{E}}\underset{\sigma_{1},\cdots,\sigma_{N}}{\mathbb{E}}\left[\sup_{f\in{\mathcal{F}}_{1}}\frac{1}{N}\sum_{k=1}^{N}\sigma_{k}f(x_{k})\right].$
(37)

By Mohri et al. (2018, Theorem 6.12), we have
$\mathfrak{R}_{N}({\mathcal{F}}_{1})\leq\kappa N^{-1/2}$. Moreover, by
Proposition 7, all $f\in{\mathcal{F}}_{1}$ satisfy $|f(x)|\leq\kappa$ for all
$x$. Thus, by Wainwright (2019, Theorem 4.10), for any $\delta>0$, with
probability at least $1-\delta/2$, it holds for all $f\in{\mathcal{F}}_{1}$
that

$\left|\frac{1}{N}\sum_{k=1}^{N}f(x_{k})-\mathbb{E}[f(X)]\right|\leq
2\mathfrak{R}_{N}({\mathcal{F}}_{1})+\kappa\sqrt{\frac{2}{N}\log\frac{2}{\delta}}\leq\left(2+\sqrt{2\log\frac{2}{\delta}}\right)\frac{\kappa}{\sqrt{N}}.$
(38)

Define matrix
${\bm{M}}={\hat{{\bm{G}}}}^{-1/2}{\hat{{\bm{F}}}}{\hat{{\bm{G}}}}^{-1/2}=(m_{i,j})_{i,j\in[d]}$.
$\|{\bm{M}}\|_{2}\leq 1$, so $\sum_{i=1}^{d}m_{i,j}^{2}\leq 1$ for all
$j\in[d]$. Consider $\operatorname{Tr}(({\bm{I}}-{\hat{{\bm{G}}}}){\bm{M}})$.
For any $j\in[d]$, we have

$(({\bm{I}}-{\hat{{\bm{G}}}}){\bm{M}})(j,j)=\left\langle\hat{\phi}_{j},\sum_{i=1}^{d}m_{i,j}\hat{\phi}_{i}\right\rangle_{{\hat{P}_{\mathcal{A}}}}-\left\langle\hat{\phi}_{j},\sum_{i=1}^{d}m_{i,j}\hat{\phi}_{i}\right\rangle_{{P_{\mathcal{A}}}}.$

Note that
$\left\|\sum_{i=1}^{d}m_{i,j}\hat{\phi}_{i}\right\|_{P_{\mathcal{A}}}\leq 1$,
so
$\left\|\hat{\phi}_{j}\left(\sum_{i=1}^{d}m_{i,j}\hat{\phi}_{i}\right)\right\|_{P_{\mathcal{A}}}^{2}\leq\sqrt{\mathbb{E}[\hat{\phi}_{j}^{4}]\mathbb{E}\left[\left(\sum_{i=1}^{d}m_{i,j}\hat{\phi}_{i}\right)^{4}\right]}\leq
C^{2}$, which means that
$C^{-1}\Gamma^{*}\left(\hat{\phi}_{j}\left(\sum_{i=1}^{d}m_{i,j}\hat{\phi}_{i}\right)\right)\in{\mathcal{F}}_{1}$.
So if Eqn. (38) holds, then for all $j\in[d]$, we have

$\displaystyle(({\bm{I}}-{\hat{{\bm{G}}}}){\bm{M}})(j,j)$
$\displaystyle=\left|\frac{1}{N}\sum_{k=1}^{N}\Gamma^{*}\left(\hat{\phi}_{j}\left(\sum_{i=1}^{d}m_{i,j}\hat{\phi}_{i}\right)\right)(x_{k})-\mathbb{E}\left[\Gamma^{*}\left(\hat{\phi}_{j}\left(\sum_{i=1}^{d}m_{i,j}\hat{\phi}_{i}\right)\right)(X)\right]\right|$
$\displaystyle\leq\left(2+\sqrt{2\log\frac{2}{\delta}}\right)\frac{C\kappa}{\sqrt{N}},$

which implies that

$\displaystyle\operatorname{Tr}\left({\hat{{\bm{G}}}}^{-1}{\hat{{\bm{F}}}}-{\hat{{\bm{F}}}}\right)=\operatorname{Tr}\left({\hat{{\bm{G}}}}^{-1/2}({\bm{I}}-{\hat{{\bm{G}}}}){\hat{{\bm{G}}}}^{-1/2}{\hat{{\bm{F}}}}\right)=\operatorname{Tr}\left(({\bm{I}}-{\hat{{\bm{G}}}}){\bm{M}}\right)\leq\left(2+\sqrt{2\log\frac{2}{\delta}}\right)\frac{C\kappa
d}{\sqrt{N}}.$

Next, define
${\mathcal{F}}_{2}={\left\\{f_{1}f_{2}\;\middle|\;f_{1},f_{2}\in{{\mathcal{H}}_{\Gamma}},\|f_{1}\|_{{\mathcal{H}}_{\Gamma}}\leq
1,\|f_{2}\|_{{\mathcal{H}}_{\Gamma}}\leq 1\right\\}}$. By Proposition 13
(proved after this lemma), we have
$\mathfrak{R}_{N}({\mathcal{F}}_{2})\leq\kappa^{2}N^{-1/2}$. And all
$f\in{\mathcal{F}}_{2}$ satisfy $|f(x)|\leq\kappa^{2}$ for all $x$ by
Proposition 7. So with probability at least $1-\delta/2$, we have for all
$f\in{\mathcal{F}}_{2}$,

$\left|\frac{1}{N}\sum_{k=1}^{N}f(x_{k})-\mathbb{E}[f(X)]\right|\leq
2\mathfrak{R}_{N}({\mathcal{F}}_{2})+\kappa^{2}\sqrt{\frac{2}{N}\log\frac{2}{\delta}}\leq\left(2+\sqrt{2\log\frac{2}{\delta}}\right)\frac{\kappa^{2}}{\sqrt{N}}.$
(39)

Note that $\|\hat{\psi}_{i}\|_{{\mathcal{H}}_{\Gamma}}\leq 1$. So under Eqn.
(39), we have for all $i,j\in[d]$,

$\left|\langle\hat{\psi}_{i},\hat{\psi}_{j}\rangle_{\hat{P}_{\mathcal{X}}}-\langle\hat{\psi}_{i},\hat{\psi}_{j}\rangle_{P_{\mathcal{X}}}\right|=\left|\frac{1}{N}\sum_{k=1}^{N}\hat{\psi}_{i}(x_{k})\hat{\psi}_{j}(x_{k})-\mathbb{E}[\hat{\psi}_{i}\hat{\psi}_{j}]\right|\leq\left(2+\sqrt{2\log\frac{2}{\delta}}\right)\frac{\kappa^{2}}{\sqrt{N}},$

which implies that
$\operatorname{Tr}\left({\hat{{\bm{F}}}}-{\bm{G}}^{-1}{\bm{F}}\right)=\operatorname{Tr}\left({\hat{{\bm{F}}}}-{\bm{F}}\right)\leq\left(2+\sqrt{2\log\frac{2}{\delta}}\right)\frac{\kappa^{2}d}{\sqrt{N}}$.

Finally, applying the union bound completes the proof. ∎

######  Proposition 13.

Let
${\mathcal{F}}_{2}={\left\\{f_{1}f_{2}\;\middle|\;f_{1},f_{2}\in{{\mathcal{H}}_{\Gamma}},\|f_{1}\|_{{\mathcal{H}}_{\Gamma}}\leq
1,\|f_{2}\|_{{\mathcal{H}}_{\Gamma}}\leq 1\right\\}}$. Then,
$\mathfrak{R}_{N}({\mathcal{F}}_{2})\leq\frac{\kappa^{2}}{\sqrt{N}}$.

###### Proof.

For any $h(x)=f_{1}(x)f_{2}(x)\in{\mathcal{F}}_{2}$, let
$f_{1}=\Gamma^{*}g_{1}$ and $f_{2}=\Gamma^{*}g_{2}$, where
$\|g_{1}\|_{P_{\mathcal{A}}}\leq 1$ and $\|g_{2}\|_{P_{\mathcal{A}}}\leq 1$.
Let $g_{1}=\sum_{i}u_{i}\phi_{i}$ and $g_{2}=\sum_{i}v_{i}\phi_{i}$. Let
${\bm{u}}=[u_{1},u_{2},\cdots]$ and ${\bm{v}}=[v_{1},v_{2},\cdots]$. Then,
$\|{\bm{u}}\|_{2}\leq 1$ and $\|{\bm{v}}\|_{2}\leq 1$. And we have
$f_{1}=\sum_{i}\lambda_{i}^{1/2}u_{i}\psi_{i}$, and
$f_{2}=\sum_{i}\lambda_{i}^{1/2}v_{i}\psi_{i}$.

For any $x\in{\mathcal{X}}$, let
$\Psi(x)=[\lambda_{1}^{1/2}\psi_{1}(x),\lambda_{2}^{1/2}\psi_{2}(x),\cdots]$.
Then, $f_{1}(x)={\bm{u}}^{\top}\Psi(x)$ and $f_{2}(x)={\bm{v}}^{\top}\Psi(x)$.
Denote $\Psi_{k}=\Psi(x_{k})$. Then, $\Psi_{k}^{\top}\Psi_{k}\leq\kappa^{2}$
for all $k\in[N]$. So for any $S=\\{x_{1},\cdots,x_{N}\\}$, the empirical
Rademacher complexity satisfies

$\displaystyle\hat{\mathfrak{R}}_{S}({\mathcal{F}}_{2})$
$\displaystyle\leq\underset{{\bm{\sigma}}}{\mathbb{E}}\left[\sup_{\|{\bm{u}}\|_{2}\leq
1,\|{\bm{v}}\|_{2}\leq
1}\left|\frac{1}{N}\sum_{k=1}^{N}\sigma_{k}{\bm{u}}^{\top}\Psi_{k}\Psi_{k}^{\top}{\bm{v}}\right|\right]$
$\displaystyle\leq\frac{1}{N}\underset{{\bm{\sigma}}}{\mathbb{E}}\left[\left\|\sum_{k=1}^{N}\sigma_{k}\Psi_{k}\Psi_{k}^{\top}\right\|_{2}\right]$
$\displaystyle\leq\frac{1}{N}\underset{{\bm{\sigma}}}{\mathbb{E}}\left[\left\|\sum_{k=1}^{N}\sigma_{k}\Psi_{k}\Psi_{k}^{\top}\right\|_{F}\right]$
$\displaystyle=\frac{1}{N}\underset{{\bm{\sigma}}}{\mathbb{E}}\left[\operatorname{Tr}\left(\left(\sum_{k=1}^{N}\sigma_{k}\Psi_{k}\Psi_{k}^{\top}\right)^{\top}\left(\sum_{l=1}^{N}\sigma_{l}\Psi_{l}\Psi_{l}^{\top}\right)\right)^{1/2}\right]$
$\displaystyle\leq\frac{1}{N}\sqrt{\underset{{\bm{\sigma}}}{\mathbb{E}}\left[\operatorname{Tr}\left(\sum_{k,l=1}^{N}\sigma_{k}\sigma_{l}\Psi_{k}\Psi_{k}^{\top}\Psi_{l}\Psi_{l}^{\top}\right)\right]}\qquad(\text{Jensen})$
$\displaystyle=\frac{1}{N}\sqrt{\operatorname{Tr}\left(\sum_{k,l=1}^{N}\mathbb{E}[\sigma_{k}\sigma_{l}]\Psi_{k}\Psi_{k}^{\top}\Psi_{l}\Psi_{l}^{\top}\right)}$
$\displaystyle=\frac{1}{N}\sqrt{\operatorname{Tr}\left(\sum_{k=1}^{N}\Psi_{k}\Psi_{k}^{\top}\Psi_{k}\Psi_{k}^{\top}\right)}$
$\displaystyle\leq\frac{1}{N}\sqrt{N\kappa^{4}}=\frac{\kappa^{2}}{\sqrt{N}}.$

Then, since
$\mathfrak{R}_{N}({\mathcal{F}}_{2})=\mathbb{E}_{S}[\hat{\mathfrak{R}}_{S}({\mathcal{F}}_{2})]$,
we obtain the result. ∎

##### Lemma 6.

Suppose $\hat{\phi}_{i}=\bar{\phi}_{i}$ for $i\in[d]$. Let
$\gamma_{{\bm{G}}}:=\lambda_{\max}({\bm{G}})/\lambda_{\min}({\bm{G}})$, which
is the condition number of ${\bm{G}}$. Then, for any $\delta>0$, both

$\sum_{j=1}^{d}\bar{\lambda}_{j}\geq\sum_{i=1}^{d}\lambda_{i}-\left(2+\sqrt{2\log\frac{2}{\delta}}\right)\frac{(\lambda_{d}^{-1}+1)\kappa^{2}}{\sqrt{N}}d$

and Eqn. (12) with $C=\kappa\bar{\lambda}_{d}^{-1}\gamma_{{\bm{G}}}^{1/2}$
hold simultaneously for
${\mathcal{H}}_{{\hat{\Psi}}}={\hat{{\mathcal{H}}}_{d}}$ with probability at
least $1-\delta$.

###### Proof.

Denote ${\bm{\Phi}^{*}_{d}}=[\phi_{1},\cdots,\phi_{d}]$ and
${\bar{\bm{\Phi}}^{*}_{d}}=[\bar{\phi}_{1},\cdots,\bar{\phi}_{d}]$. Let
${\bar{\bm{\Phi}}^{*}_{d}}={\bm{P}}{\bm{\Phi}^{*}}$, where ${\bm{P}}$ is a
matrix with $d$ rows. Observe that for any $g=\sum_{i}u_{i}\bar{\phi}_{i}$
such that $\|g\|_{P_{\mathcal{A}}}\leq 1$, we have
$g=\bar{\Gamma}\Gamma^{*}\left(\sum_{i}\bar{\lambda}_{i}^{-1}u_{i}\bar{\phi}_{i}\right)$.
Let ${\bm{u}}=(u_{1},\cdots,u_{d})$, then there is
$g={\bm{u}}^{\top}{\bar{\bm{\Phi}}^{*}_{d}}={\bm{u}}^{\top}{\bm{P}}{\bm{\Phi}^{*}}$,
so $\|{\bm{P}}^{\top}{\bm{u}}\|_{2}\leq 1$. Thus, we have
$\|\sum_{i}\bar{\lambda}_{i}^{-1}u_{i}\bar{\phi}_{i}\|_{P_{\mathcal{A}}}=\|{\bm{P}}^{\top}{\bm{D}}_{\bar{\lambda}^{d}}^{-1}{\bm{u}}\|_{2}=\|{\bm{P}}^{\top}{\bm{D}}_{\bar{\lambda}^{d}}^{-1}({\bm{P}}{\bm{P}}^{\top})^{-1}{\bm{P}}{\bm{P}}^{\top}{\bm{u}}\|_{2}$.

So we just need to show that
$\|{\bm{P}}^{\top}{\bm{D}}_{\bar{\lambda}^{d}}^{-1}({\bm{P}}{\bm{P}}^{\top})^{-1}{\bm{P}}\|_{2}\leq\bar{\lambda}_{d}^{-1}\gamma_{{\bm{G}}}^{1/2}$.
$\|{\bm{P}}^{\top}{\bm{D}}_{\bar{\lambda}^{d}}^{-1}({\bm{P}}{\bm{P}}^{\top})^{-1}{\bm{P}}\|_{2}$
is equal to the square root of the largest eigenvalue of
${\bm{P}}^{\top}{\bm{D}}_{\bar{\lambda}^{d}}^{-1}({\bm{P}}{\bm{P}}^{\top})^{-1}{\bm{D}}_{\bar{\lambda}^{d}}^{-1}{\bm{P}}$,
and by using two simple linear algebra exercises: (i)
$\lambda_{\max}({\bm{A}}{\bm{B}})\leq\lambda_{\max}({\bm{A}})\lambda_{\max}({\bm{B}})$
for positive definite matrices ${\bm{A}}$ and ${\bm{B}}$, and (ii)
${\bm{A}}{\bm{B}}$ and ${\bm{B}}{\bm{A}}$ share the same non-zero eigenvalues
(Sylvester’s Theorem), and the fact that ${\bm{G}}={\bm{P}}{\bm{P}}^{\top}$,
we can show that the largest eigenvalue of this matrix is at most
$\bar{\lambda}_{d}^{-2}\gamma_{{\bm{G}}}$.

Therefore, we have
$\|{\bm{P}}^{\top}{\bm{D}}_{\bar{\lambda}^{d}}^{-1}({\bm{P}}{\bm{P}}^{\top})^{-1}{\bm{P}}\|_{2}\leq\bar{\lambda}_{d}^{-1}\gamma_{{\bm{G}}}^{1/2}$,
which combined with $\|{\bm{P}}^{\top}{\bm{u}}\|_{2}\leq 1$ implies that
$\|\sum_{i}\bar{\lambda}_{i}^{-1}u_{i}\bar{\phi}_{i}\|_{P_{\mathcal{A}}}\leq\bar{\lambda}_{d}^{-1}\gamma_{{\bm{G}}}^{1/2}$.
By Proposition 7,
$|\Gamma^{*}\left(\sum_{i}\bar{\lambda}_{i}^{-1}u_{i}\bar{\phi}_{i}\right)(x)|\leq\kappa\bar{\lambda}_{d}^{-1}\gamma_{{\bm{G}}}^{1/2}$
for all $x$, so we have
$|\bar{\Gamma}\Gamma^{*}\left(\sum_{i}\bar{\lambda}_{i}^{-1}u_{i}\bar{\phi}_{i}\right)(a)|=|\int\Gamma^{*}\left(\sum_{i}\bar{\lambda}_{i}^{-1}u_{i}\bar{\phi}_{i}\right)(x)p(x|a)dx|\leq\kappa\bar{\lambda}_{d}^{-1}\gamma_{{\bm{G}}}^{1/2}$
for all $a$. This means that with
$C=\kappa\bar{\lambda}_{d}^{-1}\gamma_{{\bm{G}}}^{1/2}$, $g$ satisfies the
condition of Lemma 5. Therefore, with probability at least $1-\delta$, both
Eqn. (38) and Eqn. (39) hold and they lead to Eqn. (12).

Now let ${\bm{\Phi}^{*}_{d}}={\bm{Q}}{\bar{\bm{\Phi}}^{*}}$, where ${\bm{Q}}$
is a matrix with $d$ rows. Consider two matrices
${\bm{Q}}{\bm{Q}}^{\top},{\bm{Q}}{\bm{D}}_{\bar{\lambda}}{\bm{Q}}^{\top}\in\mathbb{R}^{d\times
d}$ where
${\bm{D}}_{\bar{\lambda}}={\textnormal{diag}}(\bar{\lambda}_{1},\bar{\lambda}_{2},\cdots)$,
for which we have

$({\bm{Q}}{\bm{Q}}^{\top})(i,j)=\langle\phi_{i},\phi_{j}\rangle_{\hat{P}_{\mathcal{A}}}\qquad\text{and}\qquad({\bm{Q}}{\bm{D}}_{\bar{\lambda}}{\bm{Q}}^{\top})(i,j)=\langle\Gamma^{*}\phi_{i},\Gamma^{*}\phi_{j}\rangle_{\hat{P}_{\mathcal{X}}}.$

We have
$(\langle\phi_{i},\phi_{j}\rangle_{P_{\mathcal{A}}})_{i,j\in[d]}={\bm{I}}$ and
$(\langle\Gamma^{*}\phi_{i},\Gamma^{*}\phi_{j}\rangle_{P_{\mathcal{X}}})_{i,j\in[d]}={\bm{D}}_{\lambda^{d}}:={\textnormal{diag}}(\lambda_{1},\cdots,\lambda_{d})$.
Moreover, for any $g={\bm{u}}^{\top}{\bm{\Phi}^{*}_{d}}$ such that
$\|g\|_{P_{\mathcal{A}}}\leq 1$, there is
$g=\Gamma\Gamma^{*}\left(\sum_{i}\lambda_{i}^{-1}u_{i}\phi_{i}\right)$, and
obviously
$\|\sum_{i}\lambda_{i}^{-1}u_{i}\phi_{i}\|_{P_{\mathcal{A}}}\leq\lambda_{d}^{-1}$.
Thus, we can show that for all $a$, $|g(a)|\leq\kappa\lambda_{d}^{-1}$, which
means that ${\bm{\Phi}^{*}_{d}}$ satisfies the fourth-moment control
assumption in Lemma 5 with $C^{\prime}=\kappa\lambda_{d}^{-1}$. So similar to
the proof of Lemma 5, for all ${\bm{u}}\in\mathbb{R}^{d}$ such that
$\|{\bm{u}}\|_{2}\leq 1$, we can show that

$\left|{\bm{u}}^{\top}({\bm{Q}}{\bm{Q}}^{\top}-{\bm{I}}){\bm{u}}\right|=\left|\left\langle{\bm{u}}^{\top}{\bm{\Phi}^{*}_{d}},{\bm{u}}^{\top}{\bm{\Phi}^{*}_{d}}\right\rangle_{{\hat{P}_{\mathcal{A}}}}-\left\langle{\bm{u}}^{\top}{\bm{\Phi}^{*}_{d}},{\bm{u}}^{\top}{\bm{\Phi}^{*}_{d}}\right\rangle_{{P_{\mathcal{A}}}}\right|\leq\left(2+\sqrt{2\log\frac{2}{\delta}}\right)\frac{\kappa^{2}\lambda_{d}^{-1}}{\sqrt{N}},$

which implies that $\|{\bm{Q}}{\bm{Q}}^{\top}\|_{2}\leq
1+\left(2+\sqrt{2\log\frac{2}{\delta}}\right)\frac{\kappa^{2}\lambda_{d}^{-1}}{\sqrt{N}}$
. It is easy to show that all non-zero eigenvalues of
${\bm{Q}}^{\top}{\bm{Q}}$ are also eigenvalues of ${\bm{Q}}{\bm{Q}}^{\top}$,
so $\|{\bm{Q}}^{\top}{\bm{Q}}\|_{2}\leq
1+\left(2+\sqrt{2\log\frac{2}{\delta}}\right)\frac{\kappa^{2}\lambda_{d}^{-1}}{\sqrt{N}}$.
Moreover, similar to the proof of Lemma 5, we can show that for all
$i,j\in[d]$,

$\displaystyle\left|\left({\bm{Q}}{\bm{Q}}^{\top}-{\bm{I}}\right)(i,j)\right|\leq\left(2+\sqrt{2\log\frac{2}{\delta}}\right)\frac{\kappa^{2}\lambda_{d}^{-1}}{\sqrt{N}};$
(40)
$\displaystyle\left|\left({\bm{Q}}{\bm{D}}_{\bar{\lambda}}{\bm{Q}}^{\top}-{\bm{D}}_{\lambda^{d}}\right)(i,j)\right|\leq\left(2+\sqrt{2\log\frac{2}{\delta}}\right)\frac{\kappa^{2}}{\sqrt{N}}.$
(41)

Let ${\bm{q}}_{i}$ be the $i$-th column of ${\bm{Q}}$. Then for all $i\in[d]$,
${\bm{q}}_{i}^{\top}{\bm{q}}_{i}\leq
1+\left(2+\sqrt{2\log\frac{2}{\delta}}\right)\frac{\kappa^{2}\lambda_{d}^{-1}}{\sqrt{N}}$.
And we also have
$\sum_{i=1}^{\infty}{\bm{q}}_{i}^{\top}{\bm{q}}_{i}=\operatorname{Tr}({\bm{Q}}^{\top}{\bm{Q}})=\operatorname{Tr}({\bm{Q}}{\bm{Q}}^{\top})\leq
d+\left(2+\sqrt{2\log\frac{2}{\delta}}\right)\frac{\kappa^{2}\lambda_{d}^{-1}d}{\sqrt{N}}$.
Thus, we have

$\displaystyle\sum_{i=1}^{d}\lambda_{i}-\left(2+\sqrt{2\log\frac{2}{\delta}}\right)\frac{\kappa^{2}}{\sqrt{N}}d\leq\operatorname{Tr}({\bm{Q}}{\bm{D}}_{\bar{\lambda}}{\bm{Q}}^{\top})=\operatorname{Tr}({\bm{D}}_{\bar{\lambda}}{\bm{Q}}^{\top}{\bm{Q}})$
$\displaystyle=\;$
$\displaystyle\sum_{i=1}^{\infty}\bar{\lambda}_{i}{\bm{q}}_{i}^{\top}{\bm{q}}_{i}=\sum_{j=1}^{\infty}\left(\sum_{i=1}^{j}{\bm{q}}_{i}^{\top}{\bm{q}}_{i}\right)(\bar{\lambda}_{j}-\bar{\lambda}_{j+1})$
$\displaystyle\leq\;$
$\displaystyle\sum_{i=1}^{d}\bar{\lambda}_{i}\left[1+\left(2+\sqrt{2\log\frac{2}{\delta}}\right)\frac{\kappa^{2}\lambda_{d}^{-1}}{\sqrt{N}}\right]\leq\sum_{i=1}^{d}\bar{\lambda}_{i}+\left(2+\sqrt{2\log\frac{2}{\delta}}\right)\frac{\kappa^{2}\lambda_{d}^{-1}d}{\sqrt{N}},$

which proves the assertion. ∎

##  Appendix G Proofs for Section 5

##### Example 1.

Consider ${\mathcal{X}}=\\{-1,1\\}^{d_{\mathcal{X}}}$, where each
$x\in{\mathcal{X}}$ is a vector of $-1$ and $1$ with length $d_{\mathcal{X}}$.
Let $p_{{\mathcal{X}}}$ be the uniform distribution over ${\mathcal{X}}$.
Consider a random masking augmentation, where for any $x\in{\mathcal{X}}$,
each coordinate $x^{i}$ is randomly masked to be $0$ with probability
$\alpha\in(0,1)$ independently, where $\alpha$ is the mask ratio ($0$ is the
[MASK] token). Then, $\kappa^{2}=(2-\alpha)^{d_{\mathcal{X}}}$.

###### Proof.

We know that $\kappa^{2}\geq\int\frac{p(a|x)^{2}}{p(a)}da$, and by symmetry,
the right-hand-side is the same for all $x$. Given an $a$, suppose $a$ has $r$
coordinates masked and $(d_{{\mathcal{X}}}-r)$ coordinates unmasked. Then,
there are $2^{r}$ possible $x$ that can be augmented to $a$. For each of these
$x$, $p(a|x)=\alpha^{r}(1-\alpha)^{d_{{\mathcal{X}}}-r}$. So $p(a)=\int
p(a|x)p(x)dx=2^{r-d_{{\mathcal{X}}}}\alpha^{r}(1-\alpha)^{d_{{\mathcal{X}}}-r}$.
Thus, we have

$\displaystyle\kappa^{2}$
$\displaystyle=\int\frac{p(a|x)^{2}}{p(a)}da=\sum_{r=0}^{d_{\mathcal{X}}}\binom{d_{\mathcal{X}}}{r}\frac{\alpha^{2r}(1-\alpha)^{2d_{{\mathcal{X}}}-2r}}{2^{r-d_{{\mathcal{X}}}}\alpha^{r}(1-\alpha)^{d_{{\mathcal{X}}}-r}}$
$\displaystyle=\sum_{r=0}^{d_{\mathcal{X}}}\binom{d_{\mathcal{X}}}{r}\alpha^{r}(2-2\alpha)^{d_{\mathcal{X}}-r}$
$\displaystyle=(\alpha+2-2\alpha)^{d_{\mathcal{X}}}=(2-\alpha)^{d_{\mathcal{X}}},$

which completes the proof. ∎

##### Example 2.

Consider a random block masking augmentation with ratio $\alpha$, which for
any $x\in{\mathcal{X}}$ masks $x^{i},x^{i+1},\cdots,x^{i+r-1}$ for a uniformly
random $i$, and $r=\lceil\alpha d_{{\mathcal{X}}}\rceil$. Then,
$\kappa^{2}\leq[2^{(1-\alpha)}]^{d_{{\mathcal{X}}}}$.

###### Proof.

For any $a$, we have
$p(a)=\frac{1}{d_{\mathcal{X}}-r+1}\frac{1}{2^{d_{\mathcal{X}}-r}}$, and
$p(a|x)=\frac{1}{d_{\mathcal{X}}-r+1}$ if $x$ can be augmented to $a$. So
there always is $\frac{p(a|x)}{p(a)}=2^{d_{\mathcal{X}}-r}\leq
2^{(1-\alpha)d_{\mathcal{X}}}$. Thus, we have $\kappa^{2}\leq
2^{(1-\alpha)d_{\mathcal{X}}}$. ∎

##### Example 3.

Consider random block masking $+$ flipping with ratio $\alpha$, where for any
$x\in{\mathcal{X}}$, first $x^{i},\cdots,x^{i+r-1}$ are masked to be $0$ for a
uniformly random $i$ and $r=\lceil\frac{\alpha}{2}d_{{\mathcal{X}}}\rceil$,
and then each remaining coordinate is randomly flipped sign ($1\rightarrow-1$
and $-1\rightarrow 1$) with probability $\frac{\alpha}{2}$ independently.
Then,
$\kappa^{2}\leq\left[(\alpha^{2}-2\alpha+2)^{(1-\alpha/2)}\right]^{d_{{\mathcal{X}}}}$.

###### Proof.

For any $a$, we have
$p(a)=\frac{1}{d_{\mathcal{X}}-r+1}\frac{1}{2^{d_{\mathcal{X}}-r}}$. Suppose
$a$ is augmented from $x$, and among the unmasked $(d_{\mathcal{X}}-r)$
coordinates, $a$ and $x$ have $k$ disagreeing coordinates. For a given $k$,
there are $(d_{\mathcal{X}}-r+1)\binom{d_{\mathcal{X}}-r}{k}$ possible $a$,
and we have
$p(a|x)=\frac{1}{d_{\mathcal{X}}-r+1}(\frac{\alpha}{2})^{k}(1-\frac{\alpha}{2})^{d_{\mathcal{X}}-r-k}$.
Thus, we have

$\displaystyle\int\frac{p(a|x)^{2}}{p(a)}da$
$\displaystyle=\sum_{k=0}^{d_{\mathcal{X}}-r}(d_{\mathcal{X}}-r+1)\binom{d_{\mathcal{X}}-r}{k}\frac{\frac{1}{(d_{\mathcal{X}}-r+1)^{2}}(\frac{\alpha}{2})^{2k}(1-\frac{\alpha}{2})^{2d_{\mathcal{X}}-2r-2k}}{\frac{1}{d_{\mathcal{X}}-r+1}\frac{1}{2^{d_{\mathcal{X}}-r}}}$
$\displaystyle=\sum_{k=0}^{d_{\mathcal{X}}-r}\binom{d_{\mathcal{X}}-r}{k}2^{d_{\mathcal{X}}-r}\left(\frac{\alpha^{2}}{4}\right)^{k}\left(1-\alpha+\frac{\alpha^{2}}{4}\right)^{d_{\mathcal{X}}-r-k}$
$\displaystyle=2^{d_{\mathcal{X}}-r}\left(\frac{\alpha^{2}}{4}+1-\alpha+\frac{\alpha^{2}}{4}\right)^{d_{\mathcal{X}}-r}$
$\displaystyle\leq\left(\alpha^{2}-2\alpha+2\right)^{d_{\mathcal{X}}-r}\leq\left(\alpha^{2}-2\alpha+2\right)^{(1-\alpha/2)d_{{\mathcal{X}}}},$

which completes the proof. ∎

##  Appendix H Experiment Details

This section contains the details of the experiments we conducted in Section
5.2.

###  H.1 Estimating the Augmentation Complexity of Masked Language Modeling

We estimate the $\kappa$ of four augmentations, namely Random masking, Block
masking, Random masking + Flipping, and Block masking + Flipping, on the
widely used NLP dataset wikipedia-simple. Since it is prohibitively expensive
to iterate over the entire dataset, we instead aim to estimate $\kappa$ with a
subset of the dataset. In our experiments, instead of estimating
$\sup_{x}{K_{X}}(x,x)$, we estimate its 99th percentile. This is because of
two reasons:

  1. (i)

$\sup_{x}{K_{X}}(x,x)$ is statistically impossible to estimate from a subset
of data without any extra assumptions on the distribution of ${K_{X}}(x,x)$.
This means that without iterating over the entire dataset, we cannot get a
finite confidence interval. The percentile, on the other hand, can be
estimated with a finite confidence interval via sampling regardless of the
distribution of ${K_{X}}(x,x)$, which is a well-known result in statistics
(Hahn & Meeker, 2011, Section 5.2).

  2. (ii)

Almost all real datasets contain outliers, i.e. samples that are very
different from the other samples. These samples will have a very large
${K_{X}}(x,x)$, because their augmentations rarely overlap with the
augmentations of other samples. Therefore, $\sup_{x}{K_{X}}(x,x)$ itself is
not really meaningful because it is too sensitive to outliers, and cannot show
how the augmentation works on most part of the population.

As a demonstration of (ii), the following is an example outlier in the
wikipedia-simple dataset,‡‡‡Dataset available at
huggingface.co/datasets/wikipedia. The index of the example outlier is 199562.
and it has a very large ${K_{X}}(x,x)$:

    Geroldsgrün is a municipality in Hof, Bavaria, Germany.

    Geography

    Boroughs

     Dürrenwaid
     Dürrenwaiderhammer
     Langenbachtal
     Langenau
     Langenbach
     Lotharheil
     Mühlleiten
     Geroldsgrün
     Geroldsreuth
     Großenreuth
     Hermesgrün
     Hertwegsgrün
     Hirschberglein
     Silberstein
     Steinbach
     Untersteinbach

    References

We can see that this sample is very different from a typical sample in the
dataset in that (a) It contains lots of German words while this is an English
dataset; (b) It mostly consists of individual words, while most other samples
are comprised of sentences and paragraphs. Such outliers are rare in the
dataset, but they result in a large ${K_{X}}(x,x)$. Therefore, we instead
estimate the $\beta$-th percentile of ${K_{X}}(x,x)$ for some $\beta$ close to
100. This is a more robust estimator that can be computed with a subset of
data.

Specifically, we sample $m=1000$ samples $x_{1},\cdots,x_{m}$ from the dataset
uniformly at random. The maximum length is set at $l=64$. For each $x_{i}$, we
estimate $\int\frac{p(x_{i}|a)}{p(x_{i})}p(a|x_{i})da$ via sampling $r=255$
i.i.d. augmentations from $p(a|x_{i})$ and computing the mean of
$\frac{p(x_{i}|a_{j})}{p(x_{i})}$. So it suffices to estimate $p(x_{i}|a_{j})$
and $p(x_{i})$. To do this, we leverage a bert-base-uncased, which is a bi-
directional language model. Then, we can estimate $p(x|a)$ for any $x$ and $a$
as follows: For a sample $x=[x^{(1)},\cdots,x^{(l)}]$ ($x^{(i)}$ is a token)
and its augmentation $a$, there is

$\log p\left(x\middle|a\right)=\log p\left(x^{(1)}\middle|a\right)+\log
p\left(x^{(2)}\middle|a,x^{(1)}\right)+\cdots+\log
p\left(x^{(l)}\middle|a,x^{(1)},\cdots,x^{(l-1)}\right).$

So we can estimate $\log p\left(x\middle|a\right)$ in an autoregressive
fashion: First estimate $\log p\left(x^{(1)}\middle|a\right)$, then replace
$a^{(1)}$ with $x^{(1)}$ and estimate $\log
p\left(x^{(2)}\middle|a,x^{(1)}\right)$, then replace $a^{(2)}$ with $x^{(2)}$
and estimate $\log p\left(x^{(3)}\middle|a,x^{(1)},x^{(2)}\right)$, and so on.
The bi-directionality of BERT is important for such estimation. To compute
$p(x)$, we set $a$ to be a fully masked sentence, and then compute
$p(x|a)=p(x)$.

First, we decide the percentile of ${K_{X}}(x,x)$ to report. In Figure 4, we
plot the histogram of $\log\left(\int\frac{p(x|a)}{p(x)}\hat{p}(a|x)da\right)$
estimated using the above method of random masking with mask ratio
$\alpha=0.15$ and $\alpha=0.4$. The red dashed lines indicate the $99^{th}$
percentile, and we can see that they cut the tail of the data while preserving
the bulk of the mass. Thus, we report the $99^{th}$ percentile for this
dataset.

Figure 4: Plots of $\log\left(\int\frac{p(x|a)}{p(x)}\hat{p}(a|x)da\right)$
for random masking. Left: $\alpha=0.15$; Right: $\alpha=0.4$.

We study four masking augmentations: Random masking (mask $r=\lceil\alpha
d_{\mathcal{X}}\rceil$ tokens uniformly at random), block masking (mask a
block of $r$ tokens uniformly at random), random masking and flipping (mask
$r/2$ tokens uniformly at random and then replace $r/2$ remaining tokens with
random tokens), and block masking and flipping (mask a block of $r/2$ tokens
uniformly at random and then replace $r/2$ remaining tokens with random
tokens). In standard BERT, the number of randomly replaced tokens is much
smaller than the number of masked tokens, but here we make them the same in
order to magnify their difference.

Table 1: 99th percentile of estimated $\log{K_{X}}(x,x)$ on wikipedia-simple. | Random Mask | Random Mask + Flip | Block Mask | Block Mask + Flip
---|---|---|---|---
$\alpha=0.05$ | 353.94 $\pm$ 4.63 | 350.99 $\pm$ 3.20 | 346.77 $\pm$ 4.47 | 350.46 $\pm$ 1.43
$\alpha=0.10$ | 348.45 $\pm$ 2.94 | 349.14 $\pm$ 1.15 | 339.86 $\pm$ 5.62 | 343.73 $\pm$ 5.76
$\alpha=0.15$ | 346.40 $\pm$ 1.94 | 342.77 $\pm$ 4.17 | 327.13 $\pm$ 2.33 | 336.81 $\pm$ 5.27
$\alpha=0.20$ | 339.03 $\pm$ 2.88 | 335.01 $\pm$ 2.65 | 313.90 $\pm$ 2.55 | 322.87 $\pm$ 3.55
$\alpha=0.30$ | 325.08 $\pm$ 2.35 | 312.21 $\pm$ 5.96 | 280.65 $\pm$ 1.87 | 302.60 $\pm$ 2.49
$\alpha=0.40$ | 307.00 $\pm$ 4.55 | 280.76 $\pm$ 0.71 | 254.40 $\pm$ 1.48 | 279.24 $\pm$ 4.59
$\alpha=0.50$ | 278.59 $\pm$ 2.46 | 241.59 $\pm$ 4.50 | 217.35 $\pm$ 2.81 | 240.73 $\pm$ 1.58
$\alpha=0.60$ | 250.01 $\pm$ 3.43 | 198.15 $\pm$ 4.01 | 187.60 $\pm$ 2.45 | 205.45 $\pm$ 2.63
$\alpha=0.70$ | 214.14 $\pm$ 0.88 | 151.58 $\pm$ 3.32 | 152.70 $\pm$ 1.60 | 164.48 $\pm$ 2.59
$\alpha=0.80$ | 160.24 $\pm$ 2.44 | 84.51 $\pm$ 2.35 | 113.86 $\pm$ 2.39 | 108.44 $\pm$ 1.43

In Table 1, we report the estimated 99th percentile of $\log{K_{X}}(x,x)$.
Each experiment is run five times with different random seeds, and we report
the average and standard deviation. We can see that:

  1. (i)

$\kappa$ decreases as $\alpha$ grows, showing that a stronger augmentation has
a lower complexity.

  2. (ii)

Random masking always has the highest complexity. Regarding the effect of
block masking and flipping, block masking has a greater effect when $\alpha$
is small and it makes the complexity lower, whereas flipping has a greater
effect when $\alpha$ is larger.

To conclude, as long as there is a way to estimate $\frac{p(x|a)}{p(x)}$ or
$\frac{p(a|x)}{p(a)}$, we can estimate $\kappa$ via sampling from the dataset.
Note that in our estimation, BERT is only used for estimating $p(x|a)$.
$\kappa$ itself is defined free of any model.

###  H.2 Analyzing the Effect of Augmentation on Downstream Performance

Our theoretical analysis implies that as long as Assumption 1 is satisfied, a
smaller $\kappa$, i.e. a stronger augmentation, leads to better
generalization. However, this does not mean that a stronger augmentation will
always lead to a better test performance of tighter generalization gap, due to
the following reasons:

  1. (i)

If the augmentation is too strong, then the model might have low training
performance. In the extreme case, if the sentences are 100% masked, then the
language model can learn nothing.

  2. (ii)

Stronger augmentations usually work better with larger models. For instance,
Wettig et al. (2023) demonstrated that large models with strong augmentations
can achieve higher performance than standard models and augmentations.
However, for small models, stronger augmentations can lead to lower
performance. One possible reason is that small models are not expressive
enough, but we conjecture that this is not the true cause since a Transformer
with a moderate size is already sufficiently complex. We conjecture that the
real reason lies in optimization, in that it would be harder for the optimizer
to find a point close to the global minima with a small model and a strong
augmentation. The big model, on the other hand, has more parameters and could
be easier to optimize in practice.

  3. (iii)

If the augmentation is too strong, then Assumption 1 will be violated, and our
results will not hold so that the generalization gap can be large.

We study the effect of the augmentation on two real NLP downstream tasks,
namely QNLI and SST-2. We study random masking with different mask ratios.
Unlike the experiments in Wettig et al. (2023) that applied the pretrained
encoder directly to downstream tasks, in our experiments we explicitly use the
average encoder Eqn. (7), which is estimated by sampling 16 augmentations for
each sample $x$ and then averaging their embeddings. We do, however, fine-tune
the encoder during downstream as people do in common practice, which has been
proven useful, §§§We find in our experiments that without fine-tuning, the
downstream classifiers cannot achieve meaningful training accuracy, merely
higher than 70% for a binary classification task. With the training accuracy
so low, there is no empirical generalization gap, and the test accuracy is
even higher than the training accuracy in many cases, so these results are not
meaningful. even though our theory does not analyze fine-tuning. We
acknowledge that there is a discrepancy between the theory and real practice,
which we aim to address in the future.

Details of our experiments:

  1. (i)

We train roberta-large models using the fast training recipe provided by
Wettig et al. (2023). For $\alpha\geq 0.15$, we directly use the Huggingface
checkpoints they provide. For $\alpha=0.05,0.10$, we pretrain new encoders
using their source code¶¶¶https://github.com/princeton-nlp/DinkyTrain without
any modification. Note that these models use pre-layer normalization (see the
original github repository regarding this detail). We use 8 NVIDIA A6000 GPUs
for pretraining.

  2. (ii)

For downstream fine-tuning and evaluation, we use the official repository
provided by
Huggingface.∥∥∥https://github.com/huggingface/transformers/tree/main/examples/pytorch/text-
classification The only modification we make is that we explicitly use the
average encoder. The classifiers are trained for 3 epochs on QNLI and 6 epochs
on SST-2. All hyperparameters are kept the same as the official repository. We
use 4 NVIDIA A6000 GPUs for downstream training and evaluation.

The results are plotted in Figure 3(c) in Section 5.2. As discussed there, the
“sweet spot” where the model achieves the highest test performance is in the
middle, where the augmentation is strong enough to have good generalization,
yet not too strong to break Assumption 1 or to make the training performance
too low.


# Blocking Probability in Obstructed Tunnels with Reconfigurable Intelligent
Surface

Changshan Chen, , Cunhua Pan C. Chen is with the School of Information
Engineering (School of Big Data), Xuzhou University of Technology, Xuzhou
221018, China (e-mail: cschen@xzit.edu.cn). C. Pan is with the School of
Electronic Engineering and Computer Science at Queen Mary University of
London, London E1 4NS, U.K. (e-mail: c.pan@qmul.ac.uk). (Corresponding author:
Cunhua Pan.)

###### Abstract

In the obstructed tunnels, the signal transmission will suffer the risk of
ray-path blocking caused by the obstacles owing to the Snell's law. In this
letter, the reconfigurable intelligent surface (RIS) that can reflect the
electromagnetic waves to any specific directions is introduced to mitigate the
signal blocking. The closed-form expressions for blocking probability (BP) for
one reflection with single RIS and multiple RISs under various scenarios are
derived. Compared with the case without RIS, significant reduction of BP can
be found with proper configuration of the RIS. Moreover, the impact of the
location of RIS, the height of the transmitter, and the location of the
receiver, on the BP is investigated. Finally, the case of multiple obstacles
with different distributions is discussed to further verify the effectiveness
of RIS on reduction of BP.

###### Index Terms:

Obstructed tunnel, reconfigurable intelligent surface, blocking probability,
multiple RISs.

##  I Introduction

To meet the demand of excellent wireless data service at anywhere and anytime
in emerging wireless networks, the high-reliability and even high-speed data
rate wireless communication in tunnels[1, 2, 3], e.g., the subway tunnels,
road tunnels and mine tunnels, etc., are required. Nevertheless, limited by
the Snell's law, the obstacles (e.g., the mining equipments and the rockfalls
caused by the geological hazards, etc.) in tunnels will result in the ray-path
blocking. The mitigation of signal blocking in tunnels with obstacles is
crucial to the link reliability, especially for the reliable communication in
the challenging environment, such as the rescuing communication for tunnel
disaster. To deal with this challenge, the reconfigurable intelligent surface
(RIS) is introduced in this letter to reduce the risk of signal blocking in
obstructed tunnels.

With configuration of smart controllable reflecting elements, the radio wave
can be reflected to any desired direction at the RIS [4, 5, 6]. Thus, the RIS
can overcome the restriction of Snell's law of reflection to enhance the
signal coverage. Utilizing tools from random spatial processes, [7]
demonstrated that the reflection probability can be significantly improved
from below 30% without RIS to more than 90% with RIS in free space wireless
networks. In recent years, the RIS-assisted communication has attracted
substantial attention. Both the prototype measurement [8, 9] and analytical
analysis [5, 6, 10] have proved the great potential of RIS in enhancing the
wireless communication quality. Most of the contributions on the RIS-aided
communication focus on the free space scenarios (like [6], and references
therein), while the application of RIS in confined space, like the tunnels, to
assist the wireless communication has not been fully explored. The potential
of the application of RIS in underground mine tunnel communication was
discussed in [11], nevertheless, the quantitative analysis for this RIS-aided
underground communication was not presented. Moreover, it is noted that most
of contributions concerning the analysis for RIS-aided communication only pay
attention to the single RIS model. The outage probability with multi-RIS was
analyzed in [12], and a multi-hop RIS-assisted communication system was
employed in [13] for the enhancement of network coverage. These works only
focus on the multiple RISs-assisted terrestrial communication, the
installation of multiple RISs in tunnels to assist wireless communications
needs to be further investigated.

In this letter, the closed-form expressions of signal blocking probability
(BP) in tunnels with obstacles are derived for both single RIS-aided and
multiple RISs-aided (specifically, two RISs) scenario. It is discovered that
compared with the case without RIS, the BP can be significantly reduced with
proper configuration of RIS. With increased number of RISs, a further
decrement of BP is observed. Moreover, the impact of the location of RIS, the
height of transmitter, and the location of receiver on the BP is discussed to
provide more design insights for its practical implementation. Lastly, the
investigation for the case of multiple obstacles with different distributions
further verifies the effectiveness of RIS on reduction of BP.

##  II System Model

We consider a typical straight rectangular tunnel model [14, 15, 16] as shown
in Fig. 1, in which the height of the tunnel is assumed to be $h$ m. To
facilitate the analysis of signal blocking, the two-dimensional model with
image ray tracing approach is adopted [3]. Under this model, the considered
radio signal transmission is constrained in the $y-z$ plane, and thus the
$x$-coordinate is ignored as shown in Fig. 1 (e.g., the coordinate of the
origin is expressed as $(0,0)$ ). Note that this analytical method for signal
reflection in $y-z$ plane can be directly applied to the $x-z$ plane.

Figure 1: System model.

Assume that only one transmitter Tx and one receiver Rx, the coordinates of
which are respectively represented as $(y_{t},z_{t})$
(${z_{t}}=0,0<{y_{t}}<h$) and $(y_{r},z_{r})$ ($0<{y_{r}}<h,{z_{r}}>0$), are
configured in the tunnel. The intersection point of line Rx-A (the image of Tx
with respect the ceiling of the tunnel) and the ceiling of the tunnel is
$F(y_{F},z_{F})(y_{F}=h)$. Then, according to the Snell's law, the radio
signal will travel along the ray path Tx-$F$-Rx to the Rx. It should be
mentioned that only one reflection is considered here, nevertheless, this
image method can also be applicable for analysis of multiple reflections. We
consider that a RIS with coordinates $(y_{R},z_{R})(y_{R}=h,{z_{R}}\geq 0)$ is
installed on the ceiling of the tunnel to enhance the link reliability. Then,
owing to the RIS's ability of manipulating the radio waves [6], the radio
signal transmission will be no longer restricted by the Snell's law, i.e., the
signal can be directly transmitted from the RIS to the Rx [10].

For an example in Fig. 1, if there exists an obstacle in the tunnel, then the
signal propagation in one reflection link may be blocked. However, if the RIS
is installed on the ceiling of the tunnel (case 1), the radio signal can still
be delivered to the Rx along the path Tx-RIS-Rx. Note that for indoor
communication, the signal may also be blocked by the building walls, etc.,
nevertheless, the Tx and Rx are spatially separated in this case. Thus, the
signal transmission is different from that of the tunnel communication, in
which the Tx and Rx are all installed in the confined space.

Since it is intractable to precisely predict the location and height of the
obstacle, then it is supposed that its height, denoted as ${{h_{o}}}$, is
uniformly distributed between $0$ and $h$ and its location along the $z$-axis,
denoted as ${{d_{o}}}$ , follows another uniform distribution in $(0,z_{r})$
(note that if the obstacle is located farther than $z_{r}$, the signal
transmission will not be blocked). Therefore, the probability density function
(PDF) for ${{h_{o}}}$ and ${{d_{o}}}$ can be respectively written as

${f_{{h_{o}}}}(y)=\frac{1}{h},{f_{{d_{o}}}}(z)=\frac{1}{{{z_{r}}}}.$ (1)

To further justify the effectiveness of RIS, the case of multiple obstacles
with other distribution models, e.g., the doubly truncated normal distribution
(DTND) [17] is also considered. The PDF of DTND can be expressed as [17]
${f_{DTND}}(x)=\frac{{\varphi(u,{\sigma^{2}};x)}}{{\Phi((b-u)/\sigma)-\Phi((a-u)/\sigma)}}$
for $x\in[a,b]$, and ${f_{DTND}}(x)=0$ if $x\notin[a,b]$.
$\varphi(u,{\sigma^{2}};x)=\frac{{\exp(-{{(x-u)}^{2}}/(2{\sigma^{2}}))}}{{\sqrt{2\pi}\sigma}}$,
and $\Phi(x)$ is the cumulative density function of standard normal
distribution.

##  III Signal Blocking Probability Analysis with Reconfigurable Intelligent
Surface

In this letter, if the ray path in one reflection is obstructed by the
obstacles, then we say this signal is blocked. The BP analysis for multiple
reflections can also be done by employing the above image method [3], and we
leave it for future work. Note that if one reflection is obstructed, then the
line-of-sight path will also be blocked. Therefore, the BP analysis will be
helpful for the justification of link reliability in challenging situation of
tunnels (e.g., the tunnel collapse, etc.).

As displayed in Fig. 1, different locations of RIS will result in different
BP. Moreover, the BP varies with different numbers of RISs. Thus, in the
following, the BP will be calculated for different cases of RIS location and
RIS quantity.

Suppose that only one RIS is installed on the ceiling of the tunnel, the BP
can be derived in the following theorem.

###### Theorem 1

The BP for one reflection in obstructed rectangular tunnel with one RIS (OR)
under the system model in (1) can be expressed as

$\displaystyle{\rm{BP}}=\left\\{\begin{array}[]{l}{\rm{Pr[OR|case~{}1]}}\\\
{\rm{Pr[OR|case~{}2]}}\\\ {\rm{Pr[OR|case~{}3]}}\\\
{\rm{Pr[OR|case~{}4]}}\end{array}\right.$ (6)

where ${\rm{Pr[OR|case~{}1]}},{\rm{Pr[OR|case~{}2]}},{\rm{Pr[OR|case~{}3]}}$
and ${\rm{Pr[OR|case~{}4]}}$ are presented at the top of next page, with

$\displaystyle{\rm{Pr[OR|case~{}1]}}=C\left[{(h-{y_{t}}){z_{R}}-{k_{1}}z_{R}^{2}+{{\left({-{k_{2}}{z_{F}}+{k_{1}}{z_{R}}}\right)}^{2}}/\left({{k_{1}}-{k_{2}}}\right)}\right]/2+C\left[{\left({h-{y_{r}}}\right){z_{r}}+{z_{F}}\left({{y_{r}}-{y_{t}}}\right)}\right]/2,$
(3)
$\displaystyle{\rm{Pr[OR|case~{}2]}}\\!=\\!C\\!\\!\left[\\!{\left({\\!-\\!h\\!+\\!{y_{r}}\\!-\\!{k_{3}}{z_{r}}}\\!\right){z_{F}}\\!+\\!\left(\\!{{k_{2}}\\!+\\!{k_{3}}}\\!\right)z_{F}^{2}/2\\!+\\!{{\left(\\!{{y_{t}}\\!-\\!{y_{r}}\\!+\\!{k_{3}}{z_{r}}}\\!\right)}^{2}}/\left(\\!{2\left({{k_{3}}\\!-\\!{k_{0}}}\\!\right)}\\!\right)}\\!\right]\\!\\!+\\!\\!\frac{C}{2}\\!\left[{\left(\\!{h\\!-\\!{y_{t}}}\right){z_{R}}\\!-\\!\left(\\!{{z_{R}}\\!-\\!{z_{r}}}\\!\right)\left(\\!{h\\!-\\!{y_{r}}}\\!\right)}\right],$
(4)
$\displaystyle{\rm{Pr[OR|case~{}3]\\!=}}C\left[\\!{\left(\\!{-\\!h\\!+\\!{y_{r}}\\!-\\!{k_{3}}{z_{r}}}\\!\right){z_{F}}\\!+\\!\left(\\!{{k_{2}}\\!+\\!{k_{3}}}\right)z_{F}^{2}/2}\\!\right]\\!+\\!C\left[{{{\left({{y_{t}}\\!-\\!{y_{r}}\\!+\\!{k_{3}}{z_{r}}}\\!\right)}^{2}}/\left({2\left(\\!{{k_{3}}\\!-\\!{k_{0}}}\\!\right)}\right)\\!+\\!\left({h\\!-\\!{y_{t}}}\\!\right){z_{r}}\\!-\\!{k_{0}}z_{r}^{2}/2}\right],$
(5)
$\displaystyle{\rm{Pr[OR|case~{}4]=}}\\!\left\\{\begin{array}[]{l}\\!\\!\\!\\!\\!{C\\!\left[\\!{\left(\\!{-\\!h\\!+\\!{y_{r}}\\!-\\!{k_{3}}{z_{r}}}\\!\right){z_{F}}\\!+\\!\left(\\!{{k_{2}}\\!+\\!{k_{3}}}\right)z_{F}^{2}/2}\\!\right]\\!+\\!C\\!\\!\left[{{{\left({{y_{t}}\\!-\\!{y_{r}}\\!+\\!{k_{3}}{z_{r}}}\\!\right)}^{2}}/\\!\\!\left({2\left(\\!{{k_{3}}\\!-\\!{k_{0}}}\\!\right)}\right)\\!+\\!\left({h\\!-\\!{y_{t}}}\\!\right){z_{r}}\\!-\\!{k_{0}}z_{r}^{2}/2}\\!\right]}\\!,{z_{R}}\\!\leq\\!{z_{N}}\\\
\\!\\!\\!\\!\\!C\\!\left[{\left({-h+{y_{r}}-{k_{3}}{z_{r}}}\right){z_{F}}\\!+\\!\left({{k_{3}}+{k_{2}}}\right)z_{F}^{2}/2}\right]+\\!C\\!\left[{\left({h-{y_{r}}}\right){z_{r}}\\!+\\!{k_{3}}z_{r}^{2}/2}\\!\right],\begin{array}[]{*{20}{c}}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}{{z_{R}}\\!>\\!{z_{N}}}\end{array}\end{array}\right.$
(9)

${\rm{case~{}1=\\{}}{y_{t}}\geq{y_{r}}{\rm{}}~{}{\text{or
}}~{}{y_{t}}<{y_{r}},0\leq{z_{R}}\leq{z_{F}}{\rm{\\},}}~{}\\\
{\rm{case~{}2=\\{}}{y_{t}}\geq{y_{r}}~{}{\text{or
}}~{}{y_{t}}<{y_{r}}{{,}}{z_{F}}<{z_{R}}\leq{z_{r}}{\rm{\\}}},~{}\\\
{\rm{case~{}3=\\{}}{y_{t}}\geq{y_{r}}{\rm{,}}{z_{R}}>{z_{r}}{\rm{\\}}},~{}\\\
{\rm{case~{}4=\\{}}{y_{t}}<{y_{r}}{\rm{,}}{z_{R}}>{z_{r}}{\rm{\\}}},\\\ $ and,
${k^{{}^{\prime}}}=\frac{{{y_{r}}-2h+{y_{t}}}}{{{z_{r}}}},{z_{F}}=\left({h-{y_{r}}+{k^{{}^{\prime}}}{z_{r}}}\right)/{k^{{}^{\prime}}},C=1/h{z_{r}},\\\
{k_{0}}=\frac{{h-{y_{t}}}}{{{z_{R}}}},{k_{1}}=\frac{{h-{y_{r}}}}{{{z_{R}}-{z_{r}}}},{k_{2}}=\frac{{h-{y_{t}}}}{{{z_{F}}}},{k_{3}}=\frac{{{y_{r}}-h}}{{{z_{r}}-{z_{F}}}},\\\
{z_{N}}=\left({h-{y_{r}}+{k_{4}}{z_{r}}}\right)/{k_{4}},{k_{4}}=\frac{{{y_{r}}-{y_{t}}}}{{{z_{r}}{}}}.$

Proof: See Appendix A. $\blacksquare$

Theorem 1 reveals the effects of RIS on the reduction of BP in one reflection
in the tunnels with obstacles. Moreover, it is helpful for the investigation
of the impact of system parameters, like the location of RIS, etc., on the BP,
which is beneficial for the deployment of RIS in practice to effectively
mitigate the risk of signal blocking.

When ${y_{t}}\to h$, which leads to ${z_{F}}\to 0$, therefore, the BP can be
expressed as (4) in Theorem 1 for ${z_{R}}\leq{z_{r}}$ (i.e.,
${\rm{Pr[OR|case~{}2]}}$). For this case, the ${\rm{Pr[OR|case~{}2]}}$ can be
simplified as
$\quad\quad\quad\quad{\rm{Pr[OR|case~{}2]}}\mathop{\to}\limits^{{y_{t}}\to
h}C\left[{\left({{z_{r}}-{z_{R}}}\right)\left({h-{y_{r}}}\right)/2}\right].$

Furthermore, by substituting ${y_{t}}\to h$ into (9) under
${{z_{R}}>{z_{N}}}$, i.e., the case that without RIS, the BP can be written as
${\rm{Pr[OR|case~{}4]}}\xrightarrow{{{y_{t}}\to
h,{z_{R}}>{z_{N}}}}C\left({h-{y_{r}}}\right){z_{r}}/2.$

Obviously, from the above two equations, the BP aided by RIS is smaller than
that without RIS, and the rate of reduction for BP is
$C{\left({h-{y_{r}}}\right)/2}$. Hence, we get the following corollary.

###### Corollary 1

When ${y_{t}}\to h$ under ${z_{R}}\leq{z_{r}}$, the BP decreases linearly with
${z_{R}}$ at the rate of $C{\left({h-{y_{r}}}\right)/2}$.

Corollary 1 indicates that, it is better to set the RIS closer to the Rx for
the reduction of BP under the conditions mentioned in Corollary 1. If
${y_{t}}\to h$ and ${z_{R}}\geqslant{z_{r}}$, then we have
${\rm{Pr[OR|case~{}3]\to 0}}$ from (5), which means the BP can be almost
nulled by properly installing the RIS.

When the RIS is located closer to the Tx, for instance, ${z_{R}}=0$, the
following conclusion can be acquired.

###### Corollary 2

When ${z_{R}}=0$, the location of Rx along the $z$-axis, i.e., $z_{r}$, will
have no impact on the BP.

Proof: By substituting ${z_{R}}{\text{ = }}0$ into (3), we can get
${\rm{Pr[OR|case~{}1]}}\mathop{=}\limits^{{z_{R}}{\text{ =
}}0}{\left({h-{y_{t}}}\right)^{2}}/\left({2h\left({2{y_{r}}-3h+{y_{t}}}\right)}\right)+\left({h-{y_{r}}}\right)/2h+\left({{y_{r}}-{y_{t}}}\right)\left({{y_{t}}-h}\right)/\left({2h\left({{y_{r}}+{y_{t}}-2h}\right)}\right)$,
in which no $z_{r}$ is found. $\blacksquare$

From Corollary 2, it is discovered that proper configuration of RIS can make
the BP robust to the varying locations of Rx, i.e., the motion of Rx. If it is
further assumed that $h\to\infty$, then we can obtain that the BP approaches
$1/3$. Nevertheless, for the case without RIS, BP is found to be about $1/2$
if $h\to\infty$. This means that about 30% of BP can be reduced by the
installation of RIS.

The above corollaries along with some simple examples confirm the validity of
RIS in mitigating the BP. In the following, to further validate the
effectiveness of RIS on reducing the BP, the BP with multiple RISs will be
discussed.

###### Theorem 2

Suppose that two RISs (TR) are installed in the obstructed rectangular tunnel
with location
$0\leqslant{z_{{R_{1}}}}<{z_{F}},{z_{F}}<{z_{{R_{2}}}}\leqslant{z_{r}}$ under
the system model in (1), then the BP for one reflection is given by

${\text{BP}}={P_{1,TR}}+{P_{2,TR}},$ (7)

where,

$\displaystyle{P_{1,TR}}=C\left[{(-{y_{t}}+h){z_{{R_{1}}}}/2-k_{1}^{{z_{{R_{1}}}}}z_{{R_{1}}}^{2}/2}\right]$
$\displaystyle+\\!C\\!\\!\left[{{{\left(\\!{k_{1}^{{z_{{R_{1}}}}}{z_{{R_{1}}}}\\!-\\!{k_{2}}{z_{F}}}\\!\right)}^{2}}/\left(\\!{2\left(\\!{k_{1}^{{z_{{R_{1}}}}}\\!-\\!{k_{2}}}\\!\right)}\\!\right)\\!+\\!{k_{2}}z_{F}^{2}/2}\right],$
(8)
$\displaystyle{P_{2,TR}}=C\\!\\!\left[\\!{{{\left(\\!{\\!-\\!{y_{r}}\\!\\!+\\!\\!{k_{3}}{z_{r}}\\!+\\!{y_{t}}}\\!\right)}^{2}}\\!/\\!\left(\\!{2\left(\\!{{k_{3}}\\!\\!-\\!\\!k_{0}^{{z_{{R_{2}}}}}}\\!\right)}\\!\right)\\!\\!-\\!\\!\left(\\!{h\\!-\\!{y_{r}}\\!+\\!{k_{3}}{z_{r}}}\\!\right){z_{F}}\\!}\right]$
$\displaystyle\\!+\\!C\\!\\!\left[\\!{{k_{3}}z_{F}^{2}\\!/2}\\!+\\!{\left(\\!{\\!-\\!{y_{t}}\\!+\\!h}\right)\\!\\!{z_{{R_{2}}}}\\!-\\!\left(\\!{k_{0}^{{z_{{R_{2}}}}}z_{{R_{2}}}^{2}\\!\\!+\\!\\!\left(\\!{{z_{{R_{2}}}}\\!\\!\\!-\\!\\!\\!{z_{r}}}\\!\right)\\!\left(\\!{h\\!-\\!{y_{r}}}\\!\right)}\\!\right)\\!\\!/2}\\!\right]\\!\\!,$
(9)

with $k_{1}^{{z_{{R_{1}}}}}=\frac{{h-{y_{r}}}}{{{z_{{R_{1}}}}-{z_{r}}}}$,
$k_{0}^{{z_{{R_{2}}}}}=\frac{{h-{y_{t}}}}{{{z_{{R_{2}}}}}}$, and
${z_{{R_{1}}}},{z_{{R_{2}}}}$ being the coordinates of the first and second
RIS along the $z$-axis, respectively.

Proof: To simplify the analysis, the locations of TR are set to be smaller
than $z_{r}$. Therefore, by employing the similar means of proof for the case
1 and case 2 in Theorem 1, the proof can be completed. $\blacksquare$

It should be noted that the BP in Theorem 2 is obtained without considering
the cooperation between the RISs. More possible ray-paths will be created with
the increased number of RISs, therefore, the BP can be further reduced with
two RISs. Further discussion about the benefits of TR will be presented in the
numerical results.

Only one obstacle is investigated in above theorems, to be more realistic,
let's consider that the number of obstacles, $N>0$ increases linearly with
$z_{r}$ with ratio $k_{r}>0$, i.e.,
$N=\left\lceil{{z_{r}}{k_{r}}}\right\rceil$ ($\left\lceil x\right\rceil$
indicates the smallest integer that is no smaller than $x$). For this case,
the BP can be calculated as $\text{BP}=1-{(1-\text{BP})^{N}}$ with assumption
that the obstacles are independent and identically distributed (i.i.d.). If
the obstacles follow other distributions, e.g., the DTND, we have the
following proposition.

###### Proposition 1

Considering that the heights of two obstacles with location
$0<{d_{o1}}<{z_{R}},{z_{R}}<{d_{o2}}<{z_{C1}}$ under the case 1 of Theorem 1
are i.i.d. by the DTND in the range $(0,h)$, then the BP can be expressed by

${\text{BP}}=1-{P_{o1}}{P_{o2}},$ (10)

where,

$\displaystyle{P_{o1}}={f_{u,\sigma}}({k_{0}}{d_{o1}}+{y_{t}})/\left({{f_{u,\sigma}}(h)}\right),$
(11)
$\displaystyle{P_{o2}}={f_{u,\sigma}}({k_{1}}{d_{o2}}+{y_{R}}-{k_{1}}{z_{R}})/\left({{f_{u,\sigma}}(h)}\right),$
(12)

with
${f_{u,\sigma}}(x)=\left({erf(u/(\sqrt{2}\sigma))-erf((u-x)/(\sqrt{2}\sigma))}\right)/2$
and $erf(x)=\frac{2}{{\sqrt{\pi}}}\int_{0}^{x}{\exp(-{t^{2}})}dt$ being the
error function.

The proof is similar with Theorem 1, where the PDF of obstacles is now changed
to ${f_{DTND}}(x)$. Proposition 1 is useful to verify the effectiveness of RIS
for non-uniformly distributed multiple obstacles.

##  IV Numerical Results

Fig. 2 is depicted to investigate the impact of location of RIS on the BP.
Unless otherwise stated, the $h$ is set to 4 m [18]. As shown in the left side
of Fig. 2, generally, the BP under one RIS first increases, then decreases,
and finally increases with $z_{R}$. However, when $y_{t}\to h$, the BP
linearly reduces with $z_{R}$ at a fixed rate shown in the Corollary 1. Thus,
the optimal value of $z_{R}$ that minimizes the BP varies with the relative
height between Tx and Rx. For the case $y_{t}>y_{r}$, e.g., $y_{t}=3.5$ m,
$y_{r}=2.5$ m if $z_{R}$ is set to about 100 m, the BP can be reduced from
about 0.16 (without RIS) to the minimum value, about 0.04. If $y_{t}<y_{r}$,
e.g., $y_{t}=2.5$ m, $y_{r}=3$ m, the BP can be minimized when $z_{R}$=0,
where the BP is reduced to about half of the case without RIS. The above
specific examples indicate that proper installation of RIS can effectively
mitigate the risk of signal path blocking in tunnels with obstacles.

Furthermore, the theoretical results are consistent with the simulations,
which verify our analysis. Lastly, if we set $k_{r}=0.05$, i.e., $N=5$, we can
see that, similar with the case of one obstacle, by proper installation of
RIS, the BP can also be significantly reduced. Note that for different cases
of $z_{R}$, the BP is very different according to Theorem 1, therefore, some
drastic changes of BP with $z_{R}$ are found in Fig. 2 when $z_{R}$ changes
from one case to another.

From the right side of Fig. 2, if two RISs are installed in the tunnel, the BP
can be further decreased. When $z_{R_{2}}=z_{R}=100$ m in the scenario
$y_{t}=2$ m, $y_{r}$=2.5 m, the BP with two RISs is only about 0.08,
nevertheless, the BP is doubled with only one RIS. However, it is noted that
for some specific cases, e.g., $y_{t}=3.5$ m, $y_{r}$=2 m, the BP with two
RISs is close to that of the case where only one RIS is configured.

For the RIS with large number of intelligent reflecting meta-surface (IRM),
denoted as ${M_{R}}$, and assume that the channel phases for the channel from
Tx to $j$th ($j=1,2,...,M_{R}$) IRM of RIS $\theta_{tR}^{j}$, and the channel
from $j$th IRM of RIS to Rx $\theta_{rR}^{j}$ are known. Then, to reflect the
signal to the direction of Rx and to maximize the signal-to-noise ratio (SNR),
the adjustable phase induced by $j$th IRM of RIS $\varphi_{R}^{j}$ can be set
as $\varphi_{R}^{j}=\theta_{tR}^{j}+\theta_{rR}^{j}$ [5] under the case that
only the cascaded channel Tx-RIS-Rx is found in the tunnels with obstacles.
From right side of Fig. 2, it is detected that the BP is further reduced with
the increased ${M_{R}}$, because more possible paths can be created by the
increment of IRM.

Since the signal strength reduces rapidly with the number of reflections in
tunnels [16], then the BP can be an indicator for the performance of signal
coverage. For instance, suppose that the signal can only be transmitted
through the path Tx-RIS-Rx created by the RIS in the obstructed tunnel, then
the coverage probability $P(SNR>\gamma)$ can be calculated as
$P(SNR>\gamma)=1-BP$ under small value of threshold $\gamma$.

Figure 2: The BP versus $z_{R}$ or $z_{R_{2}}$ with one RIS (left side) or two
RISs (right side). Figure 3: The BP versus $y_{t}$ (left side) and $z_{r}$
(right side) with one RIS under different cases of $z_{R}$.

The impact of height of Tx and the location of Rx (i.e., $z_{r}$) on the BP is
displayed in Fig. 3, which shows that the tendency of BP with $y_{t}$ is
different under different locations of RIS, i.e., $z_{R}$. If $z_{R}=0$, the
variation of BP with $y_{t}$ is U-shaped, whereas the BP linearly decreases
with $y_{t}$ if $z_{R}$=100 m. Moreover, when $z_{R}=20$ m, the BP first
decreases, then increases, and then decreases with $y_{t}$. This means the
optimal value of $y_{t}$ that minimizes BP varies with $z_{R}$. Therefore, for
different locations of RIS, the proper adjustment for the height of Tx can
further reduce BP.

From right side of Fig. 3, it can be seen that for the case without RIS, no
impact of $z_{r}$ on the BP is detected. However, different impacts of $z_{r}$
on the BP can be found, when only one RIS is installed. If $z_{R}>0$, the
variation of BP with $z_{r}$ is spoon-shaped. When $z_{R}=0$, the BP is found
to be a constant. Note that, for this special case, there is no significant
reduction of BP with RIS. However, from left side of Fig. 3, the height of Rx
(i.e., $y_{t}$) can be adjusted to further reduce BP. Moreover, it's
discovered larger value of $z_{R}$ can extend the effective range of RIS. For
instance, if $z_{R}=80$ m, the effective range of RIS is (0, 110) under the
metric of BP$<0.1$, whereas the effective range of RIS shrinks to about (0,
55) if $z_{R}=40$ m. The extended effective range of RIS is beneficial for the
mobile Rx. Further discussion about installation of RIS with considering the
mobility of Rx is left for future work.

Figure 4: The BP under multiple RISs (left side) and the BP for two obstacles
with distribution of DTND.

The BP with the increased number of RISs (denoted as $N_{R}$) with different
intervals between the RISs is depicted in the left side of Fig. 4, where a
linear decrease of BP with the increasing $N_{R}$ is discovered. The BP for
two obstacles under distribution of DTND is displayed in right side of Fig. 4
($h=4$ m, $z_{R}$= 15 m). We can see that, by employing RIS, the BP can be
effectively mitigated, especially for large value of $d_{o1}$ and $\sigma$.
This testifies the effectiveness of RIS on the reduction of BP for multiple
obstacles with different distributions.

##  V Conclusion

The BP in tunnels with obstacles by employing RIS is investigated in this
letter. Compared with the case without RIS, the BP can be significantly
reduced with proper configuration of RIS, and the increased number of RISs can
lead to a further decrement of BP. Moreover, for different locations of RIS,
appropriate adjustment for the height of Tx is beneficial to the mitigation of
BP. In addition, a larger distance between RIS and Tx can extend the effective
range of RIS under a given BP. Lastly, it's detected the BP can also be
effectively reduced for multiple obstacles with different distributions. The
adjustment of RIS phase shifts for signal enhancement in tunnels is an
interesting topic, which will be left for future work.

##  Appendix A Proof of Theorem 1

As shown in Fig. 1, if ${y_{t}}\geq{y_{r}}$ and
${\rm{0}}\leq{z_{R}}\leq{z_{F}}$ (i.e., case 1), then based on the location of
the obstacle, four situations, i.e., $0<{d_{o}}\leq{z_{R}}$,
${z_{R}}<{d_{o}}\leq{z_{C1}}$, ${z_{C1}}<{d_{o}}\leq{z_{F}}$,
${z_{F}}<{d_{o}}<{z_{r}}$, need to be discussed. The point $C1$ is the
intersection point of line segment Tx-F and line segment RIS-Rx. When
$0<{d_{o}}\leq{z_{R}}$, if the obstacle is higher than the intersection point
of vertical line $z=d_{0}$ and line segment Tx-RIS, then the ray path Tx-RIS-
Rx will be obstructed. Therefore, for this situation, the BP, denoted as
$P_{1,1}$, can be calculated as

$\displaystyle
P_{1,1}={\mathbb{P}}(0<{d_{o}}\leq{z_{R}},f_{1,1}({d_{0}})\leq{h_{o}}\leq h)$
$\displaystyle=\int_{0}^{{z_{R}}}{\int_{f_{1,1}(z)}^{h}{{f_{{h_{o}}}}(y){f_{{d_{o}}}}(z)dydz}}$
$\displaystyle=\\!C\\!\\!\\!\int_{0}^{{z_{R}}}\\!\\!\\!\\!\\!\\!\\!{(\\!h\\!-\\!{y_{t}}\\!+\\!{k_{0}}{z_{t}}\\!-\\!{k_{0}}z)dz}\\!=\\!C\\!\left[\\!{(h\\!-\\!{y_{t}})\\!{z_{R}}\\!-\\!{k_{0}}z_{R}^{2}/2}\\!\right],\vspace{-0.6cm}$
(13)

where $f_{1,1}(z)={k_{0}}z+{y_{t}}{{-}}{k_{0}}{z_{t}}$ and $C$ is defined in
Theorem 1. Similarly, the BP, for the case ${z_{R}}<{d_{o}}\leqslant{z_{C1}}$,
denoted as $P_{1,2}$, can be computed as

$\displaystyle P_{1,2}$
$\displaystyle={\mathbb{P}}({z_{R}}<{d_{o}}\leqslant{z_{C1}},f_{1,2}({d_{0}})\leqslant{h_{o}}\leqslant
h)$
$\displaystyle=\int_{{z_{R}}}^{{z_{C1}}}{\int_{f_{1,2}(z)}^{h}{{f_{{h_{o}}}}(y){f_{{d_{o}}}}(z)dydz}}$
$\displaystyle=C\left[{{k_{1}}{z_{R}}\left({{z_{C1}}-{z_{R}}}\right)-{k_{1}}\left({z_{C1}^{2}-z_{R}^{2}}\right)/2}\right],$
(14)

where $f_{1,2}(z)={k_{1}}z+{y_{R}}-{k_{1}}{z_{R}}$ and
${z_{C1}}=\frac{{-{k_{2}}{z_{F}}+{k_{1}}{z_{R}}}}{{{k_{1}}-{k_{2}}}}$.

Following the same method of calculating the $P_{1,1}$ and $P_{1,2}$, the BP
$P_{1,3}$ for the case ${z_{C1}}<{d_{o}}\leqslant{z_{F}}$ and the BP $P_{1,4}$
for the case ${z_{F}}<{d_{o}}<{z_{r}}$ can be respectively obtained as

$\displaystyle P_{1,3}$
$\displaystyle={\mathbb{P}}({z_{C1}}<{d_{o}}\leqslant{z_{F}},f_{1,3}({d_{0}})\leqslant{h_{o}}\leqslant
h)$
$\displaystyle=C\left[{\left({{k_{2}}{z_{F}}}\right)\left({{z_{F}}-{z_{C1}}}\right)-{k_{2}}\left({z_{F}^{2}-z_{C1}^{2}}\right)/2}\right],$
(15) $\displaystyle P_{1,4}$
$\displaystyle={\mathbb{P}}({z_{F}}<{d_{o}}<{z_{r}},f_{1,4}({d_{0}})\leqslant{h_{o}}\leqslant
h)$
$\displaystyle=\\!C\left[\\!{\left({h\\!-\\!{y_{r}}\\!+\\!{k_{3}}{z_{r}}}\\!\right)\left({{z_{r}}\\!-\\!{z_{F}}}\right)\\!-\\!{k_{3}}\left(\\!{z_{r}^{2}\\!-\\!z_{F}^{2}}\\!\right)/2}\right],$
(16)

with $f_{1,3}(z)={k_{2}}z+{y_{F}}-{k_{2}}{z_{F}}$ and
$f_{1,4}(z)={k_{3}}z+{y_{r}}-{k_{3}}{z_{r}}$. The overall BP for the case 1 is
then acquired by combing the above four different cases of BP, i.e.,

$\displaystyle{\rm{Pr[OR|case~{}1]}}=P_{1,1}+P_{1,2}+P_{1,3}+P_{1,4}.$ (17)

By substituting $z_{t}=0$ and $y_{R}=h$ into (17) and with some manipulations,
the equation (3) can be obtained. Note that for ${y_{t}}<{y_{r}}$ and
${\rm{0}}\leq{z_{R}}\leq{z_{F}}$, we can get the same expressions.

Similar to case 1, there also exist four situations in case 2, the BP of which
can be calculated as ${\rm{Pr[OR|case~{}2]=}}P_{2,1}+P_{2,2}+P_{2,3}+P_{2,4},$
where

$\displaystyle
P_{2,1}\\!=\\!{\mathbb{P}}(0\\!<\\!{d_{o}}\leqslant{z_{F}},f_{2,1}({d_{0}})\\!\leqslant{h_{o}}\\!\leqslant
h){\text{\\! = \\! }}C{k_{2}}z_{F}^{2}/2,$ (18) $\displaystyle P_{2,2}{\text{
=
}}{\mathbb{P}}({z_{F}}<{d_{o}}\leqslant{z_{C2}},f_{2,2}({d_{0}})\leqslant{h_{o}}\leqslant
h)$
$\displaystyle\\!=\\!C\left[{\left({h\\!-\\!{y_{r}}\\!+\\!{k_{3}}{z_{r}}}\right)\left({{z_{C2}}\\!-\\!{z_{F}}}\right)\\!-\\!{k_{3}}\left({z_{C2}^{2}-z_{F}^{2}}\\!\right)/2}\right],$
(19) $\displaystyle P_{2,3}{\text{ =
}}{\mathbb{P}}({z_{C2}}<{d_{o}}\leqslant{z_{R}},f_{2,3}({d_{0}})\leqslant{h_{o}}\leqslant
h)$ $\displaystyle{\text{=\\!
}}C\left[{\left({h\\!-\\!{y_{t}}\\!+\\!{k_{0}}{z_{t}}}\right)\left({{z_{R}}\\!-\\!{z_{C2}}}\right)\\!-\\!{k_{0}}\left({z_{R}^{2}\\!-\\!z_{C2}^{2}}\right)/2}\right],$
(20) $\displaystyle P_{2,4}{\text{ =
}}{\mathbb{P}}({z_{R}}<{d_{o}}<{z_{r}},f_{2,4}({d_{0}})\leqslant{h_{o}}\leqslant
h)$ $\displaystyle{\text{ =
}}C\left[{\left({h-{y_{R}}+{k_{1}}{z_{R}}}\right)\left({{z_{r}}-{z_{R}}}\right)-{k_{1}}\left({z_{r}^{2}-z_{R}^{2}}\right)/2}\right],$
(21)

with $f_{2,1}(z)=f_{1,3}(z)$, $f_{2,2}(z)=f_{1,4}(z)$,
$f_{2,3}(z)=f_{1,1}(z)$, $f_{2,4}(z)=f_{1,2}(z)$, and
${z_{C2}}=\frac{{{y_{t}}-{y_{r}}+{k_{3}}{z_{r}}-{k_{0}}{z_{t}}}}{{{k_{3}}-{k_{0}}}}$.
After some manipulations, ${\rm{Pr[OR|case~{}2]}}$ can be simplified as (4).

As for case 3 shown in Fig. 1, only three situations need to be investigated,
then the BP for this case can be expressed as
${\rm{Pr[OR|case~{}3]=}}P_{3,1}+P_{3,2}+P_{3,3}$, where

$\displaystyle
P_{3,1}=\\!{\mathbb{P}}(0\\!<\\!{d_{o}}\leqslant{z_{F}},f_{2,1}({d_{0}})\\!\leqslant{h_{o}}\\!\leqslant
h){\text{ \\!=\\! }}C{k_{2}}z_{F}^{2}/2,$ (22) $\displaystyle P_{3,2}{\text{ =
}}{\mathbb{P}}({z_{F}}<{d_{o}}\leqslant{z_{C3}},f_{2,2}({d_{0}})\leqslant{h_{o}}\leqslant
h)$ $\displaystyle{\text{ =
}}C\left[{\left(\\!{h\\!-\\!{y_{r}}\\!+\\!{k_{3}}{z_{r}}}\\!\right)\left(\\!{{z_{C3}}\\!-\\!{z_{F}}}\right)\\!-\\!{k_{3}}\left({z_{C3}^{2}\\!-\\!z_{F}^{2}}\\!\right)/2}\right],$
(23) $\displaystyle P_{3,3}{\text{ =
}}{\mathbb{P}}({z_{C3}}<{d_{o}}<{z_{r}},f_{3,3}({d_{0}})\leqslant{h_{o}}\leqslant
h)$ $\displaystyle{\text{ =
}}C\left[{\left(\\!{h\\!-\\!{y_{t}}\\!+\\!{k_{0}}{z_{t}}}\right)\left({{z_{r}}\\!-\\!{z_{C3}}}\right)\\!-\\!{k_{0}}\left({z_{r}^{2}\\!-\\!z_{C3}^{2}}\right)/2}\right],$
(24)

with $f_{3,3}(z)=f_{1,1}(z),{z_{C3}}={z_{C2}}$. With some manipulations, we
can get the simplified form of ${\rm{Pr[OR|case~{}3]}}$ in (5).

When regarding the case 4 shown in Fig. 5,

Figure 5: The sketch map for case 4.

the calculations of BP should be divided into two parts, i.e.,
${{z_{R}}\leq{z_{N}}}$ and ${{z_{R}}>{z_{N}}}$, where the point $N$ is the
intersection point of line Tx-Rx and line $y=h$. If ${{z_{R}}\leq{z_{N}}}$,
the BP for this case is same as that of case 3, i.e.,
${\rm{Pr[OR|case~{}4]=Pr[OR|case~{}3]}}$. Nevertheless, if
${{z_{R}}>{z_{N}}}$, the installation of RIS will have no contribution on
reduction of the BP, since the intersection point of line F-Rx and line Tx-RIS
is lower than Rx. The BP of this case is just the same as that of the case
without RIS, which can be calculated as
${\rm{Pr[OR|case~{}4]=}}P_{4,1}+P_{4,2},$ where

$\displaystyle
P_{4,1}={\mathbb{P}}(0<{d_{o}}\leqslant{z_{F}},f_{4,1}({d_{0}})\leqslant{h_{o}}\leqslant
h)$ $\displaystyle{\text{ =
}}C\left[{\left({h-{y_{F}}+{k_{2}}{z_{F}}}\right){z_{F}}-{k_{2}}z_{F}^{2}/2}\right],$
(25) $\displaystyle
P_{4,2}={\mathbb{P}}({z_{F}}<{d_{o}}<{z_{r}},f_{4,2}({d_{0}})\leqslant{h_{o}}\leqslant
h)$ $\displaystyle{\text{ =
}}C\left[{\left({h-{y_{r}}+{k_{3}}{z_{r}}}\right)\left({{z_{r}}-{z_{F}}}\right)-{k_{3}}\left({z_{r}^{2}-z_{F}^{2}}\right)/2}\right],$
(26)

with $f_{4,1}(z)=f_{1,3}(z),f_{4,2}(z)=f_{1,4}(z)$. After some manipulations,
the BP of case 4 can be written as in (9).

## References

  * [1] Z. Sun and I. F. Akyildiz, ``Channel modeling and analysis for wireless networks in underground mines and road tunnels,'' _IEEE Trans. Commun._ , vol. 58, no. 6, pp. 1758–1768, Jun. 2010.
  * [2] C. Zhou, J. Waynert, T. Plass, and R. Jacksha, ``Attenuation constants of radio waves in lossy-walled rectangular waveguides,'' _Progr. Electromagn. Res._ , vol. 142, pp. 75–105, 2013.
  * [3] A. Hrovat, G. Kandus, and T. Javornik, ``A survey of radio propagation modeling for tunnels,'' _IEEE Commun. Surveys Tuts._ , vol. 16, no. 2, pp. 658–669, Second Quarter 2014.
  * [4] T. J. Cui, M. Q. Qi, X. Wan, J. Zhao, and Q. Cheng, ``Coding metamaterials, digital metamaterials and programmable metamaterials,'' _Light, Sci. Appl._ , vol. 3, p. e218, 2014.
  * [5] E. Basar, M. D. Renzo, J. de Rosny et al., ``Wireless communications through reconfigurable intelligent surfaces,'' _IEEE Access_ , vol. 7, pp. 116 753–116 773, 2019.
  * [6] M. Di Renzo, A. Zappone, M. Debbah et al., ``Smart radio environments empowered by reconfigurable intelligent surfaces: How it works, state of research, and the road ahead,'' _IEEE J. Sel. Areas Commun._ , vol. 38, no. 11, pp. 2450–2525, Nov. 2020.
  * [7] M. Di Renzo and J. Song, ``Reflection probability in wireless networks with metasurface-coated environmental objects: An approach based on random spatial processes,'' _EURASIP J. Wireless Commun. Netw._ , vol. 2019, p. 99, Apr. 2019.
  * [8] W. Tang, M. Z. Chen, X. Chen et al., ``Wireless communications with reconfigurable intelligent surface: Path loss modeling and experimental measurement,'' _IEEE Trans. Wireless Commun._ , vol. 20, no. 1, pp. 421–439, Jan. 2021.
  * [9] L. Dai, B. Wang, M. Wang et al., ``Reconfigurable intelligent surface-based wireless communication: Antenna design, prototyping and experimental results,'' _IEEE Access_ , vol. 8, pp. 45 913–45 923, 2020.
  * [10] C. Pan, H. Ren, K. Wang et al., ``Reconfigurable intelligent surface for 6G systems: Principles, applications, and research directions,'' _IEEE Commun. Magazine_ , vol. 59, no. 6, pp. 14–20, Jun. 2021.
  * [11] S. Kisseleff, S. Chatzinotas, B. Ottersten, ``Reconfigurable intelligent surfaces in challenging environments: Underwater, underground, industrial and disaster,'' 2021, [Online]. Available:https://arxiv.org/abs/2011.12110.
  * [12] Z. Zhang, Y. Cui, F. Yang, and L. Ding, ``Analysis and optimization of outage probability in multi-intelligent reflecting surface-assisted systems,'' 2019, [Online]. Available: https://arxiv.org/abs/1909.02193.
  * [13] C. Huang, Z. Yang, G. C. Alexandropoulos et al., ``Multi-hop RIS-empowered terahertz communications: A DRL-based hybrid beamforming design,'' _IEEE J. Sel. Areas Commun._ , vol. 39, no. 6, pp. 1663–1677, Jun. 2021.
  * [14] D. G. Dudley, M. Liénard, S. F. Mahmoud, and P. Degauque, ``Wireless propagation in tunnels,'' _IEEE Antenna Propag. Mag._ , vol. 49, no. 2, pp. 11–26, Apr. 2007.
  * [15] A. Aziminejad, A. W. Lee, and G. Epelbaum, ``Underground communication: Radio propagation prediction for CBTC data communication subsystem design,'' _IEEE Veh. Technol. Mag._ , vol. 10, no. 3, pp. 71–79, Sep. 2015.
  * [16] C. Zhou, ``Ray tracing and modal methods for modeling radio propagation in tunnels with rough walls,'' _IEEE Trans. Antennas Propag._ , vol. 65, no. 5, pp. 2624–2634, May 2017.
  * [17] Z. Gao, J. Tao, Y. Su et al., ``Fast statistical analysis of rare failure events with truncated normal distribution in high-dimensional variation space,'' _IEEE Trans. Comput.-Aided Design Integr. Circuits Syst.,_ , 2021, Early Eccess.
  * [18] Y. P. Zhang, ``Novel model for propagation loss prediction in tunnels,'' _IEEE Trans. Veh. Technol._ , vol. 52, no. 5, pp. 1308–1314, Sep. 2003.