Ulam's History-dependent Random Adding Process

Abstract

Ulam has defined a history-dependent random sequence of integers by the recursion $X_{n+1}$ $=X_{U(n)}+X_{V(n)},n⩾r$ where $U(n)$ and $V(n)$ are independently and uniformly distributed on $\{1,\dots ,n\}$, and the initial sequence, $X_1=x_1,\dots ,X_r=x_r$, is fixed. We consider the asymptotic properties of this sequence as $n\to \infty$, showing, for example, that $n^{-2}{\sum }_{k=1}^n{X}_k$ converges to a non-degenerate random variable. We also consider the moments and auto-covariance of the process, showing, for example, that when the initial condition is $x_1=1$ with $r=1$, then ${\lim }_{n\to \infty }{n}^{-2}E{X}_n^2=(2\pi {)}^{-1}\sinh (\pi )$; and that for large $m<n$, we have $(mn{)}^{-1}E{X}_m{X}_n\doteq (3\pi {)}^{-1}\sinh (\pi ).$ We further consider new random adding processes where changes occur independently at discrete times with probability $p$, or where changes occur continuously at jump times of an independent Poisson process. The processes are shown to have properties similar to those of the discrete time process with $p=1$, and to be readily generalised to a wider range of related sequences.

Expanded version

References in corpus (7)

• A survey of random processes with reinforcement
• Understanding scaling through history-dependent processes with collapsing sample space
• A martingale approach for the elephant random walk
• Solvable random walk model with memory and its relations with Markovian models of anomalous diffusion
• The Shark Random Swim (Lévy flight with memory)
• On a class of random walks with reinforced memory
• Reverting Processes