On a random model of forgetting

Noga Alon, Dor Elboim, Allan SlyThe Annals of Applied Probability 2022 · arXiv

TL;DR

This paper provides a rigorous mathematical foundation for a "forgetting" model where new information displaces the least significant existing memory. The authors prove that the memory size stabilizes at exactly $1/e$ of the total information received and show that its fluctuations follow a normal distribution, while its long-term evolution mirrors a three-dimensional Bessel process.

What Problem Does This Paper Address?

How do we decide what to remember and what to forget? In 2021, Georgiou, Katkov, and Tsodyks proposed a deceptively simple model: imagine a stream of information (numbers between 0 and 1). You add every new piece of information to your "memory" set. However, if the new piece is "better" (larger) than the least important thing you currently remember, you discard that minimum value to make room.

While computer simulations suggested that the size of this memory set eventually settles around $n/e$ (roughly 36.8% of the total items seen), a rigorous mathematical proof was missing. This paper fills that gap, moving beyond simple averages to describe the precise "shape" of memory fluctuations and how the set of remembered items evolves over time.

Methods

The authors employ sophisticated tools from probability theory, specifically martingale theory and branching processes.

  1. The Branching Martingale: The core "aha" moment is the discovery of a "magical formula" for a process they call $W(z, n) = \sum_{x \in S} \frac{1}{1-x}$. They show that at a critical threshold ($z_0 = 1 - 1/e$), this sum behaves as a martingale—a sequence of random variables where the future expectation is equal to the current value.
  2. Coupling and Scaling: To prove the Central Limit Theorem and the convergence to a Bessel process, they use "coupling" techniques (comparing their process to a standard Brownian motion) and the Martingale Functional Central Limit Theorem.
  3. Subadditivity: They use subadditivity arguments to show that the expected size of the memory grows linearly with the number of steps.

Datasets

As a theoretical mathematics paper, no external real-world datasets were used. The authors utilized computer simulations of the random process (up to $10^6$ steps) to visualize the behavior and motivate their formal theorems.

Key Insights and Ideas

  • The Critical Threshold: The value $1 - 1/e$ acts as a "watershed." Points larger than this are likely to stay in memory, while points smaller are likely to be "forgotten" (pushed out by newer, larger arrivals).
  • Memory as a Branching Process: The authors realized that the way items enter and leave the set can be modeled as a continuous-type branching process. In this view, an item "gives birth" to new items that might eventually replace it.
  • The Bessel Connection: One of the most elegant findings is that the "error" (the difference between what is actually remembered and the "ideal" set of all items $> 1-1/e$) behaves like a three-dimensional Bessel process. This process describes the distance of a 3D Brownian motion from its origin, suggesting a deep structural symmetry in the dynamics of forgetting.

Key Results

  • Rigorous Proof of Size: The size of the memory set $|S(1, n)|$ is indeed $(1+o(1))n/e$ with high probability.
  • Central Limit Theorem: The fluctuations of the memory size around the mean, when scaled by $\sqrt{n}$, converge to a normal distribution. Specifically, the variance is calculated as $3e^{-2} - e^{-1}$.
  • Symmetric Difference: The set of remembered items is remarkably close to the set of all items larger than $1-1/e$. The "mistakes" (items $> 1-1/e$ that were forgotten or items $< 1-1/e$ that were kept) are only of size $O(\sqrt{n})$.
  • Dynamic Scaling: The paper provides a complete description of the process's evolution in the neighborhood of the critical point, showing it converges to a rescaled Brownian motion minus its minimum.

Limitations and Future Work

The authors note that while they used a uniform distribution $[0, 1]$ for simplicity, the specific distribution doesn't actually matter as long as it is "non-atomic" (continuous). The process only depends on the relative ordering of the points.

One area not deeply explored is how this model changes if the "importance" of information decays over time (non-IID arrivals) or if the memory has a fixed maximum capacity rather than an elastic one. Additionally, while this is a "simplified model of forgetting," connecting these rigorous bounds back to actual neurobiological data remains a challenge for mathematical psychologists.

Summary updated

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\ge 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\ge 1-1/e: 1 \leq k \leq n \}$ converges with proper scaling to a three dimensional Bessel process.
BibTeX
@article{alon2022random,
  author = {Noga Alon and Dor Elboim and Allan Sly},
  title = {{On a random model of forgetting}},
  journal = {The Annals of Applied Probability},
  year = {2022},
}
Figure