On a random model of forgetting

Noga Alon Department of Mathematics, Princeton University, Princeton, NJ 08544, USA and Schools of Mathematics and Computer Science, Tel Aviv University, Tel Aviv, Israel. Email: [email protected]. Research supported in part by NSF grant DMS-1855464, ISF grant 281/17, BSF grant 2018267 and the Simons Foundation. Dor Elboim Department of Mathematics, Princeton University, Princeton, NJ 08544, USA. Email: [email protected]. Allan Sly Department of Mathematics, Princeton University, Princeton, NJ 08544, USA. Email: [email protected]. Research supported in part by NSF grant DMS-1855527, a Simons Investigator grant and a MacArthur Fellowship.

Abstract

Georgiou, Katkov and Tsodyks considered the following random process. Let $x_{1},x_{2},\ldots$ be an infinite sequence of independent, identically distributed, uniform random points in $[0,1]$ . Starting with $S=\{0\}$ , the elements $x_{k}$ join $S$ one by one, in order. When an entering element is larger than the current minimum element of $S$ , this minimum leaves $S$ . Let $S(1,n)$ denote the content of $S$ after the first $n$ elements $x_{k}$ join. Simulations suggest that the size $|S(1,n)|$ of $S$ at time $n$ is typically close to $n/e$ . Here we first give a rigorous proof that this is indeed the case, and that in fact the symmetric difference of $S(1,n)$ and the set $\{x_{k}\geq 1-1/e:1\leq k\leq n\}$ is of size at most $\tilde{O}(\sqrt{n})$ with high probability. Our main result is a more accurate description of the process implying, in particular, that as $n$ tends to infinity $n^{-1/2}\big{(}|S(1,n)|-n/e\big{)}$ converges to a normal random variable with variance $3e^{-2}-e^{-1}$ . We further show that the dynamics of the symmetric difference of $S(1,n)$ and the set $\{x_{k}\geq 1-1/e:1\leq k\leq n\}$ converges with proper scaling to a three dimensional Bessel process.

1 Introduction

The following random process, which we denote by $P$ , is considered by Georgiou, Katkov and Tsodyks in [8] motivated by the study of a possible simplified model for the process of forgetting. Let $x_{1},x_{2},\ldots$ be independent, identically distributed, uniform random points in $[0,1]$ . Starting with the set $S(1,0)=\{0\}=\{x_{0}\}$ the elements $x_{k}$ enter the set one by one, in order, and if when $x_{k}$ enters $S(1,k-1)$ it is larger than the minimum member $\min(S(1,k-1))$ of $S(1,k-1)$ , this minimum leaves it. Let us note that in this process, the fact that $x_{i}$ are uniformly distributed is not crucial. Indeed, it only matters that the ordering of the arriving elements is a uniform random ordering and therefore the uniform distribution can be replaced with any other non-atomic distribution.

The set $S(1,n)$ will be called the memory. We let $P(n)$ be the finite process that stops at time $n$ . Simulations indicate that the expected size of the memory $S(1,n)$ at time $n$ is $(1+o(1))n/e$ where $e$ is the basis of the natural logarithm, and that in fact with high probability (that is, with probability approaching $1$ as $n$ tends to infinity) the size at the end is very close to the expectation. Tsodyks [12] suggested the problem of proving this behavior rigorously. Our first result here is a proof that this is indeed the case, as stated in the following theorem. Recall that for two function $f,g$ the notation $f(n)=\tilde{O}(g(n))$ means that for all large $n$ one has $f(n)\leq C(\log n)^{C}g(n)$ .

Theorem 1.

In the process $P(n)$ the size of the memory $S(1,n)$ at time $n$ is, with high probability, $(1+o(1))n/e$ . Moreover, with high probability, the symmetric difference between the final content of the memory and the set $\{x_{k}\geq 1-1/e:k\leq n\}$ is of size at most $\tilde{O}(\sqrt{n})$ .

A result similar to Theorem 1 (without any quantitative estimates) has been proved independently by Friedgut and Kozma [7] using different ideas.

Refer to caption — Figure 1: Four independent samples of the process obtained from a computer simulation. The blue points are the content of the memory set after $n=200$ steps in the first two pictures and after $n=1000$ steps in the last two. In the main theorems we analyze the evolution of the memory set and determine how close it is to the set of uniform variables that are larger than $1-1/e$ .

Our main result provides a more accurate description of the process $P$ as stated in the following theorems. To state the next theorem we let $S(1,n)$ be the content of the list at time $n$ and let $s(1,n):=|S(1,n)|$ be the size of the list.

Theorem 2.

Let $B_{t}$ be a standard Brownian motion. We have that

\Big{\{}\frac{s(1,tn)-tn/e}{\sqrt{n}}\Big{\}}_{t>0}\overset{d}{\longrightarrow}\Big{\{}\frac{\sqrt{3-e}}{e}\cdot B_{t}\Big{\}}_{t>0},\quad n\to\infty.

Our next theorem describes the final set of points obtained in this process. In particular, it strengthens the estimate in Theorem 1 by removing the poly-logarithmic factor in the bound on the size of the symmetric difference between $S(1,n)$ and the set $\{x_{k}\geq z_{0}:k\leq n\}$ where $z_{0}:=1-1/e$ . The theorem also provides the limiting distribution of this difference. To state the theorem we define

L_{n}:=\big{|}S(1,n)\setminus\big{\{}x_{k}\geq z_{0}:k\leq n\big{\}}\big{|}\quad\text{and}\quad R_{n}:=\big{|}\big{\{}x_{k}\geq z_{0}:k\leq n\big{\}}\setminus S(1,n)\big{|}.

Theorem 3.

As $n$ tends to infinity we have

\Big{\{}\Big{(}\frac{L_{tn}}{\sqrt{n}}\,,\,\frac{R_{tn}}{\sqrt{n}}\Big{)}\Big{\}}_{t>0}\overset{d}{\longrightarrow}\big{\{}\sqrt{2}e^{-1}\big{(}M_{t}-B_{t},M_{t}\big{)}\big{\}}_{t>0},

where $B_{t}$ is a standard Brownian motion and $M_{t}:=\sup_{s\leq t}B_{s}$ is the maximum process. In particular, the evolution of the size of the symmetric difference is given by

\Big{\{}\frac{L_{tn}+R_{tn}}{\sqrt{n}}\Big{\}}_{t>0}\overset{d}{\longrightarrow}\big{\{}\sqrt{2}e^{-1}X_{t}\big{\}}_{t>0},

(1)

where $X_{t}$ is a three dimensional Bessel process. It follows that the differences and the symmetric difference satisfy the following limit laws

\frac{L_{n}}{\sqrt{n}}\overset{d}{\longrightarrow}\sqrt{2}e^{-1}|N|,\quad\frac{R_{n}}{\sqrt{n}}\overset{d}{\longrightarrow}\sqrt{2}e^{-1}|N|\quad\text{and}\quad\frac{L_{n}+R_{n}}{\sqrt{n}}\overset{d}{\longrightarrow}X,

(2)

where $N$ is a standard normal random variable and $X$ has the density

f(x)=\frac{e^{3}x^{2}}{2\sqrt{\pi}}e^{-e^{2}x^{2}/4}\,\mathds{1}\{x>0\}.

(3)

In fact, in the following theorem, we give a complete description of the evolution of the process in a $n^{-1/2}$ neighbourhood around the critical point $z_{0}=1-1/e$ . For $0<z<1$ and $n\geq 1$ we let $S(z,n):=S(1,n)\cap[0,z]$ be the set of elements in the list that are smaller than $z$ at time $n$ and let $s(z,n):=|S(z,n)|$ .

Theorem 4.

As $n$ tends to infinity we have

\bigg{\{}\frac{s\big{(}z_{0}+yn^{-1/2},tn\big{)}}{\sqrt{n}}\bigg{\}}_{\begin{subarray}{c}t>0\\ y\in\mathbb{R}\end{subarray}}\overset{d}{\longrightarrow}\Big{\{}\sqrt{2}e^{-1}B_{t}+yt-\inf_{x\leq t}\big{(}\sqrt{2}e^{-1}B_{x}+yx\big{)}\Big{\}}_{\begin{subarray}{c}t>0\\ y\in\mathbb{R}\end{subarray}}.

Remark 1.1.

The convergence in Theorems 2, 3 and 4 is a weak convergence in the relevant Skorohod spaces. It is equivalent to the following statements. In Theorem 2, we define the random function $f_{n}(t):=n^{-1/2}\big{(}s(1,\lfloor tn\rfloor)-tn/e\big{)}$ . Then, for all $M>0$ there exists a coupling of the sequence $f_{n}$ and a Brownian motion $B_{t}$ such that almost surely

\sup_{t\leq M}\Big{|}f_{n}(t)-\frac{\sqrt{3-e}}{e}\cdot B_{t}\Big{|}\to 0,\quad n\to\infty.

In Theorem 4, we define $f_{n}(t,y):=n^{-1/2}s\big{(}z_{0}+yn^{-1/2},\lfloor tn\rfloor\big{)}$ . Then, for all $M>0$ , there exists a coupling such that almost surely

\sup_{t,|y|\leq M}\Big{|}f_{n}(t,y)-\Big{(}\sqrt{2}e^{-1}B_{t}+yt-\inf_{x\leq t}\big{(}\sqrt{2}e^{-1}B_{x}+yx\big{)}\Big{)}\Big{|}\to 0,\quad n\to\infty.

The convergence in Theorem 3 is similar.

The rest of the paper is organized as follows. In the next section we describe the proof of Theorem 1. It is based on subadditivity and martingale concentration applied to the natural Doob martingale associated with the process. The concentration part resembles the basic approach in [1]. In Section 3 we prove Theorem 2, Theorem 3 and Theorem 4. The main idea in the proofs is to consider the process

W(z,n):=\sum_{x\in S(z,n)}\frac{1}{1-x}

(4)

which we call “the branching martingale.” When $S(z,n)$ is not empty, this process has a zero drift when $z=1-1/e$ , a negative drift when $z<1-1/e$ and a positive drift when $z>1-1/e$ . When $S(z,n)$ is empty, $W$ can only increase in all cases. The intuition behind this magical formula comes from a certain multi-type branching process. In a multi-type branching process, there are individuals of $k$ different types. For each type $i$ , an offspring distribution $\mu_{i}$ on $\mathbb{N}^{k}$ is given. In each step, every individual of type $i$ gives birth to a random number of individuals of each type according to the distribution $\mu_{i}$ . Recall that a single-type branching process is critical when the expected number of offspring is $1$ and in this case the size of the generation is a martingale. Similarly, for a multi-type branching process one defines the expectation matrix $M$ where $M_{i,j}:=\int x_{j}d\mu_{i}(x)$ is the expected number of children of type $j$ of an individual of type $i$ . The process is then critical when the maximal eigenvalue of $M$ is one and in this case the process

N_{t}:=u\cdot Z(t)

(5)

is a martingale where $u$ is the eigenvector of $M$ with eigenvalue $1$ and $Z(t)=(Z_{1}(t),\dots,Z_{k}(t))$ is the number of individuals of each type at time $t$ . For more background on multi-type branching processes see chapters V and VI in [3].

We think of our process as a multi-type branching process in which the type space is continuous. Given $0<z<1$ , we define a branching process with the type space $[0,z]$ . In this branching, the offspring distribution of an individual of type $x<z$ is given as follows. With probability $(1-z)$ , the individual has $0$ offspring, with probability $(z-x)$ it has one offspring of type that is uniformly distributed in $[x,z]$ and with probability $x$ it has two offspring, one of type $x$ and one of type that is uniformly distributed in $[0,x]$ .

We now explain the connection between this branching and our process. Suppose we start the process with a list $S$ such that the minimum of $S$ is $z$ , and we want to study the time until $z$ is removed from the list. We think of each point $x<z$ that is added to the list as an individual of type $x$ in the branching process and ignore points that fall to the right of $z$ . We claim that the number of individuals that were born before the extinction of the branching described above is exactly the time until $z$ is removed in the minimum process. Indeed, instead of exposing the branching in the usual way according to the generations, we expose the offspring of an individual when it becomes the current minimum of the list. When the element $x$ becomes the minimum, with probability $1-z$ it is removed and $S(z,n)$ decreases by $1$ , with probability $z-x$ we remove $x$ from $S(z,n)$ and replace it with a uniform element in $[x,z]$ and with probability $x$ we keep $x$ and add another element to $S(z,n)$ that is uniformly distributed in $[0,x]$ .

The branching described above can be shown to be subcritical when $z<z_{0}$ , critical when $z=z_{0}$ and supercritical when $z>z_{0}$ , where $z_{0}=1-1/e$ . Now, in the critical case we look for a martingale of the form (5) which translates in the continuous case to the process

N_{n}:=\sum_{x\in S(z_{0},n)}f(x)

(6)

where $f$ is an eigenfunction of the expectation operator with eigenvalue $1$ . In order to find $f$ we let $m_{n}<z_{0}$ be the minimum of the list at time $n$ and write

\mathbb{E}\big{[}N_{n+1}-N_{n}\ |\ \mathcal{F}_{n}\big{]}=\int_{0}^{z_{0}}f(x)dx-(1-m_{n})f(m_{n}).

(7)

The last expression is zero only when $f(x)=1/(1-x)$ which leads to (4).

2 Proof of Theorem 1

For any integer $0\leq\ell\leq n$ and any $x\in[0,1]$ let $S(x,\ell)$ denote the set of numbers that are in $S$ and lie in $[0,x]$ after the first $\ell$ steps, that is, after $x_{1},x_{2},\ldots,x_{\ell}$ have been inserted. Put $s(x,\ell)=|S(x,\ell)|$ . Therefore $s(1,n)$ is the size of $S$ at the end of the process. Let $m_{i}$ denote the value $\min(S(1,i-1))$ just before $x_{i}$ enters it. Thus $m_{1}=0$ and $m_{2}=x_{1}$ .

We start with the following lemma showing that the expected value of the size of $S$ at the end is linear in $n$ .

Lemma 2.1.

For all $n\geq 1$ we have

\mathbb{E}[S(1,n)]\geq n/4

Proof: For each $1\leq i\leq n$ let $X_{i}$ be the indicator random variable whose value is $1$ if $x_{i}<m_{i}$ (and $0$ otherwise). Let $Y_{i}$ be the indicator random variable with value $1$ if $x_{i}>m_{i}$ and $m_{i}\leq 1/2$ . Note that $\sum_{i=1}^{n}Y_{i}$ is at most the number of $x_{i}$ , $0\leq i<n$ whose values are in $[0,1/2]$ . Indeed, whenever $Y_{i}=1$ an element $x_{j}\leq 1/2$ with $j<i$ leaves the memory set. The expected value of this number is $1+(n-1)/2$ , as $x_{0}=0<1/2$ and any other $x_{i}$ lies in $[0,1/2]$ with probability $1/2$ . Therefore the expectation of $\sum_{i=1}^{n}Y_{i}$ is at most $(n+1)/2$ . We claim that for every $1\leq i\leq n$ , the expected value of $2X_{i}+Y_{i}$ is at least $1$ . Indeed, if $m_{i}>1/2$ the expected value of $2X_{i}$ is $2m_{i}>1$ (and the expectation of $Y_{i}$ is $0$ ). If $m_{i}\leq 1/2$ , the expected value of $2X_{i}$ is $2m_{i}$ , and that of $Y_{i}$ is $1-m_{i}$ . By linearity of expectation in this case the expected value of $2X_{i}+Y_{i}$ is $2m_{i}+(1-m_{i})=1+m_{i}\geq 1$ . This proves the claim. Using again linearity of expectation we conclude that the expectation of $\sum_{i=1}^{n}(2X_{i}+Y_{i})$ is at least $n$ . Since the expectation of $\sum_{i=1}^{n}Y_{i}$ is at most $(n+1)/2$ it follows that the expectation of $\sum_{i=1}^{n}X_{i}$ is at least $(n-1)/4$ . Note that the size of $S$ at the end is exactly $1+\sum_{i=1}^{n}X_{i}$ , as it has size $1$ at the beginning, its size never decreases, and it increases by $1$ in step $i$ if and only if $X_{i}=1$ . The assertion of the lemma follows. $\Box$

We also need the following simple deterministic statement.

Lemma 2.2.

Let $T_{1},T_{2}$ be arbitrary finite disjoint subsets of $[0,1]$ . Let $P=P(n)$ be the process above with the sequence $x_{1},x_{2},\ldots,x_{n}\in[0,1]$ starting with $S=T_{1}$ . Let $P^{\prime}$ denote the process with the same sequence $x_{i}$ , starting with $S=T_{1}\cup T_{2}$ . For $x\in[0,1]$ and $0\leq\ell\leq n$ , let $S(x,\ell)$ denote the set of numbers in $S$ that lie in $[0,x]$ after the first $\ell$ steps in the process $P$ . Similarly, let $S^{\prime}(x,\ell)$ denote the set of numbers in $S$ that lie in $[0,x]$ after the first $\ell$ steps in the process $P^{\prime}$ . Then $S^{\prime}(x,\ell)$ contains $S(x,\ell)$ and moreover

|S^{\prime}(x,\ell)|-|S(x,\ell)|\leq|T_{2}|.

Proof: We first describe the proof for $x=1$ . Apply induction on $\ell$ . The result is trivial for $\ell=0$ . Assuming it holds for $\ell$ consider step number $\ell+1$ in the two processes, when $x=x_{\ell+1}$ enters the memory $S$ . If $x$ is smaller than the minimum of both sets $S(1,\ell)$ and $S^{\prime}(1,\ell)$ then it joins the memory in both processes and the desired properties clearly hold. If it is larger than the minimum in $S(1,\ell)$ then it is also larger than the minimum in $S^{\prime}(1,\ell)$ , it joins the memory in both cases, and both minima leave. It is easy to check that the desired properties hold in this case too. Finally, if $x$ is smaller than the minimum in $S(1,\ell)$ but larger than the minimum in $S^{\prime}(1,\ell)$ then $x$ joins both memories and the minimum of $S^{\prime}(1,\ell)$ leaves. In this case $S^{\prime}$ still contains $S$ , but the difference between their sizes decreases by $1$ . This also satisfies the desired properties, completing the proof of the induction step for $x=1$ . The statement for general $x$ follows from the statement for $x=1$ $\Box$

The above lemma has two useful consequences which are stated and proved in what follows.

Corollary 2.3.

For each fixed $x$ the function $f(\ell)=\mathbb{E}[s(x,\ell)]$ is subadditive.

Proof: We have to show that for every $p,q$ , $f(p+q)\leq f(p)+f(q)$ . Consider the process $P$ with the points $x_{1},x_{2},\ldots x_{p},y_{1},y_{2},\ldots,y_{q}$ . The process starts with the first $p$ steps, let $T$ be the content of the memory $S$ after these $p$ steps. We can now compare the process $P$ with the points $y_{1},y_{2},\ldots y_{q}$ starting with the empty set $S$ (which is identical to starting with $S=\{0\}$ ), and the process $P^{\prime}$ with the same points $y_{i}$ starting with $S=T$ . By Lemma 2.2, throughout the two processes, the number of elements in the process $P^{\prime}$ that lie in $[0,x]$ is always at most the number of elements in $P$ that lie in $[0,x]$ , plus $|T|$ . Taking expectations in both sides of this inequality implies the desired subadditivity. $\Box$

Corollary 2.4.

For each $x\in[0,1]$ and any integer $\ell$ , the random variable $s(x,\ell)$ is $2$ -Lipschitz, that is, its value changes by at most $2$ if we change the value of a single $x_{i}$ . Therefore for any $\lambda>0$ the probability that it deviates from its expectation by more than $\lambda\sqrt{\ell}$ is at most $2e^{-\lambda^{2}/8}.$

Proof: The effect that changing the value of $x_{i}$ to $x^{\prime}_{i}$ has on the content of $S$ after step $i$ is a change of $x_{i}$ to $x^{\prime}_{i}$ in $S$ , and possibly a removal of the minimum element of $S$ before step $i$ in one scenario and not in the other. In any case this means that one process can be converted to the other by adding an element to the memory and then by removing one or two elements from it. By Lemma 2.2 for each fixed choice of all other $x_{j}$ the first modification can only increase the value of $s(x,\ell)$ , and can increase it by at most $1$ . The second modification can then only decrease this value, decreasing it by at most $2$ . This implies that the value changes by at most $2$ , that is, the function is $2$ -Lipschitz. The concentration inequality thus follows from Azuma’s Martingale Inequality, c.f. [4, Theorem 1.1]. $\Box$

Proof of Theorem 1: The symmetric difference of the sets $S(1,n)$ and $S(1,n+1)$ is of size at most two and therefore we may assume that $n$ is even throughout the proof of the theorem. We may also assume that $n$ is sufficiently large. Without any attempt to optimize the absolute constants, let $y\in[0,1]$ be a real number so that the expected value $\mathbb{E}[s(y,n/2)]$ of the number of elements in the memory $S$ that lie in $[0,y]$ at the end of the process with the first $n/2$ elements $x_{i}$ is $5\sqrt{n\log n}$ . Since $\mathbb{E}[s(0,n/2)]=0$ , $\mathbb{E}[s(1,n/2)]>n/8$ by Lemma 2.1, and the function $f(y)=\mathbb{E}[s(y,n/2)]$ is continuous, there is such a value (provided $n/8\geq 5\sqrt{n\log n}$ .) We claim that the expected number of indices $i$ so that $n/2<i\leq n$ and the minimum in the memory satisfies $m_{i}>y$ , is smaller than $1/n^{2}$ . Indeed, it follows from Lemma 2.2 that the function $\mathbb{E}[s(y,m)]$ is monotone increasing in $m$ . Thus, for every $\ell\in(n/2,n]$ , $\mathbb{E}[s(y,\ell-1)]\geq 5\sqrt{n\log n}.$ By Corollary 2.4 (and using that $\{m_{\ell}>y\}=\{s(y,\ell-1)=0\}$ ) this implies that for every fixed $\ell$ in this range the probability that $m_{\ell}$ is larger than $y$ is at most $2e^{-25n\log n/(8\ell)}<1/n^{3}$ . Therefore, by linearity of expectation, the expected number of steps $i\in(n/2,n]$ in which $m_{i}>y$ is smaller than $1/n^{2}$ , proving the claim.

By this claim, the expected number of steps $i\in(n/2,n]$ so that $m_{i}>y$ and $x_{i}>m_{i}$ is, of course, also at most $1/n^{2}$ .

On the other hand, by the subadditivity established in Corollary 2.3, the expected value of $s(y,n)$ is at most $10\sqrt{n\log n}$ .

We next show that $y$ deviates from $1-1/e$ by $O(\frac{\sqrt{\log n}}{\sqrt{n}}).$ To this end we compute the expectation of the random variable $Y$ counting the number of indices $i\in(n/2,n]$ for which $x_{i}\leq y$ and $x_{i}$ is being removed at a step in which the arriving element exceeds $y$ . By definition $Y=\sum_{n/2<i\leq n}X_{i}$ where $X_{i}$ denotes the indicator random variable whose value is $1$ if $x_{i}\leq y$ and $x_{i}$ is being removed at a step in which the arriving element is larger than $y$ .

For all $n/2<i\leq n$ and $i<j\leq n$ , let $\mathcal{A}_{i,j}$ be the event that $x_{i}$ is removed by $x_{j}$ . Conditioning on $x_{i}$ and on the event $\mathcal{A}_{i,j}$ , the random variable $x_{j}$ is uniformly distributed on the interval $[x_{i},1]$ and therefore on the event $\{x_{i}\leq y\}$ we have

\mathbb{P}\big{(}x_{j}\geq y\mid x_{i},\mathcal{A}_{i,j}\big{)}=\frac{1-y}{1-x_{i}}.

(8)

Thus, we obtain

\begin{split}\mathbb{E}[X_{i}]&=\mathbb{E}\bigg{[}\mathds{1}\{x_{i}\leq y\}\mathbb{P}\bigg{(}\bigcup_{j=i+1}^{n}\mathcal{A}_{i,j}\cap\{x_{j}\geq y\}\mid x_{i}\bigg{)}\bigg{]}\\ &=\mathbb{E}\bigg{[}\mathds{1}\{x_{i}\leq y\}\sum_{j=i+1}^{n}\mathbb{P}\big{(}\mathcal{A}_{i,j}\mid x_{i}\big{)}\mathbb{P}\big{(}x_{j}\geq y\mid x_{i},\mathcal{A}_{i,j}\big{)}\bigg{]}\\ &=\mathbb{E}\Big{[}\mathds{1}\{x_{i}\leq y\}\frac{1-y}{1-x_{i}}\cdot\mathbb{P}\big{(}x_{i}\text{ is removed before time $n$}\mid x_{i}\big{)}\Big{]}\end{split}

The expected number of $i\in(n/2,n]$ for which $x_{i}\leq y$ is not removed is at most $10\sqrt{n\log n}$ , as all these elements belong to $S(y,n)$ . Thus,

\begin{split}\mathbb{E}[Y]&=\sum_{n/2<i\leq n}\mathbb{E}[X_{i}]=O(\sqrt{n\log n})+\sum_{n/2<i\leq n}\mathbb{E}\Big{[}\mathds{1}\{x_{i}\leq y\}\frac{1-y}{1-x_{i}}\Big{]}\\ &=O(\sqrt{n\log n})+\frac{n}{2}\int_{0}^{y}\frac{1-y}{1-x}dx=O(\sqrt{n\log n})+\frac{n}{2}(1-y)\log\Big{(}\frac{1}{1-y}\Big{)},\end{split}

where in the third equality we used that $x_{i}$ is uniform in $[0,1]$ .

On the other hand, the expected number of steps $j\in(n/2,n]$ in which the element $x_{j}>y$ arrived and caused the removal of an element $x_{i}=m_{j}<y$ for some $i\in(n/2,n]$ is $(n/2)(1-y)-O(\sqrt{n\log n})$ . Indeed, the expected number of $j\in(n/2,n]$ with $x_{j}>y$ is $(n/2)(1-y)$ , and almost each such $x_{j}$ removes an element $m_{j}$ , where the expected number of such $m_{j}$ that exceed $y$ is $O(1/n^{2})$ . In some of these steps the removed element may be $x_{i}$ for some $i\leq n/2$ , but the expected number of such indices $i$ is at most the expectation of $s(y,n/2)$ which is only $O(\sqrt{n\log n})$ .

It follows that

\frac{n}{2}(1-y)\log\Big{(}\frac{1}{1-y}\Big{)}=\frac{n}{2}(1-y)+O(\sqrt{n\log n}).

Dividing by $n(1-y)/2$ (noting that $1-y$ is bounded away from $0$ ) we conclude that $y=1-1/e+O(\frac{\sqrt{\log n}}{\sqrt{n}}).$

Since the expected number of elements $x_{i}$ for $i\in(n/2,n]$ that fall in the interval

\Big{[}y-O\Big{(}\frac{\sqrt{\log n}}{\sqrt{n}}\Big{)},y+O\Big{(}\frac{\sqrt{\log n}}{\sqrt{n}}\Big{)}\Big{]}

is $O(\sqrt{n\log n})$ we conclude that the expected number of steps $i\in(n/2,n]$ satisfying $x_{i}>1-1/e$ that leave the memory during the process is $O(\sqrt{n\log n})$ . In addition, since $\mathbb{E}[s(y,n)]\leq 10\sqrt{n\log n}$ it follows that the expected number of steps $i\in(n/2,n]$ so that $x_{i}<1-1/e$ and $x_{i}$ stays in the memory at the end of the process is also at most $O(\sqrt{n\log n})$ .

By splitting the set of all $n$ steps into dyadic intervals we conclude that the expected size of the symmetric difference between the final content of the memory and the set of all elements $x_{i}$ larger than $z=1-1/e$ is $O(\sqrt{n\log n})$ . This clearly also implies that the expected value of $s(1,n)$ deviates from $n/e$ by $O(\sqrt{n\log n})$ . Finally note that by Corollary 2.4, for any positive $\lambda$ the probability that either $s(1,n)$ or the above mentioned symmetric difference deviate from their expectations by more than $\lambda\sqrt{n}$ is at most $O(e^{-\Omega(\lambda^{2})})$ . $\Box$

3 The branching martingale

In this section we prove Theorem 2, Theorem 3 and Theorem 4. The main idea in the proof is the following martingale which we call the branching martingale.

Let $0<z<1$ and let $z_{0}:=1-1/e$ be the critical point. Recall that $S(z,n)$ is the set of elements in the list at time $n$ that are smaller than $z$ . Define the processes

W(z,n):=\sum_{x\in S(z,n)}\frac{1}{1-x}\quad\quad Z(z,n):=\sum_{k=1}^{n}W(z,k)\cdot\mathds{1}\big{\{}W(z,k-1)=0\big{\}}

and let $X(z,n):=W(z,n)-Z(z,n)$ . The following claim is the fundamental reason to consider these processes.

Proposition 3.1.

On the event $\{W(z,n)\neq 0\}$ we have that

\mathbb{E}\big{[}W(z,n+1)-W(z,n)\,|\,\mathcal{F}_{n}\big{]}=-\log(1-z)-1

and therefore $X(z_{0},n)$ is a martingale. Moreover, $Z$ is roughly minus the minimum process of $X$ . More precisely, we have almost surely

0\leq Z(z,n)+\min_{k\leq n}X(z,k)\leq\frac{1}{1-z}.

(9)

Remark 3.2.

Proposition 3.1 essentially explains all the results in this paper. See Theorem 4 for example. Since $X(z_{0},n)$ is a martingale it is a Brownian motion in the limit and $Z(z_{0},n)$ is minus the minimum process of this Brownian motion. Thus, $W(z_{0},n)$ , which is closely related to the number of elements in the list that are smaller than $z_{0}$ is the difference between the Brownian motion and its minimum.

Proof of Proposition 3.1.

On the event $\{W(z,n)\neq 0\}$ we have

W(z,n+1)-W(z,n)=\mathds{1}\{x_{n+1}\leq z\}\frac{1}{1-x_{n+1}}-\mathds{1}\{x_{n+1}\geq m_{n}\}\frac{1}{1-m_{n}},

(10)

where $m_{n}$ is the minimum of the list at time $n$ and $x_{n+1}$ is the uniform variable that arrives at time $n+1$ in the process. Thus, on the event $\{W(z,n)\neq 0\}$ we have

\mathbb{E}\big{[}W(z,n+1)-W(z,n)\ \big{|}\ \mathcal{F}_{n}\big{]}=\int_{0}^{z}\frac{1}{1-x}dx-\int_{m_{n}}^{1}\frac{1}{1-m_{m}}=-\log(1-z)-1.

It follows that $X(z_{0},n)$ is a martingale. Indeed on the event $\{W(z,n)\neq 0\}$ we have

\mathbb{E}\big{[}X(z,n+1)-X(z,n)\ \big{|}\ \mathcal{F}_{n}\big{]}=\mathbb{E}\big{[}W(z,n+1)-W(z,n)\ \big{|}\ \mathcal{F}_{n}\big{]}=-\log(1-z_{0})-1=0.

Whereas on the event $\{W(z,n)=0\}$ we have that $X(n+1,z)=X(n,z)$ .

We next turn to prove the second statement of the proposition. For all $k\leq n$ we have that

X(z,k)=W(z,k)-Z(z,k)\geq-Z(z,k)\geq-Z(z,n),

and therefore $\min_{k\leq n}X(z,k)\geq-Z(z,n)$ . Next, if $W(z,n)=0$ then

\min_{k\leq n}X(z,k)\leq X(z,n)=-Z(z,n).

If $W(z,n)\neq 0$ , we let $n^{\prime}\leq n$ be the last time before $n$ for which $W(z,n^{\prime})=0$ (assuming it exists). We have that

\min_{k\leq n}X(z,k)\leq X(z,n^{\prime})=-Z(z,n^{\prime})\leq-Z(z,n)+\frac{1}{1-x_{n^{\prime}+1}}\leq-Z(z,n)+\frac{1}{1-z}.

Finally suppose there is no such $n^{\prime}\leq n$ for which $W(z,n^{\prime})=0$ . Then $Z(z,k)=0$ for all $k\leq n$ , and hence $X(z,k)=W(z,k)$ for all $k$ , and $Z(z,n)+\min_{k\leq n}X(z,k)=1\leq 1/(1-z)$ . This finishes the proof of the proposition. ∎

In the following section we give some rough bounds on the process that hold with very high probability. We will later use these a priori bounds in order to obtain more precise estimates and in order to prove the main theorems.

3.1 First control of the process

Definition 3.1.

We say that an event $\mathcal{A}$ holds with very high probability (WVHP) if there are absolute constants $C,c>0$ such that $\mathbb{P}(\mathcal{A})\geq 1-C\exp(-n^{c})$ .

Let $\epsilon:=0.01$ and recall that $z_{0}:=1-1/e$ . Define the events

\mathcal{A}_{1}:=\big{\{}\forall z<z_{0},\ s(z,n)\leq n^{\epsilon}/(z_{0}-z)\big{\}}

and

\mathcal{A}_{2}:=\big{\{}\forall z\geq z_{0},\ s(z,n)\leq(z-z_{0})n+n^{1/2+\epsilon}\big{\}}.

Lemma 3.3.

The event $\mathcal{A}_{1}\cap\mathcal{A}_{2}$ holds WVHP.

Proof.

Let $z<z_{0}$ and note that $W(z,n)\geq s(z,n)$ . Also note that if $W(z,k-1)=0$ and $W(z,k)\neq 0$ , then $W(z,k)=1/(1-x)$ for some $x\leq z<z_{0}$ . Thus, we have that

\big{\{}s(z,n)\geq n^{\epsilon}/(z_{0}-z)\big{\}}\subseteq\big{\{}W(z,n)\geq n^{\epsilon}/(z_{0}-z)\big{\}}\subseteq\bigcup_{k\leq n}\mathcal{C}_{k}

(11)

where the events $\mathcal{C}_{k}$ are defined by

\mathcal{C}_{k}=\big{\{}0<W(z,k)\leq e,\ \forall k\leq m\leq n,W(z,m)\neq 0\text{ and }W(z,n)\geq n^{\epsilon}/(z_{0}-z)\big{\}}.

Next, we show that each of these events has a negligible probability. To this end, let $k\leq n$ and define

M_{m}:=W(z,m)+(m-k)(\log(1-z)+1),\quad\tau:=\min\{m\geq k:W(z,m)=0\}.

By Proposition 3.1, the process $M_{m\wedge\tau}$ is a martingale. Moreover, since $\log(1-z)+1\geq z_{0}-z$ , we have that

\begin{split}\mathcal{C}_{k}&\subseteq\big{\{}M_{n\wedge\tau}-M_{k\wedge\tau}\geq n^{\epsilon}/(z_{0}-z)-e+(n-k)(\log(1-z)+1)\big{\}}\\ &\subseteq\big{\{}M_{n\wedge\tau}-M_{k\wedge\tau}\geq n^{\epsilon/2}/(z_{0}-z)+(n-k)(z_{0}-z)\big{\}}.\end{split}

Thus, using that $M_{m\wedge\tau}$ has bounded increments and that $(a+b)^{2}\geq a^{2}+b^{2}$ , we get from Azuma’s inequality that

\mathbb{P}\big{(}\mathcal{C}_{k}\big{)}\leq\exp\Big{(}-c\ \frac{n^{\epsilon}(z_{0}-z)^{-2}+(n-k)^{2}(z_{0}-z)^{2}}{n-k}\Big{)}\leq C\exp(-cn^{c}),

where the last inequality clearly holds both when $n-k\leq n^{\epsilon/2}(z_{0}-z)^{-2}$ and when $n-k\geq n^{\epsilon/2}(z_{0}-z)^{-2}$ . It follows from (11) that

\mathbb{P}\big{(}s(z,n)\geq n^{\epsilon}/(z_{0}-z)\big{)}\leq C\exp(-n^{c}).

In order to obtain this inequality simultaneously for all $z\leq z_{0}$ we first use a union bound to get it simultaneously for all $z\in\{i/n:i\in\mathbb{N},i/n\leq z_{0}\}$ and then argue that $s(z,n)$ does not change by much WVHP when $z$ changes by $O(n^{-1})$ . The details are omitted. It follows that $\mathbb{P}(\mathcal{A}_{1})\geq 1-C\exp(-n^{c})$ .

We turn to bound the probability of $\mathcal{A}_{2}$ . To this end, let $z\geq z_{0}$ and $z_{1}:=z_{0}-n^{-1/2}$ . The event

\big{\{}s(z_{1},n)\leq n^{1/2+\epsilon}/2\big{\}}\cap\big{\{}\big{|}\big{\{}k\leq n:x_{k}\in[z_{1},z]\big{\}}\big{|}\leq(z-z_{0})n+n^{1/2+\epsilon}/2\big{\}}

holds WVHP by the first part of the proof and by Chernoff’s inequality for the Binomial random variable $\big{|}\big{\{}k\leq n:x_{k}\in[z_{1},z]\big{\}}\big{|}\sim\text{Bin}(n,z-z_{1})$ . On this event we have that $s(z,n)\leq(z-z_{0})n+n^{1/2+\epsilon}$ and therefore, using the discretization argument as above we obtain $\mathbb{P}(\mathcal{A}_{2})\geq 1-C\exp(-n^{c})$ . ∎

The following lemma implies in particular that, with very high probability, the minimum is rarely above $z$ for any $z>z_{0}$ . For the statement of the lemma, define the random variable

M_{n}(z):=\big{|}\big{\{}k\leq n:m_{k}\geq z\big{\}}\big{|}

and the events

\mathcal{B}_{1}:=\big{\{}\forall z>z_{0},\ M_{n}(z)\leq n^{\epsilon}/(z-z_{0})\big{\}}

and

\mathcal{B}_{2}:=\big{\{}\forall z\leq z_{0},\ \big{|}M_{n}(z)-(\log(1-z)+1)n\big{|}\leq n^{1/2+\epsilon}\big{\}}.

Lemma 3.4.

The event $\mathcal{B}_{1}\cap\mathcal{B}_{2}$ holds WVHP.

Proof.

We claim that for any $z<1$ the process

L(z,k):=W(z,k)+(\log(1-z)+1)(k-1)-M_{k-1}(z)

(12)

is a martingale. Indeed, if $W(z,k)\neq 0$ then $M_{k}(z)=M_{k-1}(z)$ and therefore by Proposition 3.1 we have $\mathbb{E}[L(z,k+1)-L(k,z)\mid\mathcal{F}_{k}]=0$ . Otherwise, using that $M_{k}(z)=M_{k-1}(z)+1$ we have

\mathbb{E}[L(z,k+1)-L(k,z)\mid\mathcal{F}_{k}]=\int_{0}^{z}\frac{1}{1-x}dx+\log(1-z)=0.

Moreover, when $z<3/4$ the martingale $L(z,k)$ has bounded increments and therefore by Azuma’s inequality we have WVHP

\big{|}W(z,n+1)+(\log(1-z)+1)n-M_{n}(z)\big{|}\leq n^{1/2+\epsilon}.

(13)

Now, when $z\leq z_{0}$ , on the event $\mathcal{A}_{2}$ we have

W(z,n+1)\leq W(z_{0},n+1)\leq e\cdot s(z_{0},n+1)\leq n^{1/2+\epsilon}.

Substituting this back into (13) we obtain that WVHP

\big{|}M_{n}(z)-(\log(1-z)+1)n\big{|}\leq n^{1/2+2\epsilon}.

(14)

This shows that $\mathcal{B}_{2}$ holds WVHP using the discretization trick. Indeed, WVHP each $z\in[0,z_{0}]$ is the minimum at most $n^{\epsilon}$ times and therefore WVHP $M_{n}(z)$ won’t change by more than $n^{2\epsilon}$ when $z$ changes by $O(n^{-1})$ .

We turn to bound the probability of $\mathcal{B}_{1}$ . To this end, let $n_{0}:=\lfloor n^{\epsilon}(z-z_{0})^{-2}\rfloor$ and let $z_{0}\leq z\leq 3/4$ . Using (13) and the fact that $\log(1-z)+1\leq-e(z-z_{0})$ we obtain that WVHP for all $n_{0}\leq k\leq n$

W(z,k+1)\geq e(z-z_{0})k-|L(z,k)|\geq e(z-z_{0})k-k^{1/2+\epsilon}>0,

(15)

where the last inequality follows from the definition of $n_{0}$ . Thus, WVHP, for all $n_{0}<k\leq n$ we have that $m_{k}\leq z$ and therefore

M_{n}(z)=M_{n_{0}}(z)\leq M_{n_{0}}(z_{0})\leq n_{0}^{1/2+\epsilon}\leq n^{\epsilon}/(z-z_{0}),

where the second to last inequality holds WVHP by (14) with $z=z_{0}$ . Of course the same bound holds when $3/4\leq z\leq 1$ (by slightly changing $\epsilon$ ) and therefore, using the discretization trick we get that $\mathcal{B}_{1}$ holds WVHP. ∎

3.2 Proof of Theorem 4

The main step toward proving the theorem is the following proposition that determines the scaling limit of $X(z,n)$ when $z$ is in a small neighborhood around $z_{0}=1-1/e$ .

Proposition 3.5.

We have that

\Big{\{}\frac{X(z_{0}+yn^{-1/2}\,,\,tn)}{\sqrt{n}}\Big{\}}_{\begin{subarray}{c}t>0\\ y\in\mathbb{R}\end{subarray}}\overset{d}{\longrightarrow}\big{\{}\sqrt{2}B_{t}+eyt\big{\}}_{\begin{subarray}{c}t>0\\ y\in\mathbb{R}\end{subarray}},\quad n\to\infty.

We start by proving Theorem 4 using Proposition 3.5.

Proof of Theorem 4.

By Proposition 3.5 and (9) we have that the joint distribution

\Big{\{}\Big{(}\frac{X(z_{0}+yn^{-1/2}\,,\,tn)}{\sqrt{n}}\ ,\ \frac{Z(z_{0}+yn^{-1/2}\,,\,tn)}{\sqrt{n}}\Big{)}\Big{\}}_{\begin{subarray}{c}t>0\\ y\in\mathbb{R}\end{subarray}}

converges to $\big{(}\sqrt{2}B_{t}+eyt\,,\,-\inf_{s\leq t}(\sqrt{2}B_{t}+eys)\big{)}$ . Thus, using that $W(z,n)=X(z,n)+Z(z,n)$ we obtain

\Big{\{}\frac{W(z_{0}+yn^{-1/2}\,,\,tn)}{\sqrt{n}}\Big{\}}_{\begin{subarray}{c}t>0\\ y\in\mathbb{R}\end{subarray}}\overset{d}{\longrightarrow}\big{\{}\sqrt{2}B_{t}+eyt-\inf_{s\leq t}\big{(}\sqrt{2}B_{t}+eys\big{)}\big{\}}_{\begin{subarray}{c}t>0\\ y\in\mathbb{R}\end{subarray}}.

(16)

For the proof of Theorem 4 it suffices to show that $W(z_{0}+yn^{-1/2}\,,\,k)$ in the equation* above can be replaced by $e\cdot s(z_{0}+yn^{-1/2},k)$ . Intuitively, it follows as most of the terms in the sum in the definition of $W$ are close to $e$ . Formally, let $z_{1}:=z_{0}-n^{-1/4}$ and $z_{2}:=z_{0}+n^{-1/2+\epsilon}$ . By Lemma 3.3 we have WVHP that for all $z_{1}\leq z\leq z_{2}$ and $k\leq n^{1+\epsilon}$

\begin{split}\big{|}W(z,k)-e\cdot s(z,k)\big{|}&\leq Cs(z_{1},k)+\sum_{x\in S(z,k)\setminus S(z_{2},k)}\Big{|}\frac{1}{1-x}-e\Big{|}\\ &\leq Cn^{1/4+\epsilon}+Cn^{-1/4}s(z_{2},k)\leq n^{1/4+2\epsilon}.\end{split}

(17)

This shows that $W$ can be replaced by $e\cdot s$ in equation (16) and therefore finishes the proof of the theorem. ∎

We turn to prove Proposition 3.5. The proposition follows immediately from the following two propositions.

Proposition 3.6.

We have that

\Big{\{}\frac{X(z_{0},tn)}{\sqrt{n}}\Big{\}}_{t>0}\overset{d}{\longrightarrow}\big{\{}\sqrt{2}B_{t}\big{\}}_{t>0},\quad n\to\infty.

Proposition 3.7.

We have WVHP for all $z$ with $|z-z_{0}|\leq n^{-1/2+\epsilon}$ that

\big{|}X(z,n)-X(z_{0},n)-en(z-z_{0})\big{|}\leq n^{1/4+3\epsilon}.

We start by proving Proposition 3.6. The main tool we use is the following martingale functional central limit theorem [5, Theorem 8.2.8] .

Theorem 3.8.

Let $M_{n}$ be a martingale with bounded increments. Recall that the predictable quadratic variation of $M_{n}$ is given by

V_{n}:=\sum_{k=1}^{n}\mathbb{E}\big{[}\big{(}M_{k}-M_{k-1}\big{)}^{2}\ |\ \mathcal{F}_{k-1}\big{]}.

Suppose that for all $t>0$ we have that

\frac{V_{tn}}{n}\overset{p}{\longrightarrow}\sigma^{2}t,\quad n\to\infty.

where the convergence is in probability. Then

\Big{\{}\frac{M_{tn}}{\sqrt{n}}\Big{\}}_{0<t<1}\overset{d}{\longrightarrow}\big{\{}\sigma B_{t}\big{\}}_{0<t<1},

where $B_{t}$ is a standard Brownian motion.

In order to use Theorem 3.8 we need to estimate the predictable quadratic variation of the martingale $X(z_{0},n)$ . To this end, we need the following lemma. Let us note that the exponent $3/4$ in the lemma is not tight. However, it suffices for the proof of the main theorems.

Lemma 3.9.

For any bounded function $f:[0,1]\to\mathbb{R}$ that is differentiable on $[0,z_{0}]$ we have

\mathbb{P}\Big{(}\Big{|}\sum_{k=1}^{n}f(m_{k})-n\int_{0}^{z_{0}}\frac{f(x)}{1-x}dx\Big{|}\leq n^{3/4+2\epsilon}\Big{)}\geq 1-C\exp(-n^{c}),

where the constants $C,c$ may depend on the function $f$ .

Proof.

Throughout the proof we let the constants $C$ and $c$ depend on the function $f$ . For the proof of the lemma we split the interval $[0,z_{0}]$ into $\lfloor n^{1/4}\rfloor$ small intervals $[y_{i-1},y_{i}]$ where $y_{i}:=iz_{0}/\lfloor n^{1/4}\rfloor$ . For all $i\leq\lfloor n^{1/4}\rfloor$ we let

J_{i}:=\big{\{}k\leq n:m_{j}\in[y_{i-1},y_{i}]\big{\}}.

(18)

We have that

\begin{split}\Big{|}\sum_{k=1}^{n}f(m_{k})&-n\int_{0}^{z_{0}}\frac{f(x)}{1-x}dx\Big{|}\\ &\leq\sum_{i=1}^{\lfloor n^{1/4}\rfloor}\Big{|}\sum_{k\in J_{i}}f(m_{k})-n\int_{y_{i-1}}^{y_{i}}\!\frac{f(x)}{1-x}dx\Big{|}+\sum_{k=1}^{n}f(m_{k})\cdot\mathds{1}\{m_{k}\geq z_{0}\}.\end{split}

(19)

Next, we estimate the size of $J_{i}$ . Using Lemma 3.4 we have WVHP

\begin{split}|J_{i}|=M_{n}(y_{i-1})-M_{n}(y_{i})&=n\big{(}\log(1-y_{i-1})-\log(1-y_{i})\big{)}+O(n^{1/2+\epsilon})\\ &=\frac{n(y_{i}-y_{i-1})}{1-y_{i}}+O(n^{1/2+\epsilon}),\end{split}

where in the last equality we used the Taylor expansion of the function $\log(1-x)$ around $x=y_{i}$ . Thus, using that $f(x)=f(y_{i})+O(n^{-1/4})$ and $f(x)/(1-x)=f(y_{i})/(1-y_{i})+O(n^{-1/4})$ for all $x\in[y_{i-1},y_{i}]$ we obtain

\begin{split}\Big{|}\sum_{k\in J_{i}}f(m_{k})-n\int_{y_{i-1}}^{y_{i}}\!\frac{f(x)}{1-x}dx\Big{|}&\leq|f(y_{i})|\cdot\Big{|}|J_{i}|-\frac{n(y_{i}-y_{i-1})}{1-y_{i}}\Big{|}+O\big{(}|J_{i}|n^{-1/4}+n^{1/2}\big{)}\\ &=O(n^{1/2+\epsilon}).\end{split}

Substituting the last estimate back into (19) we obtain

\Big{|}\sum_{k=1}^{n}f(m_{k})-n\int_{0}^{z_{0}}\frac{f(x)}{1-x}dx\Big{|}\leq O(n^{3/4+\epsilon})+CM_{n}(z_{0})=O(n^{3/4+\epsilon}),

where in the last equality we used Lemma 3.4 once again. ∎

We can now prove Proposition 3.6.

Proof of Proposition 3.6.

In order to use Theorem 3.8 we compute the predictable quadratic variation of $X(z_{0},k)$ . Clearly, on the event $\{m_{k}\geq z_{0}\}$ we have that $\mathbb{E}\big{[}(X(z_{0},k+1)-X(z_{0},k))^{2}\ \big{|}\ \mathcal{F}_{k}\big{]}=0$ . On the event $\{m_{k}\leq z_{0}\}$ we have

\begin{split}\mathbb{E}\big{[}(X&(z_{0},k+1)-X(z_{0},k))^{2}\ \big{|}\ \mathcal{F}_{k}\big{]}=\mathbb{E}\big{[}(W(z_{0},k+1)-W(z_{0},k))^{2}\ \big{|}\ \mathcal{F}_{k}\big{]}\\ &=\int_{0}^{z_{0}}\frac{1}{(1-x)^{2}}dx-\frac{2}{1-m_{k}}\int_{m_{t}}^{z_{0}}\frac{1}{1-x}dx+\frac{1}{1-m_{k}}\\ &=\frac{1}{1-x}\Big{|}_{0}^{z_{0}}+\frac{2}{1-m_{k}}\log(1-x)\Big{|}_{m_{k}}^{z_{0}}+\frac{1}{1-m_{k}}=e-1-\frac{2\log(1-m_{k})+1}{1-m_{k}}.\end{split}

Thus, the predictable quadratic variation of $X(z_{0},k)$ is given by

V_{n}:=\sum_{k=0}^{n-1}\mathbb{E}\big{[}(X(z_{0},k)-X(z_{0},k))^{2}\ \big{|}\ \mathcal{F}_{k}\big{]}=\sum_{k=1}^{n-1}f(m_{k}),

(20)

where

f(x):=\Big{(}e-1-\frac{2\log(1-x)+1}{1-x}\Big{)}\cdot\mathds{1}\{x\leq z_{0}\}.

Next, we have that

\begin{split}\int_{0}^{z_{0}}\frac{f(x)}{1-x}&dx=\int_{0}^{z_{0}}\frac{1}{1-x}\Big{(}e-1-\frac{2\log(1-x)+1}{1-x}\Big{)}dx\\ &=(1-e)\log(1-x)\Big{|}_{0}^{z_{0}}-\frac{2\log(1-x)+3}{1-x}\Big{|}_{0}^{z_{0}}=e-1-e+3=2\end{split}

and therefore, by Lemma 3.9 we have WVHP that $|V_{n}-2n|\leq Cn^{3/4+3\epsilon}$ . It follows that for all $t>0$ we have $V_{tn}/n\to 2t$ in probability and therefore by Theorem 3.8 we have

\Big{\{}\frac{X(z_{0},tn)}{\sqrt{n}}\Big{\}}_{t>0}\overset{d}{\longrightarrow}\big{\{}\sqrt{2}B_{t}\big{\}}_{t>0}

as needed. ∎

We turn to prove Proposition 3.7. The main tool we use is the following martingale concentration result due to Freedman [6]. See also [4, Theorem 1.2].

Theorem 3.10 (Freedman’s inequality).

Let $M_{n}$ be a martingale with increments bounded by $M$ and let

V_{n}:=\sum_{k=1}^{n}\mathbb{E}\big{[}(M_{k+1}-M_{k})^{2}\ |\ \mathcal{F}_{k}\big{]}

be the predictable quadratic variation. Then,

\mathbb{P}\big{(}|M_{n}|\geq x,\ V_{n}\leq y\big{)}\leq 2\exp\Big{(}-\frac{x^{2}}{2y+2Mx}\Big{)}.

We can now prove Proposition 3.7.

Proof of Proposition 3.7.

Let $z$ such that $|z-z_{0}|\leq n^{-1/2+\epsilon}$ . It follows from Proposition 3.1 that the process

N(z,k):=X(z,k)+(\log(1-z)+1)(k-1)-(\log(1-z)+1)\cdot M_{k-1}(z)

is a martingale. Next, consider the difference martingale $L(z,k):=N(z,k)-N(z_{0},k)=N(z,k)-X(z_{0},k)$ and note that

\big{|}L(z,k+1)-L(z,k)\big{|}\leq C|z-z_{0}|+C\mathds{1}\{x_{k+1}\in[z_{0},z]\cup[z,z_{0}]\}+C\mathds{1}\{m_{k}\geq z_{0}-n^{-1/2+\epsilon}\}.

Thus, by Lemma 3.4 we have WVHP

V_{n}:=\sum_{k=1}^{n}\mathbb{E}\big{[}(L(z,k)-L(z,k-1))^{2}\ |\ \mathcal{F}_{k-1}\big{]}\leq Cn^{1/2+\epsilon}+CM_{n}(z_{0}-n^{-1/2+\epsilon})\leq n^{1/2+2\epsilon}.

We obtain using Theorem 3.10 that

\begin{split}\mathbb{P}\big{(}\big{|}L(z,n)\big{|}\geq n^{1/4+2\epsilon}\big{)}&\leq\mathbb{P}\big{(}\big{|}L(z,n)\big{|}\geq n^{1/4+2\epsilon},\ V_{n}\leq n^{1/2+2\epsilon}\big{)}+\mathbb{P}\big{(}V_{k}\geq n^{1/2+2\epsilon}\big{)}\\ &\leq C\exp(-n^{c}).\end{split}

Finally, using the expansion $\log(1-z)+1=-e(z-z_{0})+O(n^{-1+2\epsilon})$ we get that WVHP

\big{|}X(z,n)-X(z_{0},n)-en(z-z_{0})\big{|}\leq\big{|}L(z,k)\big{|}+Cn^{2\epsilon}+C\cdot|z-z_{0}|\cdot M_{n}(z)\leq n^{1/4+3\epsilon}.

This finishes the proof of the proposition using the discretization trick. ∎

3.3 Proof of Theorem 3

The main statement in Theorem 3 is the scaling limit result

\Big{\{}\Big{(}\frac{L_{tn}}{\sqrt{n}}\,,\,\frac{R_{tn}}{\sqrt{n}}\Big{)}\Big{\}}_{t>0}\overset{d}{\longrightarrow}\big{\{}\sqrt{2}e^{-1}\big{(}M_{t}-B_{t},M_{t}\big{)}\big{\}}_{t>0}.

(21)

We start by proving (21) and then briefly explain how the other statements in Theorem 3 follow.

By Proposition 3.6 and Proposition 3.1 we have that

\big{\{}n^{-1/2}\big{(}W(z_{0},tn)\ ,\ Z(z_{0},tn)\big{)}\big{\}}_{t>0}\overset{d}{\longrightarrow}\big{\{}\sqrt{2}\big{(}B_{t}-\inf_{x<t}B_{x}\ ,\ -\inf_{x<t}B_{x}\big{)}\big{\}}_{t>0}.

(22)

Moreover, by symmetry

\big{\{}\sqrt{2}\big{(}B_{t}-\inf_{x<t}B_{x}\ ,\ -\inf_{x<t}B_{x}\big{)}\big{\}}_{t>0}\overset{d}{=}\big{\{}\sqrt{2}\big{(}M_{t}-B_{t}\ ,\ M_{t}\big{)}\big{\}}_{t>0}.

(23)

Next, recall that $L_{n}=s(z_{0},n)$ and therefore, by (17), WVHP

\big{|}e\cdot L_{n}-W(z_{0},n)\big{|}\leq n^{1/3}.

(24)

The convergence in (21) clearly follows from (22), (23), (24) and the following lemma

Lemma 3.11.

We have WVHP

\big{|}e\cdot R_{n}-Z(z_{0},n)\big{|}\leq n^{1/3}.

Proof.

We write

\big{|}e\cdot R_{n}-Z(z_{0},n)\big{|}\leq e\big{|}R_{n}-R_{n}^{\prime}\big{|}+\big{|}e\cdot R_{n}^{\prime}-M_{n-1}(z_{0})\big{|}+\big{|}M_{n-1}(z_{0})-Z(z_{0},n)\big{|},

(25)

where $R_{n}^{\prime}:=\sum_{k=1}^{n-1}\mathds{1}\{m_{k}\geq z_{0}\}(1-m_{k})$ and bound each one of the terms in the right hand side of (25).

We start with the first term. Note that $R_{n}=\big{|}\{2\leq k\leq n:m_{k}\geq m_{k-1}\geq z_{0}\}\big{|}$ and therefore

\mathbb{E}\big{[}R_{n+1}-R_{n}\ |\ \mathcal{F}_{n}\big{]}=\mathds{1}\big{\{}m_{n}\geq z_{0}\big{\}}(1-m_{n}).

It follows that $N_{n}:=R_{n}-R_{n}^{\prime}$ is a martingale. The predictable quadratic variation of $N_{n}$ is given by

\sum_{k=1}^{n-1}\mathbb{E}\big{[}(N_{k+1}-N_{k})^{2}\ |\ \mathcal{F}_{k}\big{]}\leq\sum_{k=1}^{n-1}\mathds{1}\{m_{k-1}\geq z_{0}\}\leq M_{n}(z_{0})\leq n^{1/2+\epsilon},

where the last inequality holds WVHP by Lemma 3.4. Thus, using the same arguments as in the proof of Proposition 3.7 and by Theorem 3.10 we have that $|R_{n}-R_{n}^{\prime}|\leq n^{1/4+\epsilon}$ WVHP.

We turn to bound the second term in the right hand side of (25). We have

\begin{split}\big{|}e\cdot R_{n}^{\prime}-M_{n-1}(z_{0})\big{|}&\leq\sum_{k=1}^{n}\mathds{1}\{m_{k}\geq z_{0}\}\big{(}1-e(1-m_{k})\big{)}\\ &\leq CM_{n}(z_{0})n^{-1/4}+M_{n}\big{(}z_{0}+n^{-1/4}\big{)}\leq n^{1/4+2\epsilon},\end{split}

where in the second inequality we separated the sum to $m_{k}\in[z_{0},z_{0}+n^{-1/4}]$ and $m_{k}\geq z_{0}+n^{-1/4}$ and where the last inequality holds WVHP by Lemma 3.4.

The last term in the right hand side of (25) is bounded by $n^{1/4+\epsilon}$ WVHP using the same arguments as in the first term. Indeed, $Z(z_{0},n)-M_{n-1}(z_{0})$ is clearly a martingale and its quadratic variation is bounded by $n^{1/2+\epsilon}$ WVHP. ∎

We turn to prove the other results in Theorem 3. By (21) we have that

\Big{\{}\frac{L_{tn}+R_{tn}}{\sqrt{n}}\Big{\}}_{t>0}\overset{d}{\longrightarrow}\big{\{}\sqrt{2}e^{-1}(2M_{t}-B_{t})\big{\}}_{t>0}.

(26)

Recall that a three dimensional Bessel process, $X_{t}$ , is the distance of a three dimensional Brownian motion from the origin. In [11] Pitman proved that

\big{\{}2M_{t}-B_{t}\big{\}}_{t>0}\overset{d}{=}\{X_{t}\}_{t>0}

and therefore the convergence in (1) follows from (26). Next, using (21) once again we get that

\frac{L_{n}}{\sqrt{n}}\overset{d}{\longrightarrow}\sqrt{2}e^{-1}(M_{1}-B_{1}),\quad\quad\frac{R_{n}}{\sqrt{n}}\overset{d}{\longrightarrow}\sqrt{2}e^{-1}M_{1}

(27)

It is well known (see [9, Theorem 2.34 and Theorem 2.21]) that $M_{1}-B_{1}\overset{d}{=}M_{1}\overset{d}{=}|N|$ . Substituting these identities into (27) finishes the proof of the first two limit laws in (2).

It remains to prove the last limit law in (2). By (1) with $t=1$ , it suffices to compute the density of $\sqrt{2}e^{-1}X_{1}$ . This is a straightforward computation as $X_{1}$ is the norm of a three dimensional normal random variable. We omit the details of the computation which lead to the density given in (3).

We note that one can compute the density of $2M_{1}-B_{1}$ without using the result of Pitman [11]. The following elementary argument was given to us by Iosif Pinelis in a Mathoverflow answer [10]. By the reflection principle for all $a>b>0$

\mathbb{P}\big{(}M_{1}>a\ ,\ B_{1}<b\big{)}=\mathbb{P}\big{(}B_{1}\geq 2a-b\big{)}=1-F(2a-b).

(28)

Equation (28) gives the joint distribution of $M_{1}$ and $B_{1}$ . From here it is straightforward to compute the joint density of $(M_{1},B_{1})$ and the density of $2M_{1}-B_{1}$ . Once again, the details of the computation are omitted.

3.4 Proof of Theorem 2

Define $E_{n}(z):=\big{|}\{k\leq n:x_{k}\geq z\}\big{|}$ and consider the martingale

N_{n}:=X(z_{0},n)+eE_{n}(z_{0})-n.

Theorem 2 clearly follows from the following two lemmas.

Lemma 3.12.

We have that

\Big{\{}\frac{N_{tn}}{\sqrt{n}}\Big{\}}_{t>0}\overset{d}{\longrightarrow}\big{\{}\sqrt{e-3}\,B_{t}\big{\}}_{t>0}

Lemma 3.13.

We have WVHP

\big{|}s(1,n)-n/e-N_{n}/e\big{|}\leq n^{1/3+\epsilon}.

We start by proving Lemma 3.12.

Proof of Lemma 3.12.

On the event $\{m_{k}\leq z_{0}\}$ we have that

N_{k+1}-N_{k}=\mathds{1}\{x_{k+1}\leq z_{0}\}\frac{1}{1-x_{k+1}}-\mathds{1}\{x_{k+1}\geq m_{k}\}\frac{1}{1-m_{k}}+e\cdot\mathds{1}\{x_{k+1}\geq z_{0}\}-1.

Thus, expanding the $10$ terms in $(N_{k+1}-N_{k})^{2}$ we get that on this event

\begin{split}&\mathbb{E}\big{[}(N_{k+1}-N_{k})^{2}\ |\ \mathcal{F}_{k}\big{]}\\ &=\int_{0}^{z_{0}}\frac{dx}{(1-x)^{2}}-\frac{1}{1-m_{k}}\int_{m_{k}}^{z_{0}}\frac{2\,dx}{1-x}-\int_{0}^{z_{0}}\frac{2\,dx}{1-x}+\frac{1}{1-m_{k}}-\frac{2}{1-m_{k}}+2+e-2+1\\ &=\frac{1}{1-x}\Big{|}_{0}^{z_{0}}+\frac{2\log(1-x)}{1-m_{k}}\Big{|}_{m_{k}}^{z_{0}}+2\log(1-x)\Big{|}_{0}^{z_{0}}-\frac{1}{1-m_{k}}+1+e\\ &=\!e-1-\frac{2}{1-m_{k}}-\frac{2\log(1-m_{k})}{1-m_{k}}-2-\frac{1}{1-m_{k}}+1+e=\frac{-2\log(1-m_{k})-3}{1-m_{k}}+2e-2.\end{split}

Thus, we can write $\mathbb{E}\big{[}(N_{k+1}-N_{k})^{2}\ |\ \mathcal{F}_{k}\big{]}=f(m_{k})$ where $f$ is given by the right hand side of the last equation when $m_{k}\leq z_{0}$ . Moreover, we have that

\int_{0}^{z_{0}}\frac{f(x)}{1-x}dx=\frac{-2\log(1-x)-5}{1-x}\Big{|}_{0}^{z_{0}}-(2e-2)\log(1-x)\Big{|}_{0}^{z_{0}}=-3e+5+2e-2=3-e.

Thus, by Lemma 3.9 we have with very high probability that

V_{n}:=\sum_{k=1}^{n-1}\mathbb{E}\big{[}(N_{k+1}-N_{k})^{2}\ |\ \mathcal{F}_{k}\big{]}=\sum_{k=1}^{n-1}f(m_{k})=(3-e)n+O(n^{5/6}).

This finishes the proof of the lemma using Theorem 3.8. ∎

We turn to prove Lemma 3.13.

Proof of Lemma 3.13.

Recall that $E_{n}(z):=\big{|}\big{\{}k\leq n:x_{k}\geq z\big{\}}\big{|}$ and let $z_{1}:=z_{0}+n^{-1/3}$ . By Proposition 3.1 the process

N_{k}^{\prime}:=X(z_{1},k)+(\log(1-z_{1})+1)(k-1)-(\log(1-z_{1})+1)\cdot M_{k-1}(z_{1})+eE_{n}(z_{1})-e(1-z_{1})n

is a martingale. It is straightforward to check that

e\cdot s(1,n)-n-N_{n}=A_{1}+A_{2}+A_{3}+A_{4}+A_{5}+A_{6}

where

\begin{split}&A_{1}:=e\big{(}s(1,n)-s(z_{1},n)-E_{n}(z_{1})\big{)},\quad A_{2}:=e\cdot s(z_{1},n)-W(z_{1},n),\\ &A_{3}:=Z(z_{1},n),\quad A_{4}:=N_{n}^{\prime}-N_{n},\quad A_{5}:=e(z_{0}-z_{1})n-(\log(1-z_{1})+1)(n-1)\\ &\text{and}\quad A_{6}=(\log(1-z_{1})+1)M_{n-1}(z_{1}).\end{split}

Next, we bound each of the $A_{i}$ WVHP. Any uniform point $x\geq z_{1}$ that arrived before time $n$ such that $x\notin S(1,n)$ can be mapped to the time $k\leq n$ in which it was removed. Thus, using also Lemma 3.4 we obtain that WVHP

0\leq E_{n}(z_{1})-\big{(}s(1,n)-s(z_{1},n)\big{)}\leq M_{n}(z_{1})\leq n^{1/3+\epsilon}.

This shows that WVHP $|A_{1}|\leq en^{1/3+\epsilon}$ .

Using the same arguments as in (17) we get that $|A_{2}|\leq n^{1/3+2\epsilon}$ .

By Lemma 3.4 we have WVHP $|A_{3}|\leq 3M_{n}(z_{1})\leq 3n^{1/3+\epsilon}$ .

In order to bound $A_{4}$ we use the same arguments as in the proof of Proposition 3.7. Define the martingale $L_{k}:=N_{k}^{\prime}-N_{k}$ . We have that

\big{|}L_{k+1}-L_{k}\big{|}\leq Cn^{-1/3}+C\mathds{1}\{x_{k+1}\in[z_{0},z_{1}]\}+C\mathds{1}\{m_{k}\geq z_{0}\}.

Thus, using Theorem 3.10 we obtain that WVHP $|N_{n}-N^{\prime}_{n}|=|L_{n}|\leq n^{1/3+3\epsilon}$ .

It follows from a second order Taylor expansion of $\log(1-z_{1})$ around $z_{0}$ that $|A_{5}|\leq Cn^{1/3}$ .

Lastly, by Lemma 3.4 we have WVHP $|A_{6}|\leq Cn^{-1/3}M_{n}(z_{1})\leq Cn^{\epsilon}$ .

∎

Acknowledgment: We thank Ehud Friedgut and Misha Tsodyks for helpful comments, we thank Ron Peled, Sahar Diskin and Jonathan Zung for fruitful discussions and we thank Iosif Pinelis for proving in [10] that the density function of $2M_{1}-B_{1}$ is given by $\frac{2x^{2}}{\sqrt{2\pi}}e^{-x^{2}/2}$ .

References

[1] N. Alon, C. Defant and N. Kravitz, The runsort permuton, arXiv:2106.14762, 2021.
[2] N. Alon and J. H. Spencer, The Probabilistic Method, Fourth Edition, Wiley, 2016, xiv+375 pp.
[3] K. B. Athreya and P. E. Ney, Branching processes, Courier Corporation, 2004.
[4] B. Bercu and A. Touati, Exponential inequalities for self-normalized martingales with applications, The Annals of Applied Probability, 18(5), 1848–1869, 2008.
[5] R. Durrett, Probability: theory and examples, volume 49, Cambridge university press, 2019.
[6] D. A. Freedman, On tail probabilities for martingales, The Annals of Probability, 3(1), 100–118, 1975.
[7] E. Friedgut and G. Kozma, Private communication.
[8] A. Georgiou, M. Katkov and M. Tsodyks, Retroactive interference model of forgetting, Journal of Mathematical Neuroscience (2021) 11:4.
[9] P. Mörters and Y. Peres, Brownian motion, volume 30, Cambridge University Press, 2010.
[10] I. Pinelis, What is the distribution of $2M_{1}-B_{1}$ where $M_{t}$ is the maximum process of the Brownian motion $B_{t}$ . MathOverflow question 409729.
[11] J. W. Pitman, One-dimensional Brownian motion and the three-dimensional Bessel process, Advances in Applied Probability, 7(3), 511–526, 1975.
[12] M. Tsodyks, Private Communication.