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_{ n\to \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.
Categories: math.PR