# Pair creation in hot electrosphere of compact astrophysical objects

Mikalai Prakapenia  ICRANet-Minsk, Institute of Physics, National Academy of
Sciences of Belarus, 220072 Nezalezhnasci Av. 68-2, Minsk, Belarus  Department
of Theoretical Physics and Astrophysics, Belarusian State University,
Nezalezhnasci Av. 4, 220030 Minsk, Belarus  Gregory Vereshchagin  ICRANet-
Minsk, Institute of Physics, National Academy of Sciences of Belarus, 220072
Nezalezhnasci Av. 68-2, Minsk, Belarus  ICRANet, 65122 Piazza della
Repubblica, 10, Pescara, Italy  ICRA, Dipartimento di Fisica, Sapienza
Università di Roma, Piazzale Aldo Moro 5, I-00185 Rome, Italy  INAF – Istituto
di Astrofisica e Planetologia Spaziali, 00133 Via del Fosso del Cavaliere,
100, Rome, Italy

###### Abstract

The mechanism of pair creation in electrosphere of compact astrophysical
objects such as quark stars or neutron stars is revisited, paying attention to
evaporation of electrons and acceleration of electrons and positrons,
previously not addressed in the literature. We perform a series of numerical
simulations using the Vlasov-Maxwell equations. The rate of pair creation
strongly depends on electric field strength in the electrosphere. Despite
Pauli blocking is explicitly taken into account, we find no exponential
suppression of the pair creation rate at low temperatures. The luminosity in
pairs increases with temperature and it may reach up to $L_{\pm}\sim 10^{52}$
erg/s, much larger than previously assumed.

##  1 Introduction

Quantum electrodynamics predicts vacuum breakdown in strong electric field,
leading to prolific creation of electron-positron pairs. An extreme value of
electric field strength required for this process $E\sim
E_{c}=m_{e}^{2}c^{3}/\hbar e\simeq 1.3\times 10^{16}$ V/cm, where $m_{e}$ is
the electron mass, $e$ is its charge, $c$ is the speed of light and $\hbar$ is
reduced Planck constant, is not yet reachable in laboratory conditions.
However, one may look for this process in some extreme astrophysical
environments, for reviews see Ruffini et al. (2010); Vereshchagin & Prakapenia
(2022). Indeed, strong electric fields may exist on bare surfaces of
hypothetical quark stars (Alcock et al., 1986; Kettner et al., 1995; Usov,
1998; Usov et al., 2005; Harko & Cheng, 2006; Picanço Negreiros et al., 2010;
Issifu et al., 2023) or even neutron stars (Rotondo et al., 2011a, b;
Belvedere et al., 2012; Rueda et al., 2014). The region with overcritical
$E>E_{c}$ electric field in these objects is called _electrosphere_. Similar
electrospheres are predicted for such hypothetical objects as superheavy
nuclei (Migdal et al., 1976) and quark nuggets (Forbes et al., 2010). The
magnitude of electric field in electrosphere depends on the sharpness of the
boundary of positively charged component (Mishustin et al., 2010). Usov (1998)
in his seminal paper proposed that hot quark stars may be a source of pair
winds, potentially observable at cosmological distances. Based on this work
detailed study of particle interactions was performed by Aksenov et al. (2004,
2005) predicting observed properties of hot quark stars.

In this paper we revisit Usov’s mechanism of pair creation in electrosphere of
compact objects. First, we show that the reasoning under Usov’s results
contain some flaws. Then, we provide new arguments how pair creation can
operate, and derive the rate of pair creation together with pair luminosity
for electrosphere of a compact astrophysical object. The self-consistent
simulations for electron-positron pair creation and electric field evolution
in electrosphere are performed. Our results indicate that hot electrosphere
indeed is a source of strong pair wind. The paper is organized as follows. In
section 2 we describe the original Usov’s idea. In section 3 we derive the
rate of pair creation in electrosphere. In section 4 we present main equations
and corresponding boundary conditions used for simulations. Our numerical
results are presented in section 5. Discussion and conclusions follow in
sections 6 and 7, respectively.

##  2 Usov’s mechanism

Usov (1998) was the first who pointed out the possibility of pair creation in
electrosphere of compact astrophysical objects. Since the work by Alcock et
al. (1986) it is argued that near the surface of bare quark star a
supercritical electric field may exist. This is because the sharpness of the
quark star surface is determined by the strong interactions, while degenerate
electrons are bound to quarks by electromagnetic interactions. Thus electron
spatial distribution extends to larger, still microscopic, distances. The
resulting charged layer generates strong and overcritical electric field.
While overcritical electric field in vacuum should produce electron-positron
pairs, this does not happen at small temperatures. The reason is that all
electronic states in this configuration are fully occupied and the Schwinger
process is forbidden. In order to start pair creation process empty electronic
states have to be present. This is possible when the quark star is just
formed, being very hot with its surface temperature
$k_{B}T_{S}\sim\varepsilon_{F}\sim 20$ MeV Usov (1998), where
$\varepsilon_{F}$ is Fermi energy inside the star, $T_{S}$ is the temperature
of the star, $k_{B}$ is the Boltzmann constant.

The mechanism proposed by Usov (1998) is the following. Given that the rate of
pair creation in overcritical electric field is extremely fast, all empty
states below the pair creation threshold are instantly occupied by creating
electrons and positrons. Then the slower process of thermalization of
electrons determines the appearance of new empty states for electrons.
Positrons are ejected by the electric field. Their outflow leads to outflow of
electrons. The number of created electron-positron pairs $N_{\pm}$ per unit
volume $\Delta V$ and unit time is estimated as (Usov, 1998):

$\dot{n}_{\pm}=\frac{\dot{N}_{\pm}}{S_{R}\Delta r_{E}}\simeq\Delta
n_{e}/\tau_{ee},$ (1)

where $S_{R}$ is the surface area of electrosphere, $\Delta r_{E}$ is its
thickness, $\tau_{ee}$ is the thermalization timescale of electron-electron
collisions, and a dot denotes time derivative. The density of electronic empty
states below the pair creation threshold $\Delta n_{e}$ in the strong
degeneracy approximation $k_{B}T_{S}\ll\varepsilon_{F}$ is

$\Delta
n_{e}\simeq\frac{3k_{B}T_{S}}{\varepsilon_{F}}n_{e}\exp{\left(-\frac{2m_{e}c^{2}}{k_{B}T_{S}}\right)},$
(2)

the thermalization timescale $\tau_{ee}$ is given by

$\tau_{ee}^{-1}\simeq\frac{3\alpha}{2\pi^{3/2}}\frac{(k_{B}T_{S})^{2}}{\hbar\varepsilon_{F}}J(\zeta),$
(3)

where $\zeta=2\alpha^{1/2}\pi^{-1/2}\frac{\varepsilon_{F}}{k_{B}T_{S}}$,
$\alpha$ is the fine structure constant and

$J(\zeta)=\left\\{\begin{array}[c]{cc}51(1-19.5\zeta^{-1}+296\zeta^{-2}),&\zeta>20,\\\
0.23\zeta^{1.8},&1<\zeta<20,\\\
(1/3)\zeta^{3}\ln{2/\zeta},&\zeta<1.\end{array}\right.$ (4)

The thickness of the electrosphere $\Delta r_{E}$ is given by Usov et al.
(2005)

$\Delta
r_{E}=\left(\frac{3\pi}{2\alpha}\right)^{1/2}\frac{m_{e}c^{2}}{e\varphi_{0}}\frac{\hbar}{m_{e}c},$
(5)

where $\varphi_{0}$ is electrostatic potential on the surface of the compact
object. For the case of fully degenerate electrons we have
$e\varphi_{0}=\frac{3}{4}\varepsilon_{F}$. Thus, for $\varepsilon_{F}=20$ MeV
one finds $\Delta r_{E}\simeq 3\times 10^{-11}$ cm.

It is found that the product $\Delta r_{E}\Delta n_{e}$ is independent on the
temperature. In addition, since the number of created pairs is considerably
smaller than the number of electrons in electrosphere, it is assumed that the
structure of electrosphere is not modified by the process of pair creation.
Therefore, the key assumption adopted by Usov (1998); Usov et al. (2005) is
that electric field acts as a catalyst for the Schwinger process and it does
not affect particles dynamics.

According to the Usov mechanism, the process of pair creation continues as
long as the temperature remains high enough, $k_{B}T_{S}>2m_{e}c^{2}$, see eq.
(2). At lower temperatures pair creation is exponentially suppressed.

##  3 Pair creation rate in electrosphere

Assuming pairs are not produced due to occupied electron states, one can find
a static solution for the Vlasov-Maxwell equations. Strictly speaking this is
true only for fully degenerate electrons. One may assume that quasi-static
equilibrium is also possible111We use the term quasi-static, because at
nonzero temperature thermal evaporation of electrons modifies the structure of
electrosphere, see below. for nonzero temperatures (Kettner et al., 1995).
Electrons in equilibrium obey the Fermi-Dirac statistics with their $f_{e}$
distribution function

$f_{e}=\frac{1}{1+\exp{\left[\left(\sqrt{{p}^{2}+m_{e}^{2}}-{\mu}\right)/T_{S}\right]}},$
(6)

where $\mu$ is their chemical potential222In this section and below we use the
units with $\hbar=c=k_{B}=1$.. The chemical equilibrium condition for
electrons is

$\mu=e\varphi,$ (7)

implying that electrons are bound by the electrosphere and also that their
distribution function does not depend on time $\partial f_{e}/\partial t=0$.
The number density of electrons for $T_{s}\ll\mu$ is (Kettner et al., 1995;
Usov et al., 2005)

$n_{e}=\frac{\mu^{3}}{3\pi^{2}}+\frac{\mu T_{S}^{2}}{3}.$ (8)

In ultrarelativistic approximation for electrons the Poisson equation gives
(Alcock et al., 1986; Kettner et al., 1995)

$\frac{d^{2}\varphi}{dz^{2}}=-\frac{4\alpha}{3\pi}\left[e^{2}\varphi^{3}+\pi^{2}T_{s}^{2}\varphi-
n_{q}\right],$ (9)

where
$n_{q}(z<0)=(\alpha/3\pi^{2})(e^{2}\varphi_{q}^{3}+\pi^{2}T_{S}\varphi_{q})$
is the density of a positively charged core, $z$ is spatial coordinate normal
to electrosphere. The electric field $E(z)$ is defined from the electrostatic
potential $\varphi(z)$ as $E(z)=-d\varphi/dz$. The solution of the
electrostatic problem is shown in Fig. 1 for selected values of temperature.
At the surface $z=0$ the values of electric field $E_{0}$ and electrostatic
potential $\varphi_{0}$ can be expressed as (Kettner et al., 1995; Usov et
al., 2005):

$\displaystyle
E_{0}=\sqrt{\frac{2\alpha}{3\pi}}\sqrt{e^{4}\varphi^{4}_{0}+2\pi^{2}T^{2}e^{2}\varphi_{0}^{2}},$
(10) $\displaystyle
e\varphi_{0}=\frac{\varepsilon_{F}(2\pi^{2}T^{2}+3\varepsilon_{F}^{2})}{4(\pi^{2}T^{2}+\varepsilon_{F}^{2})}.$
(11)

Figure 1: Electric field (top) and electron density (bottom) spatial
distribution for selected temperatures $T_{S}$: $T_{S}=3m_{e}$ (solid),
$T_{S}=6m_{e}$ (dotted),$T_{S}=9m_{e}$ (dashed). Here $e\varphi_{q}=20$ MeV
and $\lambda_{C}\simeq 2.4\times 10^{-10}$ cm is electron Compton wavelength.

It is important to note that this solution is not fully self-consistent. It
ignores thermal evaporation of electrons, and the consequent electrosphere
_inflation_. The condition of chemical equilibrium (7) is valid at zero
temperature. At non-zero temperatures some electrons have large enough
energies to overcome the Coulomb barrier and leave the electrosphere.
Therefore, spatial distribution of electrons as well as electric field in hot
electrosphere can extend on much larger distances from the surface, than in
the cold case. This effect is not accounted for by eq. (9) and is not shown in
Fig. 1. However, our numerical results clearly demonstrate this effect, see
below.

The basic assumption made by Usov (1998) is that the role of the electrosphere
is just creation of electron-positron pairs out of electric field. Their
subsequent evolution is determined by collisions, leading to thermalization.
In this approach particle acceleration by the electric field is neglected.
While thermalization is indeed relevant process for reaching equilibrium in
relativistic plasma (Aksenov et al., 2007, 2009, 2010), there are other
kinetic processes that may change electron distribution function. Below we
demonstrate that within electrosphere pairs are practically collisionless.

The Coulomb logarithm $\Lambda$ in relativistic plasma is of the order of
unity (Vereshchagin & Aksenov, 2017). Hence the transport cross section for
Coulomb collisions of electrons is
$\sigma_{\text{coul}}=\sigma_{T}\left(m_{e}/T_{S}\right)^{2}\Lambda\sim\sigma_{T}$,
where $\sigma_{T}$ is the Thomson cross-section. Thus, the Thomson cross-
section can be used as an estimation for the Coulomb scattering cross-section.
The mean free path $l$ is

$l\simeq(\sigma_{T}n_{e})^{-1}=\frac{3}{8\pi\alpha^{2}}\left(\frac{n_{e}}{\lambda_{C}^{-3}}\right)^{-1}.$
(12)

Assuming that electron density in the electrosphere is $n_{e}\sim
10^{35}~{}\text{cm}^{-3}$ (Usov, 1998), see Fig. 1, we obtain $l\sim 10^{-11}$
cm. From these estimations we see that the thickness of cold electrosphere is
equal to the mean free path of particles. As the density of electrons
decreases exponentially with radius, it makes the entire region above
electrosphere almost collisionless.

We can estimate the rate of pair creation using the Schwinger rate per unit
volume and per unit time in a constant in time and homogeneous electric field
Schwinger (1951); Narozhnyi & Nikishov (1970)

$\dot{n}_{\pm}=\frac{m_{e}^{4}}{4\pi^{3}}\left(\frac{E}{E_{c}}\right)^{2}\exp{\left(-\pi\frac{E_{c}}{E}\right)}.$
(13)

To describe pair creation for non-vacuum initial state it is necessary to take
into account Pauli blocking effect (Prakapenia & Vereshchagin, 2023; Brodin et
al., 2023). We use the differential pair creation rate given by Gatoff et al.
(1987) with additional Pauli blocking factor $(1-f_{e})$. The rate is then
given by an integral over particle momentum $d^{3}p_{e}$ in the following form

$\displaystyle\dot{n}_{\pm}=-\frac{2\pi
m_{e}^{4}}{4\pi^{3}}\frac{E}{E_{c}}\int\limits_{0}^{\infty}d\tilde{p}\tilde{p}\left(1-f_{e}\right)$
(14)
$\displaystyle\times\ln\left[1-\exp{\left(-\frac{\pi(\tilde{p}^{2}+1)}{E/E_{c}}\right)}\right].$

Without the Pauli blocking factor $(1-f_{e})$ this expression reduces to the
Schwinger rate (13). Therefore, the rate depends on three parameters:
temperature $T_{S}$, chemical potential $\mu$ and electric field $E$. The
electric field and chemical potential can be obtained from the electrostatic
configuration as a functions of the temperature. The only remaining free
parameter is the temperature.

The total rates of pair creation can be computed using the typical parameters
for strange stars: $R=10^{6}$ cm, $\varepsilon_{F}=20$ MeV and $\Delta
r_{E}=10^{-10}$ cm (Alcock et al., 1986; Usov, 1998). We show this quantity in
Fig. 2: dashed line represents Usov’s rate obtained using eq. (1), while solid
line represents the rate computed with eq. (14) and dotted line corresponds to
eq. (15), where the surface quantities (10) were substituted.

Figure 2: Pair creation rate in the electrosphere $\dot{N}_{\pm}$ according to
eq. (1) for dashed curve, eq. (15) for dotted curve and eq. (14) for solid
curve. Dots represent numerical results from the Tab. 1.

At high temperatures $T_{S}>\varepsilon_{F}$ Pauli blocking becomes negligible
and since $E\gg E_{c}$ one finds (Usov, 1998)

$\displaystyle\dot{N}_{\pm}\simeq 4\pi R^{2}\Delta
r_{E}\frac{m_{e}^{4}}{4\pi^{3}}\left(\frac{E}{E_{c}}\right)^{2}$ (15)
$\displaystyle\simeq 4\times 10^{56}\;{\rm s}^{-1}\left(\frac{E}{5\times
10^{17}{\rm V/cm}}\right)^{2}.$

We find that the luminosity in pairs is determined not by their temperature,
as Usov assumed, but by the Lorentz factor of the outflow. Positrons are
accelerated by the electrosphere and ejected with high Lorentz factor, which
can be estimated from the equation of motion

$\gamma\simeq\frac{E}{E_{c}}.$ (16)

Electrons, while decelerated in the electrosphere, are dragged together with
positrons. In fact, the flux of positrons reduces the Coulomb barrier thereby
allowing more electrons to escape. This guarantees charge neutrality of the
total outflow. From (15) and (16) we find that the luminosity in pairs can be
as large as

$\displaystyle L_{\pm}\simeq 1.3\times 10^{52}\;{\rm
erg/s}\left(\frac{E}{5\times 10^{17}{\rm V/cm}}\right)^{3}.$ (17)

In this estimate the reference value of electric field $E=30E_{c}$, see Fig. 1
in the electrosphere is used. Given strong dependence on eletric field even
larger values are expected. This result shows that even very large isotropic
luminosities of gamma-ray bursts (GRBs) of $10^{53}$ erg/s and higher are
possible for electrosphere of compact objects, provided that $E\sim 80E_{c}$
or higher at their surface.

The source of energy for pair outflow is thermal energy of the compact object
which can be as high as $10^{53}$ erg (Haensel et al., 1991) for the
temperatures of $10^{11}$ K.

Note, that in the derivation of eq. (14) the role of Pauli blocking is
overestimated. Pair acceleration by the electric field is so strong that
operates as an alternative mechanism to thermalization by creating empty
states in the phase space and thus allowing pair creation to operate. In order
for this mechanism to work the rate of pair creation obtained from (13) should
be smaller than the rate of acceleration, obtained from (16), which leads to
the following constraint (Benedetti et al., 2011)

$\frac{1}{4\pi^{3}}\frac{E}{E_{c}}\exp\left(-\pi\frac{E_{c}}{E}\right)\leq 1,$
(18)

which gives $E\lesssim 127E_{c}$. Therefore, for typical values of electric
field in electrosphere this effect strongly enhances pair creation.

##  4 Dynamical equations and initial conditions at the surface

As we consider particle dynamics in orthogonal direction to the surface of the
compact object we introduce cylindrical coordinates in momentum space
$\mathbf{p}=\\{p_{\perp},p_{\phi},p_{||}\\}$ with $p_{||}$-axis parallel to
electric field $E$. Particle energy is then
$p^{0}=[p_{\perp}^{2}+p_{||}^{2}+m_{e}^{2}]^{1/2}$.

Particle evolution is described by one-particle electron/positron distribution
function $f_{\pm}(t,z,p_{\perp},p_{||})$, which is normalized on particle
density $n_{\pm}=\int\frac{d^{3}p}{(2\pi)^{3}}f_{\pm}$.

We introduce dimensionless quantities $\tilde{t}=tm$, $\tilde{z}=zm$,
$\tilde{p}=p/m$, $\tilde{E}=Ee/m_{e}^{2}$ to write the basic dynamic equations
in dimensionless form. The set of Maxwell-Vlasov equations in our case reduces
to the Vlasov-Ampére system, which has to be supplemented with the Gauss law,
as an initial condition. For this purpose we use the Poisson equation (9). We
have

$\displaystyle\frac{\partial
f_{\pm}}{\partial\tilde{t}}+\frac{\tilde{p}_{||}}{\tilde{p}^{0}}\frac{\partial
f_{\pm}}{\partial\tilde{z}}\mp\tilde{E}\frac{\partial
f_{\pm}}{\partial\tilde{p}_{||}}=$ (19)
$\displaystyle-(1-f_{+}-f_{-})|\tilde{E}|\text{ln}\left[1-\exp\left(-\frac{\pi(1+\tilde{p}_{\perp}^{2})}{|E|}\right)\right]\delta(\tilde{p}),$
$\displaystyle\frac{\partial E}{\partial t}=2\alpha\int
d^{3}\tilde{p}\frac{\tilde{p}}{\tilde{p}^{0}}(f_{-}-f_{+})+$ $\displaystyle
4\alpha\frac{|\tilde{E}|}{\tilde{E}}(1-f_{+}-f_{-})\text{ln}\left[1-\exp\left(-\frac{\pi(1+\tilde{p}_{\perp}^{2})}{|\tilde{E}|}\right)\right]\delta(\tilde{p}).$

We recall that the solution of the Poisson equation (9) leads to the static
solution of the Vlasov-Ampére system (19) only in the case $T_{S}=0$, that is
for fully degenerate electrons. Only in this case the chemical potential
$\mu=e\varphi$ equals Fermi energy, which means that there are no electrons
with energies exceeding the Coulomb barrier. However, when the surface
temperature is non-zero $T_{S}>0$ there is a small part of electrons with
energies larger than the Coulomb barrier. These electrons move outward the
surface increasing the electric field outside the surface of the compact
object, leading to electrosphere inflation.

The initial distribution function of electrons is assumed to be the Fermi-
Dirac one (6), where the chemical potential $\mu=e\varphi$ and the temperature
$T_{S}$ are obtained from the Poisson equation (9). The initial distribution
function of electrons at the surface $z=0$ is shown in Fig. 3 for two
different values of temperature. The smaller is the temperature, the larger is
degeneracy of electrons at small momenta, where pair creation operates, and
one can expect much less pairs in this case, see Fig. 2.

Figure 3: Initial distribution of electrons in the momentum space at the
surface $z=0$ of the compact object for different surface temperatures:
$T_{S}=3m_{e}$ (solid) and $T_{S}=7m_{e}$ (dashed).

##  5 Numerical results

We integrate numerically the system of equations (19) and present the results
for $T_{S}=3m_{e}$ in Fig. 4, and for $T_{S}=7m_{e}$ in Fig. 5.

Figure 4: Electric field (top) and electron number density (bottom) as
function of distance from the surface of the compact object. Dashed curves
represent electrostatic solution. Solid curves represents inflated
electrosphere. Inset shows electron (solid) and positron (dotted) spatial
distribution. Here $T_{S}=3m_{e}$. Figure 5: The same as in Fig. 4 for
$T_{S}=7m_{e}$.

Electric field and electron number density as function of distance from the
surface of the compact object are shown. Electrostatic solutions of eq. (9),
used as initial conditions for simulations, are represented by dashed curves.
Solutions of dynamical equations (19) are shown by solid curves. Electrosphere
inflation due to evaporation of electrons, whose energy exceeds the Coulomb
barrier leads to extension of the region of overcritical electric field from
$z\sim\lambda_{C}$ up to $z\sim 10\lambda_{C}$. Electron-positron pairs are
mostly produced near the surface at $z=0$, where electric field is the
largest. The combined flux of electrons and positrons is clearly visible in
the insets in Figs. 4 and 5 at $z>10\lambda_{C}$.

The average energy of electrons and positrons is computed as

$\langle\tilde{\varepsilon}_{\pm}\rangle=\frac{1}{\tilde{n}_{\pm}}\int
2\frac{d^{3}\tilde{p}}{(2\pi)^{3}}\tilde{p}^{0}f_{\pm}.$ (20)

In Fig. 6 we present this quantity as a function of distance from the surface.
It is clear that the Coulomb barrier located as small $z$ decelerates
electrons and accelerates positrons. At larger distances positrons are
additionally accelerated by the inflated electrosphere. The Lorentz factor
$\gamma$ of the outflow here is approximately equal to the average energy.
Specifically we find $\gamma\simeq 40$ for $T_{S}=3m_{e}$ and $\gamma\simeq
50$ for $T_{S}=7m_{e}$, in agreement with the estimate (16).

Figure 6: Average energy of electrons (dashed) and positrons (solid) for
$T_{S}=3m_{e}$ (top) and $T_{S}=7m_{e}$ (bottom) as a function of distance
from the surface.

Finally, we compute the luminosity of the outflow at a distance $\tilde{z}$
from the boundary as follows

$\tilde{L}=4\pi(\tilde{R}+\tilde{z})^{2}\int
2\frac{d^{3}\tilde{p}}{(2\pi)^{3}}\tilde{p}_{||}(f_{+}+f_{-})$ (21)

The peak luminosity for $R=10$ km and $T_{S}=3m_{e}$ is $L\simeq 2\times
10^{50}$ erg/s. For $T_{S}=7m_{e}$ we obtain $L\simeq 4\times 10^{51}$ erg/s.
The values $\dot{N}\simeq L/\langle\tilde{\varepsilon}_{\pm}\rangle$ are
$6\times 10^{54}\,\rm{s}^{-1}$ and $10^{56}\,\rm{s}^{-1}$, respectively, see
Fig. 2.

Note, that the average density of pairs for $T_{S}=3m_{e}$ is about 1 pair in
Compton volume, namely $n_{\pm}\simeq 7\times 10^{28}$ cm-3. For
$T_{S}=7m_{e}$ we find $n_{\pm}\simeq 4\times 10^{29}$ cm-3. These densities
are much smaller than the density of electrons at the boundary $z=0$. The mean
free path (12) is $2\times 10^{3}\lambda_{C}$ and $1.2\times
10^{4}\lambda_{C}$ respectively, much larger than the Compton length. On such
distances from the boundary the outflow is collisionless and does not
thermalize. We also performed simulations for $T_{S}=1.5m_{e}$, $T_{S}=5m_{e}$
and $T_{S}=9m_{e}$. All results are collected in the Tab. 1.

$T_{S}$ | $1.5m_{e}$ | $3m_{e}$ | $5m_{e}$ | $7m_{e}$ | $9m_{e}$
---|---|---|---|---|---
$\dot{N}_{\pm},~{}s^{-1}$ | $7\times 10^{54}$ | $8\times 10^{54}$ | $3\times 10^{55}$ | $6\times 10^{55}$ | $2\times 10^{56}$
$L_{\pm},~{}\text{erg/s}$ | $1\times 10^{50}$ | $2\times 10^{50}$ | $1\times 10^{51}$ | $4\times 10^{51}$ | $1\times 10^{52}$
$\langle\tilde{\varepsilon}_{-}\rangle$ | $8$ | $16$ | $27$ | $46$ | $68$
$\langle\tilde{\varepsilon}_{+}\rangle$ | $12$ | $30$ | $45$ | $54$ | $65$
Table 1: Average pair creation rate $\dot{N}_{\pm}$, average luminosity
$L_{\pm}$, average energy per particle of electrons
$\langle\tilde{\varepsilon}_{-}\rangle$ and positrons
$\langle\tilde{\varepsilon}_{+}\rangle$ obtained from numerical simulations at
$t=17\lambda_{C}/c$ for selected temperatures $T_{S}$.

The numerical rate of pair creation is also represented in Fig. 2. It is clear
that the values of pair creation rate and luminosity exceed the estimates
based on Usov’s formula (1) and the estimates, which assume steady Pauli
blocking (14). However, these values are smaller than the maximum rate (15)
computed in absence of Pauli blocking.

##  6 Discussion

Our kinetic simulation reveals two physical effects in hot electrosphere,
which were ignored in previous analyses. The first effect is the inflation of
electrosphere due thermal evaporation of electrons, leading to its spatial
extension to distances much larger than the electrostatic solution implies.
The second effect is enhancement of the rate of pair creation due to pair
simultaneous acceleration by the electric field. Both effects are crucial for
estimation of pair creation rate, especially at low temperatures with strongly
degenerate electrons, where analytical formulas fail to reproduce numerical
rates, see Fig. 2.

Our numerical results show that, as expected, the Schwinger process operates
for nonzero temperature $T_{S}$. Positrons are accelerated in the Coulomb
barrier and move outward. The total outward flux is approximately neutral due
ability of electrons to overcome the Coulomb barrier. The distribution of the
electric field and electron density is quasi static, and pair creation does
not back react on the electrosphere. As a result electrons do not occupy all
empty states and the process operates continuously.

In our simulations the interior of the compact object serves as a thermal bath
of electrons. In the absence of collisions electrons with negative momentum
are absorbed in the interior and equal number of electrons with positive
momentum are created. Such mirror boundary conditions are adopted to ensure
the energy and particle conservation on the finite computational grid. We do
not investigate in this paper the fate of electrons moving inward, because we
consider collisionless dynamics. It is expected that Coulomb collisions
thermalize these electrons.

We also do not discuss the thermal evolution of of the compact object and its
impact on pair luminosity. It is expected that on sufficiently long timescale
the temperature should decrease sufficiently to halt the Schwinger process. It
has been argued by Page & Usov (2002) that neutrino cooling leads to rapid
decrease of the surface temperature below MeV values. However, recently it was
shown by Li et al. (2021) that quark stars at high temperatures are opaque to
neutrinos. Since neutrinos are captured within neutrinosphere, the cooling is
less efficient.

Clearly on larger distances from the electrosphere pair outflow becomes
collisional. Interaction between electrons and positrons eventually produces
photons. Kinetic simulations of this process has been reported by Aksenov et
al. (2004, 2005) assuming their rate is given by Usov’s formula (1).

##  7 Conclusions

In this paper we revisit Usov’s mechanism for pair creation in electrosphere
of compact astrophysical objects, such as hypothetical quark stars or neutron
stars. As the density of electrons rapidly decreases outside the surface,
electrosphere is essentially collisionless, and pair dynamics is governed by
the Vlasov-Maxwell equations. Numerically solving these equations for hot
electrosphere we found two effects, previously ignored in the literature.
First, due to thermal evaporation of electrons electrosphere is inflated to
much larger distances, though still microscopic, than electrostatic solution
implies. Second, even for strongly degenerate distribution of electrons in
electrosphere Pauli blocking is efficiently reduced by simultaneous
acceleration of pairs created by the Schwinger process. Both these effects
dramatically enhance pair creation rate, leading to luminosities that can be
as large as $10^{52}$ erg/s, see eq. (15), much larger than previously
derived.

These results imply that hot electrosphere may be a stronger source of
relativistic pair outflows than previously assumed. Electron-positron pairs
are generated in electrosphere in collisionless regime.

Acknowledgements. This work is supported within the joint BRFFR-ICRANet-2023
funding programme under the grant No. F23ICR-001.

## References

  * Aksenov et al. (2004) Aksenov, A. G., Milgrom, M., & Usov, V. V. 2004, ApJ, 609, 363, doi: 10.1086/421006
  * Aksenov et al. (2005) —. 2005, ApJ, 632, 567, doi: 10.1086/432905
  * Aksenov et al. (2007) Aksenov, A. G., Ruffini, R., & Vereshchagin, G. V. 2007, Phys. Rev. Lett., 99, 125003, doi: 10.1103/PhysRevLett.99.125003
  * Aksenov et al. (2009) —. 2009, Phys. Rev. D, 79, 043008, doi: 10.1103/PhysRevD.79.043008
  * Aksenov et al. (2010) —. 2010, Phys. Rev. E, 81, 046401, doi: 10.1103/PhysRevE.81.046401
  * Alcock et al. (1986) Alcock, C., Farhi, E., & Olinto, A. 1986, ApJ, 310, 261, doi: 10.1086/164679
  * Belvedere et al. (2012) Belvedere, R., Pugliese, D., Rueda, J. A., Ruffini, R., & Xue, S.-S. 2012, Nuclear Physics A, 883, 1, doi: 10.1016/j.nuclphysa.2012.02.018
  * Benedetti et al. (2011) Benedetti, A., Han, W.-B., Ruffini, R., & Vereshchagin, G. V. 2011, Physics Letters B, 698, 75, doi: 10.1016/j.physletb.2011.02.050
  * Brodin et al. (2023) Brodin, G., Al-Naseri, H., Zamanian, J., Torgrimsson, G., & Eliasson, B. 2023, Phys. Rev. E, 107, 035204, doi: 10.1103/PhysRevE.107.035204
  * Forbes et al. (2010) Forbes, M. M., Lawson, K., & Zhitnitsky, A. R. 2010, Phys. Rev. D, 82, 083510, doi: 10.1103/PhysRevD.82.083510
  * Gatoff et al. (1987) Gatoff, G., Kerman, A. K., & Matsui, T. 1987, Phys. Rev. D, 36, 114, doi: 10.1103/PhysRevD.36.114
  * Haensel et al. (1991) Haensel, P., Paczynski, B., & Amsterdamski, P. 1991, ApJ, 375, 209, doi: 10.1086/170182
  * Harko & Cheng (2006) Harko, T., & Cheng, K. S. 2006, ApJ, 643, 318, doi: 10.1086/502675
  * Issifu et al. (2023) Issifu, A., da Silva, F. M., & Menezes, D. P. 2023, arXiv:2311.12511.  https://arxiv.org/abs/2311.12511
  * Kettner et al. (1995) Kettner, C., Weber, F., Weigel, M. K., & Glendenning, N. K. 1995, Phys. Rev. D, 51, 1440, doi: 10.1103/PhysRevD.51.1440
  * Li et al. (2021) Li, S.-Z., Yu, Y.-W., Gao, H., Dai, Z.-G., & Zheng, X.-P. 2021, ApJ, 922, 214, doi: 10.3847/1538-4357/ac2d2f
  * Migdal et al. (1976) Migdal, A. B., Voskresenskiǐ, D. N., & Popov, V. S. 1976, Soviet Journal of Experimental and Theoretical Physics Letters, 24, 163
  * Mishustin et al. (2010) Mishustin, I. N., Ebel, C., & Greiner, W. 2010, Journal of Physics G Nuclear Physics, 37, 075201, doi: 10.1088/0954-3899/37/7/075201
  * Narozhnyi & Nikishov (1970) Narozhnyi, N., & Nikishov, A. 1970, Sov. J. Nucl. Phys., 11, 596
  * Page & Usov (2002) Page, D., & Usov, V. V. 2002, Physical Review Letters, 89, 131101, doi: 10.1103/PhysRevLett.89.131101
  * Picanço Negreiros et al. (2010) Picanço Negreiros, R., Mishustin, I. N., Schramm, S., & Weber, F. 2010, Phys. Rev. D, 82, 103010, doi: 10.1103/PhysRevD.82.103010
  * Prakapenia & Vereshchagin (2023) Prakapenia, M., & Vereshchagin, G. 2023, Phys. Rev. D, 108, 013002, doi: 10.1103/PhysRevD.108.013002
  * Rotondo et al. (2011a) Rotondo, M., Rueda, J. A., Ruffini, R., & Xue, S. S. 2011a, Physics Letters B, 701, 667, doi: 10.1016/j.physletb.2011.06.041
  * Rotondo et al. (2011b) —. 2011b, Phys. Rev. C, 83, 045805, doi: 10.1103/PhysRevC.83.045805
  * Rueda et al. (2014) Rueda, J. A., Ruffini, R., Wu, Y.-B., & Xue, S.-S. 2014, Phys. Rev. C, 89, 035804, doi: 10.1103/PhysRevC.89.035804
  * Ruffini et al. (2010) Ruffini, R., Vereshchagin, G., & Xue, S.-S. 2010, Phys. Rep., 487, 1, doi: 10.1016/j.physrep.2009.10.004
  * Schwinger (1951) Schwinger, J. 1951, Phys. Rev., 82, 664
  * Usov (1998) Usov, V. V. 1998, Phys. Rev. Lett., 80, 230
  * Usov et al. (2005) Usov, V. V., Harko, T., & Cheng, K. S. 2005, ApJ, 620, 915, doi: 10.1086/427074
  * Vereshchagin & Prakapenia (2022) Vereshchagin, G., & Prakapenia, M. 2022, Universe, 8, 473, doi: 10.3390/universe8090473
  * Vereshchagin & Aksenov (2017) Vereshchagin, G. V., & Aksenov, A. G. 2017, Relativistic Kinetic Theory (Cambridge University Press)


# Waiting Times for Ties in Random Competitions

Ivan Matic<EMAIL_ADDRESS>Department of Mathematics, Baruch
College, City University of New York
One Bernard Baruch Way, New York, NY 10010, USA

###### Abstract.

Multiple teams participate in a random competition. In each round the winner
receives one point. We study the times until ties occur among teams. The
martingales and supermartingales that vanish at the relevant stopping times do
not satisfy the boundedness conditions which are necessary for applying the
traditional optional stopping theorems. We use the positivity of the processes
to prove inequalities that allow us to avoid the restrictions imposed by
optional stopping theorems. The problems studied in this paper are motivated
by their applications to databases and their storage engines that are based on
augmented balanced search trees. The ties in the competitions are related to
the re-balancing operations that have to be executed on the database.

##  1\. Introduction

Assume that there are $m$ teams in a competition. Every round results in only
one team winning and earning $1$ point. Each of the teams has an equal chance
of winning in each of the rounds. Denote by $X_{1}(n)$, $X_{2}(n)$, $\dots$,
$X_{m}(n)$ the scores of the teams after $n$ rounds. We assume that the teams
started with different initial scores $x_{1}$, $x_{2}$, $\dots$,
$x_{m}\in\mathbb{Z}$. In other words, $X_{1}(0)=x_{1}$, $X_{2}(0)=x_{2}$,
$\dots$, $X_{m}(0)=x_{m}$ and the numbers $x_{1}$, $x_{2}$, $\dots$, $x_{m}$
are all distinct. Denote by $T$ the first time at which two of the teams are
tied.

Let $X_{1}^{\prime}(n)$, $\dots$, $X_{m}^{\prime}(n)$ be the non-decreasing
permutation of $X_{1}(n)$, $\dots$, $X_{m}(n)$. Let
$A_{k}(n)=X^{\prime}_{k+1}(n)-X^{\prime}_{k}(n)$ for
$k\in\\{1,2,\dots,m-1\\}$. Then $T$ can be written in an equivalent form as

$\displaystyle T$ $\displaystyle=$ $\displaystyle\min\left\\{n:A_{1}(n)\cdots
A_{m-1}(n)=0\right\\}.$ (1)

Let us denote $a_{i}=A_{i}(0)$ for $i\in\\{1,2,\dots,m-1\\}$. It is easy to
observe that when $m=2$, the random variable $A_{1}(n)$ is a simple random
walk starting at $a_{1}$. The random variable $T$ is the hitting time of the
set $\\{0\\}$. It is well known that the expected value of $T$ is $+\infty$.

We will prove several theorems about $T$ for $m\geq 3$. To make the
formulations of theorems more clear, let us denote by
$\tau(a_{1},a_{2},\dots,a_{m-1})$ the expected value of $T$ in the case that
initial values of the processes $A_{1}$, $\dots$, $A_{m-1}$ are $a_{1}$,
$\dots$, $a_{m-1}$.

For $m=3$ we can obtain the exact formula for $\tau$.

######  Theorem 1.1.

If $m=3$, then $\tau(a,b)=3ab$.

Theorem 1.1 is proved by observing that $A_{1}(n)A_{2}(n)+\frac{n}{3}$ is a
martingale. When $n$ is replaced by $T$, the component $A_{1}(T)A_{2}(T)$
becomes $0$ and the entire value of the martingale reduces to $\frac{T}{3}$.
The standard optional stopping theorem cannot be used because the increments
of the martingale do not have bounded conditional expectations. However, we
will be able to use the positivity of the martingale and Hölder’s inequality
to circumvent this limitation of the optional stopping theorem. In case $m\geq
4$ we will construct certain supermartingales that can be used to establish
upper bounds on $\mathbb{E}\left[T\right]$. The first of the bounds is given
by the following theorem.

######  Theorem 1.2.

If $m\geq 4$, then

$\displaystyle\tau(a_{1},a_{2},\dots,a_{m-1})$ $\displaystyle\leq$
$\displaystyle
m\cdot\min\left\\{a_{1}a_{2},a_{2}a_{3},\dots,a_{m-2}a_{m-1}\right\\}.$ (2)

It turns out that the bound (2) is tight for large values of $a_{1}$, $\dots$,
$a_{m-1}$. If two adjacent values $a_{i}$ and $a_{i+1}$ are fixed and the
remaining numbers converge to $\infty$, then the expected values
$\tau(a_{1},a_{2},\dots,a_{m-1})$ converge to $ma_{i}a_{i+1}$. The precise
statement of the theorem is

######  Theorem 1.3.

Assume that $m\geq 4$ and $i\in\\{1,2,\dots,m-2\\}$. Then

$\displaystyle\lim_{\scriptsize\begin{array}[]{c}a_{1}\to\infty,\dots,a_{i-1}\to\infty\\\
a_{i+2}\to\infty,\dots,a_{m-1}\to\infty\end{array}}\tau(a_{1},a_{2},\dots,a_{m-1})$
$\displaystyle=$ $\displaystyle ma_{i}a_{i+1}.$ (5)

While the right-hand side of (2) is a good asymptotic bound for
$\tau(a_{1},a_{2},\dots,a_{m-1})$, there is actually no hope that it is close
to the exact formula for $\tau(a_{1},\dots,a_{m-1})$. We will prove that for
$m=4$ there is an improvement to (2) in the case $a_{1}=a_{3}$. While (2)
implies that $\tau(a,b,a)\leq 4ab$, the following result offers a sharper
bound.

######  Theorem 1.4.

If $m=4$, and $a$, $b\in\mathbb{N}$, then

$\displaystyle\tau(a,b,a)$ $\displaystyle\leq$ $\displaystyle
4b\left(a-\frac{1}{2}\right).$ (6)

We will prove that the variance and second moment of $T$ are infinite in the
case $m=3$.

######  Theorem 1.5.

For $m=3$, the second moment and variance of the stopping time $T$ are
infinite.

We will now make an overview of random systems from the literature that are
similar to the one presented in this paper. Classes of related models include
allocation problems [3] and multi-color urn models [5, 17, 18, 23]. The
differences between scores can be modeled by numbers of balls of different
colors. However, in urn models different colors have different probabilities
to be chosen. These probabilities change throughout the process.

The problem that we study can also be placed in a context of
$\mathbb{Z}^{d}$-valued random walks. The available jumps belong to a
relatively small set. Consequently, the probability distribution function
assigns $0$ value to many of the steps that a traditional random walk may
take. The stopping time $T$ corresponds to the exit time of a very special
region in the space whose boundary is defined as hyperplanes where two of the
coordinates are the same.

There are several results related to large deviations and asymptotic behavior
of the exit time from cones. The Martin boundary for random walk killed when
exiting the first quadrant in $\mathbb{Z}^{d}$ is studied in [15]. When the
random walks are assumed to take jumps whose values are in $\mathbb{R}^{d}$
the results from [12] and [14] establish the properties of large deviation
events and exponential rates of decay of probabilities that the exit times are
large. The asymptotics is studied using harmonic functions [10, 13]. The
calculation of the number of random walks in quadrant is an important
combinatorial problem. The Tutte’s invariant method can be used to count the
number of such walks [7].

Discrete multidimensional random walks are known to have numerous surprising
properties. On the first sight, the most fundamental models would be the walks
that occur on hypercubes and related regular graphs. The behaviors of the
limiting distributions of the distances are established in [6]. The times to
reach stationary distributions were evaluated using Fourier analysis [9]. The
next class of finite graphs includes the lattice torus in $\mathbb{Z}^{2}$.
The random walk will cover the entire torus and the properties of the cover
times of the late points are obtained in [8].

The random walks in which certain steps are forbidden are analyzed in [19].
The behavior for the Laplace transform of the expected mean-square
displacement was quite different in dimensions 2 and 3.

A future research could analyze the convex minorants of the underlying process
[1] and see whether these results can offer an insight on the exit times.

Balanced binary search trees are the fundamental data structures that enable
us to have logarithmic complexity for insertion, deletion, and retrieval of
data. The first such tree was constructed by Adelson-Velskii and Landis [2].
Future generalization of the model to trees in which each parent can have
multiple children were obtained by Rudolf Bayer [4]. Every time we insert or
delete data, the tree may need a re-balancing procedure. If several such
operations are performed at the same time, a special care needs to be made to
maintain the integrity of data. The reduction of re-balancing operations is a
very effective way to speed up the operations. Different modifications of the
fundamental data structures are made. It is common to introduce the randomness
in the construction, as was done in [24].

Most of the results in this paper are proved by applying the optional stopping
theorem to certain martingales and supermartingales [11, 25]. However, we
cannot use the standard version of the theorem. The martingales that we
construct are not bounded and do not have increments with bounded conditional
expectations. In addition, the stopping time could not be easily controlled.
In the end it will turn out that the stopping times could have $L^{2}$ norms.
However, the martingales are positive before the stopping time occurs. This
fact will allow us to construct arguments based on Hölder’s inequality.
Another example of a situation where unbounded functions require modifications
of the optional stopping theorem occurs in [22]. There are situations where
the theorem has to be avoided completely [16, 20]. For additional
generalizations of the optional stopping theorem, the reader is referred to
[21].

##  2\. Case $m=3$

Let us use $A(n)$ and $B(n)$ instead of $A_{1}(n)$ and $A_{2}(n)$.
Furthermore, let us denote $a=A(0)$ and $b=B(0)$. Let $\mathcal{F}_{n}$ bet
the sigma algebra generated by the first $n$ steps of the process.

######  Theorem 2.1.

Define the process $\left(G(n)\right)_{n=0}^{\infty}$ with

$G(n)=A(n)B(n)+\frac{n}{3}.$

The process $\left(G(n)\right)_{n=0}^{\infty}$ is a martingale with respect to
$\left(\mathcal{F}_{n}\right)_{n=0}^{\infty}$.

Proof. Denote $\alpha(n+1)=A(n+1)-A(n)$ and $\beta(n+1)=B(n+1)-B(n)$. Then

$\displaystyle\left[\begin{array}[]{c}\alpha(n+1)\\\
\beta(n+1)\end{array}\right]$ $\displaystyle\in$
$\displaystyle\left\\{\left[\begin{array}[]{c}-1\\\
0\end{array}\right],\left[\begin{array}[]{c}1\\\
-1\end{array}\right],\left[\begin{array}[]{c}0\\\
1\end{array}\right]\right\\}.$

The conditional expectation of $G(n+1)$ with respect to $\mathcal{F}_{n}$
satisfies

$\displaystyle\mathbb{E}\left[\left.G(n+1)\right|\mathcal{F}_{n}\right]$
$\displaystyle=$
$\displaystyle\frac{n+1}{3}+\mathbb{E}\left[\left.A(n+1)B(n+1)\right|\mathcal{F}_{n}\right]$
$\displaystyle=$
$\displaystyle\frac{n+1}{3}+\mathbb{E}\left[\left.\left(A(n)+\alpha(n+1)\right)\left(B(n)+\beta(n+1)\right)\right|\mathcal{F}_{n}\right]$
$\displaystyle=$
$\displaystyle\frac{n+1}{3}+A(n)B(n)+A(n)\mathbb{E}\left[\left.\alpha(n+1)\right|\mathcal{F}_{n}\right]$
$\displaystyle+B(n)\mathbb{E}\left[\left.\beta(n+1)\right|\mathcal{F}_{n}\right]+\mathbb{E}\left[\left.\alpha(n+1)\beta(n+1)\right|\mathcal{F}_{n}\right].$

Observe that $\alpha(n+1)$ and $\beta(n+1)$ are independent of
$\mathcal{F}_{n}$ and that

$\displaystyle\mathbb{E}\left[\alpha(n+1)\right]=0,\quad\mathbb{E}\left[\beta(n+1)\right]=0,\quad\mbox{and}\quad\mathbb{E}\left[\alpha(n+1)\beta(n+1)\right]=-\frac{1}{3}.$

Therefore $\mathbb{E}\left[\left.G(n+1)\right|\mathcal{F}_{n}\right]=G(n)$,
and $\left(G(n)\right)_{n=0}^{\infty}$ is a martingale with respect to
$\left(\mathcal{F}_{n}\right)_{n=0}^{\infty}$. $\Box$

######  Theorem 2.2.

Define the process $\left(G_{2,1}(n)\right)_{n=0}^{\infty}$ with

$G_{2,1}(n)=A^{2}(n)B(n)+A(n)B^{2}(n).$

The process $\left(G_{2,1}(n)\right)_{n=0}^{\infty}$ is a martingale with
respect to $\left(\mathcal{F}_{n}\right)_{n=0}^{\infty}$.

Proof. As in the proof of Theorem 2.1 we denote $\alpha(n+1)=A(n+1)-A(n)$ and
$\beta(n+1)=B(n+1)-B(n)$. Let us define

$\displaystyle G^{A}_{2,1}(n)$ $\displaystyle=$ $\displaystyle
A^{2}(n)B(n)\quad\mbox{ and}$ $\displaystyle G^{B}_{2,1}(n)$ $\displaystyle=$
$\displaystyle A(n)B^{2}(n).$

The conditional expectation of $G^{A}_{2,1}(n+1)$ with respect to
$\mathcal{F}_{n}$ satisfies

$\displaystyle\mathbb{E}\left[\left.G^{A}_{2,1}(n+1)\right|\mathcal{F}_{n}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\left.A^{2}(n+1)B(n+1)\right|\mathcal{F}_{n}\right]$
(8) $\displaystyle=$
$\displaystyle\mathbb{E}\left[\left.\left(A(n)+\alpha(n+1)\right)^{2}\left(B(n)+\beta(n+1)\right)\right|\mathcal{F}_{n}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\left.\left(A^{2}(n)+2\alpha(n+1)A(n)+\alpha^{2}(n+1)\right)\left(B(n)+\beta(n+1)\right)\right|\mathcal{F}_{n}\right]$
$\displaystyle=$ $\displaystyle
A^{2}(n)B(n)+2A(n)\mathbb{E}\left[\left.\alpha(n+1)\beta(n+1)\right|\mathcal{F}_{n}\right]+B(n)\mathbb{E}\left[\left.\alpha^{2}(n+1)\right|\mathcal{F}_{n}\right]$
$\displaystyle+\mathbb{E}\left[\left.\alpha^{2}(n+1)\beta(n+1)\right|\mathcal{F}_{n}\right]$
$\displaystyle=$ $\displaystyle
A^{2}(n)B(n)-\frac{2}{3}A(n)+\frac{2}{3}B(n)-\frac{1}{3}.$

The conditional expectation of $G^{B}_{2,1}(n+1)$ with respect to
$\mathcal{F}_{n}$ is

$\displaystyle\mathbb{E}\left[\left.G^{B}_{2,1}(n+1)\right|\mathcal{F}_{n}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\left.A(n+1)B^{2}(n+1)\right|\mathcal{F}_{n}\right]$
(9) $\displaystyle=$
$\displaystyle\mathbb{E}\left[\left.\left(A(n)+\alpha(n+1)\right)\left(B(n)+\beta(n+1)\right)^{2}\right|\mathcal{F}_{n}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\left.\left(B^{2}(n)+2\beta(n+1)B(n)+\beta^{2}(n+1)\right)\left(A(n)+\alpha(n+1)\right)\right|\mathcal{F}_{n}\right]$
$\displaystyle=$ $\displaystyle
B^{2}(n)A(n)+2B(n)\mathbb{E}\left[\left.\alpha(n+1)\beta(n+1)\right|\mathcal{F}_{n}\right]+A(n)\mathbb{E}\left[\left.\beta^{2}(n+1)\right|\mathcal{F}_{n}\right]$
$\displaystyle+\mathbb{E}\left[\left.\beta^{2}(n+1)\alpha(n+1)\right|\mathcal{F}_{n}\right]$
$\displaystyle=$ $\displaystyle
B^{2}(n)A(n)-\frac{2}{3}B(n)+\frac{2}{3}A(n)+\frac{1}{3}.$

It remains to add (8) and (9) to conclude that $G_{2,1}(n)$ is a martingale.
$\Box$

Proof of Theorem 1.1. Let us define $T_{n}=\min\\{T,n\\}$. For every fixed
$n$, the random variable $T_{n}$ is a stopping time with respect to
$\left(\mathcal{F}_{n}\right)_{n=0}^{\infty}$. The stopping time $T_{n}$ is
bounded. Therefore, we can use the optional stopping theorem together with
theorems 2.1 and 2.2 to conclude

$\displaystyle\mathbb{E}\left[A\left({T_{n}}\right)B\left({T_{n}}\right)\right]+\frac{1}{3}\mathbb{E}\left[T_{n}\right]$
$\displaystyle=$ $\displaystyle ab,\quad\mbox{and}$ (10)
$\displaystyle\mathbb{E}\left[A^{2}({T_{n}})B({T_{n}})+A\left(T_{n}\right)B\left(T_{n}\right)^{2}\right]$
$\displaystyle=$ $\displaystyle ab(a+b).$ (11)

The random variables $A\left(T_{n}\right)$ and $B\left(T_{n}\right)$ are
positive, the sequence $\left(T_{n}\right)_{n=0}^{\infty}$ is non-decreasing,
and (10) holds for every $n$. Therefore, $\mathbb{E}\left[T_{n}\right]\leq
3ab$ for every $n$, the monotone convergence theorem implies that
$\mathbb{E}\left[T_{n}\right]\to\mathbb{E}\left[T\right]$, and the random
variable $T$ has finite $L^{1}$ norm bounded by $3ab$, i.e.

$\displaystyle\mathbb{E}\left[T\right]\leq 3ab.$ (12)

In order to prove that $\mathbb{E}\left[T\right]=3ab$, it suffices to prove

$\displaystyle\lim_{n\to\infty}\mathbb{E}\left[A\left(T_{n}\right)B\left(T_{n}\right)\right]$
$\displaystyle=$ $\displaystyle 0.$ (13)

Using Hölder’s inequality we obtain

$\displaystyle\mathbb{E}\left[A\left(T_{n}\right)B\left(T_{n}\right)\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[A\left(T_{n}\right)B\left(T_{n}\right)\cdot
1_{T>n}\right]$ (14) $\displaystyle\leq$
$\displaystyle\mathbb{E}\left[A^{\frac{3}{2}}\left(T_{n}\right)B^{\frac{3}{2}}\left(T_{n}\right)\right]^{\frac{2}{3}}\cdot\mathbb{E}\left[\left(1_{T>n}\right)^{3}\right]^{\frac{1}{3}}.$

Using Cauchy-Schwarz inequality we now obtain

$\displaystyle\mathbb{E}\left[A^{\frac{3}{2}}\left(T_{n}\right)B^{\frac{3}{2}}\left(T_{n}\right)\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\left(A\left(T_{n}\right)\sqrt{B\left(T_{n}\right)}\right)\cdot\left(B\left(T_{n}\right)\sqrt{A\left(T_{n}\right)}\right)\right]$
(15) $\displaystyle\leq$
$\displaystyle\sqrt{\mathbb{E}\left[A^{2}\left(T_{n}\right)B\left(T_{n}\right)\right]}\cdot\sqrt{\mathbb{E}\left[B^{2}\left(T_{n}\right)A\left(T_{n}\right)\right]}.$

Since $A\left(T_{n}\right)$ and $B\left(T_{n}\right)$ are non-negative, two
obvious consequences of (11) are

$\displaystyle\mathbb{E}\left[A^{2}\left(T_{n}\right)B\left(T_{n}\right)\right]\leq
ab(a+b)\quad\mbox{and}\quad\mathbb{E}\left[A\left(T_{n}\right)B^{2}\left(T_{n}\right)\right]\leq
ab(a+b).$

Therefore, inequality (15) implies

$\displaystyle\mathbb{E}\left[A^{\frac{3}{2}}\left(T_{n}\right)B^{\frac{3}{2}}\left(T_{n}\right)\right]$
$\displaystyle\leq$ $\displaystyle a^{2}b^{2}(a+b)^{2}.$ (16)

From the inequalities (14) and (16) we conclude

$\displaystyle\mathbb{E}\left[A\left(T_{n}\right)\mathbb{B}\left(T_{n}\right)\right]$
$\displaystyle\leq$ $\displaystyle a^{\frac{4}{3}}\cdot
b^{\frac{4}{3}}\cdot(a+b)^{\frac{4}{3}}\cdot\mathbb{P}\left(T>n\right)^{\frac{1}{3}}.$
(17)

From (12) we have that $L^{1}$ norm of $T$ is finite. Therefore, the right-
hand side of (17) converges to $0$ as $n\to\infty$. Thus, we are now able to
deduce (13). This completes the proof of the theorem. $\Box$

##  3\. Bounds for $m\geq 4$

The main object of our study is a vector-valued random process
$\overrightarrow{A}(n)=\left[\begin{array}[]{c}A_{1}(n)\\\ \vdots\\\
A_{m-1}(n)\end{array}\right]$ that starts from
$\overrightarrow{A}(0)=\left[\begin{array}[]{c}a_{1}\\\ \vdots\\\
a_{m-1}\end{array}\right]$ for some $a_{1}$, $\dots$, $a_{m-1}\in\mathbb{N}$.
In each step we have
$\overrightarrow{A}(n+1)=\overrightarrow{A}(n)+\overrightarrow{\xi}(n+1)$,
where $\overrightarrow{\xi}(1)$, $\overrightarrow{\xi}(2)$, $\dots$ are
independent random vectors with uniform distribution on the set
$V=\left\\{\overrightarrow{\xi_{1}},\dots,\overrightarrow{\xi_{m}}\right\\}$,
where the vectors $\overrightarrow{\xi_{1}}$, $\dots$,
$\overrightarrow{\xi_{m}}$ are of dimension $m-1$ and satisfy

$\overrightarrow{\xi_{1}}=\left[\begin{array}[]{c}-1\\\ 0\\\ \vdots\\\ 0\\\
0\end{array}\right],\quad\overrightarrow{\xi_{2}}=\left[\begin{array}[]{c}1\\\
-1\\\ \vdots\\\ 0\\\
0\end{array}\right],\quad\dots,\quad\overrightarrow{\xi_{m-1}}=\left[\begin{array}[]{c}0\\\
0\\\ \vdots\\\ 1\\\
-1\end{array}\right],\quad\overrightarrow{\xi_{m}}=\left[\begin{array}[]{c}0\\\
0\\\ \vdots\\\ 0\\\ 1\end{array}\right].$

Denote by $\mathcal{F}_{n}$ the sigma algebra determined by the process until
time $n$.

######  Theorem 3.1.

For each $i\in\\{1,2,\dots,m-2\\}$, the process
$\left(M_{i}(n)\right)_{n=0}^{\infty}$ defined with

$M_{i}(n)=A_{i}(n)A_{i+1}(n)+\frac{n}{m}$

is a martingale with respect to $\left(\mathcal{F}_{n}\right)_{n=0}^{\infty}$.

Proof. We will first calculate the conditional expectation of
$A_{i}(n+1)A_{i+1}(n+1)$ with respect to the sigma algebra $\mathcal{F}_{n}$.

$\displaystyle\mathbb{E}\left[\left.A_{i}(n+1)A_{i+1}(n+1)\right|\mathcal{F}_{n}\right]$
$\displaystyle=$
$\displaystyle\frac{1}{m}\sum_{k=1}^{m}\mathbb{E}\left[\left.A_{i}(n+1)A_{i+1}(n+1)\cdot
1_{\overrightarrow{\xi}(n+1)=\overrightarrow{\xi_{k}}}\right|\mathcal{F}_{n}\right].$
(18)

Observe that the vector $\overrightarrow{\xi_{1}}$ modifies only the first
component of $\overrightarrow{X(n)}$. For $k\in\\{2,3,\dots,m-1\\}$, the
vector $\overrightarrow{\xi_{k}}$ modifies only the components $k-1$ and $k$.
The vector $\overrightarrow{\xi_{m}}$ modifies only the component $m-1$.
Therefore, the equation (18) becomes

$\displaystyle\mathbb{E}\left[\left.A_{i}(n+1)A_{i+1}(n+1)\right|\mathcal{F}_{n}\right]$
$\displaystyle=$
$\displaystyle\frac{m-3}{m}A_{i}(n)A_{i+1}(n)+\frac{1}{m}\left(A_{i}(n)-1\right)A_{i+1}(n)$
(19)
$\displaystyle+\frac{1}{m}\left(A_{i}(n)+1\right)\left(A_{i+1}(n)-1\right)+\frac{1}{m}A_{i}(n)\left(A_{i+1}(n)+1\right).$
$\displaystyle=$ $\displaystyle A_{i}(n)A_{i+1}(n)-\frac{1}{m}.$

From equation (19) we directly obtain that
$\left(M_{i}(n)\right)_{n=0}^{\infty}$ is a martingale. $\Box$

######  Theorem 3.2.

Define the process $M(n)$ as

$M(n)=\min\left\\{M_{1}(n),M_{2}(n),\dots,M_{m-1}(n)\right\\}.$

The process $\left(M(n)\right)_{n=0}^{\infty}$ is a supermartingale with
respect to $\left(\mathcal{F}_{n}\right)_{n=0}^{\infty}$.

Proof.  The proof directly follows from the observation that the minimum of a
set of martingales is a supermartingale. $\Box$

Proof of Theorem 1.2. Consider the truncation $T_{n}=\min\\{T,n\\}$ of the
stopping time $T$. The stopping time $T_{n}$ is bounded above and we can use
optional stopping theorem together with Theorem 3.2 to obtain

$\displaystyle\mathbb{E}\left[\min\left\\{A_{i}\left(T_{n}\right)A_{i+1}\left(T_{n}\right):i\in\\{1,2,\dots,m-1\\}\right\\}\right]+\frac{1}{m}\mathbb{E}\left[T_{n}\right]$
(20) $\displaystyle\leq$
$\displaystyle\min\left\\{a_{1}a_{2},\dots,a_{m-1}a_{m}\right\\}.$

Since each of $A_{i}\left(T_{n}\right)$ is non-negative, the inequality (20)
implies

$\displaystyle\frac{1}{m}\mathbb{E}\left[T_{n}\right]$ $\displaystyle\leq$
$\displaystyle\min\left\\{a_{1}a_{2},\dots,a_{m-1}a_{m}\right\\}.$

Therefore, the stopping times $T_{n}$ have bounded $L^{1}$ norms. Hence, the
sequence of stopping times $\left(T_{n}\right)_{n=0}^{\infty}$ is non-
decreasing. The monotone convergence theorem implies that
$\lim_{n\to\infty}\mathbb{E}\left[T_{n}\right]=\mathbb{E}\left[T\right]$ and

$\mathbb{E}\left[T\right]\leq
m\min\left\\{a_{1}a_{2},\dots,a_{m-1}a_{m}\right\\}.$

The proof of the theorem is complete. $\Box$

Let us define the stopping time $T_{i,i+1}$ as

$\displaystyle T_{i,i+1}$ $\displaystyle=$
$\displaystyle\inf\left\\{n:A_{i}(n)A_{i+1}(n)=0\right\\}.$ (21)

######  Theorem 3.3.

The expected value of $T_{i,i+1}$ satisfies

$\displaystyle\mathbb{E}\left[T_{i,i+1}\right]$ $\displaystyle=$
$\displaystyle ma_{i}a_{i+1}.$ (22)

Proof.  The proof is almost the same as the proof of Theorem 1.1. $\Box$

Proof of Theorem 1.3. Assume that $i\in\\{1,2,\dots,m-2\\}$ is fixed. Assume
that $a_{i}$ and $a_{i+1}$ are two fixed positive real numbers. We will prove
that for every $\varepsilon>0$, there exists an integer $N_{0}$ such that if
$a_{j}\geq N_{0}$ for $j\in\\{1,2,\dots,m-1\\}\setminus\\{i,i+1\\}$, then

$\displaystyle\mathbb{E}\left[T\right]$ $\displaystyle\geq$ $\displaystyle
ma_{i}a_{i+1}-\varepsilon.$ (23)

Let $n_{1}$, $n_{2}$, $\dots$, be the sequence of times for which

$\left(A_{i}(n_{k}-1),A_{i+1}(n_{k}-1)\right)\neq\left(A_{i}(n_{k}),A_{i+1}(n_{k})\right).$

The quantities $n_{1}$, $n_{2}$, $\dots$ are random variables. Clearly,
$A_{i}(n)$ and $A_{i+1}(n)$ can become $0$ only for
$n\in\\{n_{1},n_{2},\dots\\}$. Define $T^{\prime}$ as

$T^{\prime}=\min\left\\{k:A_{i}(n_{k})A_{i+1}(n_{k})=0\right\\}.$

For $N\in\mathbb{N}$, let $T^{\prime}_{N}=\min\\{T^{\prime},N\\}$. Theorem 1.1
implies that

$\lim_{N\to\infty}\mathbb{E}\left[T^{\prime}_{N}\right]=3a_{i}a_{i+1}.$

Therefore, for our fixed $\varepsilon$ there exists $N\in\mathbb{N}$ such that

$\displaystyle\mathbb{E}\left[T^{\prime}_{N}\right]\geq
3a_{i}a_{i+1}-\frac{3}{2m}\varepsilon.$ (24)

Let us denote by $G_{1}$, $G_{2}$, $\dots$, the gaps in the sequence $n_{1}$,
$n_{2}$, $\dots$. More precisely, $G_{k}$ is defined as

$G_{k}=n_{k}-n_{k-1}.$

In the last equation we assume that $n_{0}=0$.

Each of the variables $G_{k}$ has geometric distribution with parameter
$\frac{3}{m}$. Therefore, $\mathbb{E}\left[G_{k}\right]=\frac{m}{3}$ for every
$k$. This implies

$\displaystyle\mathbb{E}\left[G_{1}+G_{2}+\cdots+G_{T_{N}^{\prime}}\right]$
$\displaystyle=$
$\displaystyle\sum_{p=1}^{N}\mathbb{E}\left[\left.G_{1}+G_{2}+\cdots+G_{T_{N}^{\prime}}\right|T_{N}^{\prime}=p\right]\mathbb{P}\left(T_{N}^{\prime}=p\right)$
$\displaystyle=$
$\displaystyle\sum_{p=1}^{N}\mathbb{E}\left[\left.G_{1}+G_{2}+\cdots+G_{p}\right|T_{N}^{\prime}=p\right]\mathbb{P}\left(T_{N}^{\prime}=p\right)$
$\displaystyle=$
$\displaystyle\sum_{p=1}^{N}\frac{mp}{3}\mathbb{P}\left(T_{N}^{\prime}=p\right)=\frac{m}{3}\sum_{p=1}^{N}p\mathbb{P}\left(T_{N}^{\prime}=p\right)=\frac{m}{3}\cdot\mathbb{E}\left[T_{N}^{\prime}\right].$

We can now use inequality (24) to obtain

$\displaystyle\mathbb{E}\left[G_{1}+G_{2}+\cdots+G_{T_{N}^{\prime}}\right]$
$\displaystyle\geq$
$\displaystyle\frac{m}{3}\left(3a_{i}a_{i+1}-\frac{3}{2m}\varepsilon\right)=ma_{i}a_{i+1}-\frac{\varepsilon}{2}.$
(25)

It suffices to prove that there exists $N_{0}$ such that if $a_{j}\geq N_{0}$
for every $j\not\in\\{i,i+1\\}$, then

$\displaystyle\mathbb{E}\left[T\right]$ $\displaystyle\geq$
$\displaystyle\mathbb{E}\left[G_{1}+G_{2}+\cdots+G_{T_{N}^{\prime}}\right]-\frac{\varepsilon}{2}.$
(26)

Then, inequalities (25) and (26) would imply (23).

So far, we proved that for every choice of $\left(a_{i},a_{i+1}\right)$ and
every $\varepsilon>0$, there exists $N$ such that (24) holds. The inequality
does not depend on values $a_{j}$ for $j\not\in\\{i,i+1\\}$. This is not too
surprising since the random variables $T_{N}^{\prime}$, $G_{1}$, $G_{2}$,
$\dots$ do not depend on $a_{j}$ for $j\not\in\\{i,i+1\\}$. Recall that
$T_{n}=\min\\{T,n\\}$ is the truncation of the stopping time $T$. The stopping
times $T$ and $T_{n}$ depend on all $a_{j}$, for $j\in\\{1,2,\dots,m-1\\}$.
Let us denote $\hat{G}_{N}=G_{1}+G_{2}+\dots+G_{T^{\prime}_{N}}$ and let
$Q_{n}$ be the event defined as

$Q_{n}=\\{T_{n}\geq\hat{G}_{N}\\}.$

For every $n$ and every choice of $a_{j}$ with $j\not\in\\{i,i+1\\}$ we have

$\displaystyle\mathbb{E}\left[T\right]$ $\displaystyle\geq$
$\displaystyle\mathbb{E}\left[T_{n}\right]\geq\mathbb{E}\left[T_{n}\cdot
1_{Q_{n}}\right]\geq\mathbb{E}\left[\hat{G}_{N}\cdot
1_{Q_{n}}\right]=\mathbb{E}\left[\hat{G}_{N}\right]-\mathbb{E}\left[\hat{G}_{N}\cdot
1_{Q_{n}^{C}}\right]$ (27) $\displaystyle=$
$\displaystyle\mathbb{E}\left[G_{1}+G_{2}+\cdots+G_{T_{N}^{\prime}}\right]-\mathbb{E}\left[\hat{G}_{N}\cdot
1_{Q_{n}^{C}}\right].$

We will now prove that there exists $N_{0}$ such that whenever $a_{j}\geq
N_{0}$ for $j\not\in\\{i,i+1\\}$, the following inequality holds:

$\displaystyle\mathbb{E}\left[\hat{G}_{N}\cdot 1_{Q_{n}^{C}}\right]$
$\displaystyle\leq$ $\displaystyle\frac{\varepsilon}{2}.$ (28)

Then, the inequalities (27) and (28) would imply that (26) holds whenever
$a_{j}\geq N_{0}$ for $j\not\in\\{i,i+1\\}$. Observe that
$\hat{G}_{N}=G_{1}+G_{2}+\cdots+G_{T^{\prime}_{N}}\leq
G_{1}+G_{2}+\cdots+G_{N}$ and that $G_{1}+\cdots+G_{N}$ has negative binomial
distribution with parameters $N$ and $\frac{m-3}{m}$. Here we use the
following convention: A negative binomial random variable with parameters $r$
and $p$ is the total number of Bernoulli trials until $r$ failures, where the
probability of success in each trial is $p$. The second moment of negative
binomial random variable $G_{1}+\cdots+G_{N}$ is

$\displaystyle\mathbb{E}\left[\left(G_{1}+\cdots+G_{N}\right)^{2}\right]$
$\displaystyle=$
$\displaystyle\frac{r(r+p)}{(1-p)^{2}}=\frac{N\left(N+\frac{m-3}{m}\right)}{\frac{9}{m^{2}}}=\frac{mN\left(mN+m-3\right)}{9}.$

The Cauchy–Schwarz inequality implies

$\displaystyle\mathbb{E}\left[\hat{G}_{N}\cdot 1_{Q_{n}^{C}}\right]$
$\displaystyle\leq$
$\displaystyle\sqrt{\mathbb{E}\left[\hat{G}_{N}^{2}\right]}\cdot\sqrt{\mathbb{P}\left(Q_{n}^{C}\right)}=\sqrt{\frac{mN\left(mN+m-3\right)}{9}}\sqrt{\mathbb{P}\left(Q_{n}^{c}\right)}.$
(29)

Let us now analyze the event $Q_{n}^{C}$.

$\displaystyle Q_{n}^{C}$ $\displaystyle=$
$\displaystyle\left\\{T_{n}<\hat{G}_{N}\right\\}\subseteq\left\\{T_{n}<G_{1}+G_{2}+\cdots+G_{T^{\prime}}\right\\}.$

Observe that $G_{1}+G_{2}+\cdots+G_{T^{\prime}}=T_{i,i+1}$ where $T_{i,i+1}$
is defined by (21) and is the smallest $k$ for which $A_{i}(k)A_{i+1}(k)=0$.
Therefore

$\displaystyle\mathbb{P}\left(Q_{n}^{C}\right)\leq\mathbb{P}\left(T_{n}<T_{i,i+1}\right).$
(30)

From Theorem 3.3 we know that
$\mathbb{E}\left[T_{i,i+1}\right]=ma_{i}a_{i+1}<+\infty$. Therefore, we must
have

$\lim_{w\to\infty}\mathbb{P}\left(T_{i,i+1}>w\right)=0.$

This means that for given $\varepsilon>0$ there exists $N_{0}$ such that
$n\geq N_{0}$ implies

$\displaystyle\mathbb{P}\left(T_{i,i+1}>n\right)\leq\frac{\varepsilon^{2}}{4\cdot\frac{mN\left(mN+m-3\right)}{9}}.$
(31)

We will now prove that if $a_{j}>N_{0}$ for all
$j\in\\{1,2,\dots,m-1\\}\setminus\\{i,i+1\\}$, then

$\displaystyle\left\\{T_{i,i+1}>T_{N_{0}}\right\\}\subseteq\left\\{T_{i,i+1}>N_{0}\right\\}.$
(32)

Indeed, if all $a_{j}$ for $j\not\in\\{i,i+1\\}$ are bigger than $N_{0}$, then
in the first $N_{0}$ steps none of the random variables $A_{j}$ can reach $0$.
Therefore, on the event $\left\\{T\leq N_{0}\right\\}$, the random variable
$T$ is equal to $T_{i,i+1}$. The event $\\{T_{i,i+1}>T_{N_{0}}\\}$ satisfies

$\displaystyle\left\\{T_{i,i+1}>T_{N_{0}}\right\\}$ $\displaystyle=$
$\displaystyle\left\\{T_{i,i+1}>T_{N_{0}},T<N_{0}\right\\}\cup\left\\{T_{i,i+1}>T_{N_{0}},T\geq
N_{0}\right\\}$ $\displaystyle=$
$\displaystyle\left\\{T_{i,i+1}>T,T<N_{0}\right\\}\cup\left\\{T_{i,i+1}>{N_{0}},T\geq
N_{0}\right\\}$ $\displaystyle=$
$\displaystyle\emptyset\cup\left\\{T_{i,i+1}>{N_{0}},T\geq N_{0}\right\\}.$

The last equality clearly implies (32). We now use (30), (31), and (32) with
$n=N_{0}$ to derive

$\displaystyle\mathbb{P}\left(Q_{N_{0}}^{C}\right)\leq\mathbb{P}\left(T_{N_{0}}<T_{i,i+1}\right)\leq\mathbb{P}\left(N_{0}<T_{i,i+1}\right)\leq\frac{\varepsilon^{2}}{4\cdot\frac{mN\left(mN+m-3\right)}{9}}.$

The last inequality together with (29) implies (28). As discussed earlier,
(28) immediately implies (26) under the conditions $a_{j}\geq N_{0}$ for
$j\not\in\\{i,i+1\\}$. Together with (25), the inequality (26) implies (23),
which completes the proof of the theorem. $\Box$

##  4\. Improved bound for $m=4$

The vector-valued random process
$\overrightarrow{A}(n)=\left[\begin{array}[]{c}A(n)\\\ B(n)\\\
C(n)\end{array}\right]$ starts from
$\overrightarrow{A}(0)=\left[\begin{array}[]{c}a\\\ b\\\ c\end{array}\right]$
for some $a$, $b$, $c\in\mathbb{N}$. In each step we have
$\overrightarrow{A}(n+1)=\overrightarrow{A}(n)+\overrightarrow{\xi}(n+1)$,
where $\overrightarrow{\xi}(1)$, $\overrightarrow{\xi}(2)$, $\dots$ are
independent random vectors with uniform distribution on the set

$V=\left\\{\left[\begin{array}[]{c}-1\\\ 0\\\
0\end{array}\right],\left[\begin{array}[]{c}1\\\ -1\\\
0\end{array}\right],\left[\begin{array}[]{c}0\\\ 1\\\
-1\end{array}\right]\left[\begin{array}[]{c}0\\\ 0\\\
1\end{array}\right]\right\\}.$

Let $\varphi:\mathbb{N}\times\mathbb{N}$ be the function defined in the
following way:

$\displaystyle\varphi(x,y)$ $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{ll}\max\\{x,y\\},&\mbox{if }x\neq y,\\\
\frac{2x^{2}}{2x-1},&\mbox{if }x=y.\end{array}\right.$ (35)

Let us define the following process:

$\displaystyle M(n)$ $\displaystyle=$
$\displaystyle\frac{A(n)B(n)C(n)}{\varphi\left(A(n),C(n)\right)}+\frac{n}{4}.$
(36)

######  Theorem 4.1.

The processes $\left(M(n)\right)_{n=0}^{\infty}$ is a supermartingale with
respect to the filtration $\left(\mathcal{F}_{n}\right)_{n=0}^{\infty}$ of
sigma algebras generated by the processes $A(n)$, $B(n)$, and $C(n)$. In other
words,

$\mathbb{E}\left[\left.M(n+1)\right|\mathcal{F}_{n}\right]\leq M(n).$

Proof. The conditional expectation of $M(n+1)$ with respect to the sigma
algebra $\mathcal{F}_{n}$ satisfies

$\displaystyle\mathbb{E}\left[\left.M(n+1)\right|\mathcal{F}_{n}\right]$
$\displaystyle=$
$\displaystyle\frac{n+1}{4}+\mathbb{E}\left[\left.\frac{A(n+1)B(n+1)C(n+1)}{\varphi\left(A(n+1),C(n+1)\right)}\right|\mathcal{F}_{n}\right]$
$\displaystyle=$
$\displaystyle\frac{n+1}{4}+\frac{\left(A(n)-1\right)B(n)C(n)}{4\varphi(A(n)-1,C(n))}+\frac{\left(A(n)+1\right)\left(B(n)-1\right)C(n)}{4\varphi(A(n)+1,C(n))}$
$\displaystyle+\frac{A(n)\left(B(n)+1\right)\left(C(n)-1\right)}{4\varphi(A(n),C(n)-1)}+\frac{A(n)B(n)\left(C(n)+1\right)}{4\varphi(A(n),C(n)+1)}.$

In order to prove that $\left(M(n)\right)_{n=0}^{\infty}$ is a supermartingale
it suffices to show that for all $x$, $y$, $z\in\mathbb{N}$ the following
inequality holds

$\displaystyle\frac{4xyz}{\varphi(x,z)}-1$ $\displaystyle\geq$
$\displaystyle\frac{(x-1)yz}{\varphi(x-1,z)}+\frac{(x+1)(y-1)z}{\varphi(x+1,z)}+\frac{x(y+1)(z-1)}{\varphi(x,z-1)}+\frac{xy(z+1)}{\varphi(x,z+1)}.$
(37)

We will distinguish the following $5$ cases.

  1. $1^{\circ}$

$x=z$;

  2. $2^{\circ}$

$x=z+1$;

  3. $3^{\circ}$

$x=z-1$;

  4. $4^{\circ}$

$x\geq z+2$;

  5. $5^{\circ}$

$x\leq z-2$.

In case $1^{\circ}$ the inequality (37) turns into an equality. The following
holds

$\displaystyle\frac{4x^{2}y}{\frac{2x^{2}}{2x-1}}-1$ $\displaystyle=$
$\displaystyle\frac{(x-1)yx}{x}+\frac{(x+1)(y-1)x}{(x+1)}+\frac{x(y+1)(x-1)}{x}+\frac{xy(x+1)}{(x+1)}.$
(38)

The left-hand side is equal to $L_{1}(x,y)=2y(2x-1)-1$ and the right-hand side
is $R_{1}(x,y)=(x-1)y+x(y-1)+(x-1)(y+1)+xy$. After simple algebraic
transformations one can see that the polynomials $L_{1}(x,y)$ and $R_{2}(x,y)$
are equal. We conclude that (38) is true in Case $1^{\circ}$.

In case $2^{\circ}$ the inequality (37) transforms into

$\displaystyle\frac{4xy(x-1)}{x}-1$ $\displaystyle\geq$
$\displaystyle\frac{(x-1)y(x-1)}{\frac{2(x-1)^{2}}{2(x-1)-1}}+\frac{(x+1)(y-1)(x-1)}{(x+1)}+\frac{x(y+1)(x-2)}{x}+\frac{xyx}{\frac{2x^{2}}{2x-1}}.$
(39)

After canceling the fractions we obtain that the left-hand side of (39) is
$L_{2}(x,y)=4y(x-1)-1$ and the right-hand side is
$R_{2}(x,y)=y(x-\frac{3}{2})+(y-1)(x-1)+(y+1)(x-2)+y\left(x-\frac{1}{2}\right)$.
The difference between the left-hand side and the right-hand side is $y$,
which is a non-negative integer. Therefore (37) holds in Case $2^{\circ}$.

Let us now consider the case $3^{\circ}$. The inequality (37) is equivalent to

$\displaystyle\frac{4xy(x+1)}{(x+1)}-1$ $\displaystyle\geq$
$\displaystyle\frac{(x-1)y(x+1)}{(x+1)}+\frac{(x+1)(y-1)(x+1)}{\frac{2(x+1)^{2}}{2(x+1)-1}}+\frac{x(y+1)x}{\frac{2x^{2}}{2x-1}}+\frac{xy(x+2)}{x+2}.$
(40)

The left-hand side is $L_{3}(x,y)=4xy-1$ and the right-hand side is
$R_{3}(x,y)=(x-1)y+(y-1)\left(x+\frac{1}{2}\right)+(y+1)\left(x-\frac{1}{2}\right)+xy$.
The difference between the two polynomials becomes $L_{3}(x,y)-R_{3}(x,y)=y$.
This is always a non-negative number, hence (37) holds in Case $3^{\circ}$.

In each of the cases $4^{\circ}$ and $5^{\circ}$ the inequality (37) turns
into equality. In case $4^{\circ}$ we have

$\displaystyle\frac{4xyz}{x}-1$ $\displaystyle\geq$
$\displaystyle\frac{(x-1)yz}{x-1}+\frac{(x+1)(y-1)z}{x+1}+\frac{x(y+1)(z-1)}{x}+\frac{xy(z+1)}{x}.$
(41)

The left-hand side is the polynomial $L_{4}(y,z)=4yz-1$, while the right-hand
side is the polynomial

$R_{4}(y,z)=yz+(y-1)z+(y+1)(z-1)+y(z+1)=4yz-z+z-y-1+y=4yz-1.$

It is easy to verify that $L_{4}(y,z)=R_{4}(y,z)$. In case $5^{\circ}$ we
obtain that the left-hand side of (37) is $L_{5}(x,y)=4xy-1$ while the right-
hand side is

$R_{5}(x,y)=(x-1)y+(x+1)(y-1)+x(y+1)+xy=4xy-y+y-x+x-1=4xy-1.$

The polynomials $L_{5}(x,y)$ and $R_{5}(x,y)$ are equal. This completes the
casework. Thus, the process $\left(M(n)\right)_{n=0}^{\infty}$ is a
supermartingale. $\Box$

Proof of Theorem 1.4. Using similar arguments as before, we obtain that the
stopping time $T$ is almost-surely finite. The stopping time $T$ is bounded
above by the stopping time $T_{AB}$ defined as

$T_{AB}=\min\\{n:A(n)B(n)=0\\}.$

The stopping time $T_{AB}$ is almost surely finite. Moreover, its $L^{1}$ norm
is finite, according to Theorem 3.3. Let $T_{N}=\min\\{T,N\\}$. Observe that
$M(T)=0$. At stopping time $T$ we are always having a zero factor in the
numerator. The numerator is divided by the bigger of the numbers $A(T)$ and
$C(T)$ if $A(T)\neq C(T)$, hence the zero in the numerator remains. If
$A(T)=C(T)$, then they cannot be both $0$, and $B(T)$ must be $0$ in that
case. Indeed, $A(n)$ and $B(n)$ are two of the random processes $A(n)$,
$B(n)$, $C(n)$. Two of the processes cannot attaint the value $0$ at the same
time. According to optional stopping theorem we have that for fixed $N$ the
following inequality holds

$\mathbb{E}\left[M(T_{N})\right]+\frac{1}{4}\mathbb{E}\left[T_{N}\right]\leq\frac{abc}{\varphi(a,c)}.$

Since $\mathbb{E}\left[M(T_{N})\right]\geq 0$ we obtain

$\mathbb{E}\left[T_{N}\right]\leq\frac{4abc}{\varphi(a,c)}=\left\\{\begin{array}[]{ll}4ab,&\mbox{if
}a<c,\\\ 4bc,&\mbox{if }a>c,\\\ 2b(2a-1),&\mbox{if }a=c.\end{array}\right.$

It remains to observe that the last inequality implies (6). $\Box$

##  5\. Second moments

######  Lemma 5.1.

For fixed $i\in\\{1,2,\dots,m-2\\}$, let us define the process
$\left(H_{i,i+1}(n)\right)_{n=0}^{\infty}$ as

$\displaystyle H_{i,i+1}(n)$ $\displaystyle=$ $\displaystyle
A_{i}^{2}(n)A_{i+1}^{2}(n)+\frac{2}{3}A_{i}(n)A_{i+1}(n)\left(A_{i}^{2}(n)+A_{i+1}^{2}(n)\right).$
(42)

The process $H_{i,i+1}(n)$ satisfies

$\displaystyle\mathbb{E}\left[\left.H_{i,i+1}(n+1)\right|\mathcal{F}_{n}\right]$
$\displaystyle=$ $\displaystyle
H_{i,i+1}(n)+\frac{4}{m}A_{i}(n)A_{i+1}(n)-\frac{1}{3m}.$ (43)

Proof. We will first establish the following identities.

$\displaystyle\mathbb{E}\left[\left.A_{i}^{2}(n+1)A_{i+1}^{2}(n+1)\right|\mathcal{F}_{n}\right]$
$\displaystyle=$ $\displaystyle
A_{i}^{2}(n)A_{i+1}^{2}(n)+\frac{1}{m}\left(2A_{i}^{2}(n)+2A_{i+1}^{2}(n)\right)$
(44)
$\displaystyle+\frac{1}{m}\left(2A_{i}(n)-2A_{i+1}(n)-4A_{i}(n)A_{i+1}(n)+1\right),$
$\displaystyle\mathbb{E}\left[\left.A_{i}^{3}(n+1)A_{i+1}(n+1)\right|\mathcal{F}_{n}\right]$
$\displaystyle=$ $\displaystyle A_{i}^{3}(n)A_{i+1}(n)+\frac{1}{m}\cdot
6A_{i}(n)A_{i+1}(n)$ (45)
$\displaystyle+\frac{1}{m}\left(-3A_{i}^{2}(n)-3A_{i}(n)-1\right),$
$\displaystyle\mathbb{E}\left[\left.A_{i}(n+1)A_{i+1}^{3}(n+1)\right|\mathcal{F}_{n}\right]$
$\displaystyle=$ $\displaystyle A_{i}(n)A_{i+1}^{3}(n)+\frac{1}{m}\cdot
6A_{i}(n)A_{i+1}(n)$ (46)
$\displaystyle\frac{1}{m}\left(-3A_{i+1}^{2}(n)+3A_{i+1}(n)-1\right).$

The proof of each of equalities (44), (45), and (46) is based on the
observation that

$\left[\begin{array}[]{c}A_{i}(n+1)\\\
A_{i+1}(n+1)\end{array}\right]=\left[\begin{array}[]{c}A_{i}(n)\\\
A_{i+1}(n)\end{array}\right]$

holds with probability $\frac{m-3}{m}$. The vector
$\left[\begin{array}[]{c}A_{i}(n+1)\\\ A_{i+1}(n+1)\end{array}\right]$ is
equal to one of the vectors from the set

$V_{i,i+1}(n)=\left\\{\left[\begin{array}[]{c}A_{i}(n)-1\\\
A_{i+1}(n)\end{array}\right],\left[\begin{array}[]{c}A_{i}(n)+1\\\
A_{i+1}(n)-1\end{array}\right],\left[\begin{array}[]{c}A_{i}(n)\\\
A_{i+1}(n)-1\end{array}\right]\right\\}.$

Each of the last vectors from $V_{i,i+1}(n)$ occurs with probability
$\frac{1}{m}$. Now, the left-hand side of equality (44) can be transformed
into

$\displaystyle\mathbb{E}\left[\left.A_{i}^{2}(n+1)A_{i+1}^{2}(n+1)\right|\mathcal{F}_{n}\right]$
$\displaystyle=$
$\displaystyle\frac{m-3}{m}A_{i}^{2}(n)A_{i+1}^{2}(n)+\frac{1}{m}\left(A_{i}(n)-1\right)^{2}A_{i+1}^{2}(n)$
(47)
$\displaystyle+\frac{1}{m}\left(A_{i}(n)+1\right)^{2}\left(A_{i+1}-1\right)^{2}(n)+\frac{1}{m}A_{i}^{2}(n)\left(A_{i+1}(n)+1\right)^{2}.$

Elementary algebraic transformations can be now used to turn the equality (47)
into (44). We will now prove the equality (45). To make notation shorter we
will omit the argument of $A_{i}$ and $A_{i+1}$, if it is equal to $n$. We
will write $A_{i}$ and $A_{i+1}$ instead of $A_{i}(n)$ and $A_{i+1}(n)$.

$\displaystyle\mathbb{E}\left[\left.A_{i}^{3}(n+1)A_{i+1}(n+1)\right|\mathcal{F}_{n}\right]$
$\displaystyle=$
$\displaystyle\frac{m-3}{m}A_{i}^{3}A_{i+1}+\frac{1}{m}\left(A_{i}^{3}-3A_{i}^{2}+3A_{i}-1\right)A_{i+1}$
$\displaystyle+\frac{1}{m}\left(A_{i}^{3}+3A_{i}^{2}+3A_{i}+1\right)\left(A_{i+1}-1\right)+\frac{1}{m}A_{i}^{3}\left(A_{i+1}+1\right).$

After multiplying out all polynomials, the right-hand side of the last
equation turns into the right-hand side of (45). It remains to prove (46).
Again, we will omit the argument $n$ and write $A_{i}$ and $A_{i+1}$ instead
of $A_{i}(n)$ and $A_{i+1}(n)$.

$\displaystyle\mathbb{E}\left[\left.A_{i}(n+1)A_{i+1}^{3}(n+1)\right|\mathcal{F}_{n}\right]$
$\displaystyle=$
$\displaystyle\frac{m-3}{m}A_{i}A_{i+1}^{3}+\frac{1}{m}\left(A_{i}-1\right)A_{i+1}^{3}$
$\displaystyle+\frac{1}{m}\left(A_{i}+1\right)\left(A_{i+1}^{3}-3A_{i+1}^{2}+3A_{i+1}-1\right)$
$\displaystyle+\frac{1}{m}A_{i}\left(A_{i+1}^{3}+3A_{i+1}^{2}+3A_{i+1}+1\right).$

From equations (44), (45), and (46) we obtain (43). $\Box$

######  Theorem 5.1.

Define the process $\left(M_{i,i+1}(n)\right)_{n=0}^{\infty}$ as

$\displaystyle M_{i,i+1}(n)$ $\displaystyle=$ $\displaystyle
H_{i,i+1}(n)-\frac{4n}{m}A_{i}(n)A_{i+1}(n)-\frac{2}{m^{2}}n^{2}+\left(\frac{1}{3m}-\frac{2}{m^{2}}\right)n.$
(48)

The process $\left(M_{i,i+1}(n)\right)_{n=0}^{\infty}$ is a martingale with
respect to $\left(\mathcal{F}_{n}\right)_{n=0}^{\infty}$.

Proof. Denote by $R(n)$ the random component on the right-hand side of (48).
More preciesely,

$\displaystyle R(n)=H_{i,i+1}(n)-\frac{4n}{m}A_{i}(n)A_{i+1}(n).$ (49)

The random variable $M_{i,i+1}(n)$ can be written in terms of $R(n)$ in the
following way

$\displaystyle
M_{i,i+1}(n)=R(n)-\frac{2}{m^{2}}n^{2}+\left(\frac{1}{3m}-\frac{2}{m^{2}}\right)n.$
(50)

We can use (19) and (43) to calculate the conditional expectation of $R(n)$
with respect to the sigma algebra $\mathcal{F}_{n}$. Using (49) we obtain

$\displaystyle\mathbb{E}\left[\left.R(n+1)\right|\mathcal{F}_{n}\right]$
$\displaystyle=$ $\displaystyle
H_{i,i+1}(n)+\frac{4}{m}A_{i}(n)A_{i+1}(n)-\frac{1}{3m}-\frac{4(n+1)}{m}\left(A_{i}(n)A_{i+1}(n)-\frac{1}{m}\right)$
(51) $\displaystyle=$ $\displaystyle
H_{i,i+1}(n)-\frac{4n}{m}A_{i}(n)A_{i+1}(n)+\frac{4(n+1)}{m^{2}}-\frac{1}{3m}$
$\displaystyle=$ $\displaystyle R(n)+\frac{4(n+1)}{m^{2}}-\frac{1}{3m}.$

From (50) and (51) we now obtain

$\displaystyle\mathbb{E}\left[\left.M_{i,i+1}(n+1)\right|\mathcal{F}_{n}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\left.R(n+1)\right|\mathcal{F}_{n}\right]-\frac{2}{m^{2}}(n+1)^{2}+\left(\frac{1}{3m}-\frac{2}{m^{2}}\right)(n+1)$
$\displaystyle=$ $\displaystyle
R(n)+\frac{4(n+1)}{m^{2}}-\frac{1}{3m}-\frac{2}{m^{2}}(n+1)^{2}+\frac{1}{3m}n-\frac{2}{m^{2}}n+\frac{1}{3m}-\frac{2}{m^{2}}$
$\displaystyle=$ $\displaystyle
R(n)-\frac{2}{m^{2}}n^{2}+\frac{1}{3m}n-\frac{2}{m^{2}}n.$

The right-hand side of the last equation is precisely $M_{i,i+1}(n)$. This
completes the proof that $\left(M_{i,i+1}(n)\right)_{n=0}^{\infty}$ is a
martingale with respect to $\left(\mathcal{F}_{n}\right)_{n=0}^{\infty}$.
$\Box$

Proof of Theorem 1.5. We will use the method of contradiction to prove that
$\mathbb{E}\left[T^{2}\right]=+\infty$. Assume the contrary, that
$\mathbb{E}\left[T^{2}\right]<+\infty$. Let $T_{n}=\min\\{T,n\\}$. Lebesgue
monotone convergence theorem implies that

$\lim_{n\to\infty}\mathbb{E}\left[T_{n}^{2}\right]=\mathbb{E}\left[T^{2}\right].$

We will write $A(n)$ and $B(n)$ instead of $A_{1}(n)$ and $A_{2}(n)$. We will
also use the notation $a=A(0)$ and $b=B(0)$. Let us define the random
variables $M_{1,2}(n)$ for $n\in\\{0,1,2\dots\\}$ in the following way

$\displaystyle M_{1,2}(n)$ $\displaystyle=$ $\displaystyle
A^{2}(n)B^{2}(n)+\frac{2}{3}A(n)B(n)\left(A^{2}(n)+B^{2}(n)\right)-\frac{4}{3}nA(n)B(n)-\frac{2n^{2}}{3}-\frac{1}{9}n.$

According to Theorem 5.1, the process $\left(M_{1,2}(n)\right)_{n=0}^{\infty}$
is a martingale with respect to $\left(\mathcal{F}_{n}\right)_{n=0}^{\infty}$.
The optional stopping theorem implies

$\displaystyle\mathbb{E}\left[A^{2}(T_{n})B^{2}(T_{n})+\frac{2}{3}A(T_{n})B(T_{n})\left(A^{2}(T_{n})+B^{2}(T_{n})\right)-\frac{4}{3}T_{n}A(T_{n})B(T_{n})\right]$
(52) $\displaystyle=$ $\displaystyle
a^{2}b^{2}+\frac{2}{3}ab\left(a^{2}+b^{2}\right)+\frac{2}{3}\mathbb{E}\left[T_{n}^{2}\right]+\frac{1}{9}\mathbb{E}\left[T_{n}\right].$

If we were able to justify passing to the limit as $n\to\infty$ in (52) we
would get an immediate contradiction. The left-hand side would be equal to $0$
and the right-hand side is obviously positive. However, it is not clear how to
justify the change of order of integral and limit. We will build an argument
that uses Cauchy-Schwarz inequality.

Let us denote by $L(n)$ and $R(n)$ the left-hand side and right-hand side of
(52). Formally,

$\displaystyle L(n)$ $\displaystyle=$
$\displaystyle\mathbb{E}\left[A^{2}(T_{n})B^{2}(T_{n})+\frac{2}{3}A(T_{n})B(T_{n})\left(A^{2}(T_{n})+B^{2}(T_{n})\right)-\frac{4}{3}T_{n}A(T_{n})B(T_{n})\right],$
$\displaystyle R(n)$ $\displaystyle=$ $\displaystyle
a^{2}b^{2}+\frac{2}{3}ab\left(a^{2}+b^{2}\right)+\frac{2}{3}\mathbb{E}\left[T_{n}^{2}\right]+\frac{1}{9}\mathbb{E}\left[T_{n}\right].$

Let us add $\frac{4}{9}\mathbb{E}\left[T_{n}^{2}\right]$ to both left and
right side of (52). We obtain the equation

$\displaystyle\hat{L}(n)$ $\displaystyle=$
$\displaystyle\hat{R}(n),\quad\mbox{where}$ (53) $\displaystyle\hat{L}(n)$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[A^{2}(T_{n})B^{2}(T_{n})-\frac{4}{3}T_{n}A(T_{n})B(T_{n})+\frac{4}{9}T_{n}^{2}\right]+\mathbb{E}\left[\frac{2}{3}A(T_{n})B(T_{n})\left(A^{2}(T_{n})+B^{2}(T_{n})\right)\right]$
$\displaystyle\hat{R}(n)$ $\displaystyle=$ $\displaystyle
a^{2}b^{2}+\frac{2}{3}ab\left(a^{2}+b^{2}\right)+\frac{10}{9}\mathbb{E}\left[T_{n}^{2}\right]+\frac{1}{9}\mathbb{E}\left[T_{n}\right].$

Consider the first expectation in the definition of $\hat{L}(n)$ and denote it
by $\lambda$, i.e.

$\lambda=\mathbb{E}\left[A^{2}(T_{n})B^{2}(T_{n})-\frac{4}{3}T_{n}A(T_{n})B(T_{n})+\frac{4}{9}T_{n}^{2}\right]=\mathbb{E}\left[\left(A(T_{n})B(T_{n})-\frac{2}{9}T_{n}\right)^{2}\right].$

Clearly $\lambda\geq 0$ and (53) implies

$\displaystyle
a^{2}b^{2}+\frac{2}{3}ab\left(a^{2}+b^{2}\right)+\frac{10}{9}\mathbb{E}\left[T_{n}^{2}\right]+\frac{1}{9}\mathbb{E}\left[T_{n}\right]$
$\displaystyle\geq$
$\displaystyle\mathbb{E}\left[\frac{2}{3}A(T_{n})B(T_{n})\left(A^{2}(T_{n})+B^{2}(T_{n})\right)\right].$
(54)

Let $g(n)$ be the function defined as

$\displaystyle g(n)$ $\displaystyle=$ $\displaystyle
A(T_{n})B(T_{n})\left(A^{2}(T_{n})+B^{2}(T_{n})\right).$ (55)

Due to our assumption that $\mathbb{E}\left[T_{n}^{2}\right]$ is finite, we
have that the left-hand side of (54) is convergent and, therefore, bounded.
Hence, there exist a positive real number $D$ such that the inequality

$\displaystyle D$ $\displaystyle\geq$
$\displaystyle\mathbb{E}\left[g(n)\right]$ (56)

holds for every $n\in\mathbb{N}$.

Using (11) and Cauchy-Schwarz inequality we obtain that the following
inequality also holds for every $n\in\mathbb{N}$.

$\displaystyle ab(a+b)$ $\displaystyle=$
$\displaystyle\mathbb{E}\left[\sqrt{A\left(T_{n}\right)B\left(T_{n}\right)}\cdot\sqrt{A\left(T_{n}\right)B\left(T_{n}\right)}\left(A\left(T_{n}\right)+B\left(T_{n}\right)\right)\right]$
(57) $\displaystyle\leq$
$\displaystyle\sqrt{\mathbb{E}\left[A\left(T_{n}\right)B\left(T_{n}\right)\right]}\cdot\sqrt{\mathbb{E}\left[g(n)\right]}.$

From (13), the first factor
$\sqrt{\mathbb{E}\left[A\left(T_{n}\right)B\left(T_{n}\right)\right]}$ on the
right-hand side of (57) converges to $0$ as $n\to\infty$. From (56) we have
that the factor $\sqrt{\mathbb{E}\left[g(n)\right]}$ is bounded by $\sqrt{D}$.
Therefore, as $n\to\infty$, the right-hand side of (57) converges to $0$. The
left-hand side of (57) is equal to $ab(a+b)$. This is a contradiction that
proves that $\mathbb{E}\left[T^{2}\right]=0$. $\Box$

##  6\. Further directions

The expected values of the stopping times $T$ are difficult to calculate when
$m\geq 4$ and we don’t yet have the exact formulas. We have seen that the
$L^{1}$ norms are finite. In order to use the optimal stopping theorem, we
need to first construct functions that generate convenient martingales. The
function $H:\mathbb{R}^{k}\to\mathbb{R}$ will be called perfect time
martingale generator if for some constant $\gamma\in\mathbb{R}$ it satisfies

$\displaystyle H\left(x_{1},\dots,x_{k}\right)-\gamma$ $\displaystyle=$
$\displaystyle\frac{1}{k+1}\left(H\left(x_{1}-1,\dots,x_{k}\right)\right.$
(58)
$\displaystyle+\sum_{i=1}^{k-1}H\left(x_{1},\dots,x_{i}+1,x_{i+1}-1,\dots,x_{k}\right)$
$\displaystyle\left.+H\left(x_{1},\dots,x_{k-1},x_{k}+1\right)\right),\quad\mbox{and}$
$\displaystyle H\left(x_{1},x_{2},\dots,x_{k}\right)$ $\displaystyle=$
$\displaystyle 0,\quad\mbox{if }\;x_{1}x_{2}\cdots x_{k}=0.$ (59)

If $H$ is a perfect time martingale generator, then
$H\left(\overrightarrow{A}(n)\right)+\gamma n$ is a martingale.

######  Problem 6.1.

Find functions $H$ that satisfy (58) and (59).

The process $H\left(\overrightarrow{A}(n)\right)+\gamma n$ is a martingale
even if just (58) holds. However, unless the condition (59) holds as well, the
martingale is not of a big use in calculating $\mathbb{E}[T]$. There are quite
a few functions that satisfy (58) but not (59). Examples are: $x_{i}^{2}$ and
$x_{i}x_{i+1}$. We used these functions to construct supermartingales.

It is clear that there are functions that satisfy (58) and (59) at least for
integers. We can simply define them as

$H\left(z_{1},z_{2},\dots,z_{k}\right)=\tau\left(z_{1},\dots,z_{k}\right).$

One would expect that they could be extended from $\mathbb{Z}^{k}$ to
$\mathbb{R}^{k}$. However, the search for functions that satisfy (58) and (59)
is not easy even numerically.

To guarantee that $H$ satisfies (58) and (59), we make a substitution

$\displaystyle H\left(x_{1},\dots,x_{k}\right)=x_{1}\cdots
x_{k}F\left(x_{1},\dots,x_{k}\right).$ (60)

If $H$ and $F$ satisfy the relation (60) then the equation (58) implies that
for positive real numbers $x_{1}$, $\dots$, $x_{k}$, the following equality
holds:

$\displaystyle F(x_{1},\dots,x_{k})-\frac{\gamma}{x_{1}\cdots x_{k}}$
$\displaystyle=$
$\displaystyle\frac{1}{k+1}\left(\frac{x_{1}-1}{x_{1}}F\left(x_{1}-1,\dots,x_{k}\right)\right.$
(61)
$\displaystyle+\sum_{i=1}^{k-1}\frac{1+x_{i}}{x_{i}}\cdot\frac{1-x_{i+1}}{x_{i+1}}F\left(x_{1},\dots,x_{i}+1,x_{i+1}-1,\dots,x_{k}\right)$
$\displaystyle\left.+\frac{1+x_{k}}{x_{k}}F\left(x_{1},\dots,x_{k-1},x_{k}+1\right)\right).$

Let us denote $u_{i}=\frac{1}{x_{i}}$ and

$f(u_{1},u_{2},\dots,u_{k})=F\left(\frac{1}{u_{1}},\dots,\frac{1}{u_{k}}\right).$

The equation (61) can be written in terms of variables $u_{1}$, $\dots$,
$u_{k}$ as

$\displaystyle f(u_{1},\dots,u_{k})-\gamma u_{1}\cdots u_{k}$ (62)
$\displaystyle=$
$\displaystyle\frac{1}{k+1}\left(\left(1-u_{1}\right)f\left(\frac{u_{1}}{1-u_{1}},\dots,u_{k}\right)\right.$
$\displaystyle+\sum_{i=1}^{k-1}\left(1+u_{i}\right)\left(1-u_{i+1}\right)f\left(u_{1},\dots,\frac{u_{i}}{1+u_{i}},\frac{u_{i+1}}{1-u_{i+1}},\dots,u_{k}\right)$
$\displaystyle\left.+\left(1+u_{k}\right)f\left(u_{1},\dots,u_{k-1},\frac{u_{k}}{1+u_{k}}\right)\right).$

We will rewrite the equation (62) using generalized convolution operators.

###  6.1. Generalized convolution

Let $I$ be a finite set. The set $I$ will be considered to be a set of
indices. A multidimensional sequence $\alpha$ is a function whose domain is
$\mathbb{N}^{I}$ and codomain $\mathbb{R}$. The elements of $\mathbb{N}^{I}$
are functions from $I$ to $\mathbb{N}$. There are two ways to characterize
$\alpha$ as a function. The first way is to write
$\alpha:\mathbb{N}^{I}\to\mathbb{R}$, and the second way is
$\alpha:\left(I\to\mathbb{N}\right)\to\mathbb{R}$.

For fixed $i\geq 0$, let us consider the functions
$\rho^{\pm}_{i}(x)=\frac{1}{(1\pm x)^{i}}$. Let us denote by
$\left(\varphi^{\pm}(i,k)\right)_{k=0}^{\infty}$ the sequence for which

$\displaystyle\rho^{\pm}_{i}(x)$ $\displaystyle=$
$\displaystyle\sum_{k=0}^{\infty}\varphi^{\pm}(i,k)x^{k}.$ (63)

Let $M=\\{1,2,\dots,m\\}$. Denote by $\mathcal{A}_{m}$ the set of functions
$f:\mathbb{R}^{m}\to\mathbb{R}$ that have power series representations of the
form

$f\left(x_{1},\dots,x_{m}\right)=\sum_{\theta\in\mathbb{N}^{M}}\alpha(\theta)x_{1}^{\theta(1)}x_{2}^{\theta(2)}\cdots
x_{m}^{\theta(m)},$

for some $|M|$-dimensional sequence $\alpha:\mathbb{N}^{M}\to\mathbb{R}$.

Let us define the operators $L_{k}^{\pm}:\mathcal{A}_{m}\to\mathcal{A}_{m}$ in
the following way. For given $f\in\mathcal{A}_{m}$ we define $L_{k}^{\pm}(f)$
to be the function that satisfies

$\displaystyle L_{k}^{\pm}(f)\left(x_{1},\dots,x_{m}\right)$ $\displaystyle=$
$\displaystyle f\left(x_{1},x_{2},\dots,x_{k-1},\frac{x_{k}}{1\pm
x_{k}},x_{k+1},\dots,x_{m}\right).$ (64)

Denote by $\alpha:\mathbb{N}^{M}\to\mathbb{R}$ the generating sequence of $f$.
Now we will determine the generating sequence of $L_{k}^{\pm}(f)$.

$\displaystyle L_{k}^{\pm}(f)\left(x_{1},\dots,x_{m}\right)$ $\displaystyle=$
$\displaystyle\sum_{\theta\in\mathbb{N}^{M}}\alpha(\theta)x_{1}^{\theta(1)}\cdots
x_{m}^{\theta(m)}\cdot\rho^{\pm}_{\theta(k)}(x_{k})$ $\displaystyle=$
$\displaystyle\sum_{\theta\in\mathbb{N}^{M}}\sum_{l}\alpha(\theta)x_{1}^{\theta(1)}\cdots
x_{m}^{\theta(m)}\varphi^{\pm}(\theta(k),l)x_{k}^{l}$ $\displaystyle=$
$\displaystyle\sum_{\theta\in\mathbb{N}^{M}}\sum_{l}\alpha(\theta)\varphi^{\pm}(\theta(k),l)x_{1}^{\theta(1)}\cdots
x_{k}^{\theta(k)+l}\cdots x_{m}^{\theta(m)}.$

The generating sequence $\beta:\mathbb{N}^{M}\to\mathbb{R}$ for
$L_{k}^{\pm}(f)$ satisfies

$\displaystyle\beta(\theta)$ $\displaystyle=$
$\displaystyle\sum\Big{\\{}\alpha(\mu)\varphi^{\pm}(\nu):\mu\in\mathbb{N}^{M},\nu\in\mathbb{N}^{2},P_{\\{k\\}^{C}}\left(\mu\right)=P_{\\{k\\}^{C}}\left(\theta\right),$
$\displaystyle
P_{\\{k\\}}(\mu)=P_{\\{1\\}}(\nu),P_{\\{k\\}}(\mu)+P_{\\{2\\}}(\nu)=P_{\\{k\\}}(\theta)\Big{\\}},$

where for $\eta\in\mathbb{N}^{Q}$ and $R\subseteq Q$, the projection
$P_{R}(\eta)$ of $\eta$ to $R$ defined as $P_{R}(\eta)(r)=\eta(r)$ for all
$r\in R$.

The operators $L_{k}^{\pm}$ on the set $\mathcal{A}_{m}$ naturally generate
the operators $S_{k}^{\pm}$ on the set of sequences
$\mathbb{N}^{M}\to\mathbb{R}$. If for $\alpha:\mathbb{N}^{M}\to\mathbb{R}$
there is a generating function $f\in A_{m}$, then we define
$S_{k}^{\pm}(\alpha)$ to be the generating sequence for the function
$L_{k}^{\pm}(f)$.

We will now prove that for $k_{1}\neq k_{2}$, the following equalities hold:

$S_{k_{1}}^{\pm}\circ S_{k_{2}}^{\pm}=S_{k_{2}}^{\pm}\circ S_{k_{1}}^{\pm}.$

Let $\alpha\in\mathbb{N}^{M}\to\mathbb{R}$. Then $S_{k_{1}}^{\pm}(\alpha)$
satisfies

$\displaystyle
S_{k_{1}}^{\pm}(\alpha)(\theta)=\sum_{i=0}^{\theta(k_{1})}\alpha\left(\theta(1),\dots,\theta({k_{1}}-1),i,\theta({k_{1}}+1),\dots,m\right)\varphi^{\pm}(i,\theta(k_{1})-i).$

From here we obtain that
$S_{k_{2}}^{\pm}\left(S_{k_{1}}^{\pm}(\alpha)\right)(\theta)$ satisfies

$\displaystyle S_{k_{2}}^{\pm}\left(S_{k_{1}}^{\pm}(\alpha)\right)(\theta)$
(65) $\displaystyle=$
$\displaystyle\sum_{j=0}^{\theta(k_{2})}S_{k_{1}}^{\pm}(\alpha)\left(\theta(1),\dots,\theta({k_{2}}-1),j,\theta({k_{2}}+1),\dots,m\right)\varphi^{\pm}(j,\theta(k_{2})-j)$
$\displaystyle=$
$\displaystyle\sum_{j=0}^{\theta(k_{2})}\varphi^{\pm}(j,\theta(k_{2})-j)\Big{(}\sum_{i=0}^{\theta(k_{1})}\alpha\Big{(}\theta(1),\dots,\theta({k_{1}}-1),i,\theta(k_{1}+1),$
$\displaystyle\quad\quad\dots,\theta({k_{2}}-1),j,\theta({k_{2}}+1),\dots,m\Big{)}\varphi^{\pm}(i,\theta(k_{1})-i)\Big{)}$
$\displaystyle=$
$\displaystyle\sum_{i=0}^{\theta(k_{1})}\sum_{j=0}^{\theta(k_{2})}\alpha\Big{(}\theta(1),\dots,\theta({k_{1}}-1),i,\theta(k_{1}+1),$
$\displaystyle\quad\quad\dots,\theta({k_{2}}-1),j,\theta({k_{2}}+1),\dots,m\Big{)}\times$
$\displaystyle\quad\quad\quad\quad\quad\times\varphi^{\pm}(i,\theta(k_{1})-i)\varphi^{\pm}(j,\theta(k_{2})-j).$

In a similar way we prove that
$S_{k_{2}}^{\pm}\left(S_{k_{1}}^{\pm}(\alpha)\right)(\theta)$ is equal to the
double summation on the right-hand side of equation (65).

###  6.2. Searching for solutions

The definition of sequences
$\varphi^{\pm}:\mathbb{N}^{\\{1,2\\}}\to\mathbb{R}$ from (63) and the
definition of the operators $L_{k}^{\pm}$ from (64) can be now used to re-
write the equation (62) as

$\displaystyle f\left(u_{1},\dots,u_{k}\right)-\gamma u_{1}\cdots u_{k}$
$\displaystyle=$
$\displaystyle\frac{1}{k+1}\left(\left(1-u_{1}\right)L_{1}^{-}f\left(u_{1},\dots,u_{k}\right)\right.$
(66)
$\displaystyle+\sum_{i=1}^{k-1}\left(1+u_{i}\right)\left(1-u_{i+1}\right)L_{i}^{+}\circ
L_{i+1}^{-}f\left(u_{1},\dots,u_{k}\right)$
$\displaystyle\left.+\left(1+u_{k}\right)L_{k}^{+}f\left(u_{1},\dots,u_{k}\right)\right).$

For $k=2$, one solution that works is $f(u_{1},u_{2})=1$. For $k\geq 2$, the
above equation has undesireable solutions. For example, for $k=3$, the
functions $f_{1}(u_{1},u_{2},u_{3})=u_{1}$ and
$f_{3}(u_{1},u_{2},u_{3})=u_{3}$ are the solutions. However, since the
variables $u_{i}$ are reciprocals of $x_{i}$, the corresponding functions $H$
would not satisfy (59). If we put the additional requirement that $f(0,0)\neq
0$, then (66) gives us unsolvable system of equations for the coefficients of
generating sequence for $f$.

Another approach in the case $k=3$ is to consider the function $F$ of the form

$\displaystyle F(x,y,z)=\frac{G(x,y,z)}{x+z},$ (67)

where $G$ is a bounded function. Here is the intuition behind the idea to
search for functions $F$ of the above form. As $x\to\infty$ the function
$H(x,y,z)$ converges to $3yz$. Similarly, as $z\to\infty$, the function
$H(x,y,z)$ converges to $3xy$.

We can re-write the equation (61) as

$\displaystyle\frac{G(x,y,z)}{x+z}-\frac{\gamma}{xyz}$ (68) $\displaystyle=$
$\displaystyle\frac{1}{4}\cdot\frac{x-1}{x}\cdot\frac{G(x-1,y,z)}{x+z-1}+\frac{1}{4}\cdot\frac{x+1}{x}\cdot\frac{y-1}{y}\cdot\frac{G(x+1,y-1,z)}{x+z+1}$
$\displaystyle+\frac{1}{4}\cdot\frac{y+1}{y}\cdot\frac{z-1}{z}\cdot\frac{G(x,y+1,z-1)}{x+z-1}+\frac{1}{4}\cdot\frac{z+1}{z}\cdot\frac{G(x,y,z+1)}{x+z+1}.\quad\quad$

Let us introduce the substitutions $u=\frac{1}{x}$, $v=\frac{1}{y}$,
$z=\frac{1}{w}$, and

$g(u,v,w)=G\left(\frac{1}{u},\frac{1}{v},\frac{1}{w}\right)=G\left(x,y,z\right).$

The equation (68) becomes

$\displaystyle\frac{g(u,v,w)}{u+w}-\gamma v$ (69) $\displaystyle=$
$\displaystyle\frac{1}{4}\cdot(1-u)\cdot\frac{g\left(\frac{u}{1-u},v,w\right)}{u+w-uw}+\frac{1}{4}\cdot(1+u)\cdot(1-v)\cdot\frac{g\left(\frac{u}{1+u},\frac{v}{1-v},w\right)}{u+w+uw}$
$\displaystyle+\frac{1}{4}\cdot(1+v)\cdot(1-w)\cdot\frac{g\left(u,\frac{v}{1+v},\frac{w}{1-w}\right)}{u+w-uw}+\frac{1}{4}\cdot(1+w)\cdot\frac{g\left(u,v,\frac{w}{1+w}\right)}{u+w+uw}.\quad\quad$

Let us multiply both sides by $4(u+w)(u+w+uw)(u+w-uw)$ and introduce the
functions $\Gamma$, $\Gamma_{0}$, $\Gamma_{1}$, $\Gamma_{2}$, and $\Gamma_{3}$
with the equation

$\displaystyle\Gamma(u,v,w)$ $\displaystyle=$
$\displaystyle-4(u+w+uw)(u+w-uw)\cdot g(u,v,w),$ (70)
$\displaystyle\Gamma_{0}(u,v,w)$ $\displaystyle=$
$\displaystyle(u+w)(u+w+uw)(1-u)g\left(\frac{u}{1-u},v,w\right),$ (71)
$\displaystyle\Gamma_{1}(u,v,w)$ $\displaystyle=$
$\displaystyle(u+w)(u+w-uw)(1+u)(1-v)g\left(\frac{u}{1+u},\frac{v}{1-v},w\right),$
(72) $\displaystyle\Gamma_{2}(u,v,w)$ $\displaystyle=$
$\displaystyle(u+w)(u+w+uw)(1+v)(1-w)g\left(u,\frac{v}{1+v},\frac{w}{1-w}\right),$
(73) $\displaystyle\Gamma_{3}(u,v,w)$ $\displaystyle=$
$\displaystyle(u+w)(u+w-uw)(1+w)g\left(u,v,\frac{w}{1+w}\right).$ (74)

The equation (69) is equivalent to

$\displaystyle\Gamma_{0}+\Gamma_{1}+\Gamma_{2}+\Gamma_{3}+\Gamma+4\gamma
v(u+w)(u+w+uw)(u+w-uw)$ $\displaystyle=$ $\displaystyle 0.$ (75)

Again, it turns out that the system of equations implied by (75) does not have
a solution.

Polynomial functions $F$ and functions that are reciprocals of polynomials
result in unsolvable systems. There is a hope that rational functions could
lead to better approximations for $H$. However, the search for rational
functions requires the development of more advanced software for symbolic
computation of generalized convolutions.

## References

  * [1] Josh Abramson, Jim Pitman, Nathan Ross, and Gerónimo Uribe Bravo.  Convex minorants of random walks and Levy processes.  Elect. Comm. in Probab., 16 (2011), 423–434.
  * [2] Georgy Adelson-Velsky and Evgenii Landis.  An algorithm for the organization of information.  Soviet Math. Dokl., 3 (1962), 1259–1262.
  * [3] Noga Alon, Ori Gurel-Gurevich, and Eyal Lubetzky.  Choice-memory tradeoff in allocations.  Ann. Appl. Probab., 20 (4), 1470–1511, 2010.
  * [4] Rudolf Bayer.  Symmetric binary B-Trees: Data structure and maintenance algorithms.  Acta Informatica, 1 (1972), 290–306.
  * [5] E. Crane, N. Georgiou, S. Volkov, A.R. Wade, and R.J. Waters.  The simple harmonic urn.  The Annals of Probability, 39(6): 2119-2177, 2011.
  * [6] Nathanael Berestycki and Rick Durrett.  Limiting behavior for the distance of a random walk.  Electron. J. Probab., 13 374–395, 2008.
  * [7] Olivier Bernardi, Mireille Bousquet-Melou, and Kilian Raschel.  Counting quadrant walks via Tutte’s invariant method.  Combinatorial Theory, to appear, 2021.
  * [8] Amir Dembo, Yuval Peres, Jay Rosen, and Ofer Zeitouni.  Late points for random walks in two dimensions.  The Annals of Probability, 34 (1), 2006, 213–263.
  * [9] Persi Diaconis, R.L. Graham, and J.A. Morrison.  Asymptotic analysis of a random walk on a hypercube with many dimensions.  Random Struct. Algorithms, 1 (1990), 51–72.
  * [10] Jetlir Duraj.  On harmonic functions of killed random walks in convex cones.  Electron. Commun. Probab., 19 (2014), 1–10.
  * [11] Rick Durrett.  Probability: Theory and Examples.  Cambridge University Press; 5 edition, 2019.
  * [12] Denis Denisov and Vitali Wachtel.  Random Walks in Cones.  The Annals of Probability, 2015, 43 (3), pp. 992–1044.
  * [13] Denis Denisov and Vitali Wachtel.  Alternative constructions of a harmonic function for a random walk in a cone.  Electron. J. Probab., 2019, 24(none), 1–26
  * [14] Rodolphe Garbit and Kilian Raschel.  On the exit time from a cone for random walks with drift.  Revista Matemática Iberoamericana, European Mathematical Society, 2016, 32 (2), pp. 511–532.
  * [15] Irina Ignatiouk-Robert and Christophe Loree.  Martin boundary of a killed random walk on a quadrant.  The Annals of Probability, 2010, 38 (3), pp. 1106–1142.
  * [16] Elena Kosygina, Thomas Mountford, Jonathon Peterson.  Convergence of random walks with Markovian cookie stacks to Brownian motion perturbed at extrema.  arXiv:2008.06766v1, 2020.
  * [17] Markus Kuba and Henning Sulzbach.  On martingale tail sums in affine two-color urn models with multiple drawings.  On martingale tail sums in affine two-color urn models with multiple drawings. Journal of Applied Probability, 54, 1-21, 2017.
  * [18] N. Lasmar, C. Mailler, and O. Selmi.  Multiple drawing multi-colour urns by stochastic approximation.  Journal of Applied Probability, 55 (1): 254-281 (2018).
  * [19] Sean Ledger, Bálint Tóth, and Benedek Valkó.  Random walk on the randomly-oriented Manhattan lattice.  Electron. Commun. Probab., 23 (none): 1-11 (2018).
  * [20] Konstantin Matetski, Jeremy Quastel, and Daniel Remenik.  The KPZ fixed point.  arXiv:1701.00018, 2016.
  * [21] Joseph Najnudel and Ashkan Nikeghbali.  On some universal sigma-finite measures and some extensions of Doob’s optional stopping theorem.  Stoch. Process. Appl., 2012, 122, pp. 1582–1600
  * [22] Chanwoo Oh and Fraydoun Rezakhanlou.  Metastability of zero range processes via Poisson equations.  Preprint, 2019.
  * [23] Erol Peköz, Adrian Röllin, and Nathan Ross.  Pólya urns with immigration at random times.  Bernoulli, 2019, 25 (1), pp. 189–220
  * [24] Raimund Seidel and Cecilia Aragon.  Randomized Search Trees.  Algorithmica, 16, 1996, 464–497.
  * [25] S.R.Srinivasa Varadhan.  Stochastic Processes.  American Mathematical Soc., 2007.