Ulams History-dependent Random Adding Process

Ulam has defined a history-dependent random sequence of integers by the recursion $X_{n+1}$ $= X_{U(n)}+X_{V(n)}, n geqslant 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_{nto infty} n^{-2} E X^2_n = (2 pi)^{-1} sinh(pi)$; and that for large $m < n$, we have $(m n)^{-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.