$\mathcal{C^{-}}(n,k,\bar{k})$, so let $C(n,k,\bar{k})$ denote their common
size. Observe $C(n,k,\bar{k})=C(n,\bar{k},k)$, by changing the sign of the
first letter in each factor.

######  Lemma 5.12.

The hyperoctahedral Stirling numbers are related to the type A Stirling
numbers by

$C(n,k,\bar{k})=2^{n-k-\bar{k}}c(n,k+\bar{k})\binom{k+\bar{k}}{k}.$

###### Proof.

Given $k$ and $\bar{k}$, fix any sequence of $k$ positive signs and $\bar{k}$
negative signs. There are $\binom{k+\bar{k}}{k}$ such sequences. We show below
that, for any such sequence, there are $2^{n-k-\bar{k}}c(n,k+\bar{k})$ signed
permutations whose Lyndon factors $u_{i}$ have an odd number (resp. even
number) of positive letters if the $i$th term of the sequence is positive
(resp. negative).

First, there are $c(n,k+\bar{k})$ permutations with $k+\bar{k}$ Lyndon factors
in total. The factor of $2^{n-k-\bar{k}}$ then enumerates the signs that can
be assigned: within each Lyndon factor, all but the last letter can have
arbitrary sign; the sign of the last letter is then determined by the
requirement that this factor have an odd (or even) number of positive letters.
∎

######  Lemma 5.13.

The hyperoctahedral Stirling numbers satisfy the recursion

(5.14)
$C(n,k,\bar{k})=C(n-1,k-1,\bar{k})+C(n-1,\bar{k}-1)+2(n-1)C(n-1,k,\bar{k}).$

###### Proof.

We construct a bijection between the relevant sets. Each element of
$\mathcal{C}^{+}(n,k,\bar{k})$ is obtained in precisely one of the following
manners:

  * •

Adding $n$ to the start of an element of
$\mathcal{\mathcal{C}^{+}}(n-1,k-1,\bar{k})$ \- $n$ then becomes a new left-
to-right minima, i.e. a new Lyndon factor with one positive letter.

  * •

Adding $\bar{n}$ to the start of an element of
$\mathcal{\mathcal{C}^{+}}(n-1,k,\bar{k}-1)$ \- $\bar{n}$ is then a new Lyndon
factor with one negative and no positive letters.

  * •

To an element of $\mathcal{\mathcal{C}^{+}}(n-1,k,\bar{k})$, add $\bar{n}$
between any two letters, or at the end. This does not produce any new left-to-
right minima, so $\bar{n}$ is inserted into one of the existing Lyndon
factors, and does not change its parity of its positive letters.

  * •

To an element of $\mathcal{\mathcal{C}^{+}}(n-1,k,\bar{k})$, add $n$ between
any two letters, or at the end, and also change the sign of the preceding
letter, which is necessarily within the same Lyndon factor. This sign change
ensures that the parity of positive letters remains unchanged in this factor.

∎

###### Proof of Theorem 5.10.

Fix $a$ even. From Theorems 3.8 and 3.4, and Corollary 5.6, the multiplicity
of the eigenvalue $a^{k-n}$ is $|\mathcal{C}^{-}(n,0,k)|$ for
$\frac{1}{a^{n}}\operatorname{BRiffle}\tau_{a}^{+}$ and
$\frac{1}{a^{n}}\operatorname{BRiffle}\tau_{a}^{-}$, and
$|\mathcal{C}^{+}(n,k,0)|$ for
$\frac{1}{a^{n}}\operatorname{BRiffle}\tilde{\tau}_{a}^{+}$ and
$\frac{1}{a^{n}}\operatorname{BRiffle}\tilde{\tau}_{a}^{-}$. By the symmetry
remarks before Lemma 5.12, their common generating function is

$\displaystyle\sum_{k}C(n,k,0)x^{k}$
$\displaystyle=\sum_{k}2^{n-k}c(n,k)x^{k}$
$\displaystyle=2^{n}\sum_{k}c(n,k)\left(\frac{x}{2}\right)^{k}$
$\displaystyle=2^{n}\frac{x}{2}\left(\frac{x}{2}+1\right)\dots\left(\frac{x}{2}+n-1\right)$
$\displaystyle=x(x+2)(x+4)\dots(x+2n-2).$

0 is the only other eigenvalue. So that the multiplicities of all eigenvalues
sum to $2^{n}n!$, the multiplicity of 0 must be $2^{n}n!-1\cdot
3\cdot\dots\cdot(2n-1)$.

Now consider $\frac{1}{a^{n}}\operatorname{BRiffle}\tilde{\tau}_{a}^{-}$ for
$a$ odd. From Theorems 3.5 and Corollary 5.6, the multiplicity of the
eigenvalue $a^{k-n}$ (resp. $-a^{k-n}$) is $\sum_{\bar{k}\text{
even}}|\mathcal{C}^{+}(n,k,\bar{k})|$ (resp. $\sum_{\bar{k}\text{
odd}}|\mathcal{C}^{+}(n,k,\bar{k})|$). It can be proved by induction on $n$
that

$\displaystyle\sum_{\bar{k}\text{ odd}}C(n,k,\bar{k})$
$\displaystyle=n\sum_{\bar{k}}C(n-1,k,\bar{k}),$
$\displaystyle\sum_{\bar{k}\text{ even}}C(n,k,\bar{k})$
$\displaystyle=(n-1)\sum_{\bar{k}}C(n-1,k,\bar{k})+\sum_{\bar{k}}C(n-1,k-1,\bar{k});$

briefly, use (5.14) to rewrite the left hand side in terms of $C(n-1,-,-)$,
apply the inductive hypothesis to obtain sums of $C(n-2,-,-)$, over all values
of $\bar{k}$, then collect terms using (5.14) to obtain terms of the form
$C(n-1,-,-$). Then the claimed generating functions come from observing that

$\displaystyle\sum_{k,\bar{k}}C(n-1,k,\bar{k})x^{k}$
$\displaystyle=\sum_{k,\bar{k}}2^{n-1-k-\bar{k}}c(n-1,k+\bar{k})\binom{k+\bar{k}}{k}x^{k}$
$\displaystyle=\sum_{j}2^{n-1-j}c(n-1,j)(x+1)^{j}$
$\displaystyle=2^{n-1}\sum_{k}c(n-1,j)\left(\frac{x+1}{2}\right)^{j}$
$\displaystyle=2^{n-1}\frac{x+1}{2}\left(\frac{x+1}{2}+1\right)\dots\left(\frac{x+1}{2}+n-2\right)$
$\displaystyle=(x+1)(x+3)\dots(x+2n-3).$

The multiplicity of $a^{k-n}$ for
$\frac{1}{a^{n}}\operatorname{BRiffle}\tilde{\tau}_{a}^{+}$ is the sum of the
multiplicities of $a^{k-n}$ and $-a^{k-n}$ for
$\frac{1}{a^{n}}\operatorname{BRiffle}\tilde{\tau}_{a}^{-}$. The cases of
$\frac{1}{a^{n}}\operatorname{BRiffle}\tau_{a}^{-}$ and
$\frac{1}{a^{n}}\operatorname{BRiffle}\tau_{a}^{+}$ follow from the symmetry
remarks before Lemma 5.12. ∎

###  5.5 Subdominant Eigenvectors and Expectations of Descents

The paper [DPR14, Exs. 5.8-5.9, Prop. 5.10] identified the eigenvectors of
type A riffle-shuffles with large eigenvalues, and expressed some of them in
terms of two classical permutation statistics, namely descents and peaks. This
section dervies one hyperoctahedral analogue.

First, to clarify what is meant by “large” eigenvalue:

######  Definition 5.15.

An eigenvalue $\lambda$ of a Markov chain is _subdominant_ if $|\lambda|<1$
and $|\lambda|>|\lambda^{\prime}|$ for all other eigenvalues
$\lambda^{\prime}\neq 1,-1$.

Informally, subdominant eigenvalues have maximal absolute value after 1\.
Their values and corresponding eigenspaces have the largest influence on the
convergence rate.

The corresponding eigenvectors are expressed in terms of the following
terminology:

######  Definition 5.16.

If $w=w_{1}\dots w_{n}$ where $w_{i}$ denotes the $i$th letter of $w$, then a
_consecutive subword_ of $w$ is a word of the form $w_{i}w_{i+1}\dots w_{j}$
for some $i<j$.

For example, if $w=435\bar{1}6\bar{7}\bar{2}$, then $35\bar{1}$ and
$6\bar{7}\bar{2}$ are consecutive subwords of $w$, but $36\mbox{$\bar{7}$}$ is
not.

######  Definition 5.17.

Given a word $w$, its consecutive subword $ij$ is a _descent_ if $i>j$. This
applies whether $i$ and $j$ are positive and negative letters. Let
$\operatorname{des}(w)$ denote the number of descents in $w$.

For example, the descents of $435\bar{1}6\bar{7}\bar{2}$ are $43$, $5\bar{1}$,
and $6\bar{7}$, so $\operatorname{des}(w)=3$. Notice that this differs from
the definition of descent in Coxeter type B, where additionally the first
letter is a descent if it is negative.

######  Notation 5.18.

For $i<j$, define

(5.19) $\mathbf{f}_{ij}^{+}(w):=\begin{cases}1&\mbox{ if any of }ij,\
\bar{i}\bar{j}\mbox{ is a consecutive subword in }w;\\\ -1&\mbox{ if any of
}ji,\ \bar{j}\bar{i}\mbox{ is a consecutive subword in }w;\\\ 0&\mbox{
otherwise},\end{cases}$

and

(5.20) $\mathbf{f}_{ij}^{-}(w):=\begin{cases}1&\mbox{ if any of }\bar{i}j,\
i\bar{j}\mbox{ is a consecutive subword in }w;\\\ -1&\mbox{ if any of
}j\bar{i},\ \bar{j}i\mbox{ is a consecutive subword in }w;\\\ 0&\mbox{
otherwise},\end{cases}$

And for $i\neq j$, define

(5.21) $\tilde{\mathbf{f}}_{ij}(w):=\begin{cases}1&\mbox{ if any of }ij,\
\bar{i}j,\ \bar{j}i,\ \bar{j}\bar{i}\mbox{ is a consecutive subword in }w;\\\
-1&\mbox{ if any of }ji,\ j\bar{i},\ i\bar{j},\ \bar{i}\bar{j}\mbox{ is a
consecutive subword in }w;\\\ 0&\mbox{ otherwise}.\end{cases}$

And for all $i$, define

(5.22) $\mathbf{g}_{i}(w):=\begin{cases}1&\mbox{ if }i\mbox{ is the first or
last letter of }w;\\\ -1&\mbox{ if }\bar{i}\mbox{ is the first or last letter
of }w;\\\ 0&\mbox{ otherwise}.\end{cases}$

######  Proposition 5.23.

The subdominant eigenvalues of the hyperoctahedral riffle-shuffles, and a
basis of associated eigenfunctions, are as given in Table 2.

parity of $a$ | shuffle | subdominant eigenvalues | basis of eigenfunctions
---|---|---|---
even |  $\frac{1}{a^{n}}\operatorname{BRiffle}\tau_{a}^{+}$ or $\frac{1}{a^{n}}\operatorname{BRiffle}\tau_{a}^{-}$ | $1/a$ | $\\{\mathbf{f}_{ij}^{+}\\}\cup\\{\mathbf{f}_{ij}^{-}\\}$
odd | $\frac{1}{a^{n}}\operatorname{BRiffle}\tau_{a}^{+}$ | $1/a$ | $\\{\mathbf{f}_{ij}^{+}\\}\cup\\{\mathbf{f}_{ij}^{-}\\}\cup\\{\mathbf{g}_{i}\\}$
$\frac{1}{a^{n}}\operatorname{BRiffle}\tau_{a}^{-}$ | $1/a$ | $\\{\mathbf{f}_{ij}^{+}\\}\cup\\{\mathbf{f}_{ij}^{-}\\}$
$-1/a$ | $\\{\mathbf{g}_{i}\\}$
even |  $\frac{1}{a^{n}}\operatorname{BRiffle}\tilde{\tau}_{a}^{+}$ or $\frac{1}{a^{n}}\operatorname{BRiffle}\tilde{\tau}_{a}^{-}$ | $1/a$ | $\\{\tilde{\mathbf{f}}_{ij}\\}$
odd | $\frac{1}{a^{n}}\operatorname{BRiffle}\tilde{\tau}_{a}^{+}$ | $1/a$ | $\\{\tilde{\mathbf{f}}_{ij}\\}\cup\\{\mathbf{g}_{i}\\}$
$\frac{1}{a^{n}}\operatorname{BRiffle}\tilde{\tau}_{a}^{-}$ | $1/a$ | $\\{\tilde{\mathbf{f}}_{ij}\\}$
$-1/a$ | $\\{\mathbf{g}_{i}\\}$
Table 2: Subdominant eigenvalues for hyperoctahedral riffle-shuffles, and
bases for their eigenfunctions

######  Proposition 5.24.

Fix a positive integer $a$, and let $\\{X_{t}\\}$ denote $a$-handed riffle-
shuffle with flip, i.e. the Markov chain associated to
$\frac{1}{a^{n}}\operatorname{BRiffle}\tilde{\tau}_{a}^{+}$ or
$\frac{1}{a^{n}}\operatorname{BRiffle}\tilde{\tau}_{a}^{-}$ on
$\mathcal{B}_{n}$ according to Section 5.1. Then the “normalised number of
descents” functions $w\mapsto\operatorname{des}(w)-\frac{n-1}{2}$ is an
eigenfunction of $\\{X_{t}\\}$ of eigenvalue $1/a$. Hence

$\operatorname{Expect}(\operatorname{des}X_{t}|X_{0}=w_{0})=(1-a^{-t})\frac{n-1}{2}+a^{-t}\operatorname{des}(w_{0}).$

###### Proof.

We show that

$\operatorname{des}(w)-\frac{n-1}{2}=\sum_{i<j}\tilde{\mathbf{f}}_{ij}(w)$

for all $w\in\mathcal{B}_{n}$. Note that the subwords which cause
$\tilde{\mathbf{f}}_{ij}(w)=-1$, namely $ji$, $j\bar{i}$, $i\bar{j}$ and
$\bar{i}\bar{j}$, are all descents if $i<j$. And every descent of $w$ is of
one of these 4 types, for some $i<j$. Opposingly, all consecutive subwords of
two letters that are not descents (i.e. “ascents”) contribute 1 to
$\tilde{\mathbf{f}}_{ij}(w)$ for some $i<j$. Hence
$\sum_{i<j}\tilde{\mathbf{f}}_{ij}(w)$ is the difference between the number of
ascents and the number of descents in $w$. Since each pair of consecutive
letters in $w$ is either an ascent or a descent, the number of ascents and
descents together total $n-1$. Hence this difference is
$(n-1-\operatorname{des}(w))-\operatorname{des}(w)$.

As for the expectation assertion: by the linearity of expectations, then by
Proposition 5.2,

$\displaystyle\operatorname{Expect}(\operatorname{des}X_{t}|X_{0}=w_{0})$
$\displaystyle=\operatorname{Expect}(\sum_{i<j}\tilde{\mathbf{f}}_{ij}(X_{t})|X_{0}=w)+\operatorname{Expect}\left(\frac{n-1}{2}\middle|X_{0}=w\right)$
$\displaystyle=a^{-t}\sum_{i<j}\tilde{\mathbf{f}}_{ij}(w_{0})+\frac{n-1}{2}.$

∎

###### Proof of Proposition 5.23.

According to Theorems 3.4, 3.5 and 3.8, for
$\frac{1}{a^{n}}\operatorname{BRiffle}\tau_{a}^{+}$,
$\frac{1}{a^{n}}\operatorname{BRiffle}\tau_{a}^{-}$,
$\frac{1}{a^{n}}\operatorname{BRiffle}\tilde{\tau}_{a}^{+}$ and
$\frac{1}{a^{n}}\operatorname{BRiffle}\tilde{\tau}_{a}^{-}$:

  * •

When $a$ is even, the only subdominant eigenvalue is $1/a$, and it corresponds
to $k=n-1$ and $\bar{k}=0$, i.e. the corresponding eigenvectors are formed
from $n-1$ $\tau$-invariant (or $\tilde{\tau}$-invariant) primitives, and no
$\tau$-negating (or $\tilde{\tau}$-negating) primitives.

  * •

When $a$ is odd, the subdominant eigenvalues all correspond to $k=n-1$ and
$\bar{k}$ can take any value, i.e. the corresponding eigenvectors are formed
from $n-1$ $\tau$-invariant (or $\tilde{\tau}$-invariant) primitives, and any
number of $\tau$-negating (or $\tilde{\tau}$-negating) primitives. However,
since $k+\bar{k}\leq n$ (as each primitive has degree at least one, and the
degree of their product is $n$), the only possible values of $\bar{k}$ are 0
and 1. When $\bar{k}=0$, the eigenvalue is $1/a$ for all four operator
families. When $\bar{k}=1$, the eigenvalue is $1/a$ for
$\frac{1}{a^{n}}\operatorname{BRiffle}\tau_{a}^{+}$ and
$\frac{1}{a^{n}}\operatorname{BRiffle}\tilde{\tau}_{a}^{+}$, and is $-1/a$ for
$\frac{1}{a^{n}}\operatorname{BRiffle}\tau_{a}^{-}$, and
$\frac{1}{a^{n}}\operatorname{BRiffle}\tilde{\tau}_{a}^{-}$.

The proof will be completed by showing the following:

  1. i)

$\\{\tilde{\mathbf{f}}_{ij}\ |\>i<j\\}\cup\\{-\tilde{\mathbf{f}}_{ij}\
|\>j<i\\}$ are precisely all the eigenvectors, for
$\operatorname{BRiffle}\tilde{\tau}_{a}^{+}$ and
$\operatorname{BRiffle}\tilde{\tau}_{a}^{-}$, given by Algorithm 5.7 when
$k=n-1$ and $\bar{k}=0$.

  2. ii)

$\\{\mathbf{f}_{ij}^{+}\ |\>i<j\\}$ (resp. $\\{\mathbf{f}_{ij}^{-}\
|\>i<j\\}$) are, up to scaling, the sums (resp. differences) of pairs of
eigenvectors, for $\operatorname{BRiffle}\tau_{a}^{+}$ and
$\operatorname{BRiffle}\tau_{a}^{-}$, given by Algorithm 5.7 when $k=n-1$ and
$\bar{k}=0$.

  3. iii)

$\\{\mathbf{g}_{i}\\}$ are precisely all the eigenvectors, for
$\operatorname{BRiffle}\tilde{\tau}_{a}^{+}$,
$\operatorname{BRiffle}\tilde{\tau}_{a}^{-}$,
$\operatorname{BRiffle}\tau_{a}^{+}$ and $\operatorname{BRiffle}\tau_{a}^{-}$
when $a$ is odd, given by Algorithm 5.7 when $k=n-1$ and $\bar{k}=1$.

And here are the proofs of these three assertions.

  1. i)

$k=n-1$ and $\bar{k}=0$ means that the indexing word has $n-1$ Lyndon factors,
whose standard-bracketings are all $\tilde{\tau}$-invariant. So, by the third
line of Corollary 5.6, each Lyndon factor consists of an odd number of
positive letters. Necessarily, $n-2$ of these factors must be single positive
letters, and the remaining factor consists of one positive and one negative
letter - i.e. it is $i\bar{j}$ or $\bar{i}j$, where $i<j$. Take the first
case; the standard-bracketing of $i\bar{j}$ is

(5.25)
$[i+\bar{i},j-\bar{j}]=ij-i\bar{j}+\bar{i}j-\bar{i}\bar{j}-ji-j\bar{i}+\bar{j}i+\bar{j}i.$

Observe that, if $w$ consists precisely of $i$ or $\bar{i}$ once and $j$ or
$\bar{j}$ once, then $\tilde{\mathbf{f}}_{ij}(w)$ is precisely the coefficient
of $w$ in (5.25).

Since all primitives involved are $\tilde{\tau}$-invariant, the formulas in
parts a, b, c of Theorem 3.4 all agree: the common eigenvector for
$\operatorname{BRiffle}\tilde{\tau}_{a}^{+}$ and
$\operatorname{BRiffle}\tilde{\tau}_{a}^{-}$ is the symmetrised product of
(5.25) with $r+\bar{r}$, ranging over all $r\neq i,j$. In this product, the
terms in (5.25) stay as consecutive subwords, and the letters distinct from
$i,j$ may have any order, with equal coefficient. Thus coefficient of a word
in this eigenvector is given by $\tilde{\mathbf{f}}_{ij}$.

As for $\bar{i}j$, its standard-bracketing is
$[i-\bar{i},j+\bar{j}]=-[j+\bar{j},i-\bar{i}]$, which differs from (5.25) only
by a global sign and the exchange of $i$ and $j$. So, by the same argument as
above, $-\tilde{\mathbf{f}}_{ji}(w)$ describes the coefficient of $w$ in this
eigenvector.

  2. ii)

Similar to case i) above, these eigenvectors are produced from $n-1$ Lyndon
factors whose standard-bracketing are all $\tau$-invariant. By the first line
of Corollary 5.6, each Lyndon factor consists of an even number of negative
letters. As in case i), $n-2$ of the factors are single positive letters, and
the remaining factor is $ij$ or $\bar{i}\bar{j}$. Note that

$\displaystyle\operatorname{stdbrac}(ij)$
$\displaystyle=ij+\bar{i}j+i\bar{j}+\bar{i}\bar{j}-ji-j\bar{i}-\bar{j}i-\bar{j}\bar{i};$
$\displaystyle\operatorname{stdbrac}(\bar{i}\bar{j})$
$\displaystyle=ij-\bar{i}j-i\bar{j}+\bar{i}\bar{j}-ji+j\bar{i}+\bar{j}i-\bar{j}\bar{i}.$

So
$p^{+}:=\frac{1}{2}(\operatorname{stdbrac}(ij)+\operatorname{stdbrac}(\bar{i}\bar{j}))$
and
$p^{-}:=\frac{1}{2}(\operatorname{stdbrac}(ij)-\operatorname{stdbrac}(\bar{i}\bar{j}))$
have coefficients as decribed by $\mathbf{f}_{ij}^{+}$ and
$\mathbf{f}_{ij}^{-}$, respectively, when $w$ consists only of $i$ or
$\bar{i}$ once and $j$ or $\bar{j}$ once. The extension to words longer than
$w$ is as in case i): take the symmetrised product of $p^{+}$ or $p^{-}$ with
all $r+\bar{r}$ for $r\neq i,j$, following Theorems 3.5 and 3.8. Note that
(with the obvious notation)

$\operatorname{sym}\\{p^{+}\\}\cup\\{r+\bar{r}|\ r\neq
i,j\\}=\operatorname{sym}\\{\operatorname{stdbrac}(ij)\\}\cup\\{r+\bar{r}|\
r\neq
i,j\\}+\operatorname{sym}\\{\operatorname{stdbrac}(\bar{i}\bar{j})\\}\cup\\{r+\bar{r}|\
r\neq i,j\\}$

and similarly for $p^{-}$, because taking symmetrised product is linear in
each argument.

  3. iii)

$k=n-1$ and $\bar{k}=1$ means that the indexing word has $n$ Lyndon factors,
so each factor must be a single letter. From Corollary 5.6, the standard-
bracketing of a single positive letter is both $\tau$-invariant and
$\tilde{\tau}$-invariant, and the standard-bracketing of a single negative
letter is both $\tau$-negating and $\tilde{\tau}$-negating. Hence, these $n$
Lyndon factors are precisely one negative letter, say $\bar{i}$, and $n-1$
positive letters. Since $\bar{k}=1$, the formula in Theorem 3.4.i.c (for
$\operatorname{BRiffle}\tilde{\tau}_{a}^{-}$) and (3.6) (for
$\operatorname{BRiffle}\tau_{a}^{+}$ and $\operatorname{BRiffle}\tau_{a}^{-}$)
both simplify to $(i-\bar{i})s+s(i-\bar{i})$, where $s$ denotes the
symmetrised product of $r+\bar{r}$ over all $r\neq i$. The coefficient of a
word in this eigenvector is given by $\mathbf{g}_{i}$.

∎

## References

  * [AA17] Marcelo Aguiar and Federico Ardila  “Hopf monoids and generalized permutahedra”  In _ArXiv e-prints_ , 2017  arXiv:1709.07504
  * [ABS06] Marcelo Aguiar, Nantel Bergeron and Frank Sottile  “Combinatorial Hopf algebras and generalized Dehn–Sommerville relations”  In _Compos. Math._ 142.1, 2006, pp. 1–30  eprint: 10.1112/S0010437X0500165X
  * [AL15] Marcelo Aguiar and Aaron Lauve  “The characteristic polynomial of the Adams operators on graded connected Hopf algebras”  In _Algebra Number Theory_ 9.3, 2015, pp. 547–583  DOI: 10.2140/ant.2015.9.547
  * [AS05] Marcelo Aguiar and Frank Sottile  “Cocommutative Hopf algebras of permutations and trees”  In _J. Algebraic Combin._ 22.4, 2005, pp. 451–470  DOI: 10.1007/s10801-005-4628-y
  * [BB92] François Bergeron and Nantel Bergeron  “Orthogonal idempotents in the descent algebra of $B_{n}$ and applications”  In _J. Pure Appl. Algebra_ 79.2, 1992, pp. 109–129  DOI: 10.1016/0022-4049(92)90153-7
  * [BD92] Dave Bayer and Persi Diaconis  “Trailing the dovetail shuffle to its lair”  In _Ann. Appl. Probab._ 2.2, 1992, pp. 294–313
  * [BHR99] Pat Bidigare, Phil Hanlon and Dan Rockmore  “A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements”  In _Duke Math. J._ 99.1, 1999, pp. 135–174  DOI: 10.1215/S0012-7094-99-09906-4
  * [BW17] John R. Britnell and Mark Wildon  “Bell numbers, partition moves and the eigenvalues of the random-to-top shuffle in Dynkin types A, B and D”  In _J. Combin. Theory Ser. A_ 148, 2017, pp. 116–144  DOI: 10.1016/j.jcta.2016.12.003
  * [Car07] Pierre Cartier  “A primer of Hopf algebras”  In _Frontiers in Number Theory, Physics, and Geometry. II_ Berlin: Springer, 2007, pp. 537–615  eprint: 10.1007/978-3-540-30308-4˙12
  * [CP17] Grégory Chatel and Vincent Pilaud  “Cambrian Hopf algebras”  In _Adv. Math._ 311, 2017, pp. 598–633  DOI: 10.1016/j.aim.2017.02.027
  * [DFH13] Persi Diaconis, Jason Fulman and Susan Holmes  “Analysis of casino shelf shuffling machines”  In _Ann. Appl. Probab._ 23.4, 2013, pp. 1692–1720
  * [DPR14] Persi Diaconis, C. Y. Amy Pang and Arun Ram  “Hopf algebras and Markov chains: two examples and a theory”  In _J. Algebraic Combin._ 39.3, 2014, pp. 527–585  DOI: 10.1007/s10801-013-0456-7
  * [DS] Persi Diaconis and Ben Steinberg  “Coloured shuffles and random walks on semigroups” Unpublished Manuscript
  * [DS18] A. B. Dieker and F. V. Saliola  “Spectral analysis of random-to-random Markov chains”  In _Adv. Math._ 323, 2018, pp. 427–485  DOI: 10.1016/j.aim.2017.10.034
  * [Dur08] Richard Durrett  “Genome rearrangement”  In _Probability Models for DNA Sequence Evolution_ New York: Springer, 2008, pp. 355–397
  * [Fil96] James Allen Fill  “An exact formula for the move-to-front rule for self-organizing lists”  In _J. Theoret. Probab._ 9.1, 1996, pp. 113–160  DOI: 10.1007/BF02213737
  * [Ful01] Jason Fulman  “Applications of the Brauer complex: card shuffling, permutation statistics, and dynamical systems”  In _J. Algebra_ 243.1, 2001, pp. 96–122  DOI: 10.1006/jabr.2001.8814
  * [Ful02] Jason Fulman  “Applications of symmetric functions to cycle and increasing subsequence structure after shuffles”  In _J. Algebraic Combin._ 16.2, 2002, pp. 165–194  DOI: 10.1023/A:1021177012548
  * [GR14] Darij Grinberg and Vic Reiner  “Hopf algebras in combinatorics”  In _ArXiv e-prints_ , 2014  arXiv:1409.8356
  * [Hiv07] Florent Hivert  “An introduction to combinatorial Hopf algebras—examples and realizations”  In _Physics and theoretical computer science_ 7, NATO Secur. Sci. Ser. D Inf. Commun. Secur.  Amsterdam: IOS, 2007, pp. 253–274
  * [JR79] S. A. Joni and G.-C. Rota  “Coalgebras and bialgebras in combinatorics”  In _Stud. Appl. Math._ 61.2, 1979, pp. 93–139
  * [Kna02] Anthony W. Knapp  “Lie groups beyond an introduction” 140, Progress in Mathematics  Birkhäuser Boston Inc., Boston, MA, 2002, pp. xviii+812
  * [Laf20] Nadia Lafrenière  “Eigenvalues of symmetrized shuffling operators”  In _Sém. Lothar. Combin._ 82B, 2020, pp. Art. 78, 12
  * [Lod98] Jean-Louis Loday  “Cyclic homology” Appendix E by María O. Ronco, Chapter 13 by the author in collaboration with Teimuraz Pirashvili 301, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]  Springer-Verlag, Berlin, 1998, pp. xx+513  DOI: 10.1007/978-3-662-11389-9
  * [Lot97] M. Lothaire  “Combinatorics on Words” With a foreword by Roger Lyndon and a preface by Dominique Perrin; corrected reprint of the 1983 original, with a new preface by Perrin, Cambridge Mathematical Library  Cambridge: Cambridge University Press, 1997, pp. xviii+238  eprint: 10.1017/CBO9780511566097
  * [LPW09] David A. Levin, Yuval Peres and Elizabeth L. Wilmer  “Markov chains and mixing times” With a chapter by James G. Propp and David B. Wilson  Providence, RI: American Mathematical Society, 2009, pp. xviii+371
  * [LR98] Jean-Louis Loday and María O. Ronco  “Hopf algebra of the planar binary trees”  In _Adv. Math._ 139.2, 1998, pp. 293–309  DOI: 10.1006/aima.1998.1759
  * [LSK02] Bret Larget, Donald L Simon and Joseph B Kadane  “Bayesian phylogenetic inference from animal mitochondrial genome arrangements”  In _Journal of the Royal Statistical Society: Series B_ 64.4, 2002, pp. 681–693
  * [Moy15] Matthew Moynihan  “The colored Eulerian descent algebra”  In _J. Algebraic Combin._ 42.3, 2015, pp. 671–694  DOI: 10.1007/s10801-015-0596-z
  * [MR95] Clauda Malvenuto and Christophe Reutenauer  “Duality between quasi-symmetric functions and the Solomon descent algebra”  In _J. Algebra_ 177.3, 1995, pp. 967–982  DOI: 10.1006/jabr.1995.1336
  * [MR95a] R. Mantaci and C. Reutenauer  “A generalization of Solomon’s algebra for hyperoctahedral groups and other wreath products”  In _Comm. Algebra_ 23.1, 1995, pp. 27–56  DOI: 10.1080/00927879508825205
  * [Pan18] C. Y. Amy Pang  “Markov chains from Descent Operators on Combinatorial Hopf Algebras”  In _ArXiv e-prints_ , 2018
  * [Pat94] F. Patras  “L’algèbre des descentes d’une bigèbre graduée”  In _J. Algebra_ 170.2, 1994, pp. 547–566  DOI: 10.1006/jabr.1994.1352
  * [PP98] R. M. Phatarfod and A. J. Pryde  “On some multi-request move-to-front heuristics”  In _J. Appl. Probab._ 35.4, 1998, pp. 911–918  DOI: 10.1017/s0021900200016612
  * [PP99] A. J. Pryde and R. M. Phatarfod  “Multiplicities of eigenvalues of some linear search schemes”  In _Linear Algebra Appl._ 291.1-3, 1999, pp. 115–124  DOI: 10.1016/S0024-3795(98)10246-X
  * [Sch93] William R. Schmitt  “Hopf algebras of combinatorial structures”  In _Canad. J. Math._ 45.2, 1993, pp. 412–428  eprint: 10.4153/CJM-1993-021-5
  * [Sol76] Louis Solomon  “A Mackey formula in the group ring of a Coxeter group”  In _J. Algebra_ 41.2, 1976, pp. 255–264
  * [Ste+19] W.. Stein  “Sage Mathematics Software (Version 8.7)” http://www.sagemath.org, 2019  The Sage Development Team
  * [Swe69] Moss E. Sweedler  “Hopf algebras”, Mathematics Lecture Note Series  W. A. Benjamin, Inc., New York, 1969, pp. vii+336
  * [Wil04] David Bruce Wilson  “Mixing times of Lozenge tiling and card shuffling Markov chains”  In _Ann. Appl. Probab._ 14.1, 2004, pp. 274–325  DOI: 10.1214/aoap/1075828054


# Subtractive random forests with two choices ††thanks:  Gábor Lugosi
acknowledges the support of Ayudas Fundación BBVA a Proyectos de Investigación
Científica 2021 and the Spanish Ministry of Economy and Competitiveness grant
PID2022-138268NB-I00, financed by MCIN/AEI/10.13039/501100011033,
FSE+MTM2015-67304-P, and FEDER, EU.

Francisco Calvillo
LPSM, Sorbonne Université, 4 Place Jussieu, 75005 Paris, France  Luc Devroye
School of Computer Science, McGill University,
Montreal, Canada  Gábor Lugosi
Department of Economics and Business,
Pompeu Fabra University, Barcelona, Spain
ICREA, Pg. Lluís Companys 23, 08010 Barcelona, Spain
Barcelona Graduate School of Economics

###### Abstract

Recommendation systems are pivotal in aiding users amid vast online content.
Broutin, Devroye, Lugosi, and Oliveira proposed Subtractive Random Forests
(surf), a model that emphasizes temporal user preferences. Expanding on surf,
we introduce a model for a multi-choice recommendation system, enabling users
to select from two independent suggestions based on past interactions. We
evaluate its effectiveness and robustness across diverse scenarios,
incorporating heavy-tailed distributions for time delays. By analyzing user
topic evolution, we assess the system’s consistency. Our study offers insights
into the performance and potential enhancements of multi-choice recommendation
systems in practical settings.

##  1 Introduction

Today’s online platforms have a record number of items available for their
users. In many cases presenting them as a catalogue is no longer a good option
and can make it difficult for the user to find what they are interested in.
Recommendation systems have become an essential tool to cope with the overload
of information available on the web.

A well-known way to approach recommendation systems today is through deep
learning, and many of the most effective recommendation systems use this
principle, see [14]. However, the mechanism of these systems is notable for
its opacity. In the realm of online sequential recommendation systems,
Broutin, Devroye, Lugosi, and Oliveira [6] present an approach, offering a
framework that considers the temporal aspect of user preferences by a simple
mechanism. They define a model recommending topics based on a random time
delay. The topic that is recommended at time $n$ is the same that was
recommended at time $n-Z_{n}$, where $(Z_{k})_{k\geq 1}$ is a sequence of
i.i.d. random variables identically distributed on $\\{1,2,\ldots\\}$. This
approach led them to study a family of random forests called subtractive
random forests (surf), allowing a detailed structural study. However, one
expects a recommendation system to make several recommendations at a time, not
just one.

To model this more realistic scenario, our paper proposes a two-choice
recommendation system inspired by the same idea. We envision a scenario where
users are presented with two independent recommendations, drawn from the same
temporal recommendation mechanism and allowing users to select the most
appealing option. The resulting model has some intriguing mathematical
properties and the main goal of this paper is to analyze the model in order to
understand the long-term behavior of such recommendation systems.

###  1.1 A two-choice recommendation model

We assume that the initial pool of topics is infinite and represented by the
set of non-positive integers $\\{0,-1,-2,\ldots\\}$. We now consider
independent and identically distributed random variables $Z$, $W$,
$(Z_{n})_{n\geq 1}$ and $(W_{n})_{n\geq 1}$ on the set of positive integers
$\mathbb{N}$. Define

$q_{i}=\mathbb{P}(Z=i)\quad\text{and}\quad p_{i}=\mathbb{P}(Z\geq i),\quad
i\geq 1~{}.$

Each topic $i\leq 0$ is assigned a preference value $U_{i}$ within the range
$[0,1]$, where we assume that $(U_{n})_{n\leq 0}$ is a sequence of random
variables independent of the sequences $(Z_{n})_{n\geq 1}$ and $(W_{n})_{n\geq
1}$. These preference values are user-dependent.

Following [6], we can define a sequential random colouring of the positive
integers as follows. For each non-positive integer $i\leq 0$, define its
colour $C_{i}=i$ and its preference value $V_{i}=U_{i}$. We assign colours and
preference values to the positive integers $n\in\mathbb{N}$ by the recursion

$\left\\{\begin{array}[]{ll}C_{n}=C_{n-Z_{n}}\text{ and
}V_{n}=V_{n-Z_{n}}&\text{ if }V_{n-Z_{n}}<V_{n-W_{n}}\\\
C_{n}=C_{n-W_{n}}\text{ and }V_{n}=V_{n-W_{n}}&\text{ otherwise
}~{}.\end{array}\right.$

Thus, by identifying the colour $C_{n}$ as the topic recommended at time
$n\geq 1$, this definition means that at the time instance $n\geq 1$, the user
receives two recommendations (the topic $C_{n-Z_{n}}$, and the topic
$C_{n-W_{n}}$), and chooses the one with the lowest (best) preference value.

This process naturally defines a random directed graph whose vertex set is
$\mathbb{Z}$ by drawing an edge from any positive integer $n\geq 1$ to any
integer $m<n$ if and only if $m=n-Z_{n}$ or $m=n-W_{n}$. Vertices with
negative index are called leaves, as is customary for final nodes in dags
(i.e., directed acyclic graphs). Let $T_{n}$ denote the set of vertices that
are reached from the vertex $n\geq 1$. This set can be defined recursively by
saying that $T_{n}=\\{n\\}$ for any $n\leq 0$, and

$T_{n}=\\{n,n-Z_{n},n-W_{n}\\}\cup T_{n-Z_{n}}\cup T_{n-W_{n}}$

for any $n\geq 1$. Define

$\mathcal{L}_{n}=T_{n}\cap\\{0,-1,-2,\dots\\}$

as the set of vertices with a non-positive index that is reached from $n$. In
other words, $\mathcal{L}_{n}$ is the set of leaves in the subgraph of
vertices reached from $n$. Note that

$C_{n}=\mathop{\mathrm{argmin}}_{i\in\mathcal{L}_{n}}U_{i}~{}\text{ and
}~{}V_{n}=\min_{i\in\mathcal{L}_{n}}U_{i}~{}.$

One can assess the system’s long-term performance by analyzing the asymptotic
behavior of the sequence $(V_{n})_{n\geq 1}$. If $V_{n}$ approaches
$\inf_{i\leq 0}U_{i}$ as $n\to\infty$, then this means that after waiting a
sufficient amount of time, the topics recommended to the user tend to align
more closely with their preferences. This gives us a consistency criterion for
our model. We consider the three following configurations of the preference
values:

  1. (i)

$U_{0}<U_{-1}<U_{-2}<U_{-3}\dots$

  2. (ii)

$U_{0}>U_{-1}>U_{-2}>U_{-3}\dots$

  3. (iii)

$(U_{n})_{n\leq 0}$ i.i.d. and uniformly distributed in $[0,1].$

These assumptions correspond to natural scenarios and allow us to study long-
term consistency of the recommendation system. In the first case, topics have
a monotone preference with the most recent (corresponding to $i=0$) being the
most preferred one. In the second case, older topics are preferred, while in
the third case topics have a random order of preference. We say that the
system is consistent if, on the long run, it offers near-optimal
recommendations to the user in terms of the their preference. In Section 1.3
we rigorously define various notions of consistency, corresponding to the
scenarios above. These definitions lead us to the study of the sequence
$(V_{n})_{n\geq 1}$ by studying the set of leaves $\mathcal{L}_{n}$. We will
pay particular attention to the three following random variables:

$\bullet$ $R_{n}=\max\left\\{i:i\in\mathcal{L}_{n}\right\\}$ (the rightmost
leaf in $\mathcal{L}_{n}$)

$\bullet$ $M_{n}=\min\left\\{i:i\in\mathcal{L}_{n}\right\\}$ (the leftmost
leaf in $\mathcal{L}_{n}$)

$\bullet$ $L_{n}=|\mathcal{L}_{n}|$ (the number of leaves reached from $n$).

Each of these random variables helps us understand the long-term behavior of
$V_{n}$ in each of the three initial configurations described above. One would
ideally hope that $V_{n}\to\inf_{i\leq 0}U_{i}$. In configuration (i) this is
equivalent to $R_{n}\to 0$, in configuration (ii) it is equivalent to
$M_{n}\to-\infty$, while in case (iii) to $L_{n}\to\infty$. However, one
cannot expect to have $R_{n}\to 0$ in a general case. To introduce a more
reasonable consistency criterion for case (i), we require boundedness of the
sequence $(R_{n})_{n\geq 1}~{}.$

Figure 1: An illustration of the definitions of $M_{n}$, $R_{n}$, and
$\mathcal{L}_{n}$.

Let us define the subsets $T_{n}^{Z}=T_{n}^{W}=S_{n}=\\{n\\}$ for any $n\leq
0$, and let

$T_{n}^{Z}=\\{n\\}\cup T_{n-Z_{n}}^{Z}~{},$

$T_{n}^{W}=\\{n\\}\cup T_{n-W_{n}}^{W}~{},$

$\text{and }S_{n}=\\{n\\}\cup S_{n-\min(Z_{n},W_{n})}$

for any $n\geq 1$, so that $T_{n}^{Z}\subset T_{n}$ (resp. $T_{n}^{W}\subset
T_{n}$) is the chain of vertices that can be reached from $n$ by following
only the $Z$-edges (resp. $W$-edges), and $S_{n}\subset T_{n}$ is the chain of
vertices that can be reached from $n$ by following only the shortest edges.

Finally, for any $n\geq 1$, let $r_{n}=\mathbb{P}\left(0\in
T_{n}^{Z}\right)=\mathbb{P}\left(0\in T_{n}^{W}\right)$ denote the probability
that vertex $0$ belongs to the $Z$-chain starting at vertex $n$. We set
$r_{0}=1$ so that $r_{n}$ satisfies the recursion

$r_{n}=\sum_{i=1}^{n}q_{i}r_{n-i}~{}.$ (1.1)

###  1.2 Related work

This paper builds on the work of Broutin, Devroye, Lugosi and Oliveira [6],
who studied a one-choice version of this model by examining the properties of
a graph whose vertex set is $\mathbb{Z}$, and whose edges are
$\\{n,n-Z_{n}\\}$ for every $n\geq 1$, given some sequence $(Z_{n})_{n\geq 1}$
of i.i.d. random variables distributed in $\\{1,2,3,\dots\\}$. This defines a
random forest where each non-positive integer is the root of a tree. They also
define a random coloring by setting $C_{i}=i$ for all $i\leq 0$, and
$C_{n}=C_{n-Z_{n}}$ for all $n\geq 1$. Each tree in the forest corresponds to
a colour (i.e., a topic). The graph that we consider in our paper is nothing
else than the superposition of two independent copies of this forest, and the
sets $T_{n}^{Z}$ and $T_{n}^{W}$ defined above are the chains that connect the
vertex $n$ to the root of its tree in each of these two copies.

One of the main results in [6] shows that the process has two distinct
behaviors: if $\mathbb{E}Z=\infty$, then, almost surely, all trees in the
forest are finite, meaning that no topic will be recommended infinitely often,
while if $\mathbb{E}Z<\infty$, after some random amount of time, all vertices
connect to the same tree almost surely, meaning that all topics recommended to
the user become the same. In the two-choice model however, there are three
distinct regimes: $\mathbb{E}Z<\infty$; $\mathbb{E}Z=\infty$ yet
$\mathbb{E}\min(Z,W)<\infty$; and $\mathbb{E}\min(Z,W)=\infty$. We call these
the light-, moderate-, and heavy-tailed regimes.

The random forest in [6] appears as a subgraph of a random graph model that
was previously studied by Hammond and Sheffield in [10]. Given a sequence
$(Z_{n})_{n\in\mathbb{Z}}$ of independent random variables, identically
distributed in $\\{1,2,3,\dots\\}$, they consider a graph with vertex set
$\mathbb{Z}$ such that vertices $n,m\in\mathbb{Z}$, with $m<n$, are connected
by an edge if and only if $m=n-Z_{n}$. One can obtain the random forest in [6]
by removing all edges between any two vertices with a non-positive index. They
show that the random graph has almost surely a unique component when the sum
$\sum_{n=1}^{\infty}r_{n}^{2}$ converges, and the graph almost surely has
infinitely many connected components when the sum diverges.

Other variants of the (single-choice) random subtractive process were studied,
in different contexts, by Blath, Jochen, González, Kurt, and Spano [4],
Chierichetti, Kumar, and Tomkins [8], Baccelli and Sodre [3], Baccelli, Haji-
Mirsadeghi, and Khezeli [2], Baccelli, Haji-Mirsadeghi, and Khaniha [1], and
Igelbrink and Wakolbinger [12].

###  1.3 Results

The goal of this paper is to understand the behavior of the two-choice model
by studying its consistency in each of the three configurations (i),(ii), and
(iii), for three types of tails, light, moderate, and heavy:

  1. 1.

$\mathbb{E}Z<\infty$ (light tails)

  2. 2.

$\mathbb{E}Z=\infty$ and $\mathbb{E}\min(Z,W)<\infty$ (moderate tails)

  3. 3.

$\mathbb{E}\min(Z,W)=\infty$ (heavy tails)

We now introduce the main definitions of consistency.

######  Definition 1.

We say that the system is consistent in configuration (ii) if
$M_{n}\to-\infty$; while it is consistent in configuration (iii) if
$L_{n}\to\infty$. We differentiate between strong and weak consistency based
on whether convergence occurs almost surely or in probability. In the case of
configuration (i), we say that the system is weakly consistent if
$(R_{n})_{n\geq 1}$ is a tight sequence. It is strongly consistent if the
sequence $(R_{n})_{n\geq 1}$ is almost surely bounded.

######  Remark 1.

Pareto tails. Consider a distribution with Pareto tails, that is,
$q_{n}=\Theta(1/n^{1+\alpha})$, with $\alpha>0$. This implies that
$p_{n}=\Theta(1/n^{\alpha})$. When $\alpha>1$, we see that
$\mathbb{E}Z<\infty$. The more interesting situation is when $\alpha\in(0,1]$.
For $\alpha\in(1/2,1]$, we have $\mathbb{E}Z=\infty$, yet
$\mathbb{E}\min(Z,W)<\infty$. Finally, for $\alpha\in(0,1/2]$, we have
$\mathbb{E}\min(Z,W)=\infty$. For light-tailed $Z$, we recall from Broutin,
Devroye, Lugosi, Oliveira [6] that $r_{n}\to 1/\mathbb{E}Z$. For moderate and
heavy tails, however, we have $r_{n}\to 0$. When $\alpha\in(0,1)$, then $Z$ is
in the domain of attraction of the extremal stable law with parameter
$\alpha$, which itself has a tail distribution function that decays at the
rate $1/n^{\alpha}$ (see, e.g., Ibragimov and Linnik [11], Zolotarev [15] or
Malevich [13]). One can then deduce that $r_{n}$ decays at the rate
$1/n^{1-\alpha}$. In particular, $\sum_{n}r_{n}^{2}<\infty$ when
$\alpha\in(0,1/2)$, which roughly corresponds to the case of heavy tails.

Next we describe the main results of the paper. For a summary, see the table
at the end of this section.

#### Light tails

When $\mathbb{E}Z<\infty$, time jumps are so short that $T_{n}$ can’t reach
distant leaves, thus forcing the set $\mathcal{L}_{n}$ to be bounded. This
case does not require much work, since one can quickly determine consistency
or inconsistency in each of the three configurations just by looking at the
sequence $(M_{n})_{n\geq 1}$, which happens to be bounded almost surely.

######  Theorem 2.

Let $M_{\infty}=\inf_{n\in\mathbb{N}}M_{n}$. If $\mathbb{E}Z<\infty$, then
$M_{\infty}$ is finite almost surely. Thus, the sequences
$(R_{n})_{n\in\mathbb{N}},(M_{n})_{n\in\mathbb{N}}$ and
$(L_{n})_{n\in\mathbb{N}}$ are almost surely bounded.

Proof. Note that

$\displaystyle\mathbb{P}\left(M_{\infty}\leq-x\right)\leq
2\sum_{n=1}^{\infty}\mathbb{P}\left(n-Z_{n}\leq-x\right)=2\sum_{n=1}^{\infty}p_{n+x}~{}.$

Since $\mathbb{E}Z<\infty$, we know that $\sum_{n=1}^{\infty}p_{n+x}$ is
finite and goes to $0$ as $x\rightarrow+\infty$. Thus, by continuity of
measure,

$\displaystyle\mathbb{P}\left(M_{\infty}=-\infty\right)=\lim_{x\rightarrow+\infty}\mathbb{P}\left(M_{\infty}\leq-x\right)=0~{}.$

Since $|M_{n}|\geq L_{n}$ and $|M_{n}|\geq|R_{n}|$, this also implies that
$(L_{n})_{n\in\mathbb{N}}$ and $(R_{n})_{n\in\mathbb{N}}$ are almost surely
bounded.

#### Moderate and heavy tails

When $\mathbb{E}\min(Z,W)=\infty$, a different behavior emerges:

######  Theorem 3.

Let $Z$, $W$, $(Z_{n})_{n\geq 1}$ and $(W_{n})_{n\geq 1}$ be i.i.d. random
variables. Assume furthermore that $\mathbb{E}\min(Z,W)=\infty~{}.$ Then, with
probability one, the number of leaves satisfies

$\liminf_{n\to\infty}L_{n}<\infty~{}.$

In other words, the system is not strongly consistent in the heavy-tailed
regime.

Proof. Note that if $\min(Z_{n},W_{n})\geq n$, then $L_{n}\in\\{1,2\\}$. Thus,
to prove Theorem 3, it suffices to show that with probability one,
$\min(Z_{n},W_{n})\geq n$ happens infinitely often. This follows by the second
Borel-Cantelli lemma since the events

$(\\{\min(Z_{n},W_{n})\geq n\\})_{n\in\mathbb{N}}$

are independent and

$\sum_{n\geq 1}\mathbb{P}\left(\min(Z_{n},W_{n})\geq
n\right)=\mathbb{E}\left(\min(Z,W)\right)=\infty~{}.$

The behavior of the set $\mathcal{L}_{n}$ for moderate and heavy tails is
better understood by examining its extreme points $M_{n}$ and $R_{n}$. The
following two theorems are proved in Section 3.

######  Theorem 4.

If $q_{i}>0$ for all $i\in\mathbb{N}$ and $\mathbb{E}Z=\infty$, then, with
probability one,

$M_{n}\to-\infty~{}.$

Thus, in configuration (ii) the system is strongly consistent in the moderate
and heavy-tailed regimes.

Strong (in-)consistency in configuration (i) is established in the next
result:

######  Theorem 5.

Let $Z$, $W$, $(Z_{n})_{n\geq 1}$ and $(W_{n})_{n\geq 1}$ be i.i.d. random
variables.

  1. 1.

If $\mathbb{E}\min(Z,W)<\infty$, then $\sup_{n\in\mathbb{N}}|R_{n}|<\infty$
almost surely.

  2. 2.

If $\mathbb{E}\min(Z,W)=\infty$, then $\sup_{n\in\mathbb{N}}|R_{n}|=\infty$
almost surely.

Given that the leftmost leaf in $\mathcal{L}_{n}$ goes to $-\infty$ and the
rightmost leaf remains bounded in the moderate heavy-tail regime (i.e., when
$\mathbb{E}Z=\infty$ and $\mathbb{E}\min(Z,W)<\infty$), one can expect that
the total number of leaves reached by the vertex $n$ diverges under these two
assumptions. Thus, strong consistency is observed in each of the three
configurations (i), (ii), and (iii).

On the other hand, only configuration (i) leads to strong consistency when the
distribution of $Z$ has a heavy-tail (i.e., when
$\mathbb{E}\min(Z,W)=\infty$). However, when
$\sum_{n=1}^{\infty}r_{n}^{2}<\infty$, the model remains weakly consistent in
configuration (iii), as established by the next two results. Theorems 6 and 7
are proved in Sections 4.1 and 4.2, respectively.

######  Theorem 6.

Assume that the distribution of $Z$ is not supported by any proper additive
subgroup of the integers and that $Z$ exhibits a moderate-sized tail (i.e.,
$\mathbb{E}\min(Z,W)<\infty$ and $\mathbb{E}Z=\infty$). Then

$L_{n}\to\infty\text{ almost surely. }$

######  Theorem 7.

When $Z$ has a heavy tail (i.e., $\mathbb{E}\min(Z,W)=\infty$), and
$\sum_{n\geq 0}r_{n}^{2}<\infty~{},$ then

$L_{n}\to\infty\textit{ in probability.}$

We recall from Remark 1 that the summability of $r_{n}^{2}$ is assured for
nearly all heavy-tailed $Z$.

###  1.4 Summary

The following table summarizes our findings. Observe that weak and strong
behavior coincide in most cases. They only differ in the extreme heavy tail
case ($\mathbb{E}\min(Z,W)=\infty$). For an optimal user experience, one would
need $L_{n}\to\infty$ almost surely, and the only case that assures this is
when we have moderate tails. In addition, such moderate tails also guarantee
strong consistency for the decreasing and increasing input scenarios (as is
apparent from the strong consistency of $M_{n}$ and $R_{n}$).

| $\mathbb{E}Z<\infty$ |  $\mathbb{E}Z=\infty$ and $\mathbb{E}\min(Z,W)<\infty$ | $\mathbb{E}\min(Z,W)=\infty$
---|---|---|---
| Strong consistency
$M_{n}\to-\infty$ a.s. | no (Thm. 2) | yes (Thm. 4) | yes (Thm. 4)
$L_{n}\to\infty$ a.s. | no (Thm. 2) | yes (Thm. 6) | no (Thm. 3)
$R_{n}$ bounded a.s. | yes (Thm. 2) | yes (Thm. 5) | no (Thm. 3)
| Weak consistency
$M_{n}\overset{\mathbb{P}}{\to}-\infty$ | no (Thm. 2) | yes (Thm. 4) | yes (Thm. 4)
$L_{n}\overset{\mathbb{P}}{\to}\infty$ | no (Thm. 2) | yes (Prop. 11) | yes if $\sum r_{n}^{2}<\infty$ (Thm. 7)
$R_{n}$ is tight | yes (Thm. 2) | yes (Thm. 5) |

The rest of the paper contains the proofs of the results stated above. In
Section 2 we recall some properties of the single-choice model that are useful
in our analysis. In Section 3, Theorems 4 and 5 are proven. The main technical
content of the paper is presented in Section 4 where the number of leaves is
examined in both the moderate-, and heavy-tailed cases, culminating in the
proofs of Theorems 6 and 7.

##  2 The one-choice model

Some of our proofs use the observation that the graph contains several copies
of the subtractive random forest studied in [6]. For example, Theorem 1 in [6]
states that there is a unique infinite tree in the forest when
$\mathbb{E}Z<\infty$:

######  Theorem 8 (Broutin, Devroye, Lugosi, Oliveira [6]).

Assume $\mathbb{E}Z<\infty$ and $q_{1}>0~{}.$ Then there exists a positive
random variable $N$ with $\mathbb{P}\left(N<\infty\right)=1$ such that, with
probability one,

$N\in T_{n}^{Z}\quad\textit{for all }n\geq N~{}.$

######  Remark 2.

Note that the actual statement of the theorem in [6] is slightly weaker since
it only asserts that there is a random variable $N$, finite almost surely,
such that for all $n\geq N$, the vertex $n$ belongs to the same tree as the
vertex $N$. This does not necessarily imply that $N\in T_{n}^{Z}$.
Nevertheless, one can add this property of $N$ without changing the proof
provided in [6].

Define $Z^{\prime}_{n}=\min(Z_{n},W_{n})$ and $Z^{\prime}=\min(Z,W)$ and note
that $S_{n}=T_{n}^{Z^{\prime}}$. By Theorem 8 we obtain the following result
for moderate and light tails.

######  Corollary 9.

If $\mathbb{E}\min(Z,W)<\infty$ and $q_{1}>0$, then there exists a positive
random variable $N$ with $\mathbb{P}\left(N<\infty\right)=1$ such that, with
probability one,

$N\in S_{n}\quad\textit{for all }n\geq N$

When $\mathbb{E}Z=\infty$, Theorem 3 in [6] states that every tree in the
forest is finite. This translates as follows.

######  Theorem 10 (Broutin, Devroye, Lugosi, Oliveira [6]).

If $\mathbb{E}Z=\infty$ and $q_{i}>0$ for all $i\geq 1$, then

$\mathbb{P}(\cup_{i\leq 0}\left[\left|\\{n\geq 1:i\in
T_{n}^{Z}\\}\right|=\infty\right])=0~{}.$

##  3 Rightmost and leftmost leaves

As stated in Theorem 4, the leftmost leaf $M_{n}$ reached by vertex $n$
diverges to $-\infty$ whenever $\mathbb{E}Z=\infty$. This can be seen as a
consequence of the behavior of the one-choice model, as one only needs to
check the divergence to negative infinity of the leaf $\min T_{n}^{Z}$ reached
by vertex $n$ by following only the $Z$-edges.

Proof. [Proof of Theorem 4] From Theorem 10 we know that with probability one,
for all $k\leq 0$, there are at most a finite number of integers $n\geq 1$
such that $k\in T_{n}^{Z}$. Thus, the sequence $(\min
T_{n}^{Z})_{n\in\mathbb{N}}$, taking values in $\\{0,-1,-2,\dots\\}$, cannot
take the same value an infinite number of times, so it goes to $-\infty$ as
$n\to\infty$ with probability one. This concludes the proof, since
$M_{n}\leq\min T_{n}^{Z}$ for all $n\geq 1$.

Proof. [Proof of Theorem 5] Assume that $\mathbb{E}\min(Z,W)<\infty$. From
Corollary 9, we know that there exists some random variable $N$ with
$\mathbb{P}\left(N<\infty\right)=1$ such that, with probability one, $N\in
S_{n}$ for all $n\geq N$. In particular, for any $n\geq N$ we have
$T_{N}\subset T_{n}$, which implies that $|R_{N}|\geq|R_{n}|$. Thus, with
probability one, we have

$\sup_{n\in\mathbb{N}}|R_{n}|\leq\max_{1\leq k\leq N}|R_{k}|<\infty~{}.$

When $\mathbb{E}\min(Z,W)=\infty$, we have

$\sum_{n\geq 1}\mathbb{P}\left(\min(Z_{n},W_{n})\geq 2n\right)=\sum_{n\geq
1}p_{2n}^{2}=\infty~{}.$

Hence, by the second Borel-Cantelli lemma, we know that with probability one
we have $\min(Z_{n},W_{n})\geq 2n$ infinitely often, which implies that
$R_{n}\leq-n$ infinitely often and proves the second statement of the theorem.

##  4 Number of leaves

###  4.1 Moderate tails

Consider the number $L_{n}$ of leaves reached by vertex $n$, when the
distribution of $Z$ is such that $\mathbb{E}Z=\infty$ and
$\mathbb{E}\min(Z,W)<\infty$. We first show weak divergence, implying weak
consistency in configuration (iii).

######  Proposition 11.

Assume that the distribution of $Z$ is not supported by any proper additive
subgroup of the integers. If $\mathbb{E}Z=\infty$ and
$\mathbb{E}\min(Z,W)<\infty$, then

$L_{n}\to\infty~{}\textit{ in probability as }n\to\infty.$

######  Lemma 12.

Define

$J_{n}=\sum_{m=1}^{n}\mathbbm{1}_{m\in
S_{n}}\mathbbm{1}_{\max(Z_{m},W_{m})\geq m}~{}.$

Then $\mathbb{E}J_{n}\to\infty$ as $n\to\infty$.

Proof. $J_{n}$ counts the number of vertices in $S_{n}$ with a positive index
that are connected to a leaf through its longest outgoing edge. Note that for
$n\geq m\geq 1$, the events $\\{m\in S_{n}\\}$ and $\\{\max(Z_{m},W_{m})\geq
m\\}$ are independent. It follows that

$\mathbb{E}J_{n}=\sum_{m=1}^{n}\mathbb{P}(m\in
S_{n})\mathbb{P}(\max(Z_{m},W_{m})\geq
m)=\sum_{m=1}^{n}v_{n-m}\mathbb{P}(\max(Z_{m},W_{m})\geq m)$

where $v_{m}:=\mathbb{P}(0\in S_{m})$ for all $m\geq 1$, and $v_{0}=1$.

Let $f(z)=\sum_{n\geq 0}v_{n}z^{n}$, $\tilde{q}_{m}=\mathbb{P}(\min(Z,W)=m)$
and $g(z)=\sum_{n\geq 1}\tilde{q}_{n}z^{n}$. In view of

$v_{n}=\sum_{m=0}^{n-1}\tilde{q}_{n-m}v_{m},$

we have

$f(z)=1+\sum_{n=1}^{\infty}z^{n}\sum_{m=0}^{n}\tilde{q}_{n-m}v_{m}=1+g(z)f(z)=\frac{1}{1-g(z)}.$

Since $\min(Z,W)$ is not supported by any proper additive subgroup of the
integers, the Erdős-Feller-Pollard theorem [9] implies that

$\lim_{n\to\infty}v_{n}=\frac{1}{\mathbb{E}\min(Z,W)}~{}.$ (4.1)

Thus, for some constant $c>0$, we have

$\mathbb{E}J_{n}\geq c\sum_{m=1}^{n}p_{m}\to\infty\quad\text{as
}n\to\infty~{}.$ (4.2)

We use the second-moment method to show that $J_{n}\to\infty$ in probability.

######  Lemma 13.

Assume that $\mathbb{E}Z=\infty$ and $\mathbb{E}\min(Z,W)<\infty$, and let
$\mathbb{V}J_{n}$ denote the variance of the random variable $J_{n}$. Then

$\frac{\mathbb{V}J_{n}}{(\mathbb{E}J_{n})^{2}}\to 0\quad\text{as
}n\to\infty~{}.$ (4.3)

In particular, we have:

$\mathbb{P}\left(J_{n}\leq\frac{\mathbb{E}J_{n}}{2}\right)=\mathbb{P}\left(J_{n}-\mathbb{E}J_{n}\leq-\frac{\mathbb{E}J_{n}}{2}\right)\leq
4\frac{\mathbb{V}J_{n}}{(\mathbb{E}J_{n})^{2}}\to 0~{},$

and therefore $J_{n}\to\infty$ in probability as $n\to\infty$.

Proof. [Proof of Lemma 13] To show (4.3), we prove that
$\mathbb{E}[J_{n}^{2}]/(\mathbb{E}J_{n})^{2}\to 1$ as $n\to\infty$. We first
define

$p_{n}^{*}=\mathbb{P}(\max(Z,W)\geq n)=2p_{n}-p_{n}^{2}~{}.$

Note that for $n\geq 1$,

$\displaystyle(\mathbb{E}J_{n})^{2}$ $\displaystyle=2\sum_{1\leq k<m\leq
n}p_{m}^{*}p_{k}^{*}v_{n-m}v_{n-k}+\sum_{1\leq m\leq
n}(p_{m}^{*})^{2}v_{n-m}^{2}$ $\displaystyle=2\sum_{1\leq k<m\leq
n}p_{m}^{*}p_{k}^{*}v_{n-m}v_{n-k}+O(1)$ (4.4)

since $\sum_{1\leq m\leq n}(p_{m}^{*})^{2}v_{n-m}^{2}$ is bounded by
$4\mathbb{E}\min(Z,W)<\infty$.

Now, define for any $m\geq 1$ the random variable $X_{m}=\max(Z_{m},W_{m})$
and observe that for any $1\leq k<m\leq n$, the events $\left\\{X_{k}\geq
k\right\\}$ and $\left\\{X_{m}\geq m,m\in S_{n},k\in S_{n}\right\\}$ are
independent. Thus, for any fixed $n\geq 1$, we may write

$\displaystyle\mathbb{E}\left[J_{n}^{2}\right]$ $\displaystyle=2\sum_{1\leq
k<m\leq n}\mathbb{P}\left(m\in S_{n},k\in S_{n},X_{m}\geq m,X_{k}\geq
k\right)+\mathbb{E}J_{n}$ $\displaystyle=2\sum_{1\leq k<m\leq
n}p_{k}^{*}\mathbb{P}\left(m\in S_{n},k\in S_{n},X_{m}\geq
m\right)+\mathbb{E}J_{n}$ $\displaystyle=2\sum_{1\leq k<m\leq
n}p_{k}^{*}\mathbb{P}\mathopen{}\left[k\in S_{n},X_{m}\geq m\middle|m\in
S_{n}\right]\mathbb{P}\left(m\in S_{n}\right)+\mathbb{E}J_{n}$

If $m\in S_{n}$, the event $\\{k\in S_{n},X_{m}\geq m\\}$ can only happen if
one of the two random variables $Z_{m}$ and $W_{m}$ is greater or equal to $m$
and the other one is smaller than $m-k$, for otherwise $k$ could not belong to
$S_{n}$ when $1\leq k<m\leq n$. Thus, using the independence of $Z_{m}$ with
respect to $W_{m}$, $\\{k\in S_{n}\\}$ and $\\{m\in S_{n}\\}$, and using the
fact that $p_{m}^{*}+p_{m}^{2}=2p_{m}$,

$\displaystyle\mathbb{E}$ $\displaystyle\left[J_{n}^{2}\right]$ (4.5)
$\displaystyle=2\sum_{1\leq k<m\leq n}p_{k}^{*}\times
2\mathbb{P}\mathopen{}\left[Z_{m}\geq m,W_{m}\leq m-k,k\in S_{n}\middle|m\in
S_{n}\right]\mathbb{P}\left(m\in S_{n}\right)+\mathbb{E}J_{n}$
$\displaystyle=2\sum_{1\leq k<m\leq
n}p_{k}^{*}(p_{m}^{*}+p_{m}^{2})v_{n-m}\mathbb{P}\mathopen{}\left[W_{m}\leq
m-k,k\in S_{n}\middle|m\in S_{n}\right]+\mathbb{E}J_{n}$
$\displaystyle=4\sum_{1\leq k<m\leq
n}p_{k}^{*}(p_{m}^{*}+p_{m}^{2})v_{n-m}\sum_{i=1}^{k-m}\mathbb{P}\left(k\in
S_{m-i}\right)\mathbb{P}\left(W_{m}=i\right)+\mathbb{E}J_{n}$
$\displaystyle=2\sum_{1\leq k<m\leq
n}p_{k}^{*}(p_{m}^{*}+p_{m}^{2})v_{n-m}\sum_{i=1}^{m-k}v_{m-k-i}q_{i}+\mathbb{E}J_{n}~{}.$
(4.6)

Observe that

$\displaystyle\sum_{1\leq k<m\leq
n}p_{k}^{*}p_{m}^{2}v_{n-m}\sum_{i=1}^{m-k}q_{i}v_{m-k-i}$
$\displaystyle\leq\sum_{1\leq k<m\leq n}p_{k}^{*}p_{m}^{2}v_{n-m}$
$\displaystyle\leq\sum_{1\leq k<m\leq n}p_{k}^{*}p_{m}^{2}$
$\displaystyle\leq\left(\sum_{m=1}^{\infty}p_{m}^{2}\right)\left(\sum_{k=1}^{n}p_{k}^{*}\right)$
$\displaystyle=O\left(\mathbb{E}J_{n}\right)$

by using the inequality in (4.2), which leads to

$\mathbb{E}[J_{n}^{2}]=2\sum_{1\leq k<m\leq
n}p_{k}^{*}p_{m}^{*}v_{n-m}\sum_{i=1}^{m-k}v_{m-k-i}q_{i}+O\left(\mathbb{E}J_{n}\right)~{}.$
(4.7)

Fix some $\epsilon>0$. By (4.1), we know that there exists some constant $x>0$
such that for all $m\geq x$, we have $|v_{m}-\lambda|<\epsilon$, where
$\lambda=1/(\mathbb{E}\min(Z,W))$.

If $m\geq x$, see that

$\displaystyle\sum_{i=1}^{m}q_{i}v_{m-i}$
$\displaystyle\leq\sum_{i=1}^{m-x}q_{i}(\lambda+\epsilon)+\sum_{m-x<i\leq
m}q_{i}$ $\displaystyle\leq(\lambda+\epsilon)+p_{m-x}~{}.$

Thus, there exists some constant $y>x$ such that for all $m\geq y$,

$\sum_{i=1}^{m}q_{i}v_{m-i}\leq\lambda+2\epsilon~{}.$

Moreover,

$\displaystyle\sum_{\begin{subarray}{c}1\leq k<m\leq n\\\ \textit{s.t.
}m-k<y\end{subarray}}p_{m}^{*}v_{n-m}\underbrace{p_{k}^{*}\sum_{i=1}^{m-k}v_{m-k-i}q_{i}}_{\leq
1}$ $\displaystyle\leq\sum_{1\leq m\leq n}p_{m}^{*}v_{n-m}\sum_{k=m-y}^{m}1$
$\displaystyle=(y+1)\mathbb{E}J_{n}=O\left(\mathbb{E}J_{n}\right)~{},$

and

$\displaystyle\sum_{\begin{subarray}{c}1\leq k<m\leq n\\\ \textit{s.t.
}n-m<y\end{subarray}}p_{k}^{*}\underbrace{p_{m}^{*}v_{n-m}\sum_{i=1}^{m-k}v_{m-k-i}q_{i}}_{\leq
1}$ $\displaystyle\leq\sum_{n-y\leq m\leq n}1\sum_{k=1}^{n}p_{k}^{*}$
$\displaystyle\leq(y+1)\sum_{k=1}^{n}p_{k}^{*}=O\left(\mathbb{E}J_{n}\right)~{}.$

Putting everything together, we have that

$\displaystyle\mathbb{E}[J_{n}^{2}]=\sum_{m=1}^{n-y}\sum_{k=1}^{m-y}p_{m}^{*}p_{k}^{*}v_{n-k}\sum_{i=1}^{m-k}q_{i}v_{m-k-i}+O\left(\mathbb{E}J_{n}\right)~{}.$
(4.8)

Similarly, we have

$\displaystyle(\mathbb{E}J_{n})^{2}=\sum_{s=1}^{n-y}\sum_{k=1}^{m-y}p_{m}^{*}p_{k}^{*}v_{n-m}v_{n-k}+O\left(\mathbb{E}J_{n}\right)~{}.$
(4.9)

Finally, observe that for any $n>y$ we have:

$\displaystyle\sum_{m=1}^{n-y}\sum_{k=1}^{m-y}p_{m}^{*}p_{k}^{*}\underbrace{v_{n-m}\sum_{i=1}^{m-k}q_{i}v_{m-k-i}}_{\leq(\lambda+2\epsilon)^{2}}\leq(\lambda+2\epsilon)^{2}\sum_{m=1}^{n-y}\sum_{k=1}^{m-y}p_{m}^{*}p_{k}^{*}$
(4.10)

and

$\displaystyle\sum_{m=1}^{n-y}\sum_{k=1}^{m-y}p_{m}^{*}p_{k}^{*}\underbrace{v_{n-m}v_{n-k}}_{\geq(\lambda-\epsilon)^{2}}\geq(\lambda-\epsilon)^{2}\sum_{m=1}^{n-y}\sum_{k=1}^{m-y}p_{m}^{*}p_{k}^{*}~{}.$
(4.11)

From (4.8), (4.9), (4.10) and (4.11) it follows that

$\limsup_{n\to\infty}\frac{\mathbb{E}[J_{n}^{2}]}{(\mathbb{E}J_{n})^{2}}\leq\left(\frac{\lambda+2\epsilon}{\lambda-\epsilon}\right)^{2}~{}.$

Since this is true for any $\epsilon>0$ small enough, and
$\mathbb{E}[J_{n}^{2}]\geq(\mathbb{E}J_{n})^{2}$, we conclude that

$\frac{\mathbb{E}[J_{n}^{2}]}{(\mathbb{E}J_{n})^{2}}\to 1$

as $n\to\infty$.

Proposition 11 follows from the fact that $J_{n}\to\infty$ in probability. In
order to see this, we only need to check that the fact that $J_{n}\to\infty$
in probability implies that the number of leaves connected to $T_{n}$ goes to
infinity as well.

Proof. [Proof of Proposition 11] Let us define

$\mathcal{L}_{n}^{*}=\left\\{k\leq 0:\textit{there exists an }m\in
S_{n}\textit{ such that }\max(Z_{m},W_{m})=m-k\right\\}~{}.$

In other words, $\mathcal{L}_{n}^{*}$ is the subset of vertices in
$\mathcal{L}_{n}$ that are connected to some vertex in $S_{n}$ with positive
index through the longest edge (i.e., given by $\max(Z,W)$).

Given $n\geq 1$ and $k\in\mathbb{Z}$, we introduce the random variable

$D_{n,k}=\sum_{m=1}^{n}\mathbbm{1}_{\max(Z_{m},W_{m})=m-k}.$

Note that for any fixed $x>0$,

$\displaystyle\mathbb{P}$
$\displaystyle\left(\left|\mathcal{L}_{n}^{*}\right|<x\right)$ (4.12)
$\displaystyle\leq\mathbb{P}\left(\left[\max_{k\in\mathcal{L}_{n}^{*}}\sum_{m\in
S_{n}}\mathbbm{1}_{\max(Z_{m},W_{m})=m-k}<\frac{\mathbb{E}J_{n}}{2x}\right]\cap\left[\left|\mathcal{L}_{n}^{*}\right|<x\right]\right)$
$\displaystyle\qquad+\mathbb{P}\left(\cup_{k\leq
0}\left[D_{n,k}\geq\frac{\mathbb{E}J_{n}}{2x}\right]\right)~{}.$ (4.13)

Since $J_{n}$ can be written as

$J_{n}=\sum_{k\in\mathcal{L}_{n}^{*}}\sum_{m\in
S_{n}}\mathbbm{1}_{\max(Z_{m},W_{m})=m-k}~{},$

we have that

$\displaystyle\mathbb{P}\left(\left[\max_{k\in\mathcal{L}_{n}^{*}}\sum_{m\in
S_{n}}\mathbbm{1}_{\max(Z_{m},W_{m})=m-k}<\frac{\mathbb{E}J_{n}}{2x}\right]\cap\left[\left|\mathcal{L}_{n}^{*}\right|<x\right]\right)$
$\displaystyle\quad\leq\mathbb{P}\left(J_{n}\leq\frac{\mathbb{E}J_{n}}{2}\right)$
$\displaystyle\quad\leq 4\frac{\mathbb{V}J_{n}}{(\mathbb{E}J_{n})^{2}}\to
0~{}.$ (4.14)

Moreover, for any $k\leq 0$ and $y>0$ , by Chernoff’s bound [7], [5], we have
that

$\displaystyle\mathbb{P}(D_{n,k}>y)$
$\displaystyle=\mathbb{P}\left(\sum_{m=1}^{n}\mathbbm{1}_{\max(Z_{m},W_{m})=m-k}>y\right)$
$\displaystyle\leq\exp\left(y-p_{1-k}^{*}-y\log\left(\frac{y}{p_{1-k}^{*}}\right)\right)$
$\displaystyle\leq\left(\frac{e}{y}\right)^{y}(p_{1-k}^{*})^{y}~{}.$

Let $y_{n}=\mathbb{E}J_{n}/(2x)$ and assume that $n$ is large enough so we
have $y_{n}\geq 2$ and

$\sum_{m=1}^{\infty}(p_{m}^{*})^{y_{n}}\leq\sum_{m=1}^{\infty}(p_{m}^{*})^{2}<\infty\text{
(since }\mathbb{E}\min(Z,W)<\infty\text{ )}~{}.$

Thus, by the union bound,

$\displaystyle\mathbb{P}\left(\cup_{k\leq
0}\left[D_{n,k}\geq\frac{\mathbb{E}J_{n}}{2x}\right]\right)$
$\displaystyle\leq\sum_{k\leq
0}\left(\frac{e}{y_{n}}\right)^{y_{n}}(p_{1-k}^{*})^{y_{n}}$
$\displaystyle\leq\left(\frac{e}{y_{n}}\right)^{y_{n}}\sum_{k=1}^{\infty}(p_{k}^{*})^{2}\to
0~{}.$ (4.15)

By putting (4.13), (4.14), and (4.15) together we have that
$\mathbb{P}\left(\left|\mathcal{L}_{n}^{*}\right|<x\right)\to 0$ as
$n\to\infty$ for every fixed $x>0$, which proves Proposition 11.

Proof. [Proof of Theorem 6] For any $n\geq 1$, define
$Y_{n}=\min\\{m-\min(Z_{m},W_{m}):m\geq n\\}$. A simple union bound gives, for
arbitrary $k$:

$\mathbb{P}\left(Y_{n}\leq k\right)\leq\sum_{m\geq
n}\mathbb{P}\left(\min(Z_{m},W_{m})>m-k\right).$

Since $\mathbb{E}\min(Z,W)<\infty$, the sum above is finite and goes to $0$ as
$n$ goes to infinity. Hence, $Y_{n}\to\infty$ in probability.

Let us fix $n\geq 0$ and apply Corollary 9 to the model obtained by shifting
by $n$ the set of integers so that leaves are indexed by the set $\\{k:k\leq
n\\}$ and the edges are given by the sequences of random variables
$(Z_{k})_{k\geq n+1}$ and $(W_{k})_{k\geq n+1}$. This gives us a random
variable $N_{n}>n$, finite almost surely, such that $N_{n}\in S_{k}$ for all
$k\geq N_{n}$. Let $I_{n}\leq n\\}$ be the root of this tree and note that

$Y_{n}\leq I_{n}\leq n<N_{n}~{}.$

Figure 2: Illustration of the proof of Theorem 6

Since $Y_{n}\to\infty$ in probability, $I_{n}\to\infty$ in probability as
well. Moreover, for all $n\geq 1$, one can choose $N_{n}$ such that $N_{n}-n$
is distributed as $N_{0}$. The fact that all vertices $k\geq N_{n}$ belong to
the tree rooted at $I_{n}$ in this single-choice model implies that $I_{n}\in
T_{k}$ for all $k\geq N_{n}$, and in particular $L_{I_{n}}\leq L_{k}$ for all
$k\geq N_{n}$. From Proposition 11 we know that $L_{n}\to\infty$ in
probability. Hence, $L_{I_{n}}\to\infty$ in probability. Moreover, for any
fixed $m\geq 1$ we have

$\displaystyle\mathbb{P}\left(\cup_{k\geq 2n}\left[L_{k}\leq m\right]\right)$
$\displaystyle\leq\mathbb{P}\left(N_{n}>2n\right)+\mathbb{P}\left(N_{n}\leq
2n,L_{I_{n}}\leq m\right)$
$\displaystyle\leq\mathbb{P}\left(N_{0}>n\right)+\mathbb{P}\left(L_{I_{n}}\leq
m\right)~{}.$

Thus, for any $m\geq 1$, $\mathbb{P}\left(\cup_{k\geq 2n}[L_{k}\leq
m]\right)\to 0$ as $n\to\infty$. By continuity of measure, this implies that
for any $m\geq 1$,

$\mathbb{P}\left(\cap_{n\geq 1}\cup_{k\geq 2n}\left[L_{k}\leq
m\right]\right)=0.$

By the union bound,

$\mathbb{P}\left(\cup_{m\geq 1}\cap_{n\geq 1}\cup_{k\geq 2n}\left[L_{k}\leq
m\right]\right)=0~{},$

which implies that $L_{n}\to\infty$ almost surely.

###  4.2 Heavy tails

In this section we study the heavy-tailed case, that is,
$\mathbb{E}\min(Z,W)=\infty$. From Theorem 3 we already know that $L_{n}$
cannot go to infinity with probability one. Here we show that, in contrast to
this, $L_{n}\to\infty$ in probability.

######  Lemma 14.

For any integers $k\in\mathbb{Z}$ and $n\geq\max(1,k)$,

$\mathbb{P}\left(k\in T_{n}^{Z}\right)\leq r_{n-k}~{}.$

Proof. Clearly, we have $\mathbb{P}\left(k\in T_{n}^{Z}\right)=r_{n-k}$
whenever $k\geq 0$. Moreover, $r_{n}$ satisfies the recursion

$r_{n}=\sum_{i=1}^{n}q_{i}r_{n-i}~{}.$

Thus, for any $k>0$, we have

$\displaystyle\mathbb{P}\left(-k\in T_{n}^{Z}\right)$
$\displaystyle=\sum_{i=1}^{n}\mathbb{P}\left(Z_{i}=i+k\right)\mathbb{P}\left(i\in
T_{n}\right)$ $\displaystyle=\sum_{i=1}^{n}q_{k+i}r_{n-i}$
$\displaystyle=\sum_{i=k+1}^{n+k}q_{i}r_{n+k-i}$
$\displaystyle\leq\sum_{i=1}^{n+k}q_{i}r_{n+k-i}=r_{n+k}~{}.$

Proof. [Proof of Theorem 7] Fix a constant $w>0$ and let $I_{n}^{w}$ denote
the number of intervals of the form $(kw,(k+1)w]$, with $k\in\mathbb{Z}_{\geq
0}$, that are intersected by the chain $T_{n}^{Z}$. Note that, for any $x>0$,
if $I_{n}^{w}<x$ then $T_{n}^{Z}<wx$, thus

$\displaystyle\mathbb{P}\left(I_{n}^{w}<x\right)$
$\displaystyle\leq\mathbb{P}\left(T_{n}^{Z}<wx\right)$
$\displaystyle\leq\mathbb{P}\left(Z_{1}+\dots+Z_{\lfloor
wx\rfloor}>n\right)\to 0~{}.$ (4.16)

Let $\ell\geq 1$ be an arbitrary integer and observe that, if the event
$I_{n}^{w}\geq 2\ell$ occurs, then one can define a random set of vertices
$A_{n}$ such that

  1. 1.

$A_{n}$ is independent of $(W_{k})_{k\geq 1}~{},$

  2. 2.

$A_{n}\subset T_{n}^{Z}~{},$

  3. 3.

$|A_{n}|=\ell~{},$

  4. 4.

$\text{for all }k\neq m\in A_{n}~{},~{}|k-m|\geq w~{}.$

Conditionally on $I_{n}^{w}\geq 2\ell$, we have

$\displaystyle\mathbb{P}\left(\cup_{k\neq m,k\in A_{n}}T_{k}^{W}\cap
T_{m}^{W}\neq\emptyset\right)$ (4.17)
$\displaystyle\quad\leq\mathbb{E}\sum_{\begin{subarray}{c}k,m\in A_{n}\\\
\textit{s.t. }k\neq m\end{subarray}}\mathbbm{1}_{T_{k}^{W}\cap
T_{m}^{W}\neq\emptyset}$
$\displaystyle\quad\leq\mathbb{E}\sum_{\begin{subarray}{c}k,m\in A_{n}\\\
\textit{s.t. }k\neq m\end{subarray}}\mathbb{P}\left(T_{k}^{W}\cap
T_{m}^{W}\neq\emptyset\right)$ $\displaystyle\quad\leq{\ell\choose
2}\max_{\begin{subarray}{c}k,m\leq n\\\ \textit{s.t. }|k-m|\geq
w\end{subarray}}\mathbb{P}\left(T_{k}^{W}\cap T_{m}^{W}\neq\emptyset\right)$
(4.18)

by using the first moment method and the independence of $A_{n}$ with respect
to $(W_{k})_{k\geq 1}$. Let $k<m$ be a pair of integers such that $|k-m|\geq
w$ and observe that

$\mathbb{P}\left(T_{k}^{W}\cap
T_{m}^{W}\neq\emptyset\right)=\mathbb{P}\left(T_{k}^{W}\cap
T_{m}^{Z}\neq\emptyset\right)~{}.$

Thus, the union bound, Lemma 14 and the Cauchy-Schwarz inequality yield

$\displaystyle\mathbb{P}\left(T_{k}^{W}\cap T_{m}^{W}\neq\emptyset\right)$
$\displaystyle\leq\sum_{i=-\infty}^{k}\mathbb{P}\left(i\in
T_{k}^{W}\right)\mathbb{P}\left(i\in T_{m}^{Z}\right)$
$\displaystyle\leq\sum_{i=-\infty}^{k}r_{k-i}r_{m-i}$
$\displaystyle\leq\sqrt{\sum_{i=0}^{\infty}r_{i}^{2}}\times\sqrt{\sum_{i=m-k}^{\infty}r_{i}^{2}}.$
(4.19)

From (4.18) and (4.19), it follows that

$\mathbb{P}\left(\cup_{k\neq m,k\in A_{n}}T_{k}^{W}\cap
T_{m}^{W}\neq\emptyset\right)\leq{\ell\choose
2}\sqrt{\sum_{i=0}^{\infty}r_{i}^{2}}\times\sqrt{\sum_{i=w}^{\infty}r_{i}^{2}}.$
(4.20)

Fix $\epsilon>0$. From (4.20) we know that we can choose $w$ big enough so we
have for $n\geq 1$,

$\mathbb{P}\left(\cup_{k\neq m,k\in A_{n}}T_{k}^{W}\cap
T_{m}^{W}\neq\emptyset\right)\leq\epsilon.$ (4.21)

Finally, observe that if $L_{n}<\ell$ and $I_{n}^{w}\geq 2\ell$, then there
have to be at least two distinct vertices $k,m$ in $A_{n}$ such that the
chains $T_{k}^{W}$ and $T_{m}^{W}$ meet each other: otherwise, each chain
$T_{k}^{W}$ with $k\in A_{n}$ would lead to a distinct leaf in $T_{n}$,
contradicting the event $L_{n}<\ell$. Thus, by (4.20) we have

$\mathbb{P}\left(L_{n}<\ell\right)\leq\mathbb{P}\left(I_{n}^{w}<2\ell\right)+\epsilon~{}.$

From (4.16) it follows that for any $\epsilon>0$ and any integer $\ell\geq 1$

$\limsup_{n\to\infty}\mathbb{P}\left(L_{n}<\ell\right)\leq\epsilon~{},$

which concludes the proof of Theorem 7.

##  5 Conclusion

We introduced and studied a simple mathematical model for recommendation
systems based on giving each user two random choices, which include a mixture
of past choices and untried options. In this setup, we identify three regimes
based on the tail behavior of the sizes of the jumps in the past. A natural
generalization of the model allows $k>2$ choices, left for further study. We
anticipate that in that case there are $k+1$ regimes, but even the case $k=3$
seems interesting. The eagle-eyed reader must have noticed that the bottom
right corner of the table summarizing the results is left unfilled. Indeed,
the question of the tightness of the rightmost leaf in the extremely heavy-
tailed case remains an open problem.

## References

  * Baccelli et al., [2022] Baccelli, F., Haji-Mirsadeghi, M.-O., and Khaniha, S. (2022).  Coupling from the past for the null recurrent markov chain.  arXiv preprint arXiv:2203.13585.
  * Baccelli et al., [2018] Baccelli, F., Haji-Mirsadeghi, M.-O., and Khezeli, A. (2018).  Eternal family trees and dynamics on unimodular random graphs.  Unimodularity in randomly generated graphs, 719:85–127.
  * Baccelli and Sodre, [2019] Baccelli, F. and Sodre, A. (2019).  Renewal processes, population dynamics, and unimodular trees.  Journal of Applied Probability, 56(2):339–357.
  * Blath et al., [2013] Blath, J., González Casanova, A., Kurt, N., and Spano, D. (2013).  The ancestral process of long-range seed bank models.  Journal of Applied Probability, 50(3):741–759.
  * Boucheron et al., [2013] Boucheron, S., Lugosi, G., and Massart, P. (2013).  Concentration Inequalities: A Nonasymptotic Theory of Independence.  Oxford University Press, Oxford.
  * Broutin et al., [2024] Broutin, N., Devroye, L., Lugosi, G., and Oliveira, R. I. (2024).  Subtractive random forests.  ALEA Latin American Journal of Probability and Mathematical Statistics, 21:575–591.
  * Chernoff, [1952] Chernoff, H. (1952).  A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations.  Annals of Mathematical Statistics, 23(4):493–507.
  * Chierichetti et al., [2020] Chierichetti, F., Kumar, R., and Tomkins, A. (2020).  Asymptotic behavior of sequence models.  In Proceedings of The Web Conference 2020, pages 2824–2830.
  * Erdős et al., [1949] Erdős, P., Feller, W., and Pollard, H. (1949).  A theorem on power series.  Bulletin of the American Mathematical Society, 55:201–204.
  * Hammond and Sheffield, [2013] Hammond, A. and Sheffield, S. (2013).  Power law pólya’s urn and fractional brownian motion.  Probability Theory and Related Fields, 157(3-4):691–719.
  * Ibragimov and Linnik, [1971] Ibragimov, I. and Linnik, Y. (1971).  Independent and Stationary Sequences of Random Variables.  Wolters-Noordhoff Publishing, Groningen.
  * Igelbrink and Wakolbinger, [2022] Igelbrink, J. L. and Wakolbinger, A. (2022).  Asymptotic gaussianity via coalescence probabilites in the Hammond-Sheffield urn.  arXiv e-prints, pages arXiv–2201.
  * Malevich, [2015] Malevich, N. (2015).  Approximations and Asymptotic Expansions for Sums of Heavy-tailed Random Variables.
  * Zhang et al., [2019] Zhang, S., Yao, L., Sun, A., and Tay, Y. (2019).  Deep learning based recommender system: A survey and new perspectives.  ACM Computing Surveys, 52(1):1–38.
  * Zolotarev, [1986] Zolotarev, V. (1986).  One-dimensional Stable Distributions.  American Mathematical Society, Providence.